Optymalizacja zapytań z podzapytaniami

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ń dzięki 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, iż tworzymy system, którego jednym z zadań jest zapisywanie informacji o aktywności użytkowników umieszczających pliki na serwerze. dla wszystkich zarejestrowanego użytkownika, chcemy wiedzieć, kiedy i jaki plik umieścił. Schemat bazy danych dla tej funkcjonalności wygląda następująco: 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") 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) Tabela test_user 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 test_upload. Powiedzmy, iż 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: 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; 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: 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; 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: 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: CREATE INDEX upload_user_id_idx ON test_upload(user_id); Ta prosta zmiana spowodowała, iż czas zapytania skrócił się do ok 0,6 sekundy: W tym artykule jednak chcieliśmy przedstawić inną technikę optymalizacji podzapytań: poprzez ich eliminację. Wiadomo, iż podzapytanie, którego nie ma, nie potrzebuje czasu. Zależy nam jednak na tym, aby eliminując podzapytanie, całość była przez cały czas poprawna, tj. zwracała adekwatne 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, iż 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żeli nie mamy tego szczęścia ich używać, musimy poradzić sobie sami. W pierwszej kolejności usuńmy niepotrzebny już indeks upload_user_id_idx. Następnie wykonajmy zapytanie: SELECT user_id, max(upload_time) FROM test_upload GROUP BY user_id; 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ć: 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; Czas wykonania tego zapytania wyniósł 167 ms, czyli wyeliminowanie podzapytania zapewniło prawie 4-krotne przyspieszenie: Testy przeprowadziliśmy na małym zbiorze danych, który całkowicie mieścił się w pamięci. Co się stanie jednak, jeżeli 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, iż 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 w 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, iż 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ę, iż nigdy nie zostanie dołączony więcej niż jeden rekord (w naszym przypadku poprzez proste spostrzeżenie, iż 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ł.