Optymalizacja zapytań z podzapytaniami
Author
Piotr Kolaczkowski
blog_date_icon
2 marca

Współczesne systemy relacyjnych baz danych, również te z otwartym kodem źródłowym, umożliwiają tworzenie bardzo złożonych zapytań SQL. Poprzez umieszczanie podzapytań w sekcji SELECT, FROM oraz WHERE, jak również przez łączenie zapytań za pomocą operatorów takich jak UNION czy INTERSECT, nie trudno napisać zapytanie, które nie zmieści się na monitorze. Ta elastyczność ma niestety swoją cenę: analiza takiego złożonego zapytania jest nie lada wyzwaniem dla silnika bazy danych i, jak pokazuje praktyka, niektóre systemy baz danych nie najlepiej sobie z tym radzą. Najprościej wytłumaczyć to na przykładzie, wzorowanym na prawdziwym przypadku.

Wyobraźmy sobie, że tworzymy system, którego jednym z zadań jest zapisywanie informacji o aktywności użytkowników umieszczających pliki na serwerze. Dla każdego zarejestrowanego użytkownika, chcemy wiedzieć, kiedy i jaki plik umieścił. Schemat bazy danych dla tej funkcjonalności wygląda następująco:

<pre> Table "public.test_user" Column | Type | Modifiers -----------------+-----------------------+----------- user_id | integer | not null name | character varying(64) | not null login | character varying(16) | not null hashed_password | character varying(32) | not null Indexes: "test_user_pkey" PRIMARY KEY, btree (user_id) "test_user_login_key" UNIQUE, btree ("login") </pre> <pre> Table "public.test_upload" Column | Type | Modifiers -------------+------------------------+----------- upload_id | integer | not null user_id | integer | not null path | character varying(255) | not null upload_time | timestamp | not null Indexes: "test_upload_pkey" PRIMARY KEY, btree (upload_id) Foreign-key constraints: "test_upload_user_id_fkey" FOREIGN KEY (user_id) REFERENCES test_user(user_id) </pre>

Tabela <i>test_user</i> zawiera ok. 10 tys. użytkowników. Jeden użytkownik średnio umieścił na serwerze 5 plików, choć są oczywiście tacy, którzy nie umieścili ani jednego, jak i tacy, którzy umieścili ich kilkaset. Każdemu umieszczonemu plikowi odpowiada jeden rekord w tabeli <i>test_upload</i>.

Powiedzmy, że nasz przykładowy serwis potrzebuje wyświetlić 10 różnych użytkowników, którzy dodawali ostatnio jakieś pliki. Użytkownik, który dodał plik najdawniej, ma znaleźć się na końcu listy, użytkownik, którego plik jest "najświeższy" - na samym początku. Jednak żaden użytkownik nie powinien znaleźć się na liście "top 10" więcej niż raz.

Pierwsze podejście do tego zapytania mogłoby wyglądać następująco:

<pre> SELECT name, path, upload_time FROM test_user u JOIN test_upload l ON (u.user_id = l.user_id) ORDER BY upload_time DESC LIMIT 10; </pre>

Niestety, zapytanie, choć faktycznie wyświetla ostatnio dodane pliki, niezupełnie robi to, czego oczekujemy - jeden użytkownik może wystąpić więcej niż raz na liście. Z pomocą przychodzi dodatkowy warunek, który wyeliminuje starsze wpisy dla tego samego użytkownika:

<pre> SELECT name, path, upload_time FROM test_user u JOIN test_upload l ON (u.user_id = l.user_id) WHERE upload_time = (SELECT max(upload_time) FROM test_upload WHERE user_id = u.user_id) ORDER BY upload_time DESC LIMIT 10; </pre>

Teraz zapytanie już działa poprawnie, ale w zależności od systemu baz danych, na którym pracujemy, mogliśmy wprowadzić inny poważny problem: zapytanie będzie się wykonywać dużo wolniej. Na naszym systemie testowym opartym o PostgreSQL 8.2 pierwsza (niepoprawna) wersja wykonywała się 200 ms. Tymczasem wersja "poprawiona", wykonywała się nieco ponad 10 minut, czyli ok. 3 tys. razy wolniej. Przyczynę tej powolności pokazuje wynik EXPLAIN:

<div style="width: 580px; overflow: auto;> <pre class="noborder"> QUERY PLAN ----------------------------------------------------------------------------------------------------------------------------------------------- Limit (cost=50967080.34..50967080.36 rows=10 width=40) (actual time=617733.543..617733.554 rows=10 loops=1) -> Sort (cost=50967080.34..50967080.52 rows=75 width=40) (actual time=617733.542..617733.548 rows=10 loops=1) Sort Key: l.upload_date -> Nested Loop (cost=0.00..50967078.00 rows=75 width=40) (actual time=16.545..617691.016 rows=9967 loops=1) Join Filter: (l.upload_date = (subplan)) -> Seq Scan on test_upload l (cost=0.00..894.00 rows=50000 width=28) (actual time=0.012..41.359 rows=50000 loops=1) -> Index Scan using test_user_pkey on test_user u (cost=0.00..0.28 rows=1 width=20) (actual time=0.009..0.011 rows=1 loops=50000) Index Cond: (u.user_id = l.user_id) SubPlan -> Aggregate (cost=1019.02..1019.03 rows=1 width=4) (actual time=12.333..12.333 rows=1 loops=50000) -> Seq Scan on test_upload (cost=0.00..1019.00 rows=6 width=4) (actual time=1.967..12.323 rows=6 loops=50000) Filter: (user_id = $0) Total runtime: 617733.733 ms </pre> </div>

Po pierwsze, podzapytanie jest wykonywane dosyć nieoptymalnie - skanowana jest cała tabela, aby znaleźć pliki jednego użytkownika. Po drugie, podzapytanie jest wykonywane 50000 razy, raz na każdy rekord analizowany w głównym zapytaniu. Z pierwszym problemem można sobie poradzić przez dodanie odpowiedniego indeksu:

<pre> CREATE INDEX upload_user_id_idx ON test_upload(user_id); </pre>

Ta prosta zmiana spowodowała, że czas zapytania skrócił się do ok 0,6 sekundy:

<div style="width: 580px; overflow: auto;> <pre class="noborder"> QUERY PLAN ----------------------------------------------------------------------------------------------------------------------------------------------------------------- Limit (cost=422099.29..422099.31 rows=10 width=40) (actual time=614.207..614.214 rows=10 loops=1) -> Sort (cost=422099.29..422099.47 rows=74 width=40) (actual time=614.205..614.208 rows=10 loops=1) Sort Key: l.upload_time -> Merge Join (cost=0.00..422096.99 rows=74 width=40) (actual time=0.071..602.762 rows=9967 loops=1) Merge Cond: (u.user_id = l.user_id) Join Filter: (l.upload_time = (subplan)) -> Index Scan using test_user_pkey on test_user u (cost=0.00..378.25 rows=10000 width=20) (actual time=0.021..5.243 rows=10000 loops=1) -> Index Scan using upload_user_id_idx on test_upload l (cost=0.00..1595.25 rows=50000 width=28) (actual time=0.014..24.648 rows=50000 loops=1) SubPlan -> Aggregate (cost=8.38..8.39 rows=1 width=4) (actual time=0.009..0.009 rows=1 loops=50000) -> Index Scan using upload_user_id_idx on test_upload (cost=0.00..8.36 rows=6 width=4) (actual time=0.003..0.006 rows=6 loops=50000) Index Cond: (user_id = $0) Total runtime: 614.338 ms </pre> </div>

W tym artykule jednak chcieliśmy przedstawić inną technikę optymalizacji podzapytań: poprzez ich eliminację. Wiadomo, że podzapytanie, którego nie ma, nie potrzebuje czasu. Zależy nam jednak na tym, aby eliminując podzapytanie, całość była nadal poprawna, tj. zwracała właściwe wyniki, czyli musimy je czymś zastąpić. Kluczem do zastosowania tej techniki jest zamiana podzapytania na złączenie. Złączenia są łatwiejsze dla systemu do obliczenia chociażby z tego względu, że istnieją różne algorytmy realizacji złączeń i optymalizator ma tutaj większe "pole do popisu". Poza tym hurtowy dostęp do dużej tabeli jest zwykle tańszy niż tysiące małych, prostych dostępów wybierających po kilka rekordów.

Wiele silników baz danych potrafi wykonać takie przekształcenie automatycznie dla podzapytań nieskorelowanych, jednak w tym przypadku mamy do czynienia z podzapytaniem skorelowanym, ponieważ odwołuje się ono do zapytania otaczającego. Komercyjne systemy baz danych poradziłyby sobie i z tym przypadkiem, ale jeśli nie mamy tego szczęścia ich używać, musimy poradzić sobie sami.

W pierwszej kolejności usuńmy niepotrzebny już indeks <i>upload_user_id_idx</i>. Następnie wykonajmy zapytanie:

<pre> SELECT user_id, max(upload_time) FROM test_upload GROUP BY user_id; </pre>

Wykonuje się jedynie 63 ms i zawiera wszystkie potrzebne dane do sprawdzenia, czy dany plik użytkownika jest tym "ostatnim" i powinien być uwzględniony w wyniku. Teraz tylko trzeba to zapytanie połączyć z pełną zawartością tabeli z użytkownikami i plikami, i na końcu odpowiednio posortować:

<pre> SELECT name, path, upload_time FROM test_user u JOIN test_upload l ON (u.user_id = l.user_id) JOIN ( SELECT user_id, max(upload_time) AS ud FROM test_upload GROUP BY user_id ) x ON (x.user_id = l.user_id AND l.upload_time = ud) ORDER BY upload_time DESC LIMIT 10; </pre>

Czas wykonania tego zapytania wyniósł 167 ms, czyli wyeliminowanie podzapytania zapewniło prawie 4-krotne przyspieszenie:

<div style="width: 580px; overflow: auto;> <pre class="noborder"> QUERY PLAN ---------------------------------------------------------------------------------------------------------------------------------------------------- Limit (cost=4324.97..4324.99 rows=10 width=40) (actual time=166.005..166.011 rows=10 loops=1) -> Sort (cost=4324.97..4325.13 rows=66 width=40) (actual time=166.003..166.004 rows=10 loops=1) Sort Key: l.upload_date -> Hash Join (cost=2053.31..4322.97 rows=66 width=40) (actual time=93.562..155.832 rows=9967 loops=1) Hash Cond: ((l.user_id = u.user_id) AND (l.upload_date = x.ud)) -> Seq Scan on test_upload l (cost=0.00..894.00 rows=50000 width=28) (actual time=0.010..18.370 rows=50000 loops=1) -> Hash (cost=1920.04..1920.04 rows=8885 width=28) (actual time=93.524..93.524 rows=9922 loops=1) -> Hash Join (cost=1498.00..1920.04 rows=8885 width=28) (actual time=68.164..86.451 rows=9922 loops=1) Hash Cond: (x.user_id = u.user_id) -> HashAggregate (cost=1144.00..1255.06 rows=8885 width=8) (actual time=52.218..57.378 rows=9922 loops=1) -> Seq Scan on test_upload (cost=0.00..894.00 rows=50000 width=8) (actual time=0.008..18.568 rows=50000 loops=1) -> Hash (cost=229.00..229.00 rows=10000 width=20) (actual time=15.925..15.925 rows=10000 loops=1) -> Seq Scan on test_user u (cost=0.00..229.00 rows=10000 width=20) (actual time=0.007..5.835 rows=10000 loops=1) Total runtime: 166.287 ms </pre> </div>

Testy przeprowadziliśmy na małym zbiorze danych, który całkowicie mieścił się w pamięci. Co się stanie jednak, jeśli zwiększymy ilość danych? Aby to sprawdzić, wygenerowaliśmy drugi, duży zbiór danych tak, by tabela użytkowników zawierała 500 tys. rekordów, a tabela z dodanymi plikami - 10 mln. Tym razem wersja z podzapytaniem wykorzystującym indeks na test_upload(user_id) wykonywała się ponad 30 minut i musieliśmy przerwać test. Natomiast wersja bez podzapytania skorelowanego zajęła 44 sekundy. Z kolei stosunek kosztów obu zapytań oszacowany przez optymalizator PostgreSQL wyniósł ok. 1600:1. Różnice są dlatego tak znaczne, że tym razem dane nie mieszczą się w całości w pamięci i każdorazowe wykonanie podzapytania wymagało fizycznego dostępu do przypadkowego miejsca dysku. Tymczasem w drugim przypadku rekordy są pobierane sekwencyjnie i nie traci się czasu na pozycjonowanie głowic dysku. Wersji z podzapytaniem bez indeksu nie sprawdzaliśmy na tym zbiorze danych. Gdybyśmy to zrobili, prawdopodobnie datę publikacji tego artykułu należałoby przesunąć o rok.

Jak widać, użycie złączenia i podzapytania nieskorelowanego we FROM zamiast podzapytania skorelowanego w WHERE może zapewnić duże zyski wydajności. Należy jednak pamiętać też o zagrożeniach jakie niesie ta technika. Przede wszystkim zmieniając postać zapytania, ryzykujemy, że nowe zapytanie nie będzie równoważne oryginałowi. W wielu przypadkach zamiana może wydawać się mechaniczna, ale należy bardzo uważać, żeby dodając kolejne złączenie nie wprowadzić duplikatów rekordów. Złączenia, w przeciwieństwie do zastosowania operatorów EXISTS, IN czy '=' w sekcji WHERE, mogą nie tylko eliminować rekordy, ale również je powielać. Problem ten rozwiązuje się zwykle przez upewnienie się, że nigdy nie zostanie dołączony więcej niż jeden rekord (w naszym przypadku poprzez proste spostrzeżenie, że user_id jest unikalne), albo przez dodanie słowa DISTINCT, tak aby ewentualne duplikaty usunąć na końcu. Drugim zagrożeniem jest próba stosowania tej techniki zawsze i wszędzie, gdzie się tylko da. A niestety nie zawsze daje ona zyski w wydajności. Prezentowane zapytanie udało się nam przyspieszyć do 0,4 ms na małym zbiorze danych i 1 s na zbiorze dużym. Jak? To już temat na osobny artykuł.

Przeczytaj także