Krátká úvaha ohledně zneužívání LIKE v databázích
Na svých kurzech, trochu s nadsázkou, tvrdím, že programátor, který použije LIKE, si koleduje o to, nebýt programátorem. Nedávno se na dbsvětu objevil článek na toto téma. Což je nepochybně přínosné, bohužel zmiňovaný článek nešel příliš do hloubky. Co je na tomto, na první pohled, neškodného operátoru, tak hrozného? Z mého pohledu operátor LIKE podporuje šlendrián v programování - tedy umožňuje navrhnout špatné databáze a napsat špatné program, jinak řečeno - pomalé databáze a pomalé programy.
Jedno z nejdůležitějších tvrzení v IT říká, že data se snadno spojují a velice obtížně rozdělují. Významu tohoto tvrzení odpovídá i v pořadí první první normální forma (tj. požadavek na charakter ukládaných dat) - data mají být atomická - tedy dále nedělitelná. Prostě chceme mít data uložená tak, abychom je už dodatečně nemuseli rozsekávat. A přestože je toto pravidlo směšně jednoduché, vesele se porušuje. SQL tomu jakoby samo nahrává - obsahuje datový typ varchar (případně text) a operátor LIKE. Tedy do databáze můžeme uložit cokoliv a cokoliv tam také můžeme najít. Od jisté doby mám averzi k přidávání položek typu poznámka do tabulek. Uživatelé jsou schopni bez jakýchkoliv skrupulí na základě jedné frivolnější položky vytvořit vlastní informační systém v informačním systému. Taková databáze je pak postrachem a noční můrou každého programátora. 80% dat respektuje jakási uživatelova formulovatelná pravidla, 15% dodržuje zase jiná, a to na základě logiky, která se zdá samozřejmá pouze vybraným a dlouholetým uživatelům systému, a zbytek je dezorganizovaná směs čehokoliv. Prostě chuťovka. Jako správný programátor mám rád vše strukturované a uspořádané :).
Dovolím si předpokládat, že bez operátoru LIKE, by se o toto uživatel nesnažil. Proč? Protože by v životě nic nenašel. Nestrukturovaná data by tiše zmizela v nekonečných hlubinách diskových polí. Nejen uživatelé jsou schopní přetvořit IS. Mezi programátory se najde nejeden mág, který přidáním několika sloupečků, několika řádků kódu customizoval za slušný peníz nejeden IS. Ano, takovému prznění originálních IS se říká customizace - aneb jak naučit IS, který prodáváme, dělat to, co nikdy neuměl a neměl umět, ale co naši obchodníci naslibovali a prodali. O co má programátor silnější prostředky, o to větší zrůdnost dokáže vytvořit. V některých případech, dokonce, i ke spokojenosti zákazníků.
Relativně častým zneužitím operátoru LIKE je jeho aplikace na datumové typy. Nejčastěji timestamp nebo date. Použití LIKE má několik negativních dopadů na výkon: a) každá hodnota je neustále (při každém dotazu) konvertována na varchar (zatížení procesoru), b) z důvodu různých datových typů se nikdy nepoužije index (zatížení I/O).
postgres=# insert into foo
select '1970-01-01'::timestamp + (random()*20000)::int * interval '1 day'
from generate_series(1,20000);
INSERT 0 20000
Time: 355,316 ms
postgres=# select count(*) from foo;
┌───────┐
│ count │
├───────┤
│ 20000 │
└───────┘
(1 row)
Time: 14,876 ms
postgres=# select count(*) from foo where a::varchar like '1986-10-%';
┌───────┐
│ count │
├───────┤
│ 36 │
└───────┘
(1 row)
Time: 87,791 ms
cca 70 ms padne pouze na konverzi do varcharu a test like. Po odstranění like dotaz cca 40x rychlejší.
postgres=# create index xx on foo(a); postgres=# select count(*) from foo where a > timestamp '1986-10-01' and a < timestamp '1986-11-01'; ┌───────┐ │ count │ ├───────┤ │ 35 │ └───────┘ (1 row) Time: 2,114 ms
Výše uvedený příklad ukazuje další nešvar - konverzi datových typů prostřednictvím konverze do varcharu. viz
postgres=# select count(a::date) from foo; ┌───────┐ │ count │ ├───────┤ │ 20000 │ └───────┘ (1 row) Time: 20,115 ms postgres=# select count(substring(a::varchar from 1 for 10)) from foo; ┌───────┐ │ count │ ├───────┤ │ 20000 │ └───────┘ (1 row) Time: 92,655 ms
Jsou to dva roky, co jsem se setkal patrně s nejpomalejší aplikací svého života. Každý uživatel v této aplikaci byl identifikován emailem. Aplikace sloužila k uložení dokumentace a přístup k dokumentům byl založen na tom, zda-li se v sloupci "to:" vyskytovala emailová adresa toho, či onoho uživatele. Prosté, jednoduché a až příliš jednoduché řešení, které vyhovovalo při vývoji, a které se ukázalo, jako žalostně pomalé, při prvním reálném nasazení, kde dokument byl přístupný více než třem, čtyřem uživatelům. Při každém zobrazení seznamu dokumentů se prováděl dotaz:
SELECT * FROM documents WHERE "to:" ILIKE '%jmeno.prijmeni@adresa.cz%'
Nebudu se rozepisovat o náročnosti úlohy vyhledání podřetězce v řetězci (viz pattern matching && Google). V každém případě tato aplikace dokázala žhavit procesor. A to se u dedikovaných databázových serverů stává opravdu výjimečně. Opravdu nevím, z čeho mají programátoři strach, a proč nedokáží tuto úlohu řešit korektně, což znamená přidání dvou tabulek. Pro člověka je přeci jen přirozenější držet věci pohromadě - to, co jsem navrhoval před 15 lety by taky rychlostí neoplývalo. Ale to, co vyhovuje člověku, evidentně nevyhovuje relačním databázím.
Správné řešení je použití tabulek documents(id,..), users(id,email) a vazební tabulky document_users(document_id, user_id).
SELECT d.*
FROM documents d
JOIN
document_users du
ON d.id = du.document_id
JOIN
users u
ON du.user_id = u.id
WHERE u.email = 'jmeno.prijmeni@adresa.cz';
Věřte nebo nevěřte, tento komplikovanější příkaz bude rychlejší (při objemu dat větším než malém). Pro druhý SQL příkaz může databázový stroj zapojit dvě své neúčinnější zbraně - indexy a planner. Při aktuálních statistikách dokáže planner s vysokou pravděpodobností trefit do počtu filtrovaných dokumentů a správně zvolit sekvenční čtení datového souboru nebo čtení dat. souboru s náhodným přístupem. Navíc minimalizuje počet porovnání řetězců (pokud budu mít index nad users(email)). Operace nad tabulkami documents a document_users jsou jen celočíselná porovnání (je jen málo rychlejších operací).
Kromě jiného mám k dispozici tabulku users - kterou mohu využít jinde, a tabulku document_users, kterou mohu použít například při počítání dokumentů, ke kterým má uživatel přístup. Do tabulky document_users mohu umístit např. informaci o tom, zda-li byl dokument již přečten nebo nikoliv, čas posledního přístupu, atd atd.
SELECT count(*)
FROM document_users du
JOIN
users u
ON du.user_id = u.id
WHERE u.email = 'jmeno.prijmeni@adresa.cz';
Toto opět může být velice rychlá operace - výhodou je fakt, že tabulka document_users je velice úzká. Tudíž se na jednu datovou stránku vejde víc záznamů a tudíž jsou IO operace velice efektivní (s minimálním dopadem na cache).
Není nad praktickou ukázku (nad db PostgreSQL 8.4). Vytvořil jsem si testovací funkce, které mi pomohou vytvořit testovací data:
CREATE OR REPLACE FUNCTION rndstr(integer)
RETURNS varchar AS $$
SELECT array_to_string(ARRAY(SELECT substring('abcdefghijklmnopqrst' FROM (random()*20)::int FOR 1)
FROM generate_series(1,$1) g(i)),
'')
$$ LANGUAGE sql;
CREATE OR REPLACE FUNCTION rnddoc(int)
RETURNS varchar AS $$
SELECT array_to_string(ARRAY(SELECT rndstr((random()*3+3)::int)
FROM generate_series(1, $1) g(i)),
' ')
$$ LANGUAGE sql;
Dále jsem si vytvořil normalizovanou variantu tabulek:
CREATE TABLE documents(id serial PRIMARY KEY, note varchar);
INSERT INTO documents (note)
SELECT rnddoc((random()*20+20)::int)
FROM generate_series(1,10000); -- 10 000 dokumentu
CREATE TABLE users(id serial PRIMARY KEY, email varchar);
INSERT INTO users(email)
SELECT rndstr((random()*3+3)::int)||'.'||rndstr((random()*3+3)::int)||'@adresa.cz'
FROM generate_series(1,100);
-- vypsani duplicit
SELECT email
FROM users
GROUP BY email
HAVING count(*) > 1;
-- pokud jsou, odstranit upravit
-- pokud nejsou, generovat unikatni index
CREATE INDEX users_email_idx ON users(email);
-- nahodne vybrane dokumenty maji 1..10 uzivatelu
CREATE TABLE document_users(document_id int, user_id int, PRIMARY KEY(document_id, user_id));
Primární index by se uplatnil, pokud bych dohledával uživatele k vybraným dokumentům. Postupuji opačně, takže přidám index:
INSERT INTO document_users
SELECT i, unnest(u)
FROM (SELECT i, ARRAY(SELECT DISTINCT trunc(random()*100)::int
FROM generate_series(1+i-i,trunc(random()*10+1)::int)
) AS u
FROM generate_series(1,10000) g(i)) x;
postgres=# \dt+
List of relations
Schema | Name | Type | Owner | Size | Description
--------+----------------+-------+-------+------------+-------------
public | document_users | table | pavel | 1888 kB | 53181 rows
public | documents | table | pavel | 1960 kB | 10000 rows
public | users | table | pavel | 8192 bytes | 100 rows
(3 rows)
CREATE INDEX document_users_user_id_idx ON document_users(user_id);
-- aktualizace statistik
ANALYZE;
postgres=# SELECT * FROM users LIMIT 3;
id | email
----+----------------------
1 | lrej.pnqkh@adresa.cz
2 | qgddn.edi@adresa.cz
3 | ekh.kcnso@adresa.cz
(3 rows)
Time: 1,567 ms
postgres=# SELECT * FROM document_users LIMIT 3;
document_id | user_id
-------------+---------
1 | 80
1 | 67
2 | 39
(3 rows)
postgres=# SELECT id, substring(note FROM 1 FOR 30) FROM documents LIMIT 3;
id | substring
----+--------------------------------
1 | omhih rcf pqfbp ffco bbdgi elb
2 | coghk atkbf okenbb gee sep erd
3 | fqmcf qcadb pbj rsgim hcol obd
(3 rows)
-- vyberu si uzivatele s cislem 73, a pro nej zkousim
postgres=# SELECT * FROM users WHERE id = 73;
id | email
----+----------------------
73 | pisrs.ikebre@adresa.cz
(1 row)
SELECT d.*
FROM documents d
JOIN
document_users du
ON d.id = du.document_id
JOIN
users u
ON du.user_id = u.id
WHERE u.email = 'pisrs.ikebre@adresa.cz';
Prováděcí plán:
QUERY PLAN
----------------------------------------------------------------------------------------------------
Nested Loop (cost=12.38..422.83 rows=532 width=168)
-> Nested Loop (cost=12.38..262.60 rows=532 width=4)
-> Seq Scan on users u (cost=0.00..2.25 rows=1 width=4)
Filter: ((email)::text = 'pisrs.ikebre@adresa.cz'::text)
-> Bitmap Heap Scan on document_users du (cost=12.38..253.70 rows=532 width=8)
Recheck Cond: (du.user_id = u.id)
-> Bitmap Index Scan on document_users_user_id (cost=0.00..12.24 rows=532 width=0)
Index Cond: (du.user_id = u.id)
-> Index Scan using documents_pkey on documents d (cost=0.00..0.29 rows=1 width=168)
Index Cond: (d.id = du.document_id)
(10 rows)
V případě tabulky users se nepoužil index, jelikož se všechna data vejdou do jediné datové stránky.
Odhad 532 řádků, reálně 529 (čas od 12ms do 20ms).
Nyní potřebuji vygenerovat denormalizovanou tabulku ddocuments:
CREATE TABLE ddocuments(id serial PRIMARY KEY, note varchar, "to" varchar);
INSERT INTO ddocuments
SELECT d.id, d.note, x."to"
FROM documents d
JOIN
(SELECT document_id, array_to_string(array_agg(email),',') AS "to"
FROM document_users du
JOIN
users u
ON du.user_id = u.id
GROUP BY document_id) x
ON d.id = x.document_id
ORDER BY d.id;
postgres=# \dt+ ddocuments
List of relations
Schema | Name | Type | Owner | Size | Description
--------+------------+-------+-------+---------+-------------
public | ddocuments | table | pavel | 3064 kB | obsahuje pouze primarni klic, 10000 radku
(1 row)
Dotaz skrz LIKE by vypadal následovně:
SELECT *
FROM ddocuments
WHERE "to" LIKE '%pisrs.ikebre@adresa.cz%';
QUERY PLAN
----------------------------------------------------------------
Seq Scan on ddocuments (cost=0.00..507.96 rows=554 width=278)
Filter: (("to")::text ~~ '%pisrs.ikebre@adresa.cz%'::text)
(2 rows)
Odhad je relativně slušný, rychlost kolísá mezi 20-30ms.
Při trojnásobku počtu dokumentů je to 30ms/50ms:
List of relations Schema | Name | Type | Owner | Size | Description --------+----------------+-------+-------+------------+------------- public | ddocuments | table | pavel | 6112 kB | 30000 public | document_users | table | pavel | 5680 kB | public | documents | table | pavel | 5856 kB | public | users | table | pavel | 8192 bytes | (4 rows)
S rostoucí velikostí tabulky bude rychlost sekvenčního čtení O*N, kdežto rychlost indexů O*ln(n).
Zjevnou nevýhodou denormalizovaného modelu je náročnost operace přidání nebo odebrání přístupu k dokumentu. U normalizovaného datového modelu stačí triviální INSERT nebo DELETE. Otázka - jakým SQL příkazem bych u denormalizovaného modelu zjistil počet dokumentů pro konkrétního uživatele? V pg bych mohl napsat něco ve tvaru:
SELECT email, count(*)
FROM (SELECT unnest(string_to_array("to",',')) AS email
FROM ddocuments) x
WHERE email = 'kedmo.emlap@adresa.cz'
GROUP BY email;
Rychlost je kolem 170ms versus 5ms (normalizovaný model). Je to o dost pomalejší a to mám k dispozici poměrně rychlé funkce na parsování řetězců a rozvinutí pole.
Pozor ale na ILIKE! Stačí drobná změna:
SELECT * FROM ddocuments WHERE "to" ILIKE '%pisrs.ikebre@adresa.cz%';
a doba provádění dotazu okamžitě vyskočí na dva a půl násobek.
Při dnešní rychlosti procesorů, a při faktu, že PostgreSQL používá sofistikovanější algoritmus hledání podřetězců v řetězci, nemusí vždy být dotazy v normalizovaném schématu rychlejší. Hodně záleží na selektivitě indexů. Každý uživatel má přístup cca k 5% dokumentů (pokud by průměrný uživatel měl přístup k více než 20% a více, tak pak naopak rychlejší může být denormalizovaná varianta (i když, to by znamenalo protažení řetězce "to").
Zajímavý může být i pohled do cache:
Normalizovaná varianta:
postgres=# SELECT c.relname, count(*) AS buffers
FROM pg_buffercache b INNER JOIN pg_class c
ON b.relfilenode = c.relfilenode AND
b.reldatabase IN (0, (SELECT oid FROM pg_database
WHERE datname = current_database()))
GROUP BY c.relname
ORDER BY 2 DESC LIMIT 10;
relname | buffers
---------------------------------+---------
document_users | 649
documents | 437
documents_pkey | 46
document_users_user_id | 7
Je vidět, že se četla prakticky celá tabulka document_users (celkově se zabere 710 stránek bufferu). Je to důsledek jednoduše generovaných dat. Reálná data vytvářejí jakési shluky. Pokud bych použil příkaz CLUSTER a data fyzicky seřadil podle user_id (optimální případ) pak se z tabulky document_users přečte pouze 8 stránek (to je druhý extrém, který v praxi není pravděpodobný).
relname | buffers ---------------------------------+--------- documents | 437 documents_pkey | 46 document_users | 8 document_users_user_id | 7 users | 1
Totéž lze říci i tabulce documents - přestože se použijí indexy, prochází se více než polovina datových stránek tabulky.
Denormalizovaná varianta
relname | buffers
---------------------------------+---------
ddocuments | 764
Pokud nechcete jít cestou normalizace, pak je tu ještě jedno možné řešení. Tímto řešením je fulltext.
CREATE INDEX ddocuments_to_fidx ON ddocuments USING gin(to_tsvector('simple', "to"));
postgres=# EXPLAIN SELECT * FROM ddocuments WHERE to_tsvector('simple',"to") @@ to_tsquery('simple','%pisrs.ikebre@adresa.cz%');
QUERY PLAN
---------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on ddocuments (cost=5.03..283.62 rows=100 width=278)
Recheck Cond: (to_tsvector('simple'::regconfig, ("to")::text) @@ '''pisrs.ikebre@adresa.cz'''::tsquery)
-> Bitmap Index Scan on ddocuments_to_fidx (cost=0.00..5.01 rows=100 width=0)
Index Cond: (to_tsvector('simple'::regconfig, ("to")::text) @@ '''pisrs.ikebre@adresa.cz'''::tsquery)
(4 rows)
Pokud se data udrží v cache, pak také tyto dotazy mohou být velice rychlé. Co je důležité - automaticky je podmínka case insensitive. Odhad není nijak přesný.
Obsah cache
relname | buffers
---------------------------------+---------
ddocuments | 586
ddocuments_to_fidx | 2
GIN index zajistí velice rychlé dohledání, ale jeho aktualizace je náročnější. Naopak GiST index je o dost pomalejší s mnohem rychlejší aktualizací.
relname | buffers ---------------------------------+--------- ddocuments | 764 ddocuments_to_fidx | 153
Dalším kompromisním řešením je použití polí. V podstatě se jedná o formu denormalizace:
CREATE TABLE ddocuments2(id serial PRIMARY KEY, note text, "to" int[]);
INSERT INTO ddocuments2
SELECT d.id, d.note, x."to"
FROM documents d
JOIN
(SELECT document_id, array_agg(u.id) as "to"
FROM document_users du
JOIN users u
ON du.user_id = u.id
GROUP BY document_id) x
ON d.id = x.document_id
ORDER by d.id;
postgres=# EXPLAIN ANALYZE SELECT * FROM ddocuments2 WHERE "to" @> array(SELECT id FROM users WHERE email = 'pisrs.ikebre@adresa.cz');
QUERY PLAN
--------------------------------------------------------------------------------------------------------------
Seq Scan on ddocuments2 (cost=2.25..845.01 rows=20 width=210) (actual time=0.175..41.424 rows=1044 loops=1)
Filter: ("to" @> $0)
InitPlan
-> Seq Scan on users (cost=0.00..2.25 rows=1 width=4) (actual time=0.053..0.074 rows=1 loops=1)
Filter: ((email)::text = 'pisrs.ikebre@adresa.cz'::text)
Total runtime: 44.616 ms
(6 rows)
Na testovací množině o 30000 záznamech je tato varianta zhruba o 5-10ms rychlejší než LIKE. Kritický je naprosto ustřelený odhad. To může působit následně problémy, pokud bychom tento dotaz používali např. jako pohled (view).
Můžeme zkusit přidat index:
CREATE INDEX ddocument2_to_idx ON ddocuments2 using gin ("to");
Dotazy se pak zrychlí o polovinu - cca 18ms.
relname | buffers ---------------------------------+--------- ddocuments2 | 512 ddocument2_to_idx | 2 users | 1
V tomto případě je i zajímavý rozdíl cca 1.4MB mezi tabulkami ddocuments a ddocuments2.
Dnešní extrémně rychlé procesory, do jisté míry, eliminují negativní dopad operátoru LIKE na výkon. Na druhou stranu - s dostupností velkokapacitních médií roste i velikost uchovávaných dat, a tudíž je nutné mít neustále na zřeteli rychlost operací. Máme rychlejší hw, sofistikovanější sw, ale nic už tak moc neomezuje uživatele při ukládání dat.
I případě rychlých procesorů, lze dotazem postaveným na operátoru LIKE odstavit server - to je možná přehnané, určitě si ovšem uživatel na výsledek dotazu počká. Řeč je o vícenásobném použití operátoru LIKE. Představte si, že budete vyhledávat v sloupci subject všechny řádky, kde subject obsahuje slova: Praha, smlouva, Soukenická. Bez fulltextu to budete řešit dotazem:
SELECT ...
FROM
WHERE subject ILIKE '%Praha%' AND subject ILIKE '%Soukenicka%'
AND subject ILIKE '%Smlouva%'
Závěr: Pokud to lze, pracujte s normalizovaným db modelem. Pracuje se s ním snadněji, a velká většina úloh je dostatečně rychlá (pokud není, pomohou materializované pohledy). Pokud to není možné, použijte fulltext. A pokud nemáte ani ten, tak pak Vám nezbude, než použít LIKE. V tom případě, alespoň, se vyvarujte použití operátoru ILIKE.