Trickkiste: Umkreissuche

[akretschmer]

Stellt Euch vor: ihr habt eine Datenbank mit 100000 Artikeln. Nun sucht ihr ein Artikel, der 'um die 50 Euro' kosten soll - also entweder knapp unter oder knapp über 50 Euro. Wie sucht man sowas effektiv?

Wikipedia kennt dafür KNN: http://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm

PostgreSQL kennt das auch ;-)

test=# create table artikel as select s as id, random() * 1000 as preis from generate_series(1,100000) s;
SELECT 100000
Time: 177,276 ms
test=*# create index idx_preis on artikel using gist (preis);
CREATE INDEX
Time: 1743,776 ms
test=*# analyse artikel;
ANALYZE
Time: 52,840 ms
test=*# explain analyse select * from artikel order by 50 <-> preis limit 5;
  QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.28..0.58 rows=5 width=12) (actual time=0.190..0.199 rows=5 loops=1)
  ->  Index Scan using idx_preis on artikel  (cost=0.28..6056.28 rows=100000 width=12) (actual time=0.189..0.198 rows=5 loops=1)
  Order By: (preis <-> 50::double precision)
 Total runtime: 0.230 ms
(4 rows)

Time: 0,572 ms
test=*# select * from artikel order by 50 <-> preis limit 5;
  id  |  preis
-------+------------------
 91560 | 49.9983592890203
 73813 |  49.995846580714
 12922 | 49.9917855486274
 37169 | 50.0118038617074
 65564 | 49.9865873716772
(5 rows)

PG kann das natürlich auch auf Geodaten anwenden: suche mir, ausgehend von meinem Standort, die nächsten Geldautomaten, Gaststätten oder Kinos. Indexbasierte Umkreissuche - eine sehr coole Sache!

 

[ukulele]

Klingt interessant aber wenn ich einen Preis "um die 50 Euro" suche geht das auch mit BETWEEN und / oder ORDER BY.

DECLARE    @i DECIMAL(10,2)

SET        @i = 50

SELECT    TOP 10 Gesamtkosten --TOP ist optional
FROM    datev_dbauftraege
WHERE    Gesamtkosten BETWEEN ( @i * 0.9 ) AND ( @i * 1.1 ) --BETWEEN ist auch optional
ORDER BY abs(@i - Gesamtkosten) --abs() wandelt negative Werte in positive

 

[akretschmer]

Klingt interessant aber wenn ich einen Preis "um die 50 Euro" suche geht das auch mit BETWEEN und / oder ORDER BY.

DECLARE    @i DECIMAL(10,2)

SET        @i = 50

SELECT    TOP 10 Gesamtkosten --TOP ist optional
FROM    datev_dbauftraege
WHERE    Gesamtkosten BETWEEN ( @i * 0.9 ) AND ( @i * 1.1 ) --BETWEEN ist auch optional
ORDER BY abs(@i - Gesamtkosten) --abs() wandelt negative Werte in positive

Sicher, aber bei BETWEEN muß Du Dir ja erst einmal Grenzen überlegen. Diese können zu klein sein, dann mußt das noch mal machen, mit größeren Grenzen. Oder sie sind zu groß - dann dauert die Abfrage entsprechend lang. Und ORDER BY ist auch doof: dann mußt da 2 Abfragen machen, einmal mit kleiner 50 order desc und einmal über 50 order asc.

Diese Umkreissuche so eingesetzt ist eigentlich auch nur 'Abfall' einer geografischen Umkreissuche, die (exakte) Berechnung der Entfernung ausgehend von z.B. dem aktuellen Standpunkt zur nächsten Tanke, Kneipe oder $whatever ist relativ aufwendig. Mit dieser indexbasierten Suche geht das extrem schnell.

Soweit ich weiß, war/ist PostgreSQL/PostGIS die einzige DB, die das kann.

 

[ukulele]

Und ORDER BY ist auch doof: dann mußt da 2 Abfragen machen, einmal mit kleiner 50 order desc und einmal über 50 order asc.

Nicht ganz, durch abs() werden alle Werte positiv. Die Nähe zum Ausgangswert ist also absolut und die Einträge stehen in der richtigen Reihenfolge. BETWEEN ist natürlich nur eine Einschränkung und könnte auch ganz entfallen.

Diese Umkreissuche [...] ist relativ aufwendig. Mit dieser indexbasierten Suche geht das extrem schnell.

Ja das stimmt sicherlich. Grade bei GEO Koordinaten wirds interessant. Aber um nach einem ähnlichen Preis zu suchen sollte auch eine ORDER BY Variante mit Index auf der Preisspalte herhalten können. Betrachte es als Ergänzung