LIKE-Filter indizieren


LIKE-Filter führen immer wieder zu überraschendem Performance-Verhalten, weil manche Suchbegriffe eine effiziente Index-Nutzung verhindern können. Das heißt, es gibt Suchbegriffe, die sehr gut indiziert werden können, andere hingegen nicht. Den Ausschlag macht die Position der Wildcard-Zeichen.

Die folgende Abfrage verwendet das Wildcard-Zeichen „%“ mitten im Suchbegriff:

SELECT first_name, last_name, date_of_birth
  FROM employees
 WHERE UPPER(last_name) LIKE 'WIN%D'
DB2
Explain Plan
----------------------------------------------------
ID | Operation         |                 Rows | Cost
 1 | RETURN            |                      |   13
 2 |  FETCH EMPLOYEES  |     1 of 1 (100.00%) |   13
 3 |   IXSCAN EMP_NAME | 1 of 10000 (   .01%) |    6

Predicate Information
 3 - START ('WIN....................................
      STOP (Q1.LAST_NAME <= 'WIN....................
      SARG (Q1.LAST_NAME LIKE 'WIN%D')

Für dieses Beispiel wurde die Abfrage wie folgt geändert: WHERE last_name LIKE 'WIN%D' (kein UPPER). Es scheint, als könnte DB2 LUW 10.5 keine Zugriffsprädikate nutzten, die aus LIKE-Ausdrücken kommen, wenn ein funktions-basierter Index genutzt wird (macht bestenfalls einen full index scan).

Ansonsten sticht DB2 hier positiv hervor: es zeigt ganz klar, dass nur der Teil vor dem ersten Wildcard-Zeichen als START und STOP-Bedingungen herangezogen werden können. Auch die neuerliche Prüfung gegen den vollständigen LIKE-Ausdruck wird als Filterprädikat angezeigt.

MySQL
+----+-----------+-------+----------+---------+------+-------------+
| id | table     | type  | key      | key_len | rows | Extra       |
+----+-----------+-------+----------+---------+------+-------------+
|  1 | employees | range | emp_name | 767     |    2 | Using where |
+----+-----------+-------+----------+---------+------+-------------+
Oracle
---------------------------------------------------------------
|Id | Operation                   | Name        | Rows | Cost |
---------------------------------------------------------------
| 0 | SELECT STATEMENT            |             |    1 |    4 |
| 1 |  TABLE ACCESS BY INDEX ROWID| EMPLOYEES   |    1 |    4 |
|*2 |   INDEX RANGE SCAN          | EMP_UP_NAME |    1 |    2 |
---------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   2 - access(UPPER("LAST_NAME") LIKE 'WIN%D')
       filter(UPPER("LAST_NAME") LIKE 'WIN%D')
PostgreSQL
                       QUERY PLAN
----------------------------------------------------------
Index Scan using emp_up_name on employees
   (cost=0.01..8.29 rows=1 width=17)
   Index Cond: (upper((last_name)::text) ~>=~ 'WIN'::text)
           AND (upper((last_name)::text) ~<~  'WIO'::text)
       Filter: (upper((last_name)::text) ~~ 'WIN%D'::text)

Eine LIKE-Bedingung kann nur die Zeichen vor dem ersten Wildcard-Zeichen beim Durchwandern des Indexbaumes nutzen. Alle anderen Zeichen sind lediglich Filterprädikate, die den durchsuchten Indexbereich nicht einschränken. Eine einzige LIKE-Bedingung kann also zwei Prädikat-Typen beinhalten: (1) den Teil vor dem ersten Wildcard-Zeichen als Zugriffsprädikat; (2) alle weiteren Zeichen als Filterprädikat.

Achtung

Bei PostgreSQL muss man eventuell eine Operator-Class (z. B. varchar_pattern_ops) angeben, damit LIKE-Bedingungen als Zugriffsprädikate genutzt werden können. Siehe „Operator Classes and Operator Families“ in der PostgreSQL-Dokumentation.

Je selektiver der Teil vor dem ersten Wildcard-Zeichen ist, desto kleiner ist der durchsuchte Indexbereich. Das wiederum macht die Index-Suche schneller. Abbildung 2.4 stellt dieses Verhältnis mit drei LIKE-Suchen dar. Alle drei selektieren denselben Eintrag. Dennoch ist die Größe des durchsuchten Indexbereiches – und damit auch die Performance – sehr unterschiedlich.

Abbildung 2.4. Unterschiedliche LIKE-Suchen


Der erste Suchbegriff hat nur zwei Zeichen vor dem Wildcard. Dadurch wird der durchsuchte Indexbereich auf 18 Einträge begrenzt. Nur einer davon entspricht dem vollständigen LIKE-Filter – die restlichen 17 Einträge werden zwar geladen, aber verworfen. Der zweite Suchbegriff hat einen längeren Präfix, der den durchsuchten Indexbereich von vornherein auf zwei Einträge eingeschränkt. Mit diesem Suchbegriff wird nur eine Zeile gelesen, die nicht im Endergebnis aufscheint. Beim letzten Suchbegriff gibt es überhaupt kein Filterprädikat. Es wird nur der Eintrag gelesen, der dem vollständigen LIKE-Filter entspricht.

Wichtig

Nur der Teil vor dem ersten Wildcard-Zeichen kann als Zu­griffs­prä­di­kat genutzt werden.

Die Zeichen danach können den durchsuchten Indexbereich nicht schmälern – sie verwerfen nur die Einträge, die nicht passen.

Natürlich gibt es auch den umgekehrten Grenzfall: einen LIKE-Filter, der mit einem Wildcard-Zeichen beginnt. Dann entfällt das Zugriffsprädikat. Die Datenbank muss die ganze Tabelle durchsuchen, wenn es keine anderen, indizierten, Bedingungen in der where-Klausel gibt.

Tipp

Vermeide LIKE-Bedingungen mit führendem Wildcard ('%BEGRIFF').

Die Position der Wildcards im Suchbegriff beeinflusst also die Indexwahl – zumindest theoretisch. In der Praxis erstellt der Optimizer aber einen generischen Ausführungsplan, wenn der Suchbegriff über einen Bind-Parameter angegeben wird. Dann muss der Optimizer raten, ob die Abfrage mehrheitlich mit führendem Wildcard-Zeichen ausgeführt wird, oder nicht.

Die passende Tasse zu dieser Website findest du in unserem Shop.
Sieht gut aus und unterstützt meine Arbeit hier.

Die meisten Datenbanken gehen bei einem LIKE-Filter mit Bind-Parameter davon aus, dass der Suchbegriff kein Wildcard-Zeichen am Anfang stehen hat. Das ist aber falsch, wenn die LIKE-Bedingung für eine Volltext-Suche verwendet wird. Es gibt leider keine direkte Möglichkeit, eine LIKE-Suche mit Bind-Parameter als Volltext-Suche zu kennzeichnen. Der Kasten „Volltext-Suchen statisch kennzeichnen“ zeigt einen Versuch, der nicht funktioniert. Die naheliegendste Lösung wäre, den Suchbegriff ohne Bind-Parameter anzugeben. Das führt aber nicht nur zu erhöhtem Optimierungsaufwand, sondern öffnet auch eine SQL-Injection-Schwachstelle. Eine effektive und dennoch sichere und portable Lösung ist, die LIKE-Bedingung absichtlich zu verschleiern. „Spalten zusammenfügen“ geht genauer darauf ein.

Volltext-Suchen statisch kennzeichnen

Für eine Volltext-Suche mit LIKE-Operator könnte man die Wildcards von den Suchbegriffen trennen:

WHERE text_column LIKE '%' || ? || '%'

Die Wildcards stehen direkt in der SQL-Anweisung, der Suchbegriff wird aber über einen Bind-Parameter angegeben. Die Datenbank selbst fügt die Teile mit dem Verbindungs-Operator || (Oracle, PostgreSQL) zum endgültigen LIKE-Filter zusammen. Obwohl ein Bind-Parameter verwendet wird, kann der Suchbegriff nur mit einem Wildcard-Zeichen beginnen. Die Datenbanken erkennen das aber nicht.

Bei PostgreSQL steht man vor einem anderen Problem, weil diese Datenbank für LIKE-Suchen mit Bind-Parameter immer ein führendes Wildcard-Zeichen annimmt. Daher verwendet PostgreSQL in diesem Fall keinen Index. Nur wenn man dem Optimizer den konkreten Suchbegriff zur Verfügung stellt, kann PostgreSQL eine LIKE-Bedingung mit einem Indexzugriff optimieren. Wenn man auf den Bind-Paramter verzichtet und den Suchbegriff direkt in die SQL-Anweisung schreibt, muss man natürlich andere Vorsichtsmaßnahmen gegen SQL-Injections treffen.

Selbst wenn der Ausführungsplan für eine LIKE-Bedingung mit führendem Wildcard-Zeichen ausgelegt ist, kann die Performance noch immer unzureichend sein. Dann kann man immer noch auf andere Bedingungen der where-Klausel zurückgreifen – siehe „Index-Filterprädikate gezielt einsetzen“. Wenn es keinen anderen Zugriffsweg gibt, könnte einer der folgenden, proprietären Volltext-Indizes helfen.

DB2

DB2 unterstützt das contains Schlüsselwort. Siehe „DB2 Text Search tutorial“ bei IBM developerWorks.

MySQL

MySQL verwendet die Schlüsselwörter match und against zur Volltext-Suche. Ab MySQL Version 5.6 kann man Volltext-Indizes auch auf InnoDB-Tabellen anlegen, davor nur auf MyISAM. Siehe „Full-Text Search Functions“ in der MySQL-Dokumentation.

Oracle

Die Oracle Datenbank unterstützt das Schlüsselwort contains. Siehe „Oracle Text Application Developer’s Guide.“

PostgreSQL

PostgreSQL verwendet den Operator @@ für Volltext-Suchen. Siehe „Full Text Seach“ in der PostgreSQL-Dokumentation.

Alternativ kann man die WildSpeed-Erweiterung verwenden, um LIKE-Bedingungen direkt zu optimieren. Dafür wird der indizierte String um jeweils ein Zeichen verschoben, damit jedes Zeichen einmal am Anfang steht. Der indizierte String wird also nicht nur einmal im Index abgelegt, sondern einmal pro Zeichen. Ein WildSpeed-Index kann also sehr groß werden.

SQL Server

SQL Server unterstützt das Schlüsselwort contains. Siehe „Volltextsuche“ („Full-Text Seach“) in der SQL Server-Dokumentation.

Denksport

Wie kann man eine LIKE-Suche indizieren, die nur ein Wildcard-Zeichen am Beginn des Suchbegriffes hat ('%BEGRIFF')?

Wenn dir gefällt, wie ich die Dinge erkläre, wirst du meine Kurse lieben.

Über den Autor

Photo of Markus Winand
Markus Winand stimmt Entwickler auf SQL-Performance ein. Er hat das Buch SQL Performance Explained veröffentlicht und bietet inhouse Schulungen sowie Tuning-Leistungen auf http://winand.at/ an.