Jednym z typowych scenariuszy w znanych nam aplikacjach jest wyszukiwanie danych według określonych kryteriów i wyświetlanie ich w czytelnej formie. Mogą pojawić się dodatkowe możliwości sortowania, grupowania czy paginacji. Zadanie z pozoru jest trywialne, jednak wielu programistów popełnia błędy, które wpływają na wydajność. Spróbujmy przyjrzeć się różnym rozwiązaniom tego problemu i sformułować zalecenia dotyczące wyboru najbardziej efektywnej realizacji.
Opcja paginacji #1
Najprostsza opcja, która przychodzi do głowy, to paginacja wyników wyszukiwania w jej najklasyczniejszej formie.
Załóżmy, że w aplikacji używana jest relacyjna baza danych. W takim przypadku, aby wyświetlić informacje w takiej formie, należy wykonać dwa zapytania SQL:
- Pobierz wiersze dla bieżącej strony.
- Policz całkowitą liczbę wierszy odpowiadających kryteriom wyszukiwania — jest to potrzebne do pokazania stron.
Rozważmy pierwsze zapytanie na przykładzie testowej bazy MS SQL dla serwera 2016. W tym celu skorzystamy z tabeli Sales.SalesOrderHeader:
SELECT * FROM Sales.SalesOrderHeader
ORDER BY OrderDate DESC
OFFSET 0 ROWS
FETCH NEXT 50 ROWS ONLY
Podane powyżej zapytanie wyświetli pierwsze 50 zamówień z listy, posortowane malejąco według daty dodania, innymi słowy — 50 ostatnich zamówień.
Zapytanie to wykonuje się szybko na testowej bazie, ale przyjrzyjmy się planowi wykonania i statystykom wejścia-wyjścia:
Tabela 'SalesOrderHeader'. Liczba skanów 1, odczyty logiczne 698, odczyty fizyczne 0, odczyty wyprzedzające 0, odczyty logiczne LOB 0, odczyty fizyczne LOB 0, odczyty wyprzedzające LOB 0.Statystyki wejścia/wyjścia dla każdego zapytania można uzyskać, wykonując w środowisku wykonawczym polecenie SET STATISTICS IO ON.
Jak widać z planu wykonania, najbardziej zasobożerna jest sortowanie wszystkich wierszy w tabeli źródłowej według daty dodania. Problem polega na tym, że im więcej wierszy pojawi się w tabeli, tym bardziej ‚ciężkie‘ będzie sortowanie. W praktyce należy unikać takich sytuacji, dlatego dodamy indeks na datę dodania i sprawdzimy, czy zużycie zasobów się zmieniło:
Tabela 'SalesOrderHeader'. Liczba skanów 1, odczyty logiczne 165, odczyty fizyczne 0, odczyty wyprzedzające 5, odczyty logiczne LOB 0, odczyty fizyczne LOB 0, odczyty wyprzedzające LOB 0.
Oczywiście, stało się znacznie lepiej. Ale czy wszystkie problemy zostały rozwiązane? Zmieniamy zapytanie do wyszukiwania zamówień, gdzie łączna wartość towarów przekracza 100 dolarów:
SELECT * FROM Sales.SalesOrderHeader
WHERE SubTotal > 100
ORDER BY OrderDate DESC
OFFSET 0 ROWS
FETCH NEXT 50 ROWS ONLY
Tabela 'SalesOrderHeader'. Liczba skanów 1, logiczne odczyty 1081, fizyczne odczyty 0, odczyty z wyprzedzeniem 0, logiczne odczyty LOB 0, fizyczne odczyty LOB 0, odczyty LOB z wyprzedzeniem 0.Mamy zabawną sytuację: plan zapytania nieco gorszy od poprzedniego, ale faktyczna liczba logicznych odczytów prawie dwa razy większa niż przy pełnym skanowaniu tabeli. Wyjściem jest — jeśli z już istniejącego indeksu stworzymy złożony, dodając jako drugie pole sumaryczną cenę towarów, to znów uzyskamy 165 logicznych odczytów:
CREATE INDEX IX_SalesOrderHeader_OrderDate_SubTotal on Sales.SalesOrderHeader(OrderDate, SubTotal);
Tę serię przykładów można kontynuować jeszcze długo, ale dwie główne myśli, które chcę tutaj wyrazić, są następujące:
- Dodanie jakiegokolwiek nowego kryterium lub porządku sortowania do zapytania może znacząco wpłynąć na szybkość jego wykonania.
- Ale jeśli musimy odczytać tylko część danych, a nie wszystkie wyniki pasujące do warunków wyszukiwania — istnieje wiele sposobów na optymalizację takiego zapytania.
Teraz przejdźmy do drugiego zapytania, wspomnianego na samym początku — tego, które liczy liczbę rekordów spełniających kryteria wyszukiwania. Weźmy ten sam przykład — wyszukiwanie zamówień, które kosztują więcej niż 100 dolarów:
SELECT COUNT(1) FROM Sales.SalesOrderHeader
WHERE SubTotal > 100
Przy złożonym indeksie, który został wskazany powyżej, otrzymujemy:
Tabela 'SalesOrderHeader'. Liczba skanów 1, odczyty logiczne 698, odczyty fizyczne 0, odczyty wyprzedzające 0, odczyty logiczne LOB 0, odczyty fizyczne LOB 0, odczyty wyprzedzające LOB 0.To, że zapytanie przeszło cały indeks w całości — nie dziwi, ponieważ pole SubTotal nie jest na pierwszej pozycji, więc zapytanie nie może z niego skorzystać. Problem można rozwiązać, dodając kolejny indeks na pole SubTotal, co ostatecznie daje już tylko 48 logicznych odczytów.
Można podać jeszcze kilka przykładów zapytań o zliczanie, ale istota pozostaje ta sama: uzyskanie porcji danych i zliczenie łącznej liczby — to dwa zasadniczo różne zapytania, i każde wymaga swoich środków na optymalizację. W ogólnym przypadku nie uda się znaleźć kombinacji indeksów, która równie dobrze działa dla obu zapytań.
W związku z tym, jednym z ważnych wymagań, które należy wyjaśnić podczas opracowywania takiego rozwiązania wyszukiwania, jest to, czy rzeczywiście biznesowi zależy na tym, aby zobaczyć całkowitą liczbę znalezionych obiektów. Często tak nie jest. A nawigacja po konkretnych numerach stron, moim zdaniem, jest rozwiązaniem o bardzo wąskim zakresie zastosowania, ponieważ większość scenariuszy z paginacją wygląda jak 'przejdź do następnej strony'.
Opcja paginacji #2
Przypuśćmy, że użytkownikom nie zależy na wiedzy o całkowitej liczbie znalezionych obiektów. Spróbujmy uprościć stronę wyników wyszukiwania:
W rzeczywistości zmieniło się tylko to, że nie ma możliwości przechodzenia do konkretnych numerów stron, a teraz ta tabela do wyświetlania nie musi znać, ile ich może być. Pojawia się jednak pytanie — jak tabela dowiaduje się, czy są dane dla następnej strony (aby poprawnie wyświetlić link 'Następna')?
Odpowiedź jest bardzo prosta: można odczytać z bazy o jeden rekord więcej, niż potrzebne do wyświetlenia, a obecność tego 'dodatkowego' rekordu będzie wskazywać, czy jest następna porcja. W ten sposób, aby uzyskać jedną stronę danych, trzeba będzie wykonać tylko jedno zapytanie, co znacznie poprawia wydajność i ułatwia wsparcie takiej funkcjonalności. Miałem na praktyce przypadek, kiedy rezygnacja z obliczania całkowitej liczby rekordów przyspieszyła wydanie wyników 4-5 razy.
Dla tego podejścia istnieje kilka opcji interfejsu użytkownika: przyciski 'cofnij' i 'dalej', jak w powyższym przykładzie, przycisk 'załaduj więcej', który po prostu dodaje nową porcję do wyświetlanych wyników, 'nieskończone przewijanie', które działa na zasadzie 'załaduj więcej', ale sygnałem do pobrania następnej porcji jest przewinięcie przez użytkownika wszystkich wyświetlonych wyników do końca. Niezależnie od wizualnego rozwiązania, zasada pobierania danych pozostaje taka sama.
Aspekty realizacji paginacji
We wszystkich przykładach zapytań podanych powyżej zastosowano podejście 'offset + limit', kiedy w samym zapytaniu wskazuje się, od którego wiersza wyniku oraz ile wierszy należy zwrócić. Najpierw rozważmy, jak najlepiej zorganizować przekazywanie parametrów w tym przypadku. W praktyce spotkałem kilka sposobów:
- Numer porządku żądanej strony (pageIndex), rozmiar strony (pageSize).
- Numer porządku pierwszego rekordu, który ma być zwrócony (startIndex), maksymalna liczba rekordów w wyniku (count).
- Numer porządku pierwszego rekordu, który ma być zwrócony (startIndex), numer porządku ostatniego rekordu, który ma być zwrócony (endIndex).
Na pierwszy rzut oka może się wydawać, że to tak elementarne, że nie ma większej różnicy. Ale nie jest to prawda — najbardziej wygodną i uniwersalną opcją jest druga (startIndex, count). Istnieje kilka powodów:
- Podejście z odczytem +1 rekordu, o którym mowa powyżej, w przypadku pierwszej opcji z pageIndex i pageSize jest niezwykle niewygodne. Na przykład chcemy wyświetlić 50 rekordów na stronie. Zgodnie z powyższym algorytmem, musimy odczytać jeden rekord więcej niż to konieczne. Jeśli ten „+1” nie jest oddany na serwerze, okazuje się, że dla pierwszej strony musimy żądać rekordów od 1 do 51, dla drugiej — od 51 do 101, itd. Jeśli wskaźnik rozmiaru strony wynosi 51 i zwiększamy pageIndex, to druga strona zwróci od 52 do 102 itd. W związku z tym jedynym sposobem sensownego zrealizowania przycisku przejścia do następnej strony w pierwszej opcji jest zaimplementowanie na serwerze odczytu „nadmiarowego” wiersza, co będzie bardzo niejasnym niuansem.
- Trzecia opcja w ogóle nie ma sensu, ponieważ do wykonania zapytań w większości baz danych i tak trzeba będzie przekazać liczbę, a nie indeks ostatniego rekordu. Niech odejmowanie startIndex od endIndex będzie elementarną operacją arytmetyczną, ale jest tutaj zbędne.
Teraz należy opisać wady realizacji paginacji poprzez „przesunięcie + ilość”:
- Uzyskiwanie każdej kolejnej strony będzie bardziej kosztowne i wolniejsze niż poprzedniej, ponieważ baza danych i tak musi przejść przez wszystkie rekordy „od początku” zgodnie z kryteriami wyszukiwania i sortowania, po czym zatrzymać się na odpowiednim fragmencie.
- Nie wszystkie SGBD mogą wspierać to podejście.
Alternatywy istnieją, ale również nie są idealne. Pierwsze z tych podejść nazywa się „paginacja przez klucz” lub „metoda seek” i polega na tym, że po uzyskaniu partii można zapamiętywać wartości pól w ostatnim rekordzie na stronie, a następnie używać ich do uzyskania następnej partii. Na przykład wykonywaliśmy takie zapytanie:
SELECT * FROM Sales.SalesOrderHeader
ORDER BY OrderDate DESC
OFFSET 0 ROWS
FETCH NEXT 50 ROWS ONLY
W ostatnim wpisie uzyskaliśmy wartość daty zamówienia '2014-06-29'. Aby uzyskać następną stronę, można spróbować wykonać następujące zapytanie:
SELECT * FROM Sales.SalesOrderHeader
WHERE OrderDate < '2014-06-29'
ORDER BY OrderDate DESC
OFFSET 0 ROWS
FETCH NEXT 50 ROWS ONLY
Problem polega na tym, że OrderDate nie jest unikalnym polem, a wspomniane powyżej warunki prawdopodobnie pomijają wiele potrzebnych wierszy. Aby wprowadzić jednoznaczność w to zapytanie, trzeba dodać unikalne pole (przyjmijmy, że 75074 to ostatnia wartość klucza podstawowego z pierwszej partii):
SELECT * FROM Sales.SalesOrderHeader
WHERE (OrderDate = '2014-06-29' AND SalesOrderID < 75074)
OR (OrderDate < '2014-06-29')
ORDER BY OrderDate DESC, SalesOrderID DESC
OFFSET 0 ROWS
FETCH NEXT 50 ROWS ONLY
Ta opcja będzie działać poprawnie, ale w ogólnym przypadku będzie trudna do optymalizacji, ponieważ warunek zawiera operator OR. Jeśli w miarę wzrostu OrderDate rośnie wartość klucza podstawowego, to warunek można uprościć, zostawiając tylko filtr po SalesOrderID. Jednak jeśli między wartościami klucza podstawowego a polem, według którego sortowane są wyniki, nie ma ścisłej korelacji — w większości systemów DBMS nie uda się uniknąć tego OR. Znanym wyjątkiem jest PostgreSQL, w którym w pełni wspierane jest porównanie krotek, a powyższe warunki można zapisać jako „WHERE (OrderDate, SalesOrderID) < ('2014-06-29', 75074)”. Przy istnieniu klucza złożonego z tych dwóch pól, takie zapytanie powinno być wystarczająco lekkie.
Drugie alternatywne podejście można spotkać na przykład w lub — kiedy zapytanie oprócz danych zwraca specjalny identyfikator, za pomocą którego można uzyskać następną partię danych. Jeśli ten identyfikator ma nieograniczony czas życia (jak w Comsos DB), to jest to doskonały sposób na realizację paginacji z sekwencyjnym przechodzeniem między stronami (wariant #2 wspomniany powyżej). Możliwe wady: nie jest wspierane w wielu systemach DBMS; uzyskany identyfikator następnej partii może mieć ograniczony czas życia, co w ogólnym przypadku nie nadaje się do realizacji interakcji z użytkownikami (jak na przykład ElasticSearch scroll API).
Skomplikowana filtracja
Zwiększamy trudność. Załóżmy, że pojawiło się wymaganie wdrożenia tzw. wyszukiwania z użyciem faceted search, dobrze znanego ze sklepów internetowych. Powyższe przykłady oparte na tabeli zamówień nie są w tym przypadku najbardziej reprezentatywne, dlatego przejdźmy do tabeli Product z bazy AdventureWorks:
Na czym polega idea faceted search? Polega ona na tym, że dla każdego elementu filtru wyświetlana jest liczba rekordów odpowiadających temu kryterium. z uwzględnieniem filtrów wybranych w pozostałych kategoriach..
Na przykład, jeśli w tym przypadku wybierzemy kategorię Bikes i kolor Black, tabela wyświetli tylko czarne rowery, ale:
- Dla każdego kryterium grupy „Categories” pokaże liczbę produktów w tej czarnej kategorii.
- Dla każdego kryterium grupy „Colors” pokaże liczbę rowerów w tym kolorze.
Oto przykład wyników dla takich warunków:
Jeżeli dodatkowo zaznaczymy kategorię „Clothing”, tabela pokaże również czarne ubrania dostępne w sprzedaży. Liczba produktów czarnego koloru w sekcji „Color” również zostanie przeliczona zgodnie z nowymi warunkami, tylko w sekcji „Categories” nic się nie zmieni… Mam nadzieję, że tych przykładów wystarczy, aby zrozumieć typowy algorytm działania faceted search.
Teraz wyobraźmy sobie, jak to można zrealizować w bazie danych relacyjnej. Każda grupa kryteriów, taka jak Kategoria i Kolor, będzie wymagała oddzielnego zapytania:
SELECT pc.ProductCategoryID, pc.Name, COUNT(1) FROM Production.Product p
INNER JOIN Production.ProductSubcategory ps ON p.ProductSubcategoryID = ps.ProductSubcategoryID
INNER JOIN Production.ProductCategory pc ON ps.ProductCategoryID = pc.ProductCategoryID
WHERE p.Color = 'Black'
GROUP BY pc.ProductCategoryID, pc.Name
ORDER BY COUNT(1) DESC
SELECT Color, COUNT(1) FROM Production.Product p
INNER JOIN Production.ProductSubcategory ps ON p.ProductSubcategoryID = ps.ProductSubcategoryID
WHERE ps.ProductCategoryID = 1 --Bikes
GROUP BY Color
ORDER BY COUNT(1) DESC
Co jest nie tak z tym rozwiązaniem? Jest to bardzo proste — słabo się skalują. Każda sekcja filtra wymaga oddzielnego zapytania do zliczenia ilości, a te zapytania są dość ciężkie. W sklepach internetowych w niektórych kategoriach może być nawet kilka dziesiątek sekcji filtrów, co może stanowić poważny problem dla wydajności.
Zwykle po tych stwierdzeniach przedstawiane są mi pewne rozwiązania, a mianowicie:
- Połączyć wszystkie zliczenia w jednym zapytaniu. Technicznie jest to możliwe za pomocą słowa kluczowego UNION, ale nie przyczyni się to znacząco do poprawy wydajności — baza danych nadal będzie musiała wykonać „od początku” każdy z fragmentów.
- Kategoryzować ilości. To jest mi proponowane praktycznie za każdym razem, gdy opisuję problem. Niestety, w ogólnym przypadku jest to niemożliwe. Załóżmy, że mamy 10 „fasetów”, z których każdy ma 5 wartości. To bardzo „skromna” sytuacja, w porównaniu do tego, co można zobaczyć w tych samych sklepach internetowych. Wybór jednego elementu fasetu wpływa na ilości w 9 innych, innymi słowy, dla każdej kombinacji kryteriów ilości mogą być różne. Łącznie w naszym przykładzie mamy 50 kryteriów, które użytkownik może wybrać, co oznacza, że możliwych kombinacji będzie 250. Na wypełnienie takiej masy danych nie wystarczy ani pamięci, ani czasu. Można tu wtrącić, że nie wszystkie kombinacje są realne i użytkownik rzadko wybiera więcej niż 5-10 kryteriów. Tak, można zrobić leniwe ładowanie i kategoryzowanie ilości tylko dla tego, co kiedykolwiek zostało wybrane, ale im więcej będzie opcji wyboru, tym mniej efektywny będzie taki cache i tym bardziej zauważalne będą problemy z czasem reakcji (zwłaszcza jeśli zbiór danych regularnie się zmienia).
Na szczęście podobne zadanie ma już od dawna wystarczająco efektywne rozwiązania, które przewidywalnie działają na dużych zbiorach danych. Dla każdej z tych opcji ma sens podzielić przeliczenie faset i pobieranie strony wyników na dwa równoległe zapytania do serwera i zorganizować interfejs użytkownika w taki sposób, aby ładowanie danych z faset „nie przeszkadzało” w wyświetlaniu wyników wyszukiwania.
- Wywołuj pełne przeliczenie «fasetów» tak rzadko, jak to możliwe. Na przykład, nie przeliczaj wszystkiego przy każdej zmianie kryteriów wyszukiwania, zamiast tego znajdź łączną liczbę wyników odpowiadających obecnym warunkom i zaproponuj użytkownikowi ich wyświetlenie — «znaleziono 1425 wpisów, wyświetlić?» Użytkownik może kontynuować zmianę warunków wyszukiwania lub nacisnąć przycisk «wyświetlić». Tylko w drugim przypadku zostaną wykonane wszystkie zapytania o uzyskanie wyników i przeliczenie ilości na wszystkich «fasetach». Należy zauważyć, że trzeba będzie zająć się zapytaniem o uzyskanie łącznej liczby wyników i jego optymalizacją. Takie podejście można spotkać w wielu małych sklepach internetowych. Oczywiste jest, że to nie panaceum na ten problem, ale w prostych przypadkach może być niezłym kompromisem.
- Używaj silników wyszukiwania do wyszukiwania wyników i liczenia fasetów, takich jak Solr, ElasticSearch, Sphinx i inne. Wszystkie są zaprojektowane do budowania «fasetów» i robią to dość efektywnie dzięki odwróconemu indeksowi. Jak działają systemy wyszukiwania, dlaczego w takich przypadkach są skuteczniejsze niż bazy danych ogólnego przeznaczenia, jakie są praktyki i pułapki — to temat na osobny artykuł. Chciałbym jednak zwrócić uwagę, że silnik wyszukiwania nie może zastąpić głównego repozytorium danych; jest używany jako dodatek: wszelkie zmiany w głównej bazie, mające znaczenie dla wyszukiwania, są synchronizowane z indeksem wyszukiwania; mechanizm wyszukiwania zazwyczaj współdziała tylko z silnikiem wyszukiwania i nie odnosi się do głównej bazy. Jednym z najważniejszych punktów jest tutaj, jak zorganizować tę synchronizację niezawodnie. Wszystko zależy od wymagań dotyczących «czasu reakcji». Jeśli czas między zmianą w głównej bazie a jej «manifestacją» w wyszukiwaniu nie jest krytyczny, można stworzyć serwis, który co kilka minut przeszukuje niedawno zmienione wpisy i je indeksuje. Jeśli wymagana jest minimalna możliwa reakcja, można wdrożyć coś w rodzaju do wysyłania aktualizacji do serwisu wyszukiwania.
Wnioski
- Realizacja paginacji po stronie serwera to poważne skomplikowanie, a jej zastosowanie ma sens tylko dla szybko rosnących lub po prostu dużych zbiorów danych. Jak ocenić, co oznacza »duży« lub »szybko rosnący« — nie ma absolutnie dokładnej recepty, ale trzymałbym się takiego podejścia:
- Jeśli uzyskanie pełnej kolekcji danych z uwzględnieniem czasu serwera i transferu sieciowego mieści się w wymaganiach dotyczących wydajności — nie ma sensu wdrażać paginacji po stronie serwera.
- Może zdarzyć się sytuacja, że przez najbliższy czas nie przewiduje się problemów z wydajnością, ponieważ danych jest mało, ale kolekcja danych stale rośnie. Jeśli jakiś zbiór danych w przyszłości może przestać spełniać powyższy punkt — lepiej od razu założyć paginację.
- Jeśli ze strony biznesu nie ma sztywnego wymogu dotyczącego pokazania ogólnej liczby wyników lub wyświetlania numerów stron, a w Twoim systemie nie ma silnika wyszukiwania — lepiej tych kwestii nie wdrażać i rozważyć wariant nr 2.
- Jeśli istnieje wyraźne wymaganie dotyczące wyszukiwania fasetowego, masz dwa sposoby, aby nie poświęcać wydajności:
- Nie przeliczać wszystkich ilości przy każdej zmianie kryteriów wyszukiwania.
- Używać silników wyszukiwania, takich jak Solr, ElasticSearch, Sphinx i inne. Należy jednak pamiętać, że nie mogą one zastąpić głównej bazy danych i powinny być używane jako uzupełnienie głównego repozytorium do rozwiązywania zadań wyszukiwania.
- Również w przypadku wyszukiwania fasetowego sensowne jest rozdzielenie uzyskiwania strony wyników wyszukiwania i liczenia ilości na dwa równoległe zapytania. Liczenie ilości może zająć więcej czasu niż uzyskiwanie wyników, podczas gdy wyniki są ważniejsze dla użytkownika.
- Jeśli używasz bazy danych SQL do wyszukiwania, wszelkie zmiany w kodzie dotyczące tej części powinny być dobrze testowane pod kątem wydajności na odpowiedniej objętości danych (przekraczającej objętość w »żywej« bazie). Pożądane jest również monitorowanie czasu wykonania zapytań na wszystkich instancjach bazy, a szczególnie — na »żywej«. Nawet jeśli na etapie rozwoju z planami zapytań wszystko wyglądało dobrze, w miarę wzrostu objętości danych sytuacja może się znacząco zmienić.
Źródło: habr.com
