12. Oktober 2009

LIKE-Abfragen und Indizes: Geht das ..:?

English title: LIKE queries and indexes ...

Dass man mit dem LIKE-Operator eine Wildcard-Suche durchführen kann, ist hinreichend bekannt. Interessant wird es, wenn man sich fragt, wie das denn mit der Indizierung aussieht. Dazu ein Beispiel anhand der Tabelle EMP:
Everyone knows that the LIKE operator allows wildcard searches within SQL. The interesting thing is when it's about indexes. We'll start with an example based on the EMP table.
SQL> create index idx_ename on emp (ename);

Index created.

SQL> select * from emp where ename like 'K%';

EMPNO ENAME      JOB         MGR HIREDATE   SAL  COMM DEPTNO
----- ---------- --------- ----- -------- ----- ----- ------
 7839 KING       PRESIDENT       17.11.81  5000           10
Hierfür kann ein Index genutzt werden, wie der Ausführungsplan zeigt
This query can be executed using an index - as the execution plan indicates.
-----------------------------------------------------------------------------------------
| Id  | Operation                   | Name      | Rows  | Bytes | Cost (%CPU)| Time     |
-----------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT            |           |       |       |     2 (100)|          |
|   1 |  TABLE ACCESS BY INDEX ROWID| EMP       |     1 |    87 |     2   (0)| 00:00:01 |
|*  2 |   INDEX RANGE SCAN          | IDX_ENAME |     1 |       |     1   (0)| 00:00:01 |
-----------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   2 - access("ENAME" LIKE 'K%')
       filter("ENAME" LIKE 'K%')
Das ist klar, denn die Wildcard steht am Ende. Da der Anfang des Suchstrings feststeht, kann der Index genutzt werden. Probieren wir es mal andersherum ...
That's abvious since the beginning of the search string is a literal - the wildcard is at the end. So the optimizer chooses an index range scan to speed up query execution. The next example is the other way around: The wildcard is now at the beginning of the search string.
SQL> select * from emp where ename like '%G';

EMPNO ENAME      JOB         MGR HIREDATE   SAL  COMM DEPTNO
----- ---------- --------- ----- -------- ----- ----- ------
 7839 KING       PRESIDENT       17.11.81  5000           10

1 row selected.

SQL> select * from table(dbms_xplan.display_cursor());

--------------------------------------------------------------------------
| Id  | Operation         | Name | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |      |       |       |     3 (100)|          |
|*  1 |  TABLE ACCESS FULL| EMP  |     1 |    87 |     3   (0)| 00:00:01 |
--------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   1 - filter("ENAME" LIKE '%G')
Naja und auch das ist klar; da der Anfang des Suchstrings nicht bekannt ist, kann die Datenbank den Index gar nicht nutzen. Ein Full-Table-Scan ist das einzige, was bleibt ...
And that's also obvious: When the search string starts with a wildcard the optimizer just cannot use the index - where should it enter the index tree ...? So a full table scan is the only option.
Wirklich das einzige? Es gäbe noch die Moglichkeit, mit einem function-based Index zu arbeiten. Dazu brauchen wir zunächst eine Funktion, die uns den String "umdreht".
Really? Function Based indexes might be another approach. For this we firstly need a function which "reverses" a string.
create or replace function string_reverse (
  p_string in varchar2
) return varchar2 deterministic is
  v_revstring varchar2(32767);
begin
  for i in reverse 1..length(p_string) loop
    v_revstring := v_revstring || substr(p_string, i, 1);
  end loop;
  return v_revstring;
end;
/
Wichtig ist das Schlüsselwort deterministic. Damit deklarieren wir explizit, dass diese Funktion bei gleichen Eingabeparametern das gleiche Ergebnis zurückliefert. Das ist ein wichtig für den Optimizer. Als nächstes kommt nun ein funktionsbasierter Index auf die Spalte ENAME im Zusammenspiel mit dieser Funktion.
The keyword deterministic is important here. This declared explicitly that the function returns the equal values for equal input parameters. This is important for the optimizer. The next step is to create the function based index on the ENAME column using this new function.
SQL> create index idx_ename_rev on emp (string_reverse(ename));

Index created.
Nun probieren wir das aus. Die obige Abfrage kann den Index nicht nutzen, man kann sie aber nun sinngemäß wie folgt umschreiben ... demnach ist ...
Now it's about testing this setup. The above query still cannot use the index but we could now rewrite the query - so the above query ...
SQL> select * from emp where ename like '%G';
... das gleiche wie ...
... is the same as this one ...
SQL> select * from emp where string_reverse(ename) like string_reverse('%G');
Letzteres kann allerdings nun einen Index nutzen, wie der Ausführungsplan zeigt:
And the latter one can use the new function based index - as the execution plan shows.
---------------------------------------------------------------------------------------------
| Id  | Operation                   | Name          | Rows  | Bytes | Cost (%CPU)| Time     |
---------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT            |               |     1 |  2089 |     2   (0)| 00:00:01 |
|   1 |  TABLE ACCESS BY INDEX ROWID| EMP           |     1 |  2089 |     2   (0)| 00:00:01 |
|*  2 |   INDEX RANGE SCAN          | IDX_ENAME_REV |     1 |       |     1   (0)| 00:00:01 |
---------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   2 - access("SCOTT"."STRING_REVERSE"("ENAME") LIKE "STRING_REVERSE"('%G'))
       filter("SCOTT"."STRING_REVERSE"("ENAME") LIKE "STRING_REVERSE"('%G'))
Man sieht also, dass man auch LIKE-Abfragen mit Wildcards am Anfang recht einfach beschleunigen kann. Was allerdings nicht mehr geht, wäre eine Wildcard am Anfang und am Ende (LIKE '%IN%'). Wenn Ihr sowas in großen Datenmengen braucht, wäre eher ein Volltextindex angedacht - dazu findet Ihr im Blog oracle-text-de.blogspot.com mehr Informationen.
So LIKE queries can also use an index - with function based indexes. The next step would then be a LIKE query having wildcards at the beginning as well as at the end (e.g. LIKE '%IN%'. But this case cannot be solved with this technology: If you need index support for such queries on larger data sets you might consider Oracle TEXT - the blog oracle-text-de.blogspot.com (in german) contains more information about this technology.

Kommentare:

Chris hat gesagt…

Genau genommen gibt es noch den FAST FULL SCAN:

gDEV>create table t as select * from scott.emp;

Tabelle wurde erstellt.

gDEV>create index t_ix1 on t(ename);

Index wurde erstellt.

gDEV>set autotrace traceonly
gDEV>select --+index_ffs(t,t_ix1)
2 *
3 from t
4 where ename like '%G';


1 Zeile wurde ausgewdhlt.


Ausf|hrungsplan
----------------------------------------------------------
Plan hash value: 2519616399

-------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
-------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 1 | 87 | 2 (0)| 00:00:01 |
| 1 | TABLE ACCESS BY INDEX ROWID| T | 1 | 87 | 2 (0)| 00:00:01 |
|* 2 | INDEX FULL SCAN | T_IX1 | 1 | | 1 (0)| 00:00:01 |
-------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

2 - filter("ENAME" LIKE '%G')

Note
-----
- dynamic sampling used for this statement


Statistiken
----------------------------------------------------------
0 recursive calls
0 db block gets
3 consistent gets
0 physical reads
0 redo size
725 bytes sent via SQL*Net to client
346 bytes received via SQL*Net from client
2 SQL*Net roundtrips to/from client
0 sorts (memory)
0 sorts (disk)
1 rows processed

Anonym hat gesagt…

und warum nicht ohne PL/SQL?

create index i1 on emp reverse(ename);

select * from emp where ename like reverse('G%');

Ahoi Daniel

Carsten Czarski hat gesagt…

Hallo Daniel,

das geht schon - "REVERSE" ist aber eine undokumentierte Funktion ... darauf wollte ich das Posting nicht aufbauen ...

Grüße

-Carsten

Beliebte Postings