AllYouNeedIsBackend

Jestem wielkim fanem baz danych. Chciałem nawet stworzyć swój własny DBMS, kiedy byłem na studiach. Teraz pracuję zarówno z RDBMS, jak i z rozwiązaniami NoSQL i jestem tym bardzo zachwycony. Wiesz, nie ma Złotego Młota, każdy problem ma swoje rozwiązanie. Ewentualnie podzbiór rozwiązań.

W serii wpisów The SQL I Love <3 przeprowadzam Was przez kilka problemów rozwiązanych za pomocą SQL, które wydały mi się szczególnie interesujące. Rozwiązania są testowane przy użyciu tabeli z ponad 100 milionami rekordów. Wszystkie przykłady używają MySQL, ale pomysły mają zastosowanie do innych relacyjnych magazynów danych, takich jak PostgreSQL, Oracle i SQL Server.

Ten rozdział skupia się na efektywnym skanowaniu dużej tabeli przy użyciu paginacji z offset na kluczu głównym. Jest to również znane jako paginacja za pomocą zestawu kluczy.

Tło

W rozdziale używamy dla przykładu następującej struktury bazy danych. Kanoniczny przykład o użytkownikach powinien pasować do każdej domeny.

CREATE TABLE `users` ( `user_id` int(11) unsigned NOT NULL AUTO_INCREMENT, `external_id` varchar(32) NOT NULL, `name` varchar(100) COLLATE utf8_unicode_ci NOT NULL, `metadata` text COLLATE utf8_unicode_ci, `date_created` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP, PRIMARY KEY (`user_id`), UNIQUE KEY `uf_uniq_external_id` (`external_id`), UNIQUE KEY `uf_uniq_name` (`name`), KEY `date_created` (`date_created`)) ENGINE=InnoDB DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci;

Kilka uwag na temat struktury:

• external_idkolumna przechowuje referencję do tego samego użytkownika w innym systemie w formacie UUID
• name reprezentuje Firstname Lastname
• metadatakolumna zawiera blob JSON z wszelkiego rodzaju nieustrukturyzowanymi danymi

Tabela jest stosunkowo duża i zawiera około 100 000 000 rekordów. Rozpocznijmy naszą podróż edukacyjną.

Skanowanie dużej tabeli

Problem: Musisz przejść przez tabelę, wyodrębnić każdy rekord, przekształcić go wewnątrz kodu aplikacji i wstawić w inne miejsce. Skupiamy się na pierwszym etapie w poście – skanowanie tabeli.

Oczywiste i złe rozwiązanie

SELECT user_id, external_id, name, metadata, date_createdFROM users;

W moim przypadku z 100 000 000 rekordów, zapytanie nigdy nie jest zakończone. DBMS po prostu je zabija. Dlaczego? Prawdopodobnie dlatego, że doprowadziło to do próby załadowania całej tabeli do pamięci RAM. Przed zwróceniem danych do klienta. Inne założenie – zbyt dużo czasu zajęło wstępne załadowanie danych przed wysłaniem i zapytanie zostało timed out. Tak czy inaczej, nasza próba uzyskania wszystkich rekordów na czas nie powiodła się. Musimy znaleźć jakieś inne rozwiązanie.

Rozwiązanie #2

Możemy spróbować uzyskać dane w stronach. Ponieważ rekordy nie mają gwarancji uporządkowania w tabeli na poziomie fizycznym lub logicznym – musimy je posortować po stronie DBMS za pomocą klauzuli ORDER BY.

SELECT user_id, external_id, name, metadata, date_createdFROM usersORDER BY user_id ASCLIMIT 0, 10 000;10 000 rows in set (0.03 sec)

Słodko. Udało się. Zapytaliśmy o pierwszą stronę 10 000 rekordów, a zwrócenie jej zajęło tylko 0.03 s. Jednak jak to będzie działać dla 5000-tnej strony?

SELECT user_id, external_id, name, metadata, date_createdFROM usersORDER BY user_id ASCLIMIT 50 000 000, 10 000; --- 5 000th page * 10 000 page size10 000 rows in set (40.81 sec)

Pewnie, to jest bardzo wolne. Zobaczmy, ile czasu potrzeba, aby uzyskać dane dla najnowszej strony.

SELECT user_id, external_id, name, metadata, date_createdFROM usersORDER BY user_id ASCLIMIT 99 990 000, 10 000; --- 9999th page * 10 000 page size10 000 rows in set (1 min 20.61 sec)

To jest szalone. Jednak może być OK dla rozwiązań, które działają w tle. Jeszcze jeden ukryty problem z tym podejściem może zostać ujawniony, jeśli spróbujesz usunąć rekord z tabeli w środku jej skanowania. Powiedzmy, że skończyłeś 10 stronę (100 000 rekordów jest już odwiedzonych), przechodząc do skanowania rekordów pomiędzy 100 001 a 110 000. Ale rekordy 99 998 i 99 999 są usuwane przed następnym SELECT wykonaniem. W takim przypadku poniższe zapytanie zwraca nieoczekiwany wynik:

 SELECT user_id, external_id, name, metadata, date_created FROM users ORDER BY user_id ASC LIMIT 100 000, 10 000; N, id, ... 1, 100 003, ... 2, 100 004, ...

Jak widać, zapytanie pominęło rekordy o identyfikatorach 100 001 i 100 002. Nie zostaną one przetworzone przez kod aplikacji przy takim podejściu, ponieważ po dwóch operacjach usunięcia pojawiają się one w pierwszych 100 000 rekordów. Dlatego metoda ta jest zawodna, jeśli zbiór danych jest mutowalny.

Rozwiązanie #3 – ostatnie na dziś

Podejście jest bardzo podobne do poprzedniego, ponieważ nadal wykorzystuje stronicowanie, ale teraz zamiast polegać na liczbie zeskanowanych rekordów, używamy user_id ostatniego odwiedzonego rekordu jako offset.

Uproszczony algorytm:

1. Uzyskujemy PAGE_SIZE liczbę rekordów z tabeli. Wartość przesunięcia początkowego wynosi 0.
2. Użyj maksymalnej zwróconej wartości dla user_id w partii jako przesunięcia dla następnej strony.
3. Pobierz następną partię z rekordów, które mają user_id wartość wyższą od bieżącej offset.

Kwerenda w działaniu dla 5 000 strony, każda strona zawiera dane o 10 000 użytkowników:

SELECT user_id, external_id, name, metadata, date_createdFROM usersWHERE user_id > 51 234 123 --- value of user_id for 50 000 000th recordORDER BY user_id ASCLIMIT 10 000;10 000 rows in set (0.03 sec)

Uwaga, że wartości user_id nie są sekwencyjne i mogą mieć luki np. 25 348 jest zaraz po 25 345. Rozwiązanie to działa również w przypadku usunięcia rekordów z przyszłych stron – nawet w takim przypadku zapytanie nie pomija rekordów. Słodkie, prawda?

Wyjaśnienie wydajności

Dla dalszej nauki polecam zbadanie wyników EXPLAIN EXTENDED dla każdej wersji zapytania, aby uzyskać następne 10 000 rekordów po 50 000 000.

Skupmy się na kluczowej różnicy między planami wykonania dla 2. i 3. rozwiązania, ponieważ 1. nie jest praktycznie użyteczne dla dużych tabel.

• Typ złączenia: index vs range. Pierwszy z nich oznacza, że całe drzewo indeksu jest skanowane w celu znalezienia rekordów. Typ range mówi nam, że indeks jest używany tylko do znalezienia pasujących wierszy w określonym zakresie. Tak więc, range typ jest szybszy niż index.
• Możliwe klucze: NULL vs PRIMARY. Kolumna pokazuje klucze, które mogą być użyte przez MySQL. BTW, patrząc na kolumnę kluczy, możemy zobaczyć, że ostatecznie klucz PRIMARY jest używany dla obu zapytań.
• Wiersze: 50 010 000 vs 50 000 000. Wartość ta wyświetla liczbę rekordów analizowanych przed zwróceniem wyniku. Dla drugiego zapytania, wartość zależy od tego jak głęboki jest nasz scroll. Na przykład, jeśli próbujemy uzyskać kolejne 10 000 rekordy po 9999 stronie, wtedy 99 990 000 rekordów zostanie przeanalizowanych. W przeciwieństwie do tego, trzecie zapytanie ma stałą wartość, nie ma znaczenia czy ładujemy dane dla pierwszej czy ostatniej strony. Zawsze jest to połowa rozmiaru tabeli.
• Filtrowane: 200.00 vs 100.00. Kolumna określa szacowany procent tabeli, która ma być przefiltrowana przed przetworzeniem. Posiadanie wyższej wartości jest lepsze. Wartość 100.00 oznacza, że zapytanie przegląda całą tabelę. Dla drugiego zapytania, wartość ta nie jest stała i zależy od numeru strony: jeśli zapytamy o pierwszą stronę, wartość filtrowanej kolumny wyniesie 1000000.00. Dla ostatniej strony, będzie to 100.00.
• Extra: NULL vs Using where. Dostarcza dodatkowych informacji o tym, jak MySQL rozwiązuje zapytanie. Zastosowanie WHERE na kluczu PRIMARY przyspiesza wykonanie zapytania.

Podejrzewam, że typ złączenia jest tym parametrem zapytania, który w największym stopniu przyczynił się do wydajności, dzięki czemu 3 zapytanie jest szybsze. Inną ważną rzeczą jest to, że 2. zapytanie jest bardzo zależne od liczby stron do przewinięcia. Bardziej głęboka paginacja jest wolniejsza w tym przypadku.

Więcej wskazówek dotyczących zrozumienia danych wyjściowych dla polecenia EXPLAIN można znaleźć w oficjalnej dokumentacji dla twojego RDBMS.

Podsumowanie

Główny temat wpisu na blogu był związany ze skanowaniem dużej tabeli zawierającej 100 000 000 rekordów przy użyciu offset z kluczem głównym (paginacja za pomocą zestawu kluczy). Ogólnie rzecz biorąc, 3 różne podejścia zostały przejrzane i przetestowane na odpowiednim zbiorze danych. Polecam tylko jedno z nich, jeśli potrzebujesz przeskanować dużą tabelę, która podlega mutacjom.

Zrewidowaliśmy również użycie komendy EXPLAIN EXTENDED do analizy planu wykonania zapytań MySQL. Jestem pewien, że inne RDBMS mają analogiczne funkcjonalności.

W następnym rozdziale zwrócimy uwagę na agregację danych i optymalizację przechowywania. Stay tuned!

Jaka jest Twoja metoda skanowania dużych tabel?

Czy pamiętasz jeszcze jakiś inny cel stosowania paginacji zestawów kluczy, jak w rozwiązaniu #3?

.