Index bei Like

[Bernhard Geyer]

Zitat von 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.

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 von himitsu:

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 von himitsu:

...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 von dataspider:

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.

[Bernhard Geyer]

Zitat von dataspider:

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 von 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

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.

[Namenloser]

Zitat von Furtbichler:

Zitat von himitsu:

...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 von Namenloser:

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.