Losowy rekord w SQL Server
Losowy dowcip, losowe wydarzenie, losowy temat
- Co się stało, kochanie?
- Źle się czuję, więc położyłam się do łóżka.
- To dlaczego leżysz naga? Poczekaj, zaraz wyjmę z szafy twoją koszulę nocną.
- Tylko nie z szafy, tam straszy!
Mąż otwiera szafę i widzi gołego sąsiada.
- No wiesz, Stefan? Nigdy bym się po tobie tego nie spodziewał. Żona chora, a ty ją jeszcze straszysz!
dowcip dnia,
ciekawostka na dziś,
losowa recenzja. Tego typu rozwiązania są najczęściej realizowane przy pomocy algorytmów pseudolosowych. Spośród wszystkich elementów w tabeli wybierany jest jeden (lub kilka) i pokazywany użytkownikowi. Gdy użytkownik odświeży stronę lub przejdzie w inne miejsce, znów wybierany jest losowy wpis. Istnieje szansa, że któryś z tych wpisów na tyle tego użytkownika zainteresuje, że ten kliknie i przeczyta nasze materiały. W czeluściach Internetu można oczywiście znaleźć gotowe rozwiązania i w pewnym sensie są one dobre. Nie zauważyłem jednak aby w którymś miejscu sposoby te były szczegółowo opisane, z wszystkimi wadami i zaletami każdego z tych sposobów. Nikt nad problemem nie pochylił się na tyle, żeby wyjaśnić konsekwencje swoich rozwiązań. A konsekwencje mogą być niekiedy straszliwe.
Losowy rekord przy pomocy NEWID
Pierwszy sposób, podejrzewam, najpowszechniej wykorzystywany, polega na wykorzystaniu pseudolosowej funkcji generującej globalne identyfikatoryW SQL Server istnieje funkcja RAND(), ale ma ona peną szczególną własciwość - wyliczana jest ona tylko raz w ramach jednego zapytania. Jeżeli zatem dołożymy do zapytania kolumnę z RAND(), wszystkie rekordy będą miały tę samą wartość losową. Podobną właściwość ma funkcja GETDATE().. Tak wygenerowane globalne identyfikatory sortuje się razem z resztą wartości wiersza i bierze pierwszy z brzegu. Popatrzmy na przykład:
(
Name varchar(30)
CONSTRAINT PK_Countries PRIMARY KEY,
FullName nvarchar(100) NOT NULL,
[Population] int NOT NULL,
Area int NOT NULL
)
INSERT INTO Countries VALUES('Congo', N'Republic of the Congo', 4366266, 342000);
INSERT INTO Countries VALUES('Poland', N'Republic of Poland', 38544513, 312679);
INSERT INTO Countries VALUES('USA', N'United States of America', 316962000, 9826675);
INSERT INTO Countries VALUES('United Kingdom', N'United Kingdom of Great Britain and Northern Ireland', 63181775, 243610);
INSERT INTO Countries VALUES('Germany', N'Federal Republic of Germany', 80523700, 357021);
INSERT INTO Countries VALUES('Spain', N'Kingdom of Spain', 46704314, 505992);
--Pobierz 1 losowy rekord
SELECT TOP 1 * FROM Countries
ORDER BY NEWID()
Metoda jest bardzo prosta i wydaje się, że idealna. Ma jeszcze jedną ciekawą właściwość - gdybyśmy teraz zechcieli pobrać trzy losowe i unikatowe rekordy, wyglądałoby to następująco:
SELECT TOP 3 * FROM Countries
ORDER BY NEWID()
Napisałem na początku, że postaram się zagłębić w szczegóły poszczególnych rozwiązań - ich wady i zalety. Z zalet trzeba wymienić czytelność i prostotę, dobry rozkład statystyczny wyników, brak wymagań co do kluczy i innych konstrukcji oraz możliwość łatwego rozszerzenia w celu pobrania N losowych rekordów. Podstawową wadę muszę rozwinąć
Plan wykonania - skanowanie i sortowanie
Najłatwiej dostrzec wszystkie wady rozwiązania analizując plan wykonania - sposób, w jaki SQL Server realizuje zapytanie. Przyjrzyjmy się takiemu przykładowemu planowi:
Dwa miejsca w tym planie wymagają szczególnej uwagi. Po pierwsze, wykonywana jest operacja pełnego skanowania tabeli. Dla kilku rekordów nie ma to znaczenia. Jeżeli tych rekordów jest kilkaset tysięcy, wtedy można całkowicie zamordować bazę danych. To tak, jakbyśmy zrezygnowali z użycia jakiegokolwiek indeksu. Po drugie, wykonywana jest nie mniej kosztowna operacja sortowania tych rekordówDomyślnie sortowanie W SQL Server realizowane jest przez algorytm QuickSort (średnia złożoność O(n*log(n)). Sortowanie typu TOP N może być z łatwością zrealizowane przez algorytm sortowania przez wybieranie (O(n2). W przypadku TOP 1 jest to równoznaczne z wyszukaniem minimalnego rekordu.. Te dwie kosztowne operacje sprawiają, że praktyczne zastosowanie tego rozwiązania kończy się całkowicie na kilkudziesięciu tysiącach rekordów. Popatrzmy na przykład:
(
ID int IDENTITY,
A nvarchar(50) DEFAULT 'RekordA'+CAST(NEWID() AS nvarchar(36)),
B nvarchar(50) DEFAULT 'RekordB'+CAST(NEWID() AS nvarchar(36)),
C nvarchar(50) DEFAULT 'RekordC'+CAST(NEWID() AS nvarchar(36)),
D nvarchar(50) DEFAULT 'RekordD'+CAST(NEWID() AS nvarchar(36)),
E nvarchar(50) DEFAULT 'RekordE'+CAST(NEWID() AS nvarchar(36)),
F nvarchar(50) DEFAULT 'RekordF'+CAST(NEWID() AS nvarchar(36)),
G nvarchar(50) DEFAULT 'RekordG'+CAST(NEWID() AS nvarchar(36)),
H nvarchar(50) DEFAULT 'RekordH'+CAST(NEWID() AS nvarchar(36))
)
SET NOCOUNT ON
SET STATISTICS IO OFF
SET STATISTICS TIME OFF
DECLARE @i int = 0
BEGIN TRANSACTION
WHILE @i<1000000
BEGIN
INSERT INTO TestNEWID DEFAULT VALUES;
SET @i += 1;
END
COMMIT
SELECT COUNT(*) FROM TestNEWID
SET STATISTICS IO ON
SET STATISTICS TIME ON
--Pobierz losowy rekord
SELECT TOP 1 * FROM TestNEWID
ORDER BY NEWID()
Ostatnia instrukcja w środowisku testowym wygenerowała taki rezultat:
SQL Server Execution Times:
CPU time = 1794 ms, elapsed time = 289 ms.
Pokazana powyżej tabela testowa posłuży do badania innych metod. Różnice lepiej pokazać na, powiedzmy sobie, praktycznym przykładzie.
Wykorzystanie ciągłości zbioru
Wiele tabel ma kolumnę typu IDENTITY. Sprawia to, że identyfikatory kolejnych rekordów są kolejnymi liczbami całkowitymi. To z kolei pozwala na zastosowanie nieco innego algorytmu wybierania wartości losowej:
WHERE ID = CAST(RAND()*(SELECT MAX(ID) FROM TestNEWID) AS INT)+1
Rozwiązanie jest o tyle lepsze, że nie wymaga operatora sortowania. W pokazanej konfiguracji wymaga niestety operacji pełnego skanowania tabeli. Bez indeksu środowisko testowe zwraca następujący koszt:
SQL Server Execution Times:
CPU time = 515 ms, elapsed time = 103 ms.
Liczba operacji dyskowych jest większa, ale sumaryczny czas mniejszy. To jednak nie wszystko. Zwykle tabela posiada klucz główny, który powiązany jest z odpowiadającym mu indeksem. Sprawia to, że wykonanie operacji znacząco się skraca:
ALTER TABLE TestNEWID
ADD CONSTRAINT PK_TestNEWID_ID
PRIMARY KEY CLUSTERED(ID)
Tym razem wyniki są zupełnie inne. Popatrzmy na zgłaszane przez SQL Server koszty:
SQL Server Execution Times:
CPU time = 0 ms, elapsed time = 0 ms.
Różnica jest dramatyczna. Wobec 222238 odczytów logicznych mamy tych odczytów 6. Czas przestał być mierzalny. Taka jest różnica między zapytaniem i zapytaniem
. Wydaje się, że znaleźliśmy idealne rozwiązanie. Szybkie, sprawne i w miarę przejrzyste. Wyostrzyłem zaletę, teraz czas na wady.
Losowe rekordy w dziurawej sekwencji
Poprzednie rozwiązanie zakłada ciągłość klucza. Nie zawsze możemy sobie pozwolić na taki komfort. Po pierwsze, wystarczy, że usuniemy jakiś rekord - pozostaje dziur. Istnieją wprawdzie metody wyszukiwania dziur i zapełniania ich, ale, ze względu na złożoność, rzadko się je stosuje. Co począć? Istnieje pewien trik, który może złagodzić tego typu problemy. Popatrzmy na poniższe rozwiązanie:
SELECT TOP 1 * FROM TestNEWID
WHERE ID>=CAST(RAND()*(SELECT MAX(ID) FROM TestNEWID) AS INT)+1
Co się dzieje w przypadku napotkania dziur? Pobierany jest kolejny wolny rekord. To z kolei prowadzi do innych pułapek. O ile rozkład dziur jest równomierny, metoda może być stosowana. Jeżeli dziury w numeracji są różne - mamy problem. Ten problem to nierównomierny rozkład losowych wartości. Rekord po większej dziurze będzie występował częściej niż rekord po małej dziurze. Popatrzmy na przykład pokazujący cały problem:
(
ID int PRIMARY KEY,
Value nvarchar(10)
)
INSERT INTO RandStatistic VALUES
(1, N'Wartość 1'),
(10, N'Wartość 2'),
(11, N'Wartość 3'),
(12, N'Wartość 4')
--Tymczasowa tabela
CREATE TABLE #Temp(Value nvarchar(10))
--Wylosuj 1000 razy
DECLARE @i int=0
WHILE @i < 1000
BEGIN
--Pobierz pierwsze ID większe od wylosowanego
INSERT INTO #Temp
SELECT TOP 1 Value FROM RandStatistic
WHERE ID>=CAST(RAND()*(SELECT MAX(ID) FROM RandStatistic) AS INT)+1;
SET @i += 1;
END
SELECT COUNT(*) Total, Value FROM #Temp GROUP BY Value
DROP TABLE #Temp
Ostatnie zapytanie zwróci następujący rezultat:
| Total | Value |
|---|---|
| 77 | Wartość 1 |
| 752 | Wartość 2 |
| 84 | Wartość 4 |
| 87 | Wartość 3 |
Widać wyraźnie, że wartość Wartość 2
występuje w przybliżeniu 10 razy częściej niż pozostałe wartości. Taki jest efekt nierównomiernych dziur i nieciągłości.
Jednoprzebiegowe filtrowanie z progiem
Skoro sortowanie jest kosztowne to może dałoby się je pominąć? Wychodząc z takiego założenia można dotrzeć do rozwiązania polegającego na jednoprzebiegowym filtrowaniu względem losowej wartości progowej. Na czym to niby polega? Do każdego rekordu, w locie, przypisujemy wartość całkowitą. Jeżeli ta wartość przekracza pewien próg - akceptujemy ją. Jeżeli nie - odrzucamy. Dzięki odpowiednio ustawionemu progowi można mocno przeczesać rekordy z tabeli wejściowej. Ewentualne sortowanie może być zrealizowane tylko na bardzo wąskim podzbiorze wszystkich wartości. Popatrzmy na przykładowe rozwiązanie tego typu:
--Zwrócone zostanie:
--~10 rekordów - 0.00001
--~100 rekordów - 0.0001
SELECT ROW_NUMBER() OVER (ORDER BY ID), * FROM TestNEWID
WHERE 0.00001 >= CAST(CHECKSUM(NEWID(),ID) & 0x7fffffff AS float)
/ CAST (0x7fffffff AS int)
Ustawiłem próg tak, żeby SQL Server zwracał w przybliżeniu 10 rekordów. W przybliżeniu, bo nie ma żadnej pewności, że będzie to 10. To przecież wartość losowa. W ekstremalnych przypadkach możemy dostać 0 rekordów! Trzeba to odpowiednio obsłużyć w kodzie. Popatrzmy jeszcze na koszty zgłaszane przez SQL Server:
SQL Server Execution Times:
CPU time = 390 ms, elapsed time = 387 ms.
Rozwiązanie może być stosowane w dziurawych sekwencjach, nie wymaga klucza, wszystkie rekordy wybierane są równie często. Sam koszt zapytania jest znacznie niższy niż uzyskany w pierwszym rozwiązaniu. Istnieje możliwość zwrócenia kilku losowych rekordów jednocześnie. Nie ma niestety pewności ile tych rekordów rzeczywiście będzie. Ponadto, dla dużych tabel takie rozwiązanie również może być zbyt kosztowne.
Tabela pomocnicza
Kiedyś mawiało się, że programy to algorytmy + struktury danych. Rozwiązania dla dużych i bardzo dużych tabel wymagają często denormalizacji i struktur pomocniczych (struktury danych) oraz znanych powszechnie algorytmów operujących na tej strukturze. Takie też będzie pokazane w tym podpunkcie rozwiązanie. Będzie to połączenie techniki zakładającej ciągłość identyfikatorów na tabeli potencjalnie nieciągłej z jednorazowym (a właściwie okresowym) przygotowaniu tabeli podglądu. Popatrzmy na przykład:
SELECT ROW_NUMBER() OVER (ORDER BY ID) RowNumber, ID RecordKey INTO LookupTable
FROM TestNEWID
CREATE CLUSTERED INDEX IX_LookupTableID ON LookupTable(RowNumber, RecordKey)
Jak się można przekonać, koszt utworzenia takiej tabeli nie jest jakoś wyraźnie większy niż pobranie losowego rekordu pierwszą metodą:
SQL Server Execution Times:
CPU time = 546 ms, elapsed time = 541 ms.
Table 'LookupTable'. Scan count 9, logical reads 2598, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
SQL Server Execution Times:
CPU time = 1809 ms, elapsed time = 652 ms.
Taka tabela pomocnicza może być aktualizowana raz dziennie, w nocy, w czasie zmniejszonego obciążenia bazy danych. Samo pobieranie losowych rekordów sprowadza się w tym przypadku do znanej już operacji:
JOIN TestNEWID ON ID=RecordKey
WHERE RowNumber=CAST(RAND()*(SELECT MAX(RowNumber) FROM LookupTable) AS INT)
Koszty zgłaszane przez serwer testowy wyglądają następująco:
Koszty są na granicy pomiaru. Plan wykonania pokazuje tylko operacje wyszukiwania po kluczu.
Struktury danych aktualizowane na bieżąco
Niektóre rozwiązania mogą wymagać częstej aktualizacji tabeli pomocniczej. Co w takim przypadku można zrobić? Po pierwsze, można zaangażować w to wyzwalacze działające według kilku prostych zasad:
- Przy wstawianiu (INSERT) N nowych rekordów - wstaw je na koniec i przydziel im kolejne numery.
- Przy usuwaniu (DELETE) N rekordów - spośród N ostatnich rekordów wybierz te, które nie są usuwane i wstaw w miejsce kolumny RecordKey usuwanych rekordów licząc od początku. Inaczej mówiąc, przesuń wartości z końca w powstające dziury i usuń N wartości z tego końca. Zapewnia to ciągłą numerację.
- Przy aktualizowaniu (UPDATE) wartości nie trzeba nic robić.
Unikatowość pierwszej, numeracyjnej kolumny tabeli pomocniczej daje gwarancję uporządkowania. Modyfikacja drugiej kolumny nie wpływa zatem na podziały stron indeksu. Dokładanie wartości również nie powoduje fragmentacji indeksu, bo nowe strony dokładane są na końcu. Takie drobne szczegóły, a cieszą. Złożoność przyjętego rozwiązania musi oczywiście zależeć od potrzeb. Gdy rekordy wstawiane lub usuwane są pojedynczo, opisane powyżej kroki znacząco się upraszczają. Wstawianie to położenie pary wartości na koniec, usunięcie to przeniesienie wartości z końca na miejsce usuwanego rekordu i usunięcie ostatniego (przy usuwaniu ostatniego rekordu wykonujemy niepotrzebną aktualizację, ale to przypadek szczególny).
Pokazana technika daje jeszcze większe możliwości niż się wydaje. Rekordy nie muszą być wcale posortowane według pierwotnych kluczy. Pozwala to na pobieranie kilku rekordów z rzędu i to dalej będzie sprawiało wrażenie losowości. Wszystko zależy od techniki generowania i utrzymywania tabeli pomocniczej. Generowanie tej tabeli jest kosztowne, ale wykonywane jednorazowo. Utrzymywanie polega na modyfikowaniu tylko drobnej porcji tej tabeli. To tak, jakbyśmy zamiast jednej operacji INSERT robili dwie, zamiast DELETE może trzy. Jednorazowy koszt pomijalny, a setki losowych rekordów otrzymywane w mgnieniu oka.
Podsumowanie
Technik pobierania losowych jest więcej. Postarałem się opisać te, które sam miałem okazję zastosować. Dla prostych tabelek nie ma co kombinować i pierwsza metoda sprawdzi się znakomicie. Większe tabele (dziesiątki tysięcy rekordów) wymagają bardziej finezyjnych technik. Wszystko zależy od potrzeby i technicznych możliwości wykorzystywanego sprzętu. W przypadku gigantycznych tabel warto rozważyć również operator TABLESAMPLE. Pobiera on losową stronę tabeli, a dokładniej stronę z prawdopodobieństwem znalezienia się na niej wskazanej liczby wierszy lub ich procentową wartość. Operacja działa błyskawicznie, bo na poziomie strony (nie pojedynczego rekordu!). Takie pojedyncze strony można potem potraktować innymi technikami. Opcja TABLESAMPLE jest niestety trudna do okiełznania. Zbyt mała liczba wymaganych wierszy może powodować zwracanie pustych zbiorów wynikowych, zbyt duża prowadzi do dużego rozrzutu liczby faktycznie zwracanych wierszy. Kilka prób na tabeli testowej pokazało, że przy wskazaniu 50 wierszy system zwracał od 0 do 110 rekordów. Osobiście nie ufam tej metodzie, ale zachęcam do zapoznania się z nią.
Starałem się pokazać przede wszystkim te miejsca, które są słabą stroną każdego z rozwiązań. Albo rozwiązanie jest wolne (ORDER BY NEWID, filtrowanie), albo wymaga ciągłości identyfikatora, albo prowadzi do nierównomiernego rozkładu losowanych wartości, albo jest bardziej złożone. Mam nadzieję, że dzięki analizie tych metod łatwiej będzie podjąć odpowiednią decyzję.
Kategoria:Optymalizacja SQLSQL Server
Brak komentarzy - bądź pierwszy