wie man 20 nächstgelegene Punkte effizient findet [geschlossen]

9

Angenommen, ich möchte 20 nächstgelegene Unternehmen in meiner Nähe finden.

My table structure is like this:

    BusinessID  varchar(250)    utf8_unicode_ci         No  None        Browse distinct values  Change  Drop    Primary     Unique  Index   Fulltext
    Prominent   double          No  None        Browse distinct values  Change  Drop    Primary     Unique  Index   Fulltext
    LatLong     point           No  None        Browse distinct values  Change  Drop    Primary     Unique  Index   Fulltext
    FullTextSearch  varchar(600)    utf8_bin        No  None        Browse distinct values  Change  Drop    Primary     Unique  Index   Fulltext
With selected: Check All / Uncheck All With selected:
Print viewPrint view Propose table structurePropose table structureDocumentation
Add new fieldAdd field(s) At End of Table At Beginning of Table After
Indexes: Documentation
Action  Keyname Type    Unique  Packed  Field   Cardinality Collation   Null    Comment
Edit    Drop    PRIMARY BTREE   Yes No  BusinessID  1611454 A       
Edit    Drop    Prominent   BTREE   No  No  Prominent   0   A       
Edit    Drop    LatLong BTREE   No  No  LatLong (25)    0   A       
Edit    Drop    sx_mytable_coords   SPATIAL No  No  LatLong (32)    0   A       
Edit    Drop    FullTextSearch  FULLTEXT    No  No  FullTextSearch  0           

Es gibt 1,6 Millionen Geschäfte. Natürlich ist es dumm, die Entfernung für alle zu berechnen und sie dann zu sortieren.

Hier setzt der georäumliche Index an, oder?

Welchen SQL-Befehl muss ich also umsetzen?

Hinweis:

  1. Ich verwende MySQL Myisam räumlichen Index. Dies habe ich jedoch vorher nicht angegeben. Also werde ich diejenigen akzeptieren, die darauf antworten, um meine Wertschätzung zu zeigen und eine andere Frage zu stellen.
  2. Ich möchte nicht die Entfernung für die gesamte Tabelle berechnen
  3. Ich möchte keine Entfernung für eine Region berechnen, die noch ineffizient ist
  4. Ich möchte die Entfernung für eine angemessene Anzahl von Punkten berechnen, da ich die Punkte nach Entfernung sortieren und die Punkte 1-20, 21-40, 41-60 usw. anzeigen möchte.
user4951
quelle
3
cross post dba.stackexchange.com/questions/19595/… ( Scheint auch schlecht zu sein, eine Frage zu haben, bei der jede Antwort PostGIS anspricht)
Evan Carroll

Antworten:

7

Räumliche Abfragen sind definitiv das Richtige.

Mit PostGIS würde ich zuerst etwas Einfaches wie dieses ausprobieren und den Bereich nach Bedarf anpassen:

SELECT * 
FROM table AS a
WHERE ST_DWithin (mylocation, a.LatLong, 10000) -- 10km
ORDER BY ST_Distance (mylocation, a.LatLong)
LIMIT 20

Dies würde Punkte (tatsächlich ihre Begrenzungsrahmen) unter Verwendung des räumlichen Index vergleichen, daher sollte es schnell sein. Ein anderer Ansatz, der in den Sinn kommt, besteht darin, Ihren Standort zu puffern und diesen Puffer dann mit den Originaldaten zu überschneiden, was möglicherweise noch effizienter ist.

lynxlynxlynx
quelle
9

Wenn Sie nur nach Proximity-Point-Suchen (Abfragen zum nächsten Nachbarn) suchen, möchten Sie dafür nicht die alten ST_DWithin- oder ST_Distance + ORDER BYs verwenden.

Nicht mehr.

Nach der Auslieferung von PostGIS 2.0 sollten Sie die knngist-Indexunterstützung (eine native PostgreSQL-Funktion) verwenden. Es wird um Größenordnungen schneller sein.

Ein Auszug aus diesem Blogeintrag, der beschreibt, wie man knn gist ohne PostGIS verwendet :

$ create table test ( position point );

CREATE TABLE
Table created. Now let’s insert some random points:
$ insert into test (position) select point( random() * 1000, random() * 1000) from generate_series(1,1000000);

INSERT 0 1000000
1 million points should be enough for my example. All of them have both X and Y in range <0, 1000). Now we just need the index:
$ create index q on test using gist ( position );

CREATE INDEX
And we can find some rows close to center of the points cloud:
$ select *, position <-> point(500,500) from test order by position <-> point(500,500) limit 10;

              position               |     ?column?

-------------------------------------+-------------------

 (499.965638387948,499.452529009432) | 0.548548271254899

 (500.473062973469,500.450353138149) |  0.65315122744144

 (500.277776736766,500.743471086025) | 0.793668174518778

 (499.986605718732,500.844359863549) | 0.844466095200968

 (500.858531333506,500.130807515234) | 0.868439207229501

 (500.96702715382,499.853323679417)  | 0.978087654172406

 (500.975443981588,500.170825514942) | 0.990289007195055

 (499.201623722911,499.368405900896) |  1.01799596553335

 (498.899147845805,500.683960970491) |  1.29602394829404

 (498.38217580691,499.178630765527)  |  1.81438764851559

(10 rows)
And how about speed?
$ explain analyze select *, position <-> point(500,500) from test order by position <-> point(500,500) limit 10;

                                                        QUERY PLAN

--------------------------------------------------------------------------------------------------------------------------

 Limit  (cost=0.00..0.77 rows=10 width=16) (actual time=0.164..0.475 rows=10 loops=1)

   ->  Index Scan using q on test  (cost=0.00..76512.60 rows=1000000 width=16) (actual time=0.163..0.473 rows=10 loops=1)

         Order By: ("position" <-> '(500,500)'::point)

 Total runtime: 0.505 ms

(4 rows)

Interessanterweise gibt die Indexdurchquerung die Merkmale in der Reihenfolge ihrer Nähe zurück, sodass für die Ergebnisse keine Sortierung (dh Reihenfolge nach) erforderlich ist!

Wenn Sie es jedoch zusammen mit PostGIS verwenden möchten, ist es jetzt wirklich einfach. Folgen Sie einfach diesen Anweisungen .

Der relevante Teil ist folgender:

SELECT name, gid
FROM geonames
ORDER BY geom <-> st_setsrid(st_makepoint(-90,40),4326)
LIMIT 10;

Aber nimm mein Wort nicht davon. Zeit es selbst :)

Ragi Yaser Burhum
quelle
Dies wird eine gute Antwort sein. Ich verwende jedoch MySQL Myisam. Ich habe vergessen, das hinzuzufügen.
user4951
Also +1, aber ich kann dies nicht als meine Antwort auswählen. Soll ich eine andere Frage erstellen?
user4951
@JimThio MySQL hat keinen Index für den nächsten Nachbarn, daher müssen Sie sich auf den PostGIS-ähnlichen Ansatz verlassen, bevor eine Abfrage für den nächsten Nachbarn durchgeführt wurde (ST_D innerhalb von ORDER BY ST_Distance). Willkommen zurück im Mittelalter :)
Ragi Yaser Burhum
Also muss ich nach Mongodb? Lass mich raten. Was bringt es, einen räumlichen Index für MySQL zu haben, wenn Sie nicht einmal das Einfachste tun können, wie 20 nächstgelegene Punkte zu finden?
user4951
1
Sie können den nächstgelegenen Punkt mithilfe eines Fensters finden. Gleiches gilt für jede andere räumliche Datenbank, wie sie von @lynxlynxlynx beschrieben wird. Sie können das Fenster weiter vergrößern, indem Sie es mit zwei multiplizieren. Ja, das gilt auch für Mongo oder eine andere Datenbank. Der Punkt ist, dass Sie die meisten anderen Funktionen einschränken. Außerdem weiß jeder, dass MySQL bis vor kurzem nie ein ernstzunehmender Anwärter auf etwas Räumliches war.
Ragi Yaser Burhum
8

Mit PostGIS 2.0 unter PostgreSQL 9.1 können Sie den KNN-indizierten Operator für den nächsten Nachbarn verwenden , z.

SELECT *, geom <-> ST_MakePoint(-90, 40) AS distance
FROM table
ORDER BY geom <-> ST_MakePoint(-90, 40)
LIMIT 20 OFFSET 0;

Das Obige sollte innerhalb weniger Millisekunden abgefragt werden.

Für das nächste Vielfachen von 20, ändern zu OFFSET 20, OFFSET 40usw ...

Mike T.
quelle
Könnte ich wissen, was die Bedeutung von <->? Vielen Dank.
Nordbaum
<->ist ein Operator, der den 2D-Abstand zurückgibt.
Mike T
1

MySQL Spatial

Jeder hier erklärt Ihnen, wie es mit PostgreSQL unter Verwendung von KNN geht, ohne Ihnen die Vorteile zu erklären. Mit MySQL können Sie den nächsten Nachbarn nicht ermitteln, ohne die Entfernung für alle Nachbarn zu berechnen . Das ist extrem langsam. Mit PostgreSQL kann dies für einen Index erfolgen. Weder MySQL noch MariaDB unterstützen derzeit KNN

Evan Carroll
quelle