Poniższy artykuł dotyczy zagadnienia planowania wykonania zapytania w bazie danych PostgreSQL. Prezentowane jest tu podejście praktyczne a wszystkie przykłady zostały wykonane na Postgresie w wersji 8.1. Inspiracją do napisania artykułu był rozdział "Performance" znakomitej książki "A comprehensive guide to building, programming and administering PostgreSQL databases" oraz zadziwiająco mała ilość informacji jakie dla Postgresa można w tej materii znaleźć w internecie.
1. Krótko o postgresowym planie wykonania zapytania
Planista tworzy drzewo wykonania zapytania w oparciu o operatory. Każdy operator pobiera dane (input set), przekształca je w zależności od swojego przeznaczenia (w result set) i zwraca do operatora będącego wyżej w drzewie planu wykonania. Planista korzystając z dostępnych operatorów tworzy kilka planów, szacuje ich koszt i wybiera ten o najniższym koszcie.
Do najważniejszych operatorów PostgreSQLa należą:
- Seq Scan – czyta całą tabelę od początku do końca, odrzuca wiersze nie spełniające warunków w WHERE, planista wybiera Seq Scan kiedy brakuje indeksów, lub oszacowany koszt pełnego wczytania tabeli jest mniejszy niż koszt wczytania z użyciem indeksów.
- Index Scan – używa indeksów do wczytywania tabeli, zwraca dane w porządku indeksu, może nie czytać każdego wiersza jeśli zdefiniujemy zakres wartości dla zindeksowanej kolumny, PostgreSQL obsługuje indeksy B-Tree (zakładane domyślnie), Hash, R-Tree, GiST.
- Sort – zwraca posortowany zbiór wierszy, zapewnia obsługę ORDER BY, używany przez wiele innych operatorów.
- Unique - usuwa zduplikowane wartości. Jego input set musi być posortowany, implementuje operację UNIQUE.
- Aggregate – używany gdy w zapytaniu występują funkcje agregujące, czyta wszystkie wiersze w input set, oblicza i zwraca wartość agregatu. Jeśli input set jest pogrupowany zwraca wartości agregatu w poszczególnych grupach.
- Append - używany do implementacji operacji UNION, zwraca wszystkie wiersze z pierwszego input set'a, następnie wszystkie z drugiego input set'a itd.
- Nested Loop – wykonuje iteracyjne złączenie dwóch tabel, pobiera na wejściu dwa zbiory wierszy, dla każdego wiersza z jednego zbioru ( outer table ) szuka wiersza w drugim zbiorze ( inner table ) pasującego do warunku złączenia.
- Merge Join – łączy przez scalanie dwie tabele, na wejściu wymaga dwóch posortowanych po kolumnie złączenia zbiorów wierszy (tabele outer, inner).
- Hash Join – wykonuje łączenie hashowane, używa operatora Hash do utworzenia tymczasowego indeksu hashowanego na kolumnie złączenia w inner table.
- GroupAggregate - zapewnienia obsługę klauzuli GROUP BY, na wejściu wymaga posortowany względem kolumny grupowania zbiór wierszy, koniec każdej grupy zaznacza zerowym wierszem.
- Subplan - używany w podselekcjach, skanuje input set i umieszcza wiersze spełniające warunki w result set.
- Setop Intersect, Setop Except – zapewniają obsługę klauzul INTERSECT, EXCEPT.
- Bitmap Heap Scan - składa się z dwóch faz, pierwsza Bitmap Index Scan używa dostępnego indeksu (lub indeksów - możliwe wykorzystanie kilku naraz w zależności od decyzji planisty i warunków w WHERE) do utworzenia bitmapy (in-memory) reprezentującej tuple spełniające dane warunki. Właściwe zadanie operacji Bitmap Heap Scan to pobranie i zwrócenie pasujących tupli ( tuple z 1 w bitmapie ).
2. Instrukcja EXPLAIN
Instrukcja wyświetla plan wykonania zapytania wybrany przez planistę PostgreSQLa, może być użyta do analizy operacji SELECT, INSERT, DELETE, UPDATE, DECLARE, CURSOR.
Składnia:
EXPLAIN [ANALYZE][VERBOSE] query;Użycie parametru ANALYZE spowoduje wykonanie zapytania i wyświetli jego rzeczywisty koszt.
Przykład:
db1=> EXPLAIN ANALYZE select * from emp;Planista zdecydował o wykonaniu operacji skanu sekwencyjnego (Seq Scan) na tabeli emp. Parametr cost=0.00..155.00 jest oszacowaniem kosztów operacji Seq Scan, pierwsza liczba pokazuje jak szybko może być zwrócony pierwszy wiersz rezultatu, druga jest oszacowaniem kosztu całej operacji. rows=10000 pokazuje jak dużo wierszy zostanie zwróconych przez operację, width=12 określa średnią długość wiersza w zbiorze wynikowym (w bajtach). Parametry actual time, rows, loops, Total runtime podają rzeczywiste koszty wykonania operacji i są wyświetlane tylko gdy użyjemy parametru ANALYZE.
QUERY PLAN
---------------------------------------------------------------------------------------------------------
Seq Scan on emp (cost=0.00..155.00 rows=10000 width=12) (actual time=9.727..31.449 rows=10000 loops=1)
Total runtime: 34.349 ms
(2 rows)
3. Przygotowanie testowych danych
Zanim przystąpimy do analizy planów wykonania zapytań utworzymy tabele: EMP( empno, deptno, sal), DEPT( deptno, mgrno ), MANAGER( mgrno, sal ) z testowymi danymi:
db1=> create table EMP( empno integer PRIMARY KEY, deptno integer, sal integer );Dla powyższych tabel PostgreSQL automatycznie generuje indeksy na kluczach głównych ( w postaci B drzew ).
db1=> create table MANAGER( mgrno integer PRIMARY KEY, sal integer );
db1=> create table DEPT( deptno integer PRIMARY KEY, mgrno integer );
Utworzymy też proste relacje:
db1=> alter table EMP add foreign key(deptno) references DEPT;Tworzymy 30 menedżerów o losowym wynagrodzeniu:
db1=> alter table DEPT add foreign key(mgrno) references MANAGER;
db1=> create sequence mgr_seq start 1 increment 1 no maxvalue;Tworzymy 20 oddziałów o losowych menedżerach:
db1=> insert into manager select nextval('mgr_seq'), dround(random()*100+100) from generate_series(1,30);
db1=> create sequence dept_seq start 1 increment 1 no maxvalue;Tworzymy 10000 pracownikow:
db1=> insert into dept select nextval('dept_seq'), dround(random()*29+1) from generate_series(1,20);
db1=> create sequence emp_seq start 1 increment 1 no maxvalue;Planista PostgreSQL'a intensywnie korzysta z tabel systemowych, w których znajdują się metadane i statystyki dla każdej tabeli w bazie. Najważniejsze tabele to pg_class i pg_statistic. Statystyki nie są automatycznie aktualizowane dlatego okresowo należy je odświeżyć poleceniem ANALYZE. Zaleca się również używanie komendy VACUUM, która oczyszcza tabelę z niewidzialnych tupli zmniejszających wydajność operacji I/O. Zanim więc przystąpimy do właściwych działań wykonamy następujące instrukcje:
db1=> insert into emp select nextval('emp_seq'), dround(random()*19+1), dround(random()*50+50) from generate_series(1,10000);
db1=> ANALYZE emp;
db1=> VACUUM emp;
4. Przykładowe plany wykonania
Znając podstawy działania planisty PostgreSQLowego spróbujemy teraz przewidzieć wybrany przez niego plan wykonania dla kilku prostych operacji na utworzonych właśnie tabelach.
Seq Scan vs B-Tree Index Scan
Jeśli zapytanie posiada warunki selekcji, PostgreSQL wykorzysta utworzone indeksy do wczytania ograniczonego zbioru wyników. Indeksy dzięki swoim właściwościom wykorzystywane są również przy sortowaniu danych i wybieraniu danych unikalnych. Jeśli wiersze danej kolumny nie zostały zindeksowane lub brak warunków selekcji PostgreSQL czyta każdy wiersz tabeli od początku do końca (Seq Scan). Planista wybiera Seq Scan również w sytuacji kiedy nie opłaca się stosować indeksów tj. przy wczytywaniu dużego zbioru wierszy, kieruje się tu regułą, że kompletny index scan na całej tabeli jest bardziej kosztowny niż full scan. Wczytamy więc duży zbiór wierszy, prawdopodobnie zostanie użyty Seq Scan:
db1=> explain analyze select * from emp where empno < 8000;Wczytamy teraz mały zbiór wierszy z określonego zakresu wartości, powinien zostać użyty index scan:
QUERY PLAN
-------------------------------------------------------------------------------------------------------
Seq Scan on emp (cost=0.00..180.00 rows=8065 width=12) (actual time=0.024..19.278 rows=7999 loops=1)
Filter: (empno < 8000)
Total runtime: 21.799 ms
(3 rows)
db1=> explain analyze select empno from emp where empno > 4500 and empno < 5500;
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------
Index Scan using emp_pkey on emp (cost=0.00..15.89 rows=493 width=4) (actual time=0.202..1.620 rows=999 loops=1)
Index Cond: ((empno > 4500) AND (empno < 5500))
Total runtime: 1.987 ms
(3 rows)
Chcemy malejąco posortować wiersze, planista zapewne użyje indeksów oraz operacji odwrócenia porządku:
db1=> explain analyze select empno from emp order by empno desc;
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------
Index Scan Backward using emp_pkey on emp (cost=0.00..228.00 rows=10000 width=4) (actual time=0.033..16.763 rows=10000 loops=1)
Total runtime: 19.448 ms
(2 rows)
Wybieramy dane unikalne, zostanie użyty operator Unique, wymaga on na wejściu posortowanego zbioru wierszy, który od razu może być zwrócony przez Index Scan:
db1=> explain analyze select distinct empno from emp;
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------
Unique (cost=0.00..253.00 rows=10000 width=4) (actual time=0.103..30.502 rows=10000 loops=1)
-> Index Scan using emp_pkey on emp (cost=0.00..228.00 rows=10000 width=4) (actual time=0.097..14.767 rows=10000 loops=1)
Total runtime: 33.518 ms
(3 rows)
BTREE Index vs HASH Index
Przy selekcji danych w oparciu o warunek równości teoretycznie najlepiej spisują się indeksy hashowane, jednak nie pozwalają one na uniknięcie operacji sortowania wymuszanej przez ORDER BY a przy wyszukiwaniu danych w określonym zakresie wartości wymagają przejrzenia każdego kubełka. Do tego typu zadań lepiej nadają się indeksy w postaci B drzew. Planista mając do dyspozycji indeksy BTREE i HASH napotykając na operatory <, <=, >=, > zawsze wybierze indeks w postaci B-drzewa.
Aby sprawdzić czy rzeczywiście tak jest utworzymy indeksy B-Tree i HASH na kolumnie sal tabeli EMP:
db1=> create index emp_sal_hash on emp using hash (sal);Szukamy pracownika, który zarabia 100, prawdopodobnie zostanie wykorzystany indeks hashowany:
db1=> create index emp_sal_btree on emp(sal);
db1=> explain analyze select * from emp where emp.sal=100;Plan niezgodny z oczekiwanym- PostgreSQL użył indeksu w postaci B drzewa, wybór prawdopodobnie podyktowany dużym kosztem utworzenia tymczasowego indeksu hashowanego oraz nieefektywną wymianą stron w pamięci cache przy obsłudze indeksów hashowanych.
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on emp (cost=2.68..60.12 rows=195 width=12) (actual time=0.111..0.248 rows=89 loops=1)
Recheck Cond: (sal = 100)
-> Bitmap Index Scan on emp_sal_btree (cost=0.00..2.68 rows=195 width=0) (actual time=0.085..0.085 rows=89 loops=1)
Index Cond: (sal = 100)
Total runtime: 0.394 ms
(5 rows)
Usuniemy teraz index w postaci B-drzewa i sprawdzimy koszt tego zapytania z wykorzystaniem indeksu hashowanego:
db1=> drop index emp_sal_btree;Widać, że rzeczywisty koszt tego zapytania jest większy niż w przypadku indeksu w postaci B drzewa ( 0.423ms > 0.394 ms ).
db1=> explain analyze select * from emp where emp.sal = 100;
QUERY PLAN
------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on emp (cost=2.68..60.12 rows=195 width=12) (actual time=0.166..0.296 rows=89 loops=1)
Recheck Cond: (sal = 100)
-> Bitmap Index Scan on emp_sal_hash (cost=0.00..2.68 rows=195 width=0) (actual time=0.141..0.141 rows=89 loops=1)
Index Cond: (sal = 100)
Total runtime: 0.423 ms
(5 rows)
Policzmy teraz pracowników którzy zarabiają mniej niż 75, na kolumnie sal zdefiniowany jest tylko indeks hashowany zatem prawdopodobnie zostanie użyty Seq Scan, który wczyta i przekaże wiersze 'wyżej' do operatora Aggregate:
db1=> explain analyze select count(*) from emp where sal<75;
QUERY PLAN
------------------------------------------------------------------------------------------------------------
Aggregate (cost=192.83..192.84 rows=1 width=0) (actual time=17.179..17.180 rows=1 loops=1)
-> Seq Scan on emp (cost=0.00..180.00 rows=5132 width=0) (actual time=0.024..15.182 rows=4969 loops=1)
Filter: (sal < 75)
Total runtime: 17.277 ms
(4 rows)
Policzmy pracowników, którzy zarabiają tyle samo, planista prawdopodobnie wczyta sekwencyjnie całą tabelę (Seq Scan), posortuje zbiór wierszy (Sort) i przekaże do operatora GroupAggregate, który dokona właściwego pogrupowania danych:
db1=> explain analyze select sal, count(*) from emp group by sal;W tym przypadku sortowanie musi być zbyt kosztowne, planista zdecydował się na grupowanie z użyciem funkcji hashującej.
QUERY PLAN
-------------------------------------------------------------------------------------------------------------
HashAggregate (cost=205.00..205.64 rows=51 width=4) (actual time=18.906..18.949 rows=51 loops=1)
-> Seq Scan on emp (cost=0.00..155.00 rows=10000 width=4) (actual time=0.015..7.498 rows=10000 loops=1)
Total runtime: 19.075 ms
(3 rows)
Wyszukamy pracowników i menedżerów, którzy mają te same numery, prawdopodobnie zostaną wykonane dwie operacje Seq Scan na tabelach emp i manager, zbiory wierszy zwrócone przez Seq Scan'y muszą być połączone i posortowane spodziewamy się więc operacji Append a następnie Sort, na koniec operator SetOp Intersect wybierze ze zbioru powtarzające się wiersze w obu tabelach:
db1=> explain select empno from emp intersect select mgrno from manager;
QUERY PLAN
--------------------------------------------------------------------------------------
SetOp Intersect (cost=923.20..973.35 rows=1003 width=4)
-> Sort (cost=923.20..948.27 rows=10030 width=4)
Sort Key: empno
-> Append (cost=0.00..256.60 rows=10030 width=4)
-> Subquery Scan "*SELECT* 1" (cost=0.00..255.00 rows=10000 width=4)
-> Seq Scan on emp (cost=0.00..155.00 rows=10000 width=4)
-> Subquery Scan "*SELECT* 2" (cost=0.00..1.60 rows=30 width=4)
-> Seq Scan on manager (cost=0.00..1.30 rows=30 width=4)
(8 rows)
Złączenia
Złączenia tabel najwydajniej wykonuje Hash Join, jednak kiedy tabele są posortowane po kolumnie złączenia najlepszym wyborem będzie Merge Join. Generalnie najmniej wydajną jest strategia złączenia interacyjnego- Nested Loop, planista rozważy tą strategię kiedy jedna z tabel będzie miała bardzo małą liczbę wierszy.
Połączymy tabele emp i dept względem kolumny deptno. Kolumna emp.deptno jest nieuporządkowana, planista wybierając strategię Merge Join musiałby umieścić w drzewie wykonania również operację Sort, która jest dość kosztowna na tabeli emp. Najprawdopobniej zostanie wybrana strategia Hash Join, czytamy całe tabele więc zostaną wykonane operacje Seq Scan:
db1=> explain select * from emp join dept on (emp.deptno=dept.deptno);Założymy indeks na kolumnie deptno tabeli emp:
QUERY PLAN
-----------------------------------------------------------------
Hash Join (cost=1.25..306.25 rows=10000 width=20)
Hash Cond: ("outer".deptno = "inner".deptno)
-> Seq Scan on emp (cost=0.00..155.00 rows=10000 width=12)
-> Hash (cost=1.20..1.20 rows=20 width=8)
-> Seq Scan on dept (cost=0.00..1.20 rows=20 width=8)
(5 rows)
db1=> create index emp_deptno on emp(deptno);Wykonajmy ponownie poprzednie zapytanie, planista powinien użyć indeksu na emp.deptno i zastosować Merge Join:
db1=> explain select * from emp join dept on (emp.deptno=dept.deptno);I w tym przypadku Hash Join okazał się mniej kosztowny.
QUERY PLAN
-----------------------------------------------------------------
Hash Join (cost=1.25..306.25 rows=10000 width=20)
Hash Cond: ("outer".deptno = "inner".deptno)
-> Seq Scan on emp (cost=0.00..155.00 rows=10000 width=12)
-> Hash (cost=1.20..1.20 rows=20 width=8)
-> Seq Scan on dept (cost=0.00..1.20 rows=20 width=8)
(5 rows)
Sprawdźmy jaki plan wykonania zostanie wygenerowany dla małych tabel, prawdopodobnie ze względu na nieuporządkowanie kolumny dept.mgrno będzie to znowu HashJoin:
db1=> explain select * from dept join manager on (dept.mgrno=manager.mgrno);Wykonamy złączenie zewnętrzne prawostronne tabel manager i dept względem kolumny mgrno, plan wykonania nie powinien się zbytnio różnić od poprzedniego:
QUERY PLAN
-----------------------------------------------------------------
Hash Join (cost=1.25..3.05 rows=20 width=16)
Hash Cond: ("outer".mgrno = "inner".mgrno)
-> Seq Scan on manager (cost=0.00..1.30 rows=30 width=8)
-> Hash (cost=1.20..1.20 rows=20 width=8)
-> Seq Scan on dept (cost=0.00..1.20 rows=20 width=8)
(5 rows)
db1=> explain select * from dept right join manager on (dept.mgrno=manager.mgrno);Połączymy dwie tabele względem posortowanych kolumn, prawdopodobnie zostanie użyty Merge Join oraz indeksy zdefiniowane na kluczach gównych:
QUERY PLAN
-----------------------------------------------------------------
Hash Left Join (cost=1.25..3.05 rows=30 width=16)
Hash Cond: ("outer".mgrno = "inner".mgrno)
-> Seq Scan on manager (cost=0.00..1.30 rows=30 width=8)
-> Hash (cost=1.20..1.20 rows=20 width=8)
-> Seq Scan on dept (cost=0.00..1.20 rows=20 width=8)
(5 rows)
db1=> explain select * from emp join manager on (emp.empno=manager.mgrno);Połączymy tabele emp, manager i dept wyszukując dla każdego pracownika jego menedżera. Prawdpodobnie planista aby zredukować koszty użyje reguł optymalizacji i złączy ze sobą najpierw tabele dept i manager. Wcześniej skorzysta prawdopodobnie ze strategii złączenia hashowanego i wykona Seq Scan na każdej tabeli:
QUERY PLAN
---------------------------------------------------------------------------------
Merge Join (cost=2.04..3.14 rows=30 width=20)
Merge Cond: ("outer".empno = "inner".mgrno)
-> Index Scan using emp_pkey on emp (cost=0.00..228.00 rows=10000 width=12)
-> Sort (cost=2.04..2.11 rows=30 width=8)
Sort Key: manager.mgrno
-> Seq Scan on manager (cost=0.00..1.30 rows=30 width=8)
(6 rows)
db1=> explain select emp.empno, manager.mgrno from emp join dept on (emp.deptno=dept.deptno) join manager on (dept.mgrno=manager.mgrno);
QUERY PLAN
-----------------------------------------------------------------------------
Hash Join (cost=3.10..308.10 rows=10000 width=8)
Hash Cond: ("outer".deptno = "inner".deptno)
-> Seq Scan on emp (cost=0.00..155.00 rows=10000 width=8)
-> Hash (cost=3.05..3.05 rows=20 width=8)
-> Hash Join (cost=1.25..3.05 rows=20 width=8)
Hash Cond: ("outer".mgrno = "inner".mgrno)
-> Seq Scan on manager (cost=0.00..1.30 rows=30 width=4)
-> Hash (cost=1.20..1.20 rows=20 width=8)
-> Seq Scan on dept (cost=0.00..1.20 rows=20 width=8)
(9 rows)
Podzapytania
Wyszukamy pracowników którzy zarabiają więcej niż najmniej zarabiający menedżer. Planista musi obliczyć wartość agregatu min, wczyta więc całą tabelę manager korzystając z Seq Scan i użyje operatora Aggregate, aby uzyskać minimalny zarobek. Zwróconą przez Aggregate wartość użyje przy selekcji wierszy z emp:
db1=> explain select * from emp where sal > (select min(sal) from manager);
QUERY PLAN
----------------------------------------------------------------------
Seq Scan on emp (cost=1.39..181.39 rows=3333 width=12)
Filter: (sal > $0)
InitPlan
-> Aggregate (cost=1.38..1.39 rows=1 width=4)
-> Seq Scan on manager (cost=0.00..1.30 rows=30 width=4)
(5 rows)
Sprawdzimy plan zapytania skorelowanego, szukamy pracowników, którzy zarabiają więcej niż pozostali pracownicy z tego z samego działu. Zapytania skorelowane są kosztowne w realizacji, ponieważ wymagają sprawdzenia warunku w podzapytaniu skorelowanym dla każdego wiersza z zapytania zewnętrznego. Planista prawdopobnie będzie starał się pozbyć podzapytania skorelowanego zastępując je operacją złączenia:
db1=> explain analyze select a.empno, a.deptno, a.sal from emp a where a.sal >= ALL ( select b.sal from emp b where a.deptno = b.deptno);Planista zdecydował się użyć tradycyjnej metody wykonania zapytania skorelowanego- za każdym razem wczytuje tabelę emp aby sprawdzić warunek w podzapytaniu skorelowanym.
QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------
Seq Scan on emp a (cost=0.00..360180.00 rows=5000 width=12) (actual time=21.710..2256.719 rows=86 loops=1)
Filter: (subplan)
SubPlan
-> Bitmap Heap Scan on emp b (cost=4.75..66.00 rows=500 width=4) (actual time=0.202..0.215 rows=10 loops=10000)
Recheck Cond: ($0 = deptno)
-> Bitmap Index Scan on emp_deptno (cost=0.00..4.75 rows=500 width=0) (actual time=0.185..0.185 rows=512 loops=10000)
Index Cond: ($0 = deptno)
Total runtime: 2257.060 ms
(8 rows)
Brak komentarzy:
Prześlij komentarz