Subselect to fajne zapytanie, ale co w sytuacji, kiedy musimy przeszukać miliony rekordów i to setki razy w ciągu minuty. Subselect okaże się mało wydajny, a przy dużej ilości zapytań liczy się każda oszczędność. W portalach społecznościowych często użytkownicy poszukują innych profili na postawie wieku lub wzrostu i tutaj nie ma żadnych problemów, gdyż łatwo przechować je w jednej tabeli. Gorzej jest natomiast z danymi typu znajomość języków obcych czy zainteresowania, gdzie pola te mogą mieć wiele wartości. Niektórzy stosują harcerskie rozwiązania w stylu umieszczania wielu danych do jednego varchar’a i użycie LIKE w zapytaniu. Mnie chyba nie przyszłoby coś takiego do głowy 😉 Innym pomysłem byłoby zastosowanie pól typu array, lecz odradzane jest to nawet na stronie PostgreSQL:
Tip: Arrays are not sets; searching for specific array elements may be a sign of database misdesign. Consider using a separate table with a row for each item that would be an array element. This will be easier to search, and is likely to scale up better to large numbers of elements.
Najlepszym rozwiązaniem byłoby zastosowanie kolejnej tabeli z danymi, oddzielnej dla języka i zainteresowań w relacji wiele do wielu z naszą tabelą profili. To dobry sposób zachowujący wszystkie zasady budowania schematów baz danych, niestety trochę powolny. Zapytanie wykonujące subselect na milionach rekordów to wydajnościowa masakra dla bazy danych. W czasach programowania w DOS’ie, kiedy każdy bit i cykl procesora był niezwykle ważny, dane przechowywano jako bity wewnątrz wartości integer, aby zużyć mniejszą ilość pamięci. Taki sam trick można zastosować w bazach danych, by zaoszczędzić miejsce i zasoby podczas przeszukiwania.
Aby pokazać na przykładzie różnice w wydajności zastosowałem poniższy schemat.
Moje dane testowe:
- 11 rekordów w tabelach usr_profile_languages i usr_profile_linterests ( po jedenaście grup)
- ponad milion rekordów w tabeli usr_table
- ponad trzy miliony rekordów w tabelach łączących profil ze znajomościa języków – usr_profile_languages_list, usr_profile_linterests_list (średnio każdy posiada trzy zainteresowania i zna trzy języki)
- indeksy na wieku, kraju, językach, zainteresowaniach
Test z wykorzystaniem subquery:
Aby sprawdzić możliwości bazy rozpocząłem od prostego zapytania:
- select count(*) from usr_table u WHERE age > 56;
Otrzymaliśmy 200 000 rekordów w 1,5 sekundy
- select count(*) from usr_table u WHERE age < 42;
Zapytanie ma ponad 600 000 rekordów i trwało 1,6 sekundy.
Teraz zapytanie o ludzi poniżej 50 lat znających jeden wybrany język z wykorzystaniem podzapytania.
- select count(*) from usr_table u WHERE age < 50 AND (SELECT count(*) FROM usr_profile_languages_list l WHERE l.usr_profile_languages_id=4 AND l.id=u.id)=1;
Zapytanie zabrało od 14s do 50s. Różnica wynika z cachowania zapytania w bazie.
Następnie zapytanie o profile znające dwa języki powyżej 58 roku życia (większość rekordów została wycięta przez index wieku)
- select count(*) from usr_table u WHERE age >58 AND (SELECT count(*) FROM usr_profile_languages_list l WHERE (l.usr_profile_languages_id=4 OR l.usr_profile_languages_id=6) AND l.id=u.id)=2;
Zapytanie wyszukało około 10000 rekordów w ciągu 17 do 40 sekund.
Podobnie jest z ludźmi powyżej 58 lat znającymi dwa z trzech wybranych języków.
- select count(*) from usr_table u WHERE age >58 AND (SELECT count(*) FROM usr_profile_languages_list l WHERE (l.usr_profile_languages_id=4 OR l.usr_profile_languages_id=6 OR l.usr_profile_languages_id=7) AND l.id=u.id)>=2;
18000 rekordów w 14 do 20 sekund.
Test na bitach:
Teraz pola bitowe: tworzymy dane typu integer wewnątrz tabeli użytkowników usr_table i wypełniamy je trzema losowymi zainteresowaniami z jedenastu dostępnych.
alter table usr_table add column languagebit integer;
UPDATE usr_table set languagebit=2^(ROUND(RANDOM()*10+1));
UPDATE usr_table set languagebit=languagebit+2^(ROUND(RANDOM()*10+1));
UPDATE usr_table set languagebit=languagebit+2^(ROUND(RANDOM()*10+1));
Prymitywna skuteczność 🙂
Profile poniżej 50 lat z jednym zainteresowaniem wyszukano w 1,8s .
- select now() ;select count(*) from usr_table u WHERE age <50 AND languagebit & 32 = 32
Użyłem 32 ponieważ 2^5 daje 32, a poszukiwaną grupą była grupa numer 5.
Ludzie powyżej 58 lat z dwoma zainteresowaniami zostali wyszukani w 1,6s
- select count(*) from usr_table u WHERE age >58 AND languagebit & 2 = 2 AND languagebit & 1024 = 1024;
%
kwiecień 12th, 2008 at 11:13
Wyśmienity Technic Blog – zaczynam go śledzić … 🙂
Pozdrawiam i życzę dalszych dobrych artykułów.
kwiecień 14th, 2008 at 23:37
Mam pytanko co do sensowności rozwiązania. Tzn. jest ono z całą pewnością sensowne, sam kiedyś wpadłem na coś takiego ale zrezygnowałem z kombinacji bo to była praca zaliczeniowa ;p Z tego czegoś musiał się jeszcze bronić kumpel a ja powątpiewałem w jego możliwości.
Mniejsza o moje new_anse. Potrafię obsłużyć Sybase, a teraz przesiadam się na Postgresa i chciałbym wiedzieć czy jest tu takie coś o czym marzę (nie ma tego sybase). Mianowicie czy można stworzyć komurkę typu danych przypominającego coś na wzór list czy vector tak jak w STL pod C++?
Dajmy na to tworzymy sobie w tabeli pole typu vector dla języków. User w momencie dodawania znajomości języków może wtedy dodawać własne języki no i nie jesteśmy ograniczeni rozmiarem inta. Vector jak vector ma swoją długość więc wyszukiwanie userów znających 2 języki wyglądało by
select (*) FROM user_tab u WHERE u.jezyki->ilosc = 2;
ta strzałka to takie c++owe zboczenie, ale może też takie masz więc szybciej zrozumiesz o co mi chodzi i dlaczego nie mam racji ;p
Takie rozwiązanie jest o tyle kłopotliwe że wydłuża nam się czas sprawdzania czy ktoś zna konkretny język. Jest to jednak chyba nadal szybsze od subselecta.
Czekam na odpowiedź w komentarzu, mam zamiar często zaglądać na twojego bloga. Papatki
kwiecień 20th, 2008 at 14:39
Do minusów rozwiązania dodałbym jeszcze:
– ograniczenie pól integer w bazie w przechowywaniu informacji w takiej postaci (np. mamy 100 kategorii=2^100), wtedy trzeba kombinować, dzieląc przechowywanie informacji bitowych na kilka pól (a to później zaczyna się nieco komplikować…),
– nieczytelny zapis w bazie danych, czyli potrzeba “zaszycia” pewnych dodatkowych informacji w aplikacji.
Poza tym polecam to rozwiązanie bo faktycznie jest wydajne 🙂
Świetna strona i równie dobre artykuły, dodam link do swojego nowo powstałego bloga 🙂
kwiecień 20th, 2008 at 19:00
Wykoncypowałem dzisiaj jeszcze coś podobnego i bardziej przejżystego.
Robimy sobie varchara(nie wiem jak to się nazywa na postgresie, używam sybase) o jakiejś sporej długości. W tabeli z nazwami języków id są równe pozycji w tym varcharze. Po za przejżystością otrzymujemy możliwość nadania 256 wariantów dla jednego artybutu – a więc mocno więcej niż prawda/fałsz.
Rozwiązanie nieco bardziej pamięciorzerne, ale wcale nie wolniejsze – jeśli będziemy odwoływać się do konkretnych pól spokojnie zmieścimy się przynajmniej w teorii w długości rozkazu. Nie prowadziłem żadnych statystyk, ale nawet niech to będzie 3s zamiast 1s – wole tak bo jest po prostu łatwiej.
kwiecień 20th, 2008 at 19:23
pamiętaj że varchar ma zmienną długość i przeszukiwanie go jest znacznie wolniejsze niż pól typu integer.
kwiecień 25th, 2008 at 17:45
Takie zapytanie:
select count(*) from usr_table u WHERE age < 50 AND (SELECT count(*) FROM usr_profile_languages_list l WHERE l.usr_profile_languages_id=4 AND l.id=u.id)=1;
Zapisałbym raczej tak:
SELECT count(*) FROM usr_table u WHERE age < 50 AND u.id IN (SELECT l.id FROM usr_profile_languages_list l WHERE l.usr_profile_languages_id=4)
Powinieneś uzyskać znaczy przyrost wydajności. Sprawdź, i daj znać 🙂
maj 3rd, 2008 at 02:10
Witam,
Jak chodzi o tworzenie masek bitowych na dane potencjalnie 1..n, to ja mówię zdecydowanie NIE. Takie rozwiązanie ma piekielnie krótkie nogi, i mści się na swoim pomysłodawcy wraz z pierwszym “rewelacyjnym” pomysłem klienta.
Podzapytanie, czy to w klauzuli IN, czy to jako osobny warunek we WHERE to zasadniczo faktycznie nie najlepsze pomysły. Optymalizatory zapytań mają często problemy z doprowadzaniem ich do naprawdę optymalnej postaci.
Poprawne rozwiązania są dwa:
Część wspólna: prawidłowe poindeksowanie obu tabel (nikt nic nie wspomniał o indeksach na pola o nazwie ‘id’ we _wszystkich_ tabelach), ale oczywiste rzeczy pomijam 🙂
– jeżeli język jest zawsze jeden, zwykły JOIN
SELECT COUNT(*)
FROM usr_table u INNER JOIN
usr_profile_languages_list l ON l.id = u.id
WHERE u.age < 50 AND
l.usr_profile_languages_id = 4
– jeżeli języków jest potencjalnie więcej niż jeden
SELECT COUNT(*)
FROM usr_table u
WHERE u.age < 50 AND
EXISTS
(
SELECT 1
FROM usr_profile_languages_list l
WHERE l.usr_profile_languages_id =4 AND
l.id = u.id
)
A tak w ogóle to poczciwe EXPLAIN czyni cuda, jak chodzi o wyjaśnianie przyczyn wolno wykonujących się zapytań 🙂 Optymalizator to narzędzie nieco bardziej skomplikowane od prostego sprawdzenia, gdzie są indeksy, więc nie mówię, że zaprzyjaźnienie się z tym poleceniem trwa krótko.
Dlaczego EXISTS? W przeważającej większości przypadków optymalizator każe zaprzestać wykonywanie podzapytania z EXISTS po pierwszym odnalezionym rekordzie, czego nie może zrobić w przypadku warunku we WHERE. Może to zrobić w przypadku IN, zgodzę się z przedmówcą – ale wcale nie jest powiedziane, że zawsze tak zrobi.
Testy z użyciem SELECT COUNT(*) nie są zbyt wiarygodne – jak baza inteligentnie zrobiła statystyki, nie musi sięgać do danych źródłowych we wszystkich przypadkach (w szczególności, gdy jest proste zapytanie z wartością jednego pola).
Przy takiej dużej różnicy w czasie wykonania zapytania należałoby popatrzeć na wynik EXPLAIN SELECT [i tam to co po oryginalnym SELECT]. Założę się, że w tym drugim wypadku jest NESTED LOOP ze skanem wewnątrz pętli, a dla zapytań:
– zwracających dużo rekordów powinien być HASH JOIN lub MERGE JOIN
– zwracających mało rekordów powinien być NESTED LOOP z seekiem po indeksie wewnątrz pętli
Pozdrawiam,
Tomasz Kurkiewicz
PS. Gratuluję pomysłu na bloga i jego dotychczasowej realizacji.
maj 3rd, 2008 at 09:51
Niestaty nie zgodze się z Toba poniewaz obojętnie jak bardzo nie zoptymalizujesz zapytania i nie dodasz indexów (bez indexów rozwiazanie z subselect nie miało by żadnych szans zadziałać) to łączenie tabel w podasbytaniu czy jakiekolwiek JOINY będą zawsze dużo wilniejsze niż wyszukiwanie danych z jednej tabeli. Jeżeli robimy to na milionach rekordów a wydajność musi być ogromna to tylko takimi trikami lub cachowaniem zapytań można uzyskać zadowalające wyniki. A co do :rewelacyjnych” pomysłów klienta to ludzie którzy zamawiają tak wydajne rozwiązanie wiedzą przeważnie co robią i tacy klienci mają przeważnie całą specyfikacje tego na co się zdecyduja. Skoro wszystko jest opisane w projekcie to możesz zdecydować czy takie triki wchodzą w gre czy nie. A jażeli klient zamawia portal i twierdzi że będzie tam milion odwiedzin dziennie a nie ma zielonego pojecia o co chodzi to najzwyczejniej daruj sobie takiego klienta bo projekt skonczy sie zle albo bardzo zle 😉
maj 6th, 2008 at 11:00
Troszkę potestowałem, szukając różnych optymalnych rozwiązań. Moje testy opierały się o MySQLu, ale mam nadzieję, że będą jakoś reprezentatywne 😉
Generalnie bardzo dobre wyniki dostałem dla zwykłego złączenia wewnętrznego, natomiast bardzo złe wyniki dostałem dla zapytania z subselectem I dodatkowym ograniczeniem, np:
SELECT COUNT(*) FROM users WHERE
userId IN (SELECT userId FROM users_languages WHERE languageId = 3)
AND
age > 25
Po przerobieniu jednak tego zapytania na taką postać:
SELECT COUNT(*) FROM users WHERE
userId IN (SELECT userId FROM users_languages WHERE languageId = 3)
AND
userId IN (SELECT userId FROM users WHERE age > 25)
wydajność skoczyła wielkrotnie (z ok. 300 sekund na ok. 20, jeśli dobrze pamiętam). Testowana baza miała ok. 900 tys rekordów w tabeli users i 2.7 miliona rekordów w tabeli users_languages.
I jeszcze słowo o podzapytaniach – staram się unikać złączeń z zapytaniem nadrzędnym w podzapytaniach. Podając za “SQL. Sztuka programowania” – taka konstrukcja wymusza na bazie wykonanie podzapytania dla każdego wiersza w potencjalnym zestawie wynikowym. Faroult i Robson zalecają korzystanie z operatora IN, a ja się z nimi zgadzam – doświadczenia prowadzone na MSSQL dały nam olbrzymi wzrost wydajności.
I zupełnie na koniec – klienci zmieniają specyfikację, niestety. I dobrze się dzieje, jeśli robią to przed zakończeniem prac, często, niestety, robią to po zakończeniu pracy. A nie pamiętam sytuacji, w której złamanie postaci normalnej wyszło mi na dobre.
maj 8th, 2008 at 13:46
[…] ostatnio na ciekawy wpis na blogu Krisa, traktujący o problemach związanych z wydajnością SQL subselect w dużych bazach (a […]
maj 8th, 2008 at 13:52
Trochę pogrzebałem, i przetestowałem problem na MySQL i SQL Serverze. Gdyby ktoś był zainteresowany, zapraszam tutaj: http://www.oladesign.biz/2008/05/08/sql-subselect-pare-slow-o-wydajnosci/
lipiec 22nd, 2008 at 16:21
Witam,
Szukałem dziś w necie czegoś innego ale ten blog mnie od tego odwiódł (i całe szczęście!). Blog zatem jest świetny. Co prawda nie jestem żadnym guru jeśli chodzi o PostgreSQL ale tu i tam trochę piszę. Na podstawie własnych doświadczeń muszę zgodzić się z kolegą Kurkiewiczem, że tworzenie masek bitowych potrafi się paskudnie czknąć podczas rozwijania aplikacji. Też natknąłem się na problemy wydajnościowe zapytań do bazy danych i każda ze standardowych metod czy to subselect, czy inner join wieszała mi aplikację na kilka minut. Aż któregoś pięknego dnia poczytałem sobie w man. nieco dokładniej o poleceniu select. Otóż umożliwia ono zapisanie wyniku do tabeli tymczasowej umiejscowionej tylko w ram’ie. Tabela ta egzystuje jedynie podczas danej sesji i jest usuwana po jej zamknięciu (co wcale nie oznacza zamknięcia połączenia z DB). Po prostu kolejny command do DB to już inna sesja. Co prawda taka metoda potrafi pochłaniać spore ilości ram’u ale dziś to już nie jest zbyt wielki problem a wydajność kilkakrotnie się zwiększa w stosunku do operacji na fizycznych tabelach. Zakładając, że baza jest dobrze poindeksowana można pokusić się o coś takiego:
— zapytanie zapisane do tabeli tymczasowej:
SELECT id, COUNT(id) as licznik INTO TEMP tmplanguages_FROM usr_profile_languages_list WHERE usr_profile_languages_id = 4 GROUP BY id;
— zapytanie właściwe
SELECT COUNT(m.id) FROM usr_table m INNER JOIN tmplanguages s ON m.id=s.id WHERE m.age<50 AND s.licznik=1;
Postgres ma dobrze zoptymalizowane funkcje agregacji – niektórzy twierdzą (a sam się do nich zaliczam), że znacznie lepiej niż uznawany za szybszy MySQL. Podany przykład to żadne tam mistrzostwo świata ale w niektórych sytuacjach potrafi naprawdę pomóc. Można go użyć np. do NpgsqlCommand’a jako CommandString i wykonać na czymś takim np ExecuteScalar.
Pozdrawiam
Maciej Budzynowski
PS. Tekst pisany w pośpiechu za wszelkie błędy przepraszam.