Information ausblenden
Willkommen im Forum für alle Datenbanken! Registriere Dich kostenlos und diskutiere über DBs wie Mysql, MariaDB, Oracle, Sql-Server, Postgres, Access uvm

Trickkiste: Umkreissuche

Dieses Thema im Forum "PostgreSQL" wurde erstellt von akretschmer, 2 Dezember 2013.

  1. akretschmer

    akretschmer Datenbank-Guru

    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 ;-)

    Code:
    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!
     
  2. ukulele

    ukulele Datenbank-Guru

    Klingt interessant aber wenn ich einen Preis "um die 50 Euro" suche geht das auch mit BETWEEN und / oder ORDER BY.
    Code:
    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
     
  3. akretschmer

    akretschmer Datenbank-Guru

    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.
     
  4. ukulele

    ukulele Datenbank-Guru

    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.

    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 :)
     
    akretschmer gefällt das.
Die Seite wird geladen...

Diese Seite empfehlen

  1. Diese Seite verwendet Cookies. Wenn du dich weiterhin auf dieser Seite aufhältst, akzeptierst du unseren Einsatz von Cookies.
    Information ausblenden