Ideen fuer best (oder longest) match?

Eine Fragestellung, die man ab und zu mal findet, ist die Suche nach
einem best match oder longest match: Gesucht sei der laengste
Eintrag, der mit dem Anfang der Suchworts ueberstimmt.

Zur Illustration:

> CREATE TABLE data (
id INTEGER UNSIGNED NOT NULL AUTO_INCREMENT PRIMARY KEY,
elem VARCHAR(255) NOT NULL
);

> INSERT INTO data (elem) VALUES
('a'), ('abc'), ('abcdef'), ('abcxyz'), ('d'), ('def');

> SELECT id, elem FROM data WHERE elem = LEFT('abcde', LENGTH(elem))
ORDER BY LENGTH(elem) DESC LIMIT 1;
+----+------+
| id | elem |
+----+------+
| 2 | abc |
+----+------+
1 row in set (0.00 sec)

> SELECT id, elem FROM data WHERE 'abcde' LIKE CONCAT(elem, '%')
ORDER BY LENGTH(elem) DESC LIMIT 1;
+----+------+
| id | elem |
+----+------+
| 2 | abc |
+----+------+
1 row in set (0.02 sec)


Beide Queries sind natuerlich vollkommen Index-lose Table-Scans (was
nicht daran liegt, dass auf elem kein Index existiert, sondern
einfach technisch nicht anders geht).

Gibt's irgendwelche best practices, wie man derartiges effizient auch
bei grossen Tabellen hinbekommt (ausser die ganze Tabelle in den
Speicher zu schluerfen, die einzelnen Feldinhalte zeichenweise in
einen Baum zu verpointern und dann flink mit allen Anfragen dort
entlangzusaussen)?

Halbwegs sinnvoll kaeme mir noch ein generierter Query

SELECT id, elem FROM data
WHERE elem IN ('a', 'ab', 'abc', 'abcd', 'abcde')
ORDER BY LENGTH(elem) DESC LIMIT 1;

vor, da koennte ein Index drauf packen, aber so richtig huebsch ist
das bei laengeren Strings natuerlich auch nicht ...

Es kann auch ruhig ein anderes Datenmodell sein (eine winzige
Optimierung waere ja z.B., LENTH(elem) direkt als getrennte Spalte
vorzuhalten - ob das wirklich was bringt, sei dahingestellt)

Helgolandshut (was: Ideen fuer best (oder longest) match?)

Sven Paulus wrote:
> Eine Fragestellung, die man ab und zu mal findet, ist die Suche nach
> einem best match oder longest match: Gesucht sei der laengste
> Eintrag, der mit dem Anfang der Suchworts ueberstimmt.


Nicht ganz zum Thema, aber fast:
http://jan.kneschke.de/blog/19 -- Helgolandshut

> Es kann auch ruhig ein anderes Datenmodell sein (eine winzige
> Optimierung waere ja z.B., LENTH(elem) direkt als getrennte Spalte
> vorzuhalten - ob das wirklich was bringt, sei dahingestellt)

Das ist das, was Jan dazu einfällt.

Kris

Re: Ideen fuer best (oder longest) match?

Sven Paulus wrote:

> Eine Fragestellung, die man ab und zu mal findet, ist die Suche nach
> einem best match oder longest match: Gesucht sei der laengste
> Eintrag, der mit dem Anfang der Suchworts ueberstimmt.

Kenn ich aus dem Telco-Bereich zum matchen von Telefonnummern mit
Tarifzonen:
41 = Switzerland
411 = Switzerland, Zurich
4122 = Switzerland, Geneva
4174 = Switzerland, Mobile

41223456789 gibt zwei passende Tarifzonen, die längere ist die gesuchte.

> Halbwegs sinnvoll kaeme mir noch ein generierter Query
>
> SELECT id, elem FROM data
> WHERE elem IN ('a', 'ab', 'abc', 'abcd', 'abcde')
> ORDER BY LENGTH(elem) DESC LIMIT 1;
>
> vor, da koennte ein Index drauf packen, aber so richtig huebsch ist
> das bei laengeren Strings natuerlich auch nicht ...

Nicht hübsch, aber vermutlich mit SQL nicht einfacher zu machen und das
sollte auch effizient über einen Index gehen. Was willst du mehr,
solange du nur *einen* String suchst?

> Es kann auch ruhig ein anderes Datenmodell sein (eine winzige
> Optimierung waere ja z.B., LENTH(elem) direkt als getrennte Spalte
> vorzuhalten - ob das wirklich was bringt, sei dahingestellt)

Ich kenn das Problem mit mehreren Tausend Tarifcodes und Millionen
Telefonnummern, da gibt ein Join über LIKE oder Substring einen hübschen
Cross-Join :-)
Ich hatte damals diverse Möglichkeiten (mit Teradata) durchgetestet,
wenn's dich interessiert, kannst du dich ja mal bei mir melden...

Dieter