Last Updated on December 8, 2019
Przywracanie losowych wierszy w losowej kolejności z relacyjnej bazy danych jest bardzo trudnym problemem. W tym artykule zobaczymy antipattern, przedyskutujemy dlaczego ten problem jest tak trudny i zbadamy kilka niedoskonałych rozwiązań.
UPDATE: Niektóre DBMSy obsługują TABLESAMPLE. Nie wspomniałem o tym, ponieważ do dziś znałem tylko implementację SQL Server, i nie uważam, że jest ona dobra do wyodrębniania losowych wierszy (wyjaśnię dlaczego). Ale po pytaniu na Facebooku przez Daniëla van Eedena zrobiłem trochę badań i odkryłem, że implementacja PostgreSQL może być o wiele bardziej odpowiednia. Będę więcej o tym czytał i próbował, a potem prawdopodobnie napiszę drugi artykuł na ten temat. Tak czy inaczej, MySQL i MariaDB nie obsługują TABLESAMPLE.
Nieprawidłowy sposób: ORDER BY RAND()
Wielu programistów uważa, że mogą to zrobić w ten sposób:
SELECT some_columns FROM some_table ORDER BY RAND() LIMIT 10;Jest to jedyne zapytanie, które robi dokładnie to, czego się oczekuje. Jeśli funkcja RAND() jest niezawodnie losowa, zwraca losowy zestaw wierszy, gdzie każdy wiersz ma takie same szanse na zwrócenie.
Problemem jest to, jak to działa pod maską. Aby zamówić losowe wartości, trzeba je najpierw utworzyć. Aby utworzyć wartość losową dla każdego wiersza w tabeli, DBMS musi przeczytać każdy wiersz. Tak więc DBMS wykona operację w dwóch krokach:
- Kopiuje wiersze plus wartość losową do tabeli tymczasowej, miejmy nadzieję, że w pamięci;
- Porządkuje wiersze w tabeli tymczasowej.
Zauważ, że ten szczegół: miejmy nadzieję, że w pamięci. W zależności od DBMS, mogą istnieć powody, dla których tabela musi zostać utworzona na dysku. Zazwyczaj dzieje się tak, jeśli tabela jest zbyt duża. Stare wersje MySQL również tworzą tymczasowe tabele na dysku, jeśli zawierają TEXT lub BLOB kolumn.
Nie trzeba dodawać, że jeśli tabela jest duża, jest to powolna operacja, która zużywa dużo zasobów.
Dlaczego relacyjne DBMS-y nie zapewniają wbudowanego sposobu zwracania losowych wierszy?
Relacyjne bazy danych są zbudowane wokół gałęzi matematyki zwanej algebrą relacyjną. Jest ona oparta na logice, ponieważ zajmuje się predykatami typu prawda/fałsz; ans podobna do teorii zbiorów, nawet jeśli relacja jest czymś bardziej złożonym niż zbiór, a nawet postrzeganie jej jako tabeli nie jest matematycznie poprawne. Ten artykuł jest miłym przykładem tego, co mam na myśli, ale istnieją bardziej złożone argumenty.
Pomimo że SQL nie jest dokładną implementacją modelu relacyjnego, jego algebra jest używana jako odniesienie. Podobnie jak wszystkie gałęzie matematyki, ma ona dobrze zdefiniowany zestaw operacji. Pobieranie losowych krotek z relacji na pewno nie jest jedną z nich.
Ta odpowiedź brzmi trochę zbyt teoretycznie, prawda? ORDER BY i tabele bez klucza głównego również naruszają zasady algebry relacyjnej, ale SQL je obsługuje.
Jednakże w przypadku baz danych szybkość ma kluczowe znaczenie. Relacyjne systemy DBMS są zaprojektowane do wykonywania operacji relacyjnych bardzo szybko. Oczywiście, struktura danych zaprojektowana do optymalizacji pewnych operacji nie jest zoptymalizowana dla innych operacji. Tak więc, relacyjne DBMS nie są zoptymalizowane do losowego wyszukiwania.
Powinno być oczywiste, że zapętlanie się nad wierszami w celu losowego wyboru niektórych z nich byłoby powolne. Teoretycznie, odczytanie losowego wiersza za pomocą indeksu byłoby tak szybkie, jak znalezienie wiersza według wartości klucza głównego. Ale wtedy różne wiersze miałyby różne szanse na wybór.
Powyższy obrazek pochodzi z repozytorium GitHub Jeremy’ego Cole’a, innodb_diagrams. Prędzej czy później powinienem napisać o jego projektach do analizy struktur danych InnoDB.
Ważne jest tutaj to, że indeks jest drzewem, którego węzły są stronami pamięci. Węzły liści zawierają rzeczywiste dane; górne poziomy zawierają jedynie informacje potrzebne do wybrania najkrótszej ścieżki do żądanego węzła liści. Szczegóły nie są ważne w tym kontekście.
DBAMS mógłby teoretycznie wybrać losową stronę, wykonując serię losowych decyzji: czy pójdę w lewo, czy w prawo? Ale wtedy strony liści zawierają zmienną liczbę wierszy. Mogłyby być nawet puste. Tak więc różne wiersze miałyby różne szanse na wybór.
Wynik jest wyraźnie poza zamierzonymi przypadkami użycia DBMSs; i może być powolny lub błędny, w zależności od tego, czy indeks jest używany, czy nie. DBMSy słusznie zdecydowały się nie implementować tej funkcji.
Kilka rozwiązań
Nie ma idealnych rozwiązań. Istnieją rozwiązania, które mogą być akceptowalne, ale mają wady. Powinniśmy wybrać jedno z nich od przypadku do przypadku.
Wybór losowy z zakresu
To rozwiązanie ma zastosowanie do tabel, które mają autoinkrementacyjny klucz główny. Jest najprostsze w implementacji, ale „fragmentaryczny” klucz główny powoduje problemy.
Polega na sprawdzeniu minimalnego id, maksymalnego id i wygenerowaniu losowej liczby z tego zakresu:
Niestety zapytania z MIN() i MAX() na dowolnym indeksie, bez innych klauzul, są bardzo szybkie.
Wynikiem jest naprawdę losowy wiersz. Aby wybrać więcej niż jeden wiersz, możemy powtórzyć to zapytanie wiele razy. To prowadzi nas do dwóch wad:
- Jeśli ta operacja jest wykonywana często, możemy uruchomić to zapytanie wiele razy.
- Nie ma gwarancji, że ten sam wiersz nie zostanie wybrany wiele razy. Jeśli tak się stanie, aplikacja może ponowić próbę wykonania zapytania. Jeśli tabela jest duża, zdarzenie to jest rzadkie i możemy je zignorować – chyba że funkcja
RAND()jest zawodna. Jednak w przypadku małych tabel może to stanowić problem.
Ponadto, klucz główny może mieć dziury – innymi słowy, może brakować niektórych liczb. Jest to spowodowane usuwaniem danych i nieudanymi transakcjami. Numery niższe niż maksymalne nie są ponownie wykorzystywane. Aby obejść ten problem, możemy użyć dwóch technik.
Użycie >=
Jeśli użyjemy operatora >= w klauzuli WHERE, zapytanie zawsze zwróci wiersz. Jeśli wygenerowany numer nie występuje, zostanie użyty następny. Oznacza to jednak, że wartości zaraz po dołku będą miały większe szanse na wybór. Im większa dziura, tym większe szanse.
Możesz pomyśleć, że nie powinieneś się tym przejmować i prawdopodobnie masz rację. Ale zanim podejmiesz ostateczną decyzję, rozważ możliwość wystąpienia dużej dziury.
Próbowanie na siłę
Jeśli zapytanie nie zwróci żadnych wierszy, możemy po prostu ponowić próbę. Dla dużych tabel z kilkoma małymi dziurami, jest to całkowicie w porządku. Ale dla dużych tabel z wieloma dziurami, lub dużymi dziurami, ta technika może pochłonąć zbyt wiele zasobów.
Proszę nie popadać w zbytnią paranoję. Po prostu zrób trochę matematyki. Jaki jest stosunek brakujących wartości w twojej tabeli? To powie ci, ile razy zapytanie będzie próbowane ponownie, średnio.
Wybieranie wielu wierszy
Aby wybrać wiele wierszy za pomocą tej techniki, możemy:
- Powtórzyć zapytanie wiele razy;
- Albo, dla lepszej wydajności, użyć operatora
>=i użyćLIMITwiększego niż jeden. To jednak sprawia, że wyniki są znacznie mniej losowe.
Przeniesienie losowego wyboru do aplikacji
W swojej najprostszej formie technika ta polega na losowym wyborze bloku sąsiadujących id. Aplikacja losowo wybierze te, których użyje, a następnie wybierze pasujące wiersze.
Załóżmy, że chcesz wybrać z bloków 1000 wartości:
Im większy blok, tym więcej zasobów zużywasz, tym bardziej losowy jest wynik. Aplikacja jest odpowiedzialna za wybór losowych unikalnych istniejących id z bloków, więc nigdy nie powinno być potrzeby ponawiania zapytania.
Wariant MOD
Problemem z tą techniką jest to, że wiersze są zwracane z tego samego bloku sąsiadujących id. Może to być całkowicie akceptowalne, szczególnie jeśli blok jest duży. Ale jeśli tak nie jest, moglibyśmy dodać trochę złożoności, aby wybrać blok nieciągnących się wierszy.
Pomysł tego wariantu polega na:
- Zdefiniuj makrobloki w większości nieciągnących się wierszy;
- Losowo wybierz jeden makroblok;
- Zwróć blok z niego.
Aby to zrobić, możemy obliczyć modulus id i użyć go do losowego wyboru wyników. Na przykład, możemy zdefiniować indeksowaną wirtualną kolumnę z wyrażeniem takim jak (id MOD 4). Każdy wiersz będzie miał wartość z przedziału od 0 do 3. Nawet jeśli istnieją dziury, wiersze z tych makrobloków będą w większości nieskojarzone i powinny mieć w przybliżeniu taką samą liczbę.
Aplikacja powinna wygenerować liczbę losową z przedziału od 0 do 3. Następnie, aby wybrać bloki z tych makro-bloków:
SET @block_size := 1000;SELECT id FROM some_table WHERE id_mod = FLOOR(RAND() * 3) ORDER BY id LIMIT @block_size;Podobnym sposobem realizacji tego pomysłu jest użycie partycji, gdzie funkcją partycjonowania jest modulus id. Sugerowałbym to tylko wtedy, gdy tabela skorzystałaby z partycjonowania z innych powodów.
Wybór techniki
Techniki blokowe uruchamiają więcej zapytań w porównaniu do pierwszej z operatorem >=, a wynik może być lepszy lub nie. W porównaniu z wariantem retry, może to uruchomić więcej lub mniej zapytań, a wynik jest gorszy.
Ogólnie techniki blokowe są lepsze, jeśli mamy dziury w kluczu głównym.
Buforowanie losowych serii
Poprzednie metody są kompromisem: wydajność kontra lepsza losowość, gdzie szybsze rozwiązania są również bardziej złożone w implementacji. Tak długo jak nie używamy ORDER BY RAND() antipattern, wybieranie losowych wierszy nie powinno powodować problemów z wydajnością. Ale co jeśli tak się stanie?
Moglibyśmy zbuforować losowo posortowane id uzyskane za pomocą któregoś z poprzednich rozwiązań. Moglibyśmy użyć zapytania takiego jak to (składnia MySQL):
Moglibyśmy użyć serii w porządku rosnącym lub malejącym, losowo. Albo aplikacja mogłaby je tasować.
Problemy:
- Gdy element jest dodawany, powinniśmy losowo wybrać, czy musi być wstawiony do serii, zastępując losowy element.
- Gdy element jest usuwany, powinniśmy go usunąć ze wszystkich serii. Powinien być zastąpiony przez inny losowy element.
- Możemy chcieć okresowo usuwać najstarsze serie i zastępować je nowymi, aby poprawić losowość w doświadczeniu użytkownika.
Wnioski
Jak zwykle, proszę komentuj i daj mi znać, jeśli zauważysz błąd w tym artykule, jeśli nie zgadzasz się z czymś, powiedz mi o swoich osobistych doświadczeniach, lub jeśli masz więcej pomysłów do dodania.