Index bei Like

[Dumpfbacke]

Hallo Leute,
sagt einmal warum benutze Firebird bei einer Abfrage wie z.B.

Delphi-Quellcode:

Where Strasse like 'Hauptstr%'

keinen Index auch wenn einer vorhanden ist ?

Tanja

[vagtler]

Benutze stattdessen

Code:

Where Strasse starting with 'Hauptstr'

Der Plan bei Einsatz von Like benutzt keinen Index, da der Like-Parameter auch mit einer Wildcard anfangen könnte - und da nützt ein Index nichts.

[Bernhard Geyer]

Zitat:

Zitat von vagtler (Beitrag 1239001)

Benutze stattdessen

Code:

Where Strasse starting with 'Hauptstr'

Der Plan bei Einsatz von Like benutzt keinen Index, da der Like-Parameter auch mit einer Wildcard anfangen könnte - und da nützt ein Index nichts.

Wenn der SQL-Parser so dumm ist (kommt ab und zu bei Oracle vor) dann ist er tiefstes SW-Steinzeit.
Jeder halbwegs vernünftiger Parser wird erkennen ob eine Wildcard am Anfang steht oder nicht.

[himitsu]

Es kommt auch auf die Art des Indizes drauf an.

Einen B-Tree kann man auch teilweise auflösen, also bis zum ersten Wildcard und braucht dann nicht mehr so viel zu durchsuchen.
Ein Hash kann dagegen aber nur komplett aufgelöst benutzt werden.

[Furtbichler]

Zitat:

Zitat von himitsu (Beitrag 1239005)

Es kommt auch auf die Art des Indizes drauf an.
Ein Hash ...

Welches RDBMS verwendet für Indexe den eine Hashtabelle? Ich kenne das nur für schnelle Suchen *ohne* Index.

[himitsu]

Einige DBMS können mehrere Indextypen.

MySQL kann zum BTREE und HASH, je nach verwendeter Speicherengine.


Für reine DupplicateChecks ist eine sortierte Liste der Hashs wohl schneller durchsuchbar, als in einem B-Tree in mehrere Ebenen den passenden Ast zu finden.

[Furtbichler]

Zitat:

Zitat von himitsu (Beitrag 1239016)

...eine sortierte Liste der Hashs...

Bestimmt (imho) keine sortierte Liste von Hashes, denn das müsste auch ein B-Baum sein und wäre auch nicht schneller. Wenn, dann eine Art Hashmap. Da geht das Matchen in O(1), wogegen bei einem B-Baum vom Aufwand O(log n) ist, allerdings mit einer sehr großen Logarithmusbasis: Bei einer Seitengröße von 8k und 4-Byte Key immerhin log zur Basis 2000.

Gut, aber egal: Hash und Sortierung -> geht nicht -> LIKE geht auch nicht.

[dataspider]

Hi,

Firebird sollte hier einen Index verwenden, wenn dieser für das Feld STRASSE definiert ist.

Reinfallen kann man, wenn man hier Parameter verwendet in der Form:

where Strasse like :strasse

und dann den Parameter strasse auf 'Hauptst%' setzt.

Hier kann beim Prepare der Plan nicht ermittelt werden, da nicht klar ist, ob z.B. anstatt

'Hauptsr%' '%Hauptst%' als Wert für den Parameter kommt.


Frank

[EDIT]
Was ich auch schon hatte:
Die Selektivität des Index war irgendwie nicht funktionstüchtig...
Kann man mit
SET STATISTICS INDEX INDEX_NAME
neu berechnen lassen.
[/EDIT]

[Furtbichler]

Zitat:

Zitat von dataspider (Beitrag 1239042)

Reinfallen kann man, wenn man hier Parameter verwendet in der Form:

Code:

where Strasse like :strasse

Das ist aber eine ausgesprochene Schwäche von FB und ein 'fail by design'. Die könnten das Teil auch mit Index kompilieren: Zur Not scant der den Index eben, anstatt den Suchstring anhand der Sortierposition zu finden. Na ja.

[mkinzler]

Das Problem tritt aber auch bei anderen DBMS auf, sogar beim Microsoft SQLServer 2008 R2, dann ist dieser auch schlecht designed.

http://stackoverflow.com/questions/1...erformance-hit

[Bernhard Geyer]

Zitat:

Zitat von dataspider (Beitrag 1239042)

Reinfallen kann man, wenn man hier Parameter verwendet in der Form:

where Strasse like :strasse

und dann den Parameter strasse auf 'Hauptst%' setzt.

Hier kann beim Prepare der Plan nicht ermittelt werden, da nicht klar ist, ob z.B. anstatt

'Hauptsr%' '%Hauptst%' als Wert für den Parameter kommt.

Dann ist hier FB aber sehr mangelhaft implementiert.
In Zeichen von SQL-Injection und Co. sollte alle Abfragen Parametrisiert erfolgen.

Zitat:

Zitat von mkinzler (Beitrag 1239057)

Das Problem tritt aber auch bei anderen DBMS auf, sogar beim Microsoft SQLServer 2008 R2, dann ist dieser auch schlecht designed.
http://stackoverflow.com/questions/1...erformance-hit

Kenn dieses Problem beim MS SQL-Server wenn man varchar und nvarchar mischt. Dann wird oft auf Full-Table-Scan umgeschaltet.
Wenn man konsequent nur nvarchar verwendet ist mir das bisher nicht aufgefallen.

[mkinzler]

Zitat:

Dann ist hier FB aber sehr mangelhaft implementiert.
In Zeichen von SQL-Injection und Co. sollte alle Abfragen Parametrisiert erfolgen.

Ist halt nicht von Microsoft! :stupid:

[dataspider]

Zitat:

Zitat von Furtbichler (Beitrag 1239055)

Zitat:

Zitat von dataspider (Beitrag 1239042)

Reinfallen kann man, wenn man hier Parameter verwendet in der Form:

Code:

where Strasse like :strasse

Das ist aber eine ausgesprochene Schwäche von FB und ein 'fail by design'. Die könnten das Teil auch mit Index kompilieren: Zur Not scant der den Index eben, anstatt den Suchstring anhand der Sortierposition zu finden. Na ja.

Hab ich auch lange drüber nachgedacht. Aber das Prepare ist nun mal vor der Zuweisung der Parameter.
Es ist ja wohl so gedacht, dass bei Benutzung der Parameter nur 1 Mal das Prepare erfolgen soll und nicht bei jeder Neuzuweisung eines Parameterwertes.
Die gewünschte Zeitersparnis geht hier natürlich in die Hose.
Mir würde es anders auch gefallen, aber ob das bei anderen DB' s besser gelöst ist, weiß ich nicht.
Ich bin übrigens schon in diese Falle getappt und Thomas Steinmaurer hat das näher erklärt...


Frank

[Dumpfbacke]

Zitat:

Zitat von vagtler (Beitrag 1239001)

Benutze stattdessen

Code:

Where Strasse starting with 'Hauptstr'

Der Plan bei Einsatz von Like benutzt keinen Index, da der Like-Parameter auch mit einer Wildcard anfangen könnte - und da nützt ein Index nichts.

Das geht leider nicht oder zumindest mein Firebird 2.5 macht es nicht.

[Namenloser]

Zitat:

Zitat von Furtbichler (Beitrag 1239022)

Zitat:

Zitat von himitsu (Beitrag 1239016)

...eine sortierte Liste der Hashs...

Bestimmt (imho) keine sortierte Liste von Hashes, denn das müsste auch ein B-Baum sein und wäre auch nicht schneller. Wenn, dann eine Art Hashmap. Da geht das Matchen in O(1), wogegen bei einem B-Baum vom Aufwand O(log n) ist

Vielleicht eine Hashmap und die einzelnen Buckets noch mal sortiert? Dadurch hat man eine bessere Worst-Case-Laufzeit als bei einer „normalen“ Hashmap.

Sowas war vor 1–2 Jahren mal im Gespräch als bei PHP ein Angriff bekannt wurde, bei dem URL-Parameter so präpariert werden konnten, dass es beim Ablegen der Parameter in einem assoziativen Array (was offenbar bei PHP als Hashmap realisiert ist) möglichst viele Kollisionen gab, mit dem Ergebnis dass man den Server sehr leicht lahmlegen konnte. Ich glaube, die PHP-Entwickler haben es am Ende einfach umgangen, indem sie die maximale Anzahl an Parametern standardmäßig limitiert haben.

[Furtbichler]

Zitat:

Zitat von Smut (Beitrag 1239193)

Furchti nörgelt halt gerne über Firebird... ich denke, er ärgert sich, dass er selbst nicht mit FB arbeitete :oops:

Sag mal, bist Du irgendwie weich in der Birne?

[vagtler]

Zitat:

Zitat von Dumpfbacke (Beitrag 1239181)

[...] Das geht leider nicht oder zumindest mein Firebird 2.5 macht es nicht.

Dann muss es aber wirklich an Deinem Firebird liegen. Schau in die Doku und staune.

[hoika]

Hallo,

starting with
sucht genau, also Groß- und Kleinschreibung wird beachtet.

Heiko

[Furtbichler]

Zitat:

Zitat von Namenloser (Beitrag 1239183)

Vielleicht eine Hashmap und die einzelnen Buckets noch mal sortiert? Dadurch hat man eine bessere Worst-Case-Laufzeit als bei einer „normalen“ Hashmap.

... Bucketsort wird beim -on-the-fly- 'indizieren' verwendet, um kleinere Datenmengen zu sortieren und dadurch ein besseres Ergebnis zu erzielen. Eine Hashmap hat erst einmal keine Buckets, weil nicht klar ist, wie die Hashmap umgesetzt wurde (open hashing vs. separate chaining). Falls sie als separate chainging umgesetzt wurde, sind die einzelnen 'Buckets' bereits sortiert.

PS: Bei PHP wurde offenbar eine Hashmap mit fester Größe verwendet. Die Problematik kann durch eine dynamische Hashmap vermieden werden. Diese würde ihre Größe ggf. (zu viele Kollisionen) einfach verdoppeln. Da dadurch die Hashfunktion verändert wird, sollten die Angriffe ins Leere laufen.

Aber wir kommen vom Thema ab.

[tsteinmaurer]

Generell sieht die Verwendung eines Index auf einem Feld c1 bei LIKE wie folgt aus:

Code:

select * from t1 where c1 like :c1

=> Kein Index, da parametrisierte Abfrage und zum Zeitpunkt des Prepare der Inhalt des Parameters nicht bekannt ist.

Code:

select * from t1 where c1 like '%Hugo'

=> Kein Index, wenn ein Wildcard als Prefix verwendet wird

Code:

select * from t1 where c1 like 'Hugo'

=> Index

Code:

select * from t1 where c1 like 'Hugo%'

=> Index, bei einem Wildcard als Suffix (wird intern ein STARTING WITH)

Code:

select * from t1 where c1 like upper('Hugo')

=> Index

Code:

select * from t1 where upper(c1) like 'Hugo'

=> Kein Index, da temporäres UPPER auf dem Feld. Abhilfe schafft hier ein Expression-Index, der den UPPER-Inhalt indexiert

Es gibt sicher noch andere Kombinationen ... :-D

[Namenloser]

Zitat:

Zitat von Furtbichler (Beitrag 1239242)

Zitat:

Zitat von Namenloser (Beitrag 1239183)

Vielleicht eine Hashmap und die einzelnen Buckets noch mal sortiert? Dadurch hat man eine bessere Worst-Case-Laufzeit als bei einer „normalen“ Hashmap.

... Bucketsort wird beim -on-the-fly- 'indizieren' verwendet, um kleinere Datenmengen zu sortieren und dadurch ein besseres Ergebnis zu erzielen. Eine Hashmap hat erst einmal keine Buckets, weil nicht klar ist, wie die Hashmap umgesetzt wurde (open hashing vs. separate chaining). Falls sie als separate chainging umgesetzt wurde, sind die einzelnen 'Buckets' bereits sortiert.

Meistens wird Separate Chaining verwendet. Und nein, da sind die Einträge normalerweise nicht sortiert, weil das bei einer verketteten Liste auch gar keinen Sinn ergeben würde: Auf einer verketteten Liste kann man keine binäre Suche durchführen. Neue Elemente werden einfach unsortiert am Anfang der Liste eingefügt.

Und von Bucketsort war überhaupt nicht die Rede...?

Zitat:

Zitat von Furtbichler (Beitrag 1239242)

PS: Bei PHP wurde offenbar eine Hashmap mit fester Größe verwendet. Die Problematik kann durch eine dynamische Hashmap vermieden werden. Diese würde ihre Größe ggf. (zu viele Kollisionen) einfach verdoppeln. Da dadurch die Hashfunktion verändert wird, sollten die Angriffe ins Leere laufen.

Je nach Hashfunktion ist es durchaus möglich, dass die Elemente immer noch im selben Bucket landen, egal in welcher Größe die Hashmap (neu-)angelegt wird. Dass die Hashmap von PHP eine konstante Größe hat, kann ich mir ehrlich gesagt auch nicht vorstellen.

[Furtbichler]

Zitat:

Zitat von Namenloser (Beitrag 1239380)

Meistens wird Separate Chaining verwendet. Und nein, da sind die Einträge normalerweise nicht sortiert, weil das bei einer verketteten Liste auch gar keinen Sinn ergeben würde

:thumb: Autschn. Self-Fail :oops:

Zitat:

Zitat von Namenloser (Beitrag 1239380)

Je nach Hashfunktion ist es durchaus möglich, dass die Elemente immer noch im selben Bucket landen, egal in welcher Größe die Hashmap (neu-)angelegt wird.

Na.. eher nicht:

Hashmap hat X Einträge (X=Prim). Hashfunktion = F(Key) Mod X.
Bei Vergrößerung auf Y Einträge (Y=Prim und ca. X*2) ist die Funktion F(Key) Mod Y.

Da dürften nicht die gleichen Kollisionen auftreten... Aber da bin ich kein Spezi.