Jednym z typowych scenariuszy we wszystkich znanych nam aplikacjach jest wyszukiwanie danych według określonych kryteriów i wyświetlanie ich w czytelnej formie. Mogą również istnieć dodatkowe opcje sortowania, grupowania i stronicowania. Zadanie jest teoretycznie trywialne, ale przy jego rozwiązywaniu wielu programistów popełnia szereg błędów, które później powodują spadek produktywności. Spróbujmy rozważyć różne opcje rozwiązania tego problemu i sformułować zalecenia dotyczące wyboru najbardziej efektywnego wdrożenia.
Opcja stronicowania nr 1
Najprostszą opcją, jaka przychodzi na myśl, jest wyświetlanie wyników wyszukiwania strona po stronie w najbardziej klasycznej formie.
Załóżmy, że Twoja aplikacja korzysta z relacyjnej bazy danych. W tym przypadku, aby wyświetlić informacje w tym formularzu, konieczne będzie uruchomienie dwóch zapytań SQL:
- Pobierz wiersze dla bieżącej strony.
- Oblicz całkowitą liczbę wierszy odpowiadających kryteriom wyszukiwania - jest to konieczne do wyświetlenia stron.
Przyjrzyjmy się pierwszemu zapytaniu na przykładzie testowej bazy danych MS SQL dla serwera 2016. W tym celu wykorzystamy tabelę Sales.SalesOrderHeader:
SELECT * FROM Sales.SalesOrderHeader
ORDER BY OrderDate DESC
OFFSET 0 ROWS
FETCH NEXT 50 ROWS ONLY
Powyższe zapytanie zwróci pierwsze 50 zamówień z listy posortowanych malejąco według daty dodania, czyli 50 ostatnich zamówień.
Działa szybko na bazie testów, ale spójrzmy na plan wykonania i statystyki we/wy:
Table 'SalesOrderHeader'. Scan count 1, logical reads 698, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.Statystykę we/wy można uzyskać dla każdego zapytania, uruchamiając komendę SET STATISTICS IO ON w środowisku wykonawczym zapytania.
Jak widać z planu wykonania, najbardziej zasobochłonną opcją jest posortowanie wszystkich wierszy tabeli źródłowej według daty dodania. Problem w tym, że im więcej wierszy pojawi się w tabeli, tym „trudniejsze” będzie sortowanie. W praktyce takich sytuacji należy unikać, dlatego do daty dodania dodajmy indeks i zobaczmy, czy zmieniło się zużycie zasobów:
Table 'SalesOrderHeader'. Scan count 1, logical reads 165, physical reads 0, read-ahead reads 5, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Oczywiście, że jest dużo lepiej. Ale czy wszystkie problemy zostały rozwiązane? Zmieńmy zapytanie, aby wyszukać zamówienia, w których łączny koszt towaru przekracza 100 USD:
SELECT * FROM Sales.SalesOrderHeader
WHERE SubTotal > 100
ORDER BY OrderDate DESC
OFFSET 0 ROWS
FETCH NEXT 50 ROWS ONLY
Table 'SalesOrderHeader'. Scan count 1, logical reads 1081, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.Mamy zabawną sytuację: plan zapytań nie jest dużo gorszy od poprzedniego, ale rzeczywista liczba odczytów logicznych jest prawie dwukrotnie większa niż przy skanowaniu pełnej tabeli. Jest wyjście - jeśli z już istniejącego indeksu zrobimy indeks złożony i do drugiego pola dodamy łączną cenę towaru, ponownie otrzymamy 165 odczytów logicznych:
CREATE INDEX IX_SalesOrderHeader_OrderDate_SubTotal on Sales.SalesOrderHeader(OrderDate, SubTotal);
Tę serię przykładów można kontynuować długo, ale dwie główne myśli, które chcę tutaj wyrazić, to:
- Dodanie nowego kryterium lub porządku sortowania do wyszukiwanego hasła może mieć znaczący wpływ na szybkość wyszukiwania.
- Jeśli jednak musimy odjąć tylko część danych, a nie wszystkie wyniki pasujące do wyszukiwanych haseł, istnieje wiele sposobów optymalizacji takiego zapytania.
Przejdźmy teraz do drugiego zapytania wspomnianego na samym początku – tego, które zlicza liczbę rekordów spełniających kryterium wyszukiwania. Weźmy ten sam przykład - wyszukiwanie zamówień o wartości większej niż 100 USD:
SELECT COUNT(1) FROM Sales.SalesOrderHeader
WHERE SubTotal > 100
Biorąc pod uwagę wskazany powyżej wskaźnik złożony, otrzymujemy:
Table 'SalesOrderHeader'. Scan count 1, logical reads 698, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.Fakt, że zapytanie przechodzi przez cały indeks nie jest zaskakujący, ponieważ pole SubTotal nie znajduje się na pierwszej pozycji, więc zapytanie nie może go wykorzystać. Problem rozwiązuje się dodając kolejny indeks w polu SubTotal i w rezultacie daje to tylko 48 odczytów logicznych.
Możesz podać jeszcze kilka przykładów żądań zliczenia ilości, ale istota pozostaje ta sama: otrzymanie fragmentu danych i policzenie łącznej kwoty to dwa zasadniczo różne żądania, a każdy z nich wymaga własnych środków optymalizacji. Ogólnie rzecz biorąc, nie będzie można znaleźć kombinacji indeksów, która działałaby równie dobrze w przypadku obu zapytań.
W związku z tym jednym z ważnych wymagań, które należy wyjaśnić przy opracowywaniu takiego rozwiązania wyszukiwania, jest to, czy dla firmy naprawdę ważne jest wyświetlanie całkowitej liczby znalezionych obiektów. Często zdarza się, że nie. A nawigacja po konkretnych numerach stron to moim zdaniem rozwiązanie o bardzo wąskim zakresie, gdyż większość scenariuszy stronicowania wygląda jak „przejdź do następnej strony”.
Opcja stronicowania nr 2
Załóżmy, że użytkownikom nie zależy na znajomości całkowitej liczby znalezionych obiektów. Spróbujmy uprościć stronę wyszukiwania:
Tak naprawdę jedyne co się zmieniło to to, że nie ma możliwości nawigowania do konkretnych numerów stron i teraz ta tabela nie musi wiedzieć ile ich może być, aby ją wyświetlić. Powstaje jednak pytanie - skąd tabela wie, czy są dane na następną stronę (aby poprawnie wyświetlić link „Dalej”)?
Odpowiedź jest bardzo prosta: można odczytać z bazy o jeden rekord więcej, niż potrzeba do wyświetlenia, a obecność tego „dodatkowego” rekordu pokaże, czy jest już kolejna porcja. Dzięki temu wystarczy uruchomić jedno żądanie, aby otrzymać jedną stronę danych, co znacznie poprawia wydajność i ułatwia obsługę takiej funkcjonalności. W mojej praktyce zdarzały się przypadki, gdy odmowa przeliczenia całkowitej liczby rekordów przyspieszała dostarczenie wyników 4-5 razy.
Istnieje kilka opcji interfejsu użytkownika dla tego podejścia: polecenia „wstecz” i „dalej”, jak w powyższym przykładzie, przycisk „ładuj więcej”, który po prostu dodaje nową porcję do wyświetlanych wyników, „nieskończone przewijanie”, które działa na zasadzie „ładuj więcej”, ale sygnałem do pobrania kolejnej porcji jest dla użytkownika przewinięcie wszystkich wyświetlonych wyników do końca. Niezależnie od rozwiązania wizualnego, zasada próbkowania danych pozostaje taka sama.
Niuanse implementacji stronicowania
Wszystkie przykłady zapytań podane powyżej wykorzystują podejście „przesunięcie + liczba”, gdy samo zapytanie określa, w jakiej kolejności wiersze wyników i ile wierszy należy zwrócić. Najpierw przyjrzyjmy się, jak najlepiej zorganizować przekazywanie parametrów w tym przypadku. W praktyce spotkałem się z kilkoma metodami:
- Numer seryjny żądanej strony (pageIndex), rozmiar strony (pageSize).
- Numer seryjny pierwszego zwracanego rekordu (startIndex), maksymalna liczba rekordów w wyniku (count).
- Numer kolejny pierwszego zwracanego rekordu (startIndex), numer kolejny ostatniego zwracanego rekordu (endIndex).
Na pierwszy rzut oka może się wydawać, że jest to na tyle elementarne, że nie ma żadnej różnicy. Ale tak nie jest - najwygodniejszą i uniwersalną opcją jest druga (startIndex, liczba). Istnieje kilka powodów:
- W przypadku metody korekty wpisu +1 podanej powyżej, pierwsza opcja z pageIndex i pageSize jest wyjątkowo niewygodna. Na przykład chcemy wyświetlić 50 postów na stronę. Zgodnie z powyższym algorytmem należy odczytać o jeden rekord więcej niż to konieczne. Jeśli na serwerze nie zaimplementowano tego „+1”, okazuje się, że dla pierwszej strony musimy zażądać rekordów od 1 do 51, dla drugiej – od 51 do 101 itd. Jeśli określisz rozmiar strony 51 i zwiększysz pageIndex, wówczas druga strona powróci z 52 do 102 itd. W związku z tym w pierwszej opcji jedynym sposobem prawidłowego zaimplementowania przycisku przejścia do następnej strony jest sprawdzenie przez serwer „dodatkowej” linii, co będzie bardzo ukrytym niuansem.
- Trzecia opcja w ogóle nie ma sensu, ponieważ aby uruchamiać zapytania w większości baz danych, nadal będziesz musiał przekazać liczbę, a nie indeks ostatniego rekordu. Odejmowanie startIndex od endIndex może być prostą operacją arytmetyczną, ale tutaj jest zbędne.
Teraz powinniśmy opisać wady implementacji stronicowania poprzez „offset + ilość”:
- Odtworzenie każdej kolejnej strony będzie droższe i wolniejsze od poprzedniej, gdyż baza danych i tak będzie musiała przejść przez wszystkie rekordy „od początku” według kryteriów wyszukiwania i sortowania, a następnie zatrzymać się na żądanym fragmencie.
- Nie wszystkie systemy DBMS obsługują to podejście.
Istnieją alternatywy, ale są one również niedoskonałe. Pierwsze z tych podejść nazywa się „stronicowaniem zestawu kluczy” lub „metodą wyszukiwania” i polega na tym, że po otrzymaniu porcji możesz zapamiętać wartości pól w ostatnim rekordzie na stronie, a następnie użyć ich do uzyskania następna porcja. Na przykład uruchomiliśmy następujące zapytanie:
SELECT * FROM Sales.SalesOrderHeader
ORDER BY OrderDate DESC
OFFSET 0 ROWS
FETCH NEXT 50 ROWS ONLY
A w ostatnim rekordzie otrzymaliśmy wartość daty zamówienia „2014-06-29”. Następnie, aby uzyskać następną stronę, możesz spróbować to zrobić:
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 warunek określony powyżej prawdopodobnie pominie wiele wymaganych wierszy. Aby dodać jednoznaczności temu zapytaniu, należy dodać do warunku unikalne pole (załóżmy, że 75074 to ostatnia wartość klucza podstawowego z pierwszej części):
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 ogólnie będzie trudna do optymalizacji, ponieważ warunek zawiera operator OR. Jeśli wartość klucza podstawowego wzrasta wraz ze wzrostem OrderDate, wówczas warunek można uprościć, pozostawiając jedynie filtr według SalesOrderID. Ale jeśli nie ma ścisłej korelacji między wartościami klucza podstawowego a polem, według którego sortowany jest wynik, w większości systemów DBMS nie można uniknąć tego OR. Wyjątkiem, o którym wiem, jest PostgreSQL, który w pełni obsługuje porównania krotek, a powyższy warunek można zapisać jako „WHERE (OrderDate, SalesOrderID) <('2014-06-29', 75074)”. Biorąc pod uwagę klucz złożony z tymi dwoma polami, takie zapytanie powinno być dość łatwe.
Drugie alternatywne podejście można znaleźć np lub — gdy żądanie oprócz danych zwraca specjalny identyfikator, za pomocą którego można uzyskać kolejną porcję danych. Jeśli identyfikator ten ma nieograniczony czas życia (jak w Comsos DB), to jest to świetny sposób na zaimplementowanie stronicowania z sekwencyjnym przejściem pomiędzy stronami (opcja nr 2 wspomniana powyżej). Jego możliwe wady: nie jest obsługiwany we wszystkich systemach DBMS; powstały identyfikator następnego fragmentu może mieć ograniczony czas życia, co generalnie nie jest odpowiednie do implementowania interakcji użytkownika (takich jak interfejs API przewijania ElasticSearch).
Złożone filtrowanie
Skomplikujmy zadanie jeszcze bardziej. Załóżmy, że istnieje potrzeba wdrożenia tzw. wyszukiwania fasetowego, które jest doskonale znane każdemu ze sklepów internetowych. Powyższe przykłady oparte na tabeli zamówień nie są w tym przypadku zbyt ilustracyjne, więc przejdźmy do tabeli Produkt z bazy AdventureWorks:
Jaka jest idea wyszukiwania fasetowego? Faktem jest, że dla każdego elementu filtrującego pokazana jest liczba rekordów spełniających to kryterium z uwzględnieniem filtrów wybranych we wszystkich pozostałych kategoriach.
Na przykład, jeśli w tym przykładzie wybierzemy kategorię Rowery i kolor Czarny, w tabeli pojawią się tylko czarne rowery, ale:
- Dla każdego kryterium w grupie Kategorie liczba produktów z tej kategorii zostanie wyświetlona na czarno.
- Dla każdego kryterium grupy „Kolory” zostanie wyświetlona liczba rowerów tego koloru.
Oto przykład wyniku dla takich warunków:
Jeśli zaznaczysz także kategorię „Odzież”, w tabeli pojawią się także czarne ubrania, które są na stanie. Liczba czarnych produktów w sekcji „Kolor” również zostanie przeliczona zgodnie z nowymi warunkami, jedynie w sekcji „Kategorie” nic się nie zmieni… Mam nadzieję, że te przykłady wystarczą, aby zrozumieć zwykły algorytm wyszukiwania fasetowego.
Teraz wyobraźmy sobie, jak można to zaimplementować na zasadzie relacyjnej. Każda grupa kryteriów, taka jak Kategoria i Kolor, będzie wymagała osobnego 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? To bardzo proste – nie skaluje się dobrze. Każda sekcja filtra wymaga osobnego zapytania do obliczenia ilości, a zapytania te nie należą do najłatwiejszych. W sklepach internetowych niektóre kategorie mogą posiadać kilkadziesiąt sekcji filtrów, co może stanowić poważny problem wydajnościowy.
Zwykle po tych stwierdzeniach oferowane są mi pewne rozwiązania, a mianowicie:
- Połącz wszystkie liczniki ilości w jedno zapytanie. Technicznie jest to możliwe przy użyciu słowa kluczowego UNION, ale nie poprawi to zbytnio wydajności - baza danych i tak będzie musiała wykonać każdy z fragmentów od zera.
- Ilości pamięci podręcznej. Sugeruje mi się to prawie za każdym razem, gdy opisuję problem. Z zastrzeżeniem, że jest to generalnie niemożliwe. Załóżmy, że mamy 10 „aspektów”, z których każdy ma 5 wartości. To bardzo „skromna” sytuacja w porównaniu z tym, co można zobaczyć w tych samych sklepach internetowych. Wybór jednego elementu aspektowego wpływa na ilości w 9 pozostałych, czyli dla każdej kombinacji kryteriów wielkości mogą być inne. W naszym przykładzie użytkownik może wybrać łącznie 50 kryteriów, zatem możliwych kombinacji będzie 250. Nie ma wystarczającej ilości pamięci i czasu, aby wypełnić taką tablicę danych. Tutaj możesz zgłosić sprzeciw i stwierdzić, że nie wszystkie kombinacje są prawdziwe i użytkownik rzadko wybiera więcej niż 5-10 kryteriów. Tak, możliwe jest leniwe ładowanie i buforowanie tylko tej ilości, która została kiedykolwiek wybrana, ale im więcej jest selekcji, tym mniej wydajna będzie taka pamięć podręczna i tym bardziej zauważalne będą problemy z czasem reakcji (szczególnie jeśli zbiór danych zmienia się regularnie).
Na szczęście taki problem od dawna ma dość skuteczne rozwiązania, które działają przewidywalnie na dużych wolumenach danych. W przypadku każdej z tych opcji sensowne jest podzielenie przeliczania aspektów i otrzymania strony wyników na dwa równoległe wywołania serwera i zorganizowanie interfejsu użytkownika w taki sposób, aby ładowanie danych po aspektach „nie przeszkadzało” w wyświetlaniu wyniki wyszukiwania.
- Nawołuj do pełnego przeliczenia „aspektów” tak rzadko, jak to możliwe. Na przykład nie przeliczaj wszystkiego za każdym razem, gdy zmienią się kryteria wyszukiwania, ale zamiast tego znajdź całkowitą liczbę wyników spełniających bieżące warunki i poproś użytkownika o ich wyświetlenie - „Znaleziono 1425 rekordów, pokazać?” Użytkownik może kontynuować zmianę wyszukiwanych haseł lub kliknąć przycisk „pokaż”. Dopiero w drugim przypadku zostaną zrealizowane wszystkie prośby o uzyskanie wyników i przeliczenie ilości we wszystkich „aspektach”. W tym przypadku, jak łatwo zauważyć, będziesz musiał poradzić sobie z prośbą o uzyskanie całkowitej liczby wyników i jej optymalizację. Metodę tę można spotkać w wielu małych sklepach internetowych. Oczywiście nie jest to panaceum na ten problem, ale w prostych przypadkach może być dobrym kompromisem.
- Skorzystaj z wyszukiwarek, aby znaleźć wyniki i zliczyć aspekty, takie jak Solr, ElasticSearch, Sphinx i inne. Wszystkie są przeznaczone do budowania „aspektów” i robią to dość sprawnie dzięki odwróconemu indeksowi. Jak działają wyszukiwarki, dlaczego w takich przypadkach są skuteczniejsze od baz danych ogólnego przeznaczenia, jakie praktyki i pułapki się w nich kryją – to temat na osobny artykuł. W tym miejscu chciałbym zwrócić Państwa uwagę na fakt, że wyszukiwarka nie może zastępować głównego magazynu danych, lecz pełni funkcję dodatku: wszelkie istotne dla wyszukiwania zmiany w głównej bazie danych są synchronizowane z indeksem wyszukiwania; Wyszukiwarka zazwyczaj współpracuje tylko z wyszukiwarką i nie uzyskuje dostępu do głównej bazy danych. Jednym z najważniejszych punktów jest to, jak niezawodnie zorganizować tę synchronizację. Wszystko zależy od wymagań dotyczących „czasu reakcji”. Jeżeli czas pomiędzy zmianą w głównej bazie danych a jej „przejawem” w wyszukiwaniu nie jest krytyczny, można stworzyć usługę, która co kilka minut wyszukuje ostatnio zmienione rekordy i je indeksuje. Jeśli chcesz najkrótszego możliwego czasu reakcji, możesz zaimplementować coś takiego aby wysyłać aktualizacje do usługi wyszukiwania.
odkrycia
- Implementacja stronicowania po stronie serwera jest znaczną komplikacją i ma sens tylko w przypadku szybko rosnących lub po prostu dużych zbiorów danych. Nie ma absolutnie dokładnego przepisu na ocenę „duży” lub „szybko rosnący”, ale zastosowałbym następujące podejście:
- Jeśli otrzymanie pełnego zbioru danych, biorąc pod uwagę czas serwera i transmisję sieciową, normalnie spełnia wymagania wydajnościowe, nie ma sensu wdrażać stronicowania po stronie serwera.
- Może zaistnieć sytuacja, w której w najbliższej przyszłości nie należy spodziewać się problemów z wydajnością, ponieważ danych jest mało, ale ich ilość stale rośnie. Jeśli w przyszłości jakiś zestaw danych może już nie spełniać poprzedniego punktu, lepiej od razu rozpocząć stronicowanie.
- Jeśli firma nie ma ścisłych wymagań dotyczących wyświetlania całkowitej liczby wyników lub numerów stron, a Twój system nie ma wyszukiwarki, lepiej nie wdrażać tych punktów i rozważyć opcję nr 2.
- Jeśli istnieje wyraźny wymóg wyszukiwania fasetowego, masz dwie możliwości bez poświęcania wydajności:
- Nie przeliczaj wszystkich ilości za każdym razem, gdy zmieniają się kryteria wyszukiwania.
- Korzystaj z wyszukiwarek takich jak Solr, ElasticSearch, Sphinx i innych. Należy jednak rozumieć, że nie może ona zastąpić głównej bazy danych i powinna być używana jako dodatek do głównej pamięci w celu rozwiązywania problemów z wyszukiwaniem.
- Ponadto w przypadku wyszukiwania fasetowego sensowne jest podzielenie pobierania strony wyników wyszukiwania i zliczania na dwa równoległe żądania. Liczenie ilości może zająć więcej czasu niż uzyskanie wyników, a wyniki są ważniejsze dla użytkownika.
- Jeśli do wyszukiwania używasz bazy danych SQL, wszelkie zmiany w kodzie związane z tą częścią powinny zostać dobrze przetestowane pod kątem wydajności na odpowiedniej ilości danych (przekraczającej objętość działającej bazy danych). Wskazane jest również stosowanie monitorowania czasu wykonania zapytań na wszystkich instancjach bazy danych, a zwłaszcza na tej „żywej”. Nawet jeśli na etapie rozwoju z planami zapytań wszystko było w porządku, wraz ze wzrostem ilości danych sytuacja może się zauważalnie zmienić.
Źródło: www.habr.com