cómo encontrar 20 puntos más cercanos de manera eficiente [cerrado]

9

Digamos que quiero encontrar 20 negocios más cercanos cerca de mí.

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           

Hay 1.6 millones de negocios. Por supuesto, es estúpido calcular la distancia para todos ellos y luego ordenarlos.

Ahí es donde entra en juego el índice geoespacial, ¿verdad?

Entonces, ¿qué comando SQL necesito para lanzar?

Nota:

  1. Estoy usando el índice espacial mysql myisam . Sin embargo, no especifiqué esto antes. Así que aceptaré a quienes lo respondan para mostrar mi agradecimiento y hacer otra pregunta.
  2. No quiero calcular la distancia para toda la tabla
  3. No quiero calcular la distancia para ninguna región que todavía sea ineficiente
  4. Quiero calcular la distancia para un número razonable de puntos porque quiero ordenar los puntos por distancia y poder mostrar los puntos 1-20, 21-40, 41-60, etc.
user4951
fuente
3
cross post dba.stackexchange.com/questions/19595/… (También parece un mal juju tener una pregunta donde cada respuesta se dirige a PostGIS)
Evan Carroll

Respuestas:

7

Las consultas espaciales son definitivamente lo que hay que usar.

Con PostGIS, primero probaría algo simplista como este y ajustaría el rango según sea necesario:

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

Esto compararía puntos (en realidad sus cuadros delimitadores) utilizando el índice espacial, por lo que debería ser rápido. Otro enfoque que viene a la mente es almacenar su ubicación en el búfer y luego intersecar ese búfer con los datos originales, lo que puede ser aún más eficiente.

lynxlynxlynx
fuente
9

Si todo lo que está buscando son búsquedas de puntos de proximidad (consultas de vecinos más cercanos), entonces no desea usar los viejos ST_DWithin o ST_Distance + ORDER BY para eso.

Ya no.

Ahora que se envió PostGIS 2.0, debería usar el soporte de índice knngist (una característica nativa de PostgreSQL). Serán órdenes de magnitud más rápido.

Un extracto de esta entrada de blog que describe cómo usar knn gist sin PostGIS :

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

Lo suficientemente interesante, el recorrido del índice devolverá las características en orden de proximidad, por lo que no es necesario hacer una clasificación (es decir, ordenar por) para obtener los resultados.

Sin embargo, si desea usarlo junto con PostGIS, ahora es realmente fácil. Solo sigue estas instrucciones .

La parte relevante es esta:

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

Pero no confíes en mi palabra. Míralo tú mismo :)

Ragi Yaser Burhum
fuente
Esta será una buena respuesta. Sin embargo, estoy usando mysql myisam. Me olvido de agregar eso.
user4951
Entonces +1 pero no puedo seleccionar esto como mi respuesta. ¿Debo crear otra pregunta?
user4951
@JimThio MySQL no tiene un índice vecino más cercano, por lo que tendrá que confiar en el enfoque similar a PostGIS antes de que haya una consulta vecina más cercana (ST_Dwithin con ORDER BY ST_Distance). Bienvenido de nuevo a la edad media :)
Ragi Yaser Burhum
¿Entonces tengo que ir a mongodb? Déjame adivinar. ¿Cuál es el punto de tener un índice espacial en mysql si ni siquiera puede hacer lo más simple como encontrar 20 puntos más cercanos?
user4951
1
Puede encontrar el punto más cercano usando una ventana. Lo mismo es cierto para cualquier otra base de datos espacial como se describe por @lynxlynxlynx. Puedes seguir aumentando la ventana multiplicándola por dos. Sí, lo mismo es cierto para Mongo o cualquier otra base de datos. El punto es que reduces la mayoría de las otras características. Además, todo el mundo sabe que hasta hace poco, MySQL nunca fue un contendiente serio para nada espacial.
Ragi Yaser Burhum
8

Con PostGIS 2.0 en PostgreSQL 9.1, puede usar el operador vecino más cercano indexado KNN , por ejemplo:

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

Lo anterior debería consultar en unos pocos milisegundos.

Durante los siguientes múltiplos de 20, a modificar OFFSET 20, OFFSET 40etc ...

Mike T
fuente
¿Podría saber cuál es el significado de <->? Gracias.
northtree
<->es un operador que devuelve la distancia 2D.
Mike T
1

MySQL espacial

Todos aquí te están diciendo cómo hacerlo con PostgreSQL usando KNN, sin decirte las ventajas. Usando MySQL no puede determinar el vecino más cercano sin calcular la distancia para todos los vecinos. Eso es extremadamente lento. Con PostgreSQL esto se puede hacer en un índice. Ni MySQL ni MariaDB admiten actualmente KNN

Evan Carroll
fuente