[Erledigt] Gemeinsame Präfixe ermitteln (Vorwahlen von Telefonnummern)

[Blar]

Vor einige Zeit habe ich mir über Wikipedia mal eine Liste von Vorwahlen die es in Deutschland so gibt erstellt. Ziel war es zu einer Telefonnummer die auf einer Seite eingegeben wird, die entsprechenden öffentlichen Informationen zu ermitteln.

http://static.blar.de/vorwahlen_2015-01-08.sql.zip

Der Aufbau der Tabelle ist relativ einfach in folgenden Code. Die Spalte prefix ist für die Vorwahl und in der Spalte title befindet sich ein Titel (Anbietername, Ort, Dienstleistung) zur jeweiligen Vorwahl.

CREATE TABLE vorwahlen (
    prefix VARCHAR(11) NOT NULL DEFAULT '',
    title VARCHAR(128) NOT NULL DEFAULT '',
    PRIMARY KEY (prefix)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

Hier noch ein Beispiel der Daten die sich in der Tabelle befinden, für alle die sich nicht gleich den Dump runterladen und einspielen wollen.

prefix    title
0137      MABEZ - Televoting, Gewinnspiele
01371     MABEZ 14 Cent pro Anruf
0138      T-VoteCall 14 Cent pro Minute
014       unbelegt
015       Mobilfunk
0150      Group 3G
01505     Quam
0151      Telekom Deutschland
01511     Telekom Deutschland
0152      Vodafone
01520     Vodafone

Mit folgendem Query werden dann schon alle gemeinsamen Präfixe ermittelt.

SELECT * FROM vorwahlen WHERE '01379123456789' LIKE CONCAT(prefix, '%');

prefix    title
013       Abstimmungs- und Gewinnspielnummern
0137      MABEZ - Televoting, Gewinnspiele
01379     MABEZ 50 Cent pro Anruf

• Gibt es einen besseren weg, alle gemeinsamen Präfixe zu ermitteln?
• Wie bekommt man nur das längste Präfix?
• Gibt es Vorschläge wie man eine solche Abfrage oder auch den Index optimieren kann um die Abfrage zu beschleunigen?

Die erste Optimierung

Leider ist der Query wie man aus dem Explain (vom letzten Query) erkennen kann relativ langsam, da kein Index benutzt werden kann.

id               1
select_type      SIMPLE
table            vorwahlen
type             ALL
possible_keys    
key              
key_len          
ref              
rows             5670
Extra            Using where

Um das ganze doch noch etwas zu beschleunigen habe ich eine extra Spalte (cache) für den Index erstellt. Da eine Vorwahl in dieser Tabelle mindestens 3 Zeichen lang sein muss, kopiere ich die ersten 3 Zeichen in diese Spalte und setze darauf einen Index.

Die Tabelle sieht dann folgendermassen aus:

CREATE TABLE vorwahlen (
    prefix VARCHAR(11) NOT NULL DEFAULT '',
    cache CHAR(3) NOT NULL DEFAULT '',
    title VARCHAR(128) NOT NULL DEFAULT '',
    PRIMARY KEY (prefix),
    KEY cache (cache) USING BTREE
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

Nun muss auch noch der Query entsprechend angepasst werden, damit der Index verwendet werden kann:

SELECT * FROM vorwahlen WHERE cache = '013' AND '01379123456789' LIKE CONCAT(prefix, '%');

Der Explain mit dem neuen Index:

id               1
select_type      SIMPLE
table            vorwahlen
type             ref
possible_keys    cache
key              cache
key_len          9
ref              const
rows             13
Extra            Using index condition

Wie man jetzt sieht, ist der Query durch den Index schon deutlich besser, da nur noch 13 anstatt 5670 Zeilen gelesen werden müssen um ein Ergebnis von 3 Zeilen zu erstellen.

[Blar]

Wie bekommt man nur das längste Präfix?

Das ermitteln des längsten Präfix geht natürlich per

SELECT * FROM vorwahlen WHERE cache = '013' AND '01379123456789' LIKE CONCAT(prefix, '%') ORDER BY LENGTH(prefix) DESC LIMIT 1;

Die Frage hatte natürlich auch darauf abgezielt, ob es hier einen besseren Weg gibt.

[akretschmer]

Das ermitteln des längsten Präfix geht natürlich per

SELECT * FROM vorwahlen WHERE cache = '013' AND '01379123456789' LIKE CONCAT(prefix, '%') ORDER BY LENGTH(prefix) DESC LIMIT 1;

Die Frage hatte natürlich auch darauf abgezielt, ob es hier einen besseren Weg gibt.

Ja, index-basiert mit pg_trgm. PostgreSQL. http://dba.stackexchange.com/questio...longest-prefix

[Phpyton]

Für diesen Fall würde sich Caching ideal eignen. Das würde Optimierung bringen.