Effizientes Prefix-Matching

Hallo,

ich habe eine Tabelle, in der Kennzahlen stehen, denen dann natürlich irgendwelche Daten zugeordnet sind, z.B. so:

CREATE TABLE car_wabe 
(
  digits text,
  value  text
);
 
INSERT INTO car_wabe(digits, value) VALUES ('47111', 'network station 47111');
INSERT INTO car_wabe(digits, value) VALUES ('47112', 'network station 47112');
INSERT INTO car_wabe(digits, value) VALUES ('77',    'external node 77');
INSERT INTO car_wabe(digits, value) VALUES ('78',    'external node 78');
 
 digits |         value
--------+-----------------------
 47111  | network station 47111
 47112  | network station 47112
 77     | external node 77
 78     | external node 78

Gesucht werden soll jetzt nach Ziffernfolgen, deren Prefix mit einem Prefix meiner Kennzahlen übereinstimmt, die aber länger oder kürzer sein können.

So möchte ich
a) bei einer Suche nach “4711” die Einträge “network station 47111” und “network station 47112” finden,
b) bei einer Suche nach “77100” den Eintrag “external node 77”


Also Lösung eingefallen ist mir folgendes:

SELECT * FROM car_wabe WHERE (digits LIKE '471%')   OR (471    LIKE digits || '%');
 
 digits |         value
--------+-----------------------
 47111  | network station 47111
 47112  | network station 47112
 
 
SELECT * FROM car_wabe WHERE (digits LIKE '77100%') OR (77100  LIKE digits || '%');
 
 digits |      value
--------+------------------
 77     | external node 77

Da das ganze aber oft ausgeführt werden wird, sollte es auch möglichst schnell gehen. Obwohl ich einen Index definiert habe [CREATE INDEX car_wabe_pattern_index ON car_wabe(digits text_pattern_ops);] sagt mir EXPLAIN aber, dass ein SequentialScan gemacht wird:

explain SELECT * FROM car_wabe WHERE (digits LIKE '^471%')   OR (471    LIKE '^' || digits || '%') LIMIT 2;
------------------------------------------------------------------------------------------------------
 Limit  (cost=0.00..2.35 rows=2 width=34)
   ->  Seq Scan on car_wabe  (cost=0.00..116.18 rows=99 width=34)
         Filter: ((digits ~~ '^471%'::text) OR ('471'::text ~~ (('^'::text || digits) || '%'::text)))

Immerhin wird wohl nicht die ganze Tabelle durchsucht, aber eine Laufzeit von 90ms für eine Abfrage in einer Tabelle mit 4000 Einträgen ist für die Anwendung wohlmöglich kritisch.

Kann man da noch was beschleunigen?

Danke im Voraus,
Rüdiger

Mal abgesehen davon, daß ohne ’ um die Ziffern nach dem OR das nicht funzt, glaube ich nicht, daß es mit einem Index zu erschlagen ist. Index hilft nur für:

test=*# \d car_wabe
  Table "public.car_wabe"
 Column | Type | Modifiers
--------+------+-----------
 digits | text |
 value  | text |
Indexes:
    "idx2_car" btree (lower(digits) text_pattern_ops)

test=*# explain SELECT * FROM car_wabe WHERE lower(digits) ~ '^77100' ;
                                           QUERY PLAN
------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on car_wabe  (cost=10.83..310.75 rows=250 width=49)
   Filter: (lower(digits) ~ '^77100'::text)
   ->  Bitmap Index Scan on idx2_car  (cost=0.00..10.76 rows=250 width=0)
         Index Cond: ((lower(digits) ~>=~ '77100'::text) AND (lower(digits) ~<~ '77101'::text))
(4 rows)

aber das liefert Dir ja nicht das gewünschte. Sorry.

Andreas

Schade, aber immerhin wegen der ’ noch was gelernt (dieses Beispiel funktioniert nämlich auch ohne ', warum auch immer).

Rüdiger

Welche Version? Ich habe 8.3, und da sind automatische Casts entfallen.

Andreas

Aha, da hätte ich also schonmal ein schönes konkretes Beispiel für etwas was schiefläuft, wenn man von 8.2.4 aus mal hochrüstet. Natürlich nur bei fehlerhaftem Code, aber den soll’s ja ab und an geben …