Indexace intervalů - období příp. rozsah ip pomocí prostorových indexů
Celá optimalizace dotazů je postavena na schopnosti databáze dobře odhadnout účinnost predikátů dotazu. Pokud ale predikát obsahuje závislé sloupce, tak výpočet účinnosti selže. Není splněna podmínka nezávislosti hodnot. Mírná závislost nevadí. Jsou však případy, kdy mezi sloupci je absolutní závislost, a tehdy optimalizátor kolabuje. Typicky pokud máme dohledat interval, pro který platí podmínka start <= x and x <= konec - podobný výraz se objeví i v predikátu.
Testovací množina
Testovací množina má simulovat vyhledávání rozsahu ip adres z uloženého seznamu rozsahů pro danou ip adresu (pro jednoduchost jsou v příkladu ip adresy reprezentovány celým číslem). Tabulka rozsahů obsahuje jeden milión záznamů.
CREATE TABLE testip(id serial, startip int, endip int);
CREATE OR REPLACE FUNCTION fill()
RETURNS void AS $$
DECLARE m int; d int;
BEGIN
m := 1;
FOR i IN 1 .. 1000000 LOOP
d := (random()*50)::int + 1;
INSERT INTO testip VALUES(default, m, m + d);
m := m + d + 1;
END LOOP;
RETURN;
END;
$$ LANGUAGE plpgsql;
SELECT *
FROM testip
ORDER BY id;
id | startip | endip
----+---------+-------
1 | 1 | 13
2 | 14 | 40
3 | 41 | 45
4 | 46 | 95
5 | 96 | 135
6 | 136 | 137
7 | 138 | 174
Indexy
V tomto případě je navíc závislost i mezi řádky. Jednoduchým explainem se můžeme přesvědčit, že odhad je irelevantní. Jelikož na základě statistik optimalizátor předpokládá, že se vrátí prakticky čtvrtina tabulky, je minimální šance, že se použije index.
postgres=# EXPLAIN ANALYZE SELECT * FROM testip WHERE 19999999 BETWEEN startip AND endip;
QUERY PLAN
----------------------------------------------------------------
Seq Scan on testip (cost=0.00..19902.00 rows=200814 width=12) (actual time=3.457..434.218 rows=1 loops=1)
Filter: ((19999999 >= startip) AND (19999999 <= endip))
Total runtime: 434.299 ms
(3 rows)
Time: 435,865 ms
V podstatě rozumné řešení neexistuje. Jeden trik spočívá v použití podvržených statistik. Optimalizátor pak může použít index. Čistší řešení je použití prostorového indexu. Klasický B-tree index pracuje pouze s jedním číslem. V tomto případě potřebuji do indexu dostat dvě hodnoty, a ještě takovým způsobem, aby je optimalizátor akceptoval. Toto dokáží prostorové indexy, které PostgreSQL podporuje.
Z intervalu startip..endip vytvořím obdélník o((startip,startip),(endip,endip)). Nad takovýmito obdélníky vytvořím index. Pak budu dohledávat záznam, pro který bude platit, že obdélník o obsahuje obdélník i ((ip,ip),(ip,ip)).
postgres=# CREATE INDEX ggg ON testip USING gist ((box(point(startip,startip),point(endip,endip))) box_ops);
CREATE INDEX
Time: 75530,079 ms
postgres=# EXPLAIN ANALYZE
SELECT *
FROM testip
WHERE box(point(startip,startip),point(endip,endip)) @> box(point (19999999,19999999), point(19999999,19999999));
QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on testip (cost=60.50..2550.14 rows=1000 width=12) (actual time=0.169..0.172 rows=1 loops=1)
Recheck Cond: (box(point((startip)::double precision, (startip)::double precision), point((endip)::double precision, (endip)::double precision)) @> '(19999999,19999999),(19999999,19999999)'::box)
-> Bitmap Index Scan on ggg (cost=0.00..60.25 rows=1000 width=0) (actual time=0.152..0.152 rows=1 loops=1)
Index Cond: (box(point((startip)::double precision, (startip)::double precision), point((endip)::double precision, (endip)::double precision)) @> '(19999999,19999999),(19999999,19999999)'::box)
Total runtime: 0.285 ms
(5 rows)
Time: 2,805 ms
V tomto případě je řádově přesnější odhad a i dotaz je několikanásobně rychlejší. Kromě rozsahů se tento způso indexace používá ještě pro temporar dotazy - vyhledávání překryvu časových období.
Závislé sloupce, selhání predikce
Při závislosti mezi řádky predikce nadsadí počet řádků. Důsledkem je nepoužití indexu - předpokládá se, že predikát není příliš účinný, a že je efektivnější číst data sekvenčně. Opakem je závislost sloupců. Při ní dojde k opačné chybě a to k předpokladu příliš restriktivního predikátu - ve výsledku se chybně použije nested loop, který je pro větší počet řádků neefektivní. Index se použije téměř vždy. V následujících příkladech se zaměřte na odhad počtu řádků a skutečný počet řádků.
postgres=> CREATE TABLE tt(a integer, b integer);
CREATE TABLE
postgres=> INSERT INTO tt SELECT (random()*500)::int, null FROM generate_series(1,1000000);
INSERT 0 1000000
postgres=> UPDATE tt SET b = a;
UPDATE 1000000
postgres=> VACUUM ANALYZE tt;
VACUUM
-- spravny odhad
postgres=> EXPLAIN ANALYZE SELECT * FROM tt WHERE a BETWEEN 0 AND 10;
QUERY PLAN
-----------------------------------------------------------------------------------------------------------
Seq Scan on tt (cost=0.00..23347.00 rows=19435 width=8) (actual time=56.978..447.808 rows=21042 loops=1)
Filter: ((a >= 0) AND (a <= 10))
Total runtime: 475.028 ms
(3 rows)
postgres=> CREATE INDEX ax ON tt(a);
-- chybny odhad
CREATE INDEX
postgres=> EXPLAIN ANALYZE SELECT * FROM tt WHERE a BETWEEN 0 AND 10 AND b BETWEEN 0 AND 10;
QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on tt (cost=366.78..9102.48 rows=378 width=8) (actual time=24.930..134.435 rows=21042 loops=1)
Recheck Cond: ((a >= 0) AND (a <= 10))
Filter: ((b >= 0) AND (b <= 10))
-> Bitmap Index Scan on ax (cost=0.00..366.69 rows=19435 width=0) (actual time=22.364..22.364 rows=21042 loops=1)
Index Cond: ((a >= 0) AND (a <= 10))
Total runtime: 163.820 ms
(6 rows)
Řešením je vyloučit z predikátu závislé sloupce (pokud to lze):
postgres=> EXPLAIN ANALYZE SELECT * FROM tt WHERE a BETWEEN 0 AND 10;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on tt (cost=371.55..9010.07 rows=19435 width=8) (actual time=13.512..146.244 rows=21042 loops=1)
Recheck Cond: ((a >= 0) AND (a <= 10))
-> Bitmap Index Scan on bx (cost=0.00..366.69 rows=19435 width=0) (actual time=9.085..9.085 rows=21042 loops=1)
Index Cond: ((a >= 0) AND (a <= 10))
Total runtime: 180.146 ms
(5 rows)
V tomto případě si to mohu dovolit - závislost mezi a a b je absolutní (navíc se v tomto případě jen minimálně měnil prováděcí plán). Tento příklad je také ukázkou neefektivity B-tree indexu. 500 unikátních hodnot na jeden milión záznamů představuje velice špatnou selectivitu. Bohužel PostgreSQL nepodporuje bitmapové indexy, které jsou pro tento typ dat vhodnější. Pokud nelze druhý predikát odstranit, pak je dost pravděpodobné, že pro velké tabulky a operaci JOIN bude tato závislost způsobovat velké problémy. Pak je asi vhodnější rozdělit takovýto dotaz do dvou. V první části vygenerovat dočasnou tabulku a aktualizovat její statistiky. A v druhém kroku provést JOIN.