Nein, hier soll es nicht um Twitter, Instagram oder Youtube gehen, sondern um Datenbankabfragen in PostgreSQL wie diese:
blog # SELECT * FROM kunden WHERE vorname LIKE 'Ann%';
Diese Abfragen sind recht häufig anzutreffen, man denke z.B. an Drop-Down-Boxen, die z.B. per AJAX mit Vorschlägen gefüllt werden, sobald drei oder mehr Buchstaben eingegeben wurden.
Das Spielfeld
Unsere Beispieldaten enthalten 1.000.000 zufällig generierte Kunden in dieser Form und mit dieser Verteilung von Vornamen, die mit ‚Ann‘ beginnen:
blog # \d kunden
Table "public.kunden"
┌────────────┬─────────┬───────────┬──────────┬────────────────────────────────────┐
│ Column │ Type │ Collation │ Nullable │ Default │
├────────────┼─────────┼───────────┼──────────┼────────────────────────────────────┤
│ id │ integer │ │ not null │ nextval('kunden_id_seq'::regclass) │
│ vorname │ text │ │ not null │ │
│ nachname │ text │ │ not null │ │
│ strasse │ text │ │ not null │ │
│ hausnummer │ integer │ │ not null │ │
│ plz │ text │ │ not null │ │
│ ort │ text │ │ not null │ │
│ bundesland │ text │ │ not null │ │
└────────────┴─────────┴───────────┴──────────┴────────────────────────────────────┘
Indexes:
"kunden_pkey" PRIMARY KEY, btree (id)
Check constraints:
"kunden_plz_check" CHECK (length(plz) = 5)
blog # vorname,count(*) FROM kunden WHERE vorname LIKE 'Ann%' GROUP BY vorname;
┌───────────┬───────┐
│ vorname │ count │
├───────────┼───────┤
│ Anni │ 963 │
│ Annabella │ 984 │
│ Anne │ 965 │
│ Annalena │ 971 │
│ Annika │ 1017 │
│ Anna │ 1011 │
│ Ann │ 1003 │
│ Annelie │ 976 │
│ Annemarie │ 1001 │
│ Annabell │ 996 │
└───────────┴───────┘
(10 rows)
Ein erster Versuch – „vanilla“
Schauen wir doch mal, wie unsere PostgreSQL-Datenbank eine Suche nach ‚Ann%‘ bearbeitet:
blog # EXPLAIN (ANALYSE,COSTS) SELECT * FROM kunden WHERE vorname LIKE 'Ann%'; ┌────────────────────────────────────────────────────────────────────┐ │ QUERY PLAN │ ├────────────────────────────────────────────────────────────────────┤ │ Seq Scan on kunden (cost=0.00..24667.00 rows=10244 width=65) | | (actual time=0.019..90.620 rows=9887 loops=1) │ │ Filter: (vorname ~~ 'Ann%'::text) │ │ Rows Removed by Filter: 990113 │ │ Planning time: 0.100 ms │ │ Execution time: 90.956 ms │ └────────────────────────────────────────────────────────────────────┘ (5 rows)
Ein Seq Scan, also der gefürchtete Sequential-Scan aka. Full table scan; alle Datensätze werden gelesen und ‚vorname‘ mit ‚Ann%‘ verglichen. Das ist sehr ineffektiv.
Ein Index muss her!
Die Lösung ist offensichtlich: wenn solche Abfragen häufig vorkommen, muss ein Index her. Der wird den Vorgang beschleunigen:
blog # CREATE INDEX vorname_btree_vanilla ON kunden (vorname); blog # EXPLAIN (ANALYSE,COSTS) SELECT * FROM kunden WHERE vorname LIKE 'Ann%'; ┌───────────────────────────────────────────────────────────────────────┐ │ QUERY PLAN │ ├───────────────────────────────────────────────────────────────────────┤ │ Seq Scan on kunden (cost=0.00..24667.00 rows=10244 width=65) | | (actual time=0.011..105.340 rows=9887 loops=1) │ │ Filter: (vorname ~~ 'Ann%'::text) │ │ Rows Removed by Filter: 990113 │ │ Planning time: 0.195 ms │ │ Execution time: 105.768 ms │ └───────────────────────────────────────────────────────────────────────┘ (5 rows)
Uhm, Moment mal… warum nimmt meine Datenbank nicht den Index zu Hilfe?!? Geht es denn mit einzelnen Werten?
blog # EXPLAIN (ANALYSE,COSTS) SELECT * FROM kunden WHERE vorname IN ('Anna','Anne','Annelie');
┌────────────────────────────────────────────────────────────────────────────────────────┐
│ QUERY PLAN │
├────────────────────────────────────────────────────────────────────────────────────────┤
│ Bitmap Heap Scan on kunden (cost=59.83..6892.21 rows=2909 width=65) |
| (actual time=1.275..5.054 rows=2952 loops=1) │
│ Recheck Cond: (vorname = ANY ('{Anna,Anne,Annelie}'::text[])) │
│ Heap Blocks: exact=2656 │
│ -> Bitmap Index Scan on vorname_btree_vanilla (cost=0.00..59.10 rows=2909 width=0) |
| (actual time=0.652..0.652 rows=2952 loops=1) │
│ Index Cond: (vorname = ANY ('{Anna,Anne,Annelie}'::text[])) │
│ Planning time: 0.136 ms │
│ Execution time: 5.292 ms │
└────────────────────────────────────────────────────────────────────────────────────────┘
(7 rows)
Ja, da wird der Index genommen, und die Ausführung ist auch gleich um Größenordnungen schneller.
Was ist also das Problem?
„C“ und seine Spätfolgen – Schei* encoding!
Das Geheimnis liegt – wie so häufig – in der Lokalisierung. Btree-Indexe sind (für Text-Daten) auf das C-Locale hin optimiert. Wenn aber die Datenbank (wie heutzutage üblich!) mit en_US.UTF8 oder de_DE.UTF8 initialisiert wurde, müssen wir dem Index bei der Erstellung mitteilen, dass wir pattern operator-Aktionen ausführen können wollen. PostgreSQL kommt mit einem ganzen Haufen dieser Operator Classes.
Für unser TEXT-Feld ‚vorname‘ nehmen wir text_pattern_ops. Nach der Erstellung testen wir, ob der Index unsere LIKE-Anfrage beschleunigt und verifizieren, dass auch weiterhin die klassischen <=, == und >= Vergleichsoperatoren funktionieren:
blog # DROP INDEX vorname_btree_vanilla ;
blog # CREATE INDEX vorname_btree_opclass ON kunden (vorname text_pattern_ops);
blog # EXPLAIN (ANALYSE,COSTS) SELECT * FROM kunden WHERE vorname LIKE 'Ann%';
┌─────────────────────────────────────────────────────────────────────────────────────────┐
│ QUERY PLAN │
├─────────────────────────────────────────────────────────────────────────────────────────┤
│ Bitmap Heap Scan on kunden (cost=129.19..10234.85 rows=10244 width=65) |
| (actual time=5.327..16.083 rows=9887 loops=1) │
│ Filter: (vorname ~~ 'Ann%'::text) │
│ Heap Blocks: exact=6830 │
│ -> Bitmap Index Scan on vorname_btree_opclass (cost=0.00..126.62 rows=5820 width=0) |
| (actual time=3.524..3.524 rows=9887 loops=1) │
│ Index Cond: ((vorname ~>=~ 'Ann'::text) AND (vorname ~<~ 'Ano'::text)) │
│ Planning time: 0.378 ms │
│ Execution time: 16.650 ms │
└─────────────────────────────────────────────────────────────────────────────────────────┘
(7 rows)
blog # EXPLAIN (ANALYSE,COSTS) SELECT * FROM kunden WHERE vorname IN ('Anna','Anne','Annelie');
┌─────────────────────────────────────────────────────────────────────────────────────────┐
│ QUERY PLAN │
├─────────────────────────────────────────────────────────────────────────────────────────┤
│ Bitmap Heap Scan on kunden (cost=59.83..6892.21 rows=2909 width=65) |
| (actual time=1.233..5.001 rows=2952 loops=1) │
│ Recheck Cond: (vorname = ANY ('{Anna,Anne,Annelie}'::text[])) │
│ Heap Blocks: exact=2656 │
│ -> Bitmap Index Scan on vorname_btree_opclass (cost=0.00..59.10 rows=2909 width=0) |
| (actual time=0.634..0.634 rows=2952 loops=1) │
│ Index Cond: (vorname = ANY ('{Anna,Anne,Annelie}'::text[])) │
│ Planning time: 0.135 ms │
│ Execution time: 5.246 ms │
└─────────────────────────────────────────────────────────────────────────────────────────┘
(7 rows)
Wunderbar! Und 17ms klingt auch gleich viel besser als 100ms.
Geht da noch was?
Jedes Kind weiß, dass Indexe nur Anfragen wie LIKE ‚Ann%‘ beschleunigen können. Für LIKE ‚%nna%‘ gibt es leider keine Hilfe von der Datenbank. Ist ja auch irgendwie klar, der Btree muss ja von links nach rechts aufgebaut werden…
EXPLAIN (ANALYSE,COSTS) SELECT * FROM kunden WHERE vorname LIKE '%nna%'; ┌─────────────────────────────────────────────────────────────────────────────────────────┐ │ QUERY PLAN │ ├─────────────────────────────────────────────────────────────────────────────────────────┤ │ Seq Scan on kunden (cost=0.00..24667.00 rows=19022 width=65) | | (actual time=0.014..110.607 rows=11993 loops=1) │ │ Filter: (vorname ~~ '%nna%'::text) │ │ Rows Removed by Filter: 988007 │ │ Planning time: 0.131 ms │ │ Execution time: 111.006 ms │ └─────────────────────────────────────────────────────────────────────────────────────────┘ (5 rows)
Aber stimmt das? Gibt es wirklich keine Möglichkeit, solche Abfragen zu beschleunigen?
PostgreSQL ist schier unfassbar erweiterbar, und unter anderem kommt es von Haus aus mit einer Extension pg_trgm, die wiederum operator classes für GIN und GiST Indexe mitbringt.
blog # CREATE EXTENSION IF NOT EXISTS pg_trgm; CREATE EXTENSION blog # CREATE INDEX vorname_gin_trgm ON kunden USING GIN (vorname gin_trgm_ops); blog # EXPLAIN (ANALYSE,COSTS) SELECT * FROM kunden WHERE vorname LIKE '%nna%'; ┌──────────────────────────────────────────────────────────────────────────────────────────┐ │ QUERY PLAN │ ├──────────────────────────────────────────────────────────────────────────────────────────┤ │ Bitmap Heap Scan on kunden (cost=183.42..13123.52 rows=19022 width=65) | | (actual time=5.049..15.935 rows=11993 loops=1) │ │ Recheck Cond: (vorname ~~ '%nna%'::text) │ │ Heap Blocks: exact=7670 │ │ -> Bitmap Index Scan on vorname_gin_trgm (cost=0.00..178.67 rows=19022 width=0) | | (actual time=3.014..3.014 rows=11993 loops=1) │ │ Index Cond: (vorname ~~ '%nna%'::text) │ │ Planning time: 0.253 ms │ │ Execution time: 16.488 ms │ └──────────────────────────────────────────────────────────────────────────────────────────┘ (7 rows)
pg_trgm kann noch mehr
Eine vermeintlich nette Spielerei, aber – wenn man es denn kennt – in vielen Situationen hilfreich, ist die Ähnlichkeitssuche, die pg_trgm in Form von Funktionen und Operatoren mitbringt:
blog # SELECT vorname, count(*) FROM kunden WHERE vorname % 'Nick' GROUP BY vorname ORDER BY similarity(vorname, 'Nick') DESC; ┌─────────┬───────┐ │ vorname │ count │ ├─────────┼───────┤ │ Nick │ 995 │ │ Nico │ 1047 │ │ Nicole │ 977 │ │ Nicolas │ 1026 │ └─────────┴───────┘ (4 rows)
Und auch hier beschleunigt der GIN-Index die Abfrage signifikant:
blog # EXPLAIN ANALYSE SELECT vorname, count(*) FROM kunden WHERE vorname % 'Nick' GROUP BY vorname ORDER BY similarity(vorname, 'Nick') DESC; ┌──────────────────────────────────────────────────────────────────────────────────────────┐ │ QUERY PLAN │ ├──────────────────────────────────────────────────────────────────────────────────────────┤ │ Sort (cost=24761.50..24763.07 rows=630 width=18) | | (actual time=915.696..915.697 rows=4 loops=1) . │ │ Sort Key: (similarity(vorname, 'Nick'::text)) DESC │ │ Sort Method: quicksort Memory: 25kB │ │ -> GroupAggregate (cost=24716.83..24732.20 rows=630 width=18) | | (actual time=915.305..915.689 rows=4 loops=1) │ │ Group Key: vorname │ │ -> Sort (cost=24716.83..24719.33 rows=1000 width=6) | | (actual time=915.162..915.305 rows=4045 loops=1) │ │ Sort Key: vorname │ │ Sort Method: quicksort Memory: 286kB │ │ -> Seq Scan on kunden (cost=0.00..24667.00 rows=1000 width=6) | | (actual time=0.650..914.065 rows=4045 loops=1) │ │ Filter: (vorname % 'Nick'::text) │ │ Rows Removed by Filter: 995955 │ │ Planning time: 0.296 ms | │ Execution time: 915.737 ms │ └──────────────────────────────────────────────────────────────────────────────────────────┘ (13 rows) blog # CREATE INDEX vorname_gin_trgm ON kunden USING GIN (vorname gin_trgm_ops); blog # EXPLAIN ANALYSE SELECT vorname, count(*) FROM kunden WHERE vorname % 'Nick' GROUP BY vorname ORDER BY similarity(vorname, 'Nick') DESC; ┌──────────────────────────────────────────────────────────────────────────────────────────┐ │ QUERY PLAN │ ├──────────────────────────────────────────────────────────────────────────────────────────┤ │ Sort (cost=3164.18..3165.75 rows=630 width=18) | | (actual time=32.510..32.510 rows=4 loops=1) │ │ Sort Key: (similarity(vorname, 'Nick'::text)) DESC │ │ Sort Method: quicksort Memory: 25kB │ │ -> HashAggregate (cost=3127.01..3134.88 rows=630 width=18) | | (actual time=32.497..32.503 rows=4 loops=1) │ │ Group Key: vorname │ │ -> Bitmap Heap Scan on kunden (cost=75.75..3122.01 rows=1000 width=6) | | (actual time=5.993..31.447 rows=4045 loops=1) │ │ Recheck Cond: (vorname % 'Nick'::text) │ │ Rows Removed by Index Recheck: 13010 │ │ Heap Blocks: exact=9174 │ │ -> Bitmap Index Scan on vorname_gin_trgm | | (cost=0.00..75.50 rows=1000 width=0) (actual time=4.976..4.976 rows=17055 loops=1) │ │ Index Cond: (vorname % 'Nick'::text) │ │ Planning time: 0.123 ms │ │ Execution time: 32.563 ms │ └──────────────────────────────────────────────────────────────────────────────────────────┘ (13 rows)
Fazit
Dass PostgreSQL nicht von Haus aus alle LIKE-Anfragen per Index beschleunigt, sorgt gerne für Irritationen. Auf der anderen Seite öffnen sich, sobald man anfängt, sich mit dem Thema auseinanderzusetzen, ganz neue Möglichkeiten, die man in dieser Form bei anderen DBMS nicht findet. Und wir haben noch gar nicht über eine echte Volltextsuche gesprochen!
P.S.: pg_trgm kann kein Chinesisch!
Wenn nicht-alphanumerische Buchstaben in’s Spiel kommen (oder pg_trgm zu langsam ist…) sollte man einen Blick auf PGroonga werfen, das in diesen Bereichen glänzt.
Über den Author
Gunnar “Nick” Bluth hat seine Liebe zu relationalen Datenbanken Ende des letzten Jahrtausends entdeckt. Über MS Access und MySQL 3.x landete er sehr schnell bei PostgreSQL und hat nie zurückgeschaut, zumindest nie ohne Schmerzen. Er verdient seine Brötchen seit beinahe 20 Jahren mit FOSS (Administration, Schulungen, Linux, PostgreSQL). Gelegentlich taucht er auch tiefer in die Programmierung ein, so als SQL-Programmierer bei der Commerzbank oder in App-Nebenprojekten
