Úvaha ohledně zneužívání LIKE v databázích

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ů.

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 e-mailem. Aplikace sloužila k uložení dokumentace a přístup k dokumentům byl založen na tom, zda se v sloupci „to:“ vyskytovala e-mailová 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ím dvou tabulek. Pro člověka je přece 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_user­s(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 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–10 ms 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,4 MB 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.

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.