cómo encontrar eficazmente los 20 puntos más cercanos

Question

Digamos que quiero encontrar los 20 negocios más cercanos a 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 empresas. Por supuesto, es estúpido calcular la distancia de todos ellos y luego ordenarla.

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

Entonces, ¿qué comman de SQL tengo que lanzar?

Nota:

1. Estoy usando mysql myisam índice espacial. Sin embargo, no lo he especificado antes. Así que voy a aceptar a los que responden para mostrar mi agradecimiento y hacer otra pregunta.
2. No quiero computar la distancia para toda la tabla
3. No quiero calcular la distancia para ninguna región que siga siendo 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.

Answer 1

Si todo lo que busca son búsquedas de puntos de proximidad (consultas de vecinos más cercanos), entonces no querrá utilizar los antiguos ST_DWithin o ST_Distance + ORDER BY para ello.

Ya no.

Ahora que PostGIS 2.0 ha sido enviado, deberías usar el soporte de índices knngist (una característica nativa de PostgreSQL). Será órdenes de magnitud más rápido.

Un extracto de esta entrada del blog que describe cómo utilizar 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 más interesante es que el índice devuelve las características por orden de proximidad, por lo que no es necesario ordenar los resultados.

Sin embargo, si quieres usarlo junto a PostGIS, ahora es realmente fácil. Sólo tienes que seguir 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 te fíes de mi palabra. Cronometrelo usted mismo :)

Answer 2

Con PostGIS 2.0 en PostgreSQL 9.1, puede utilizar el operador de 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 consultarse en unos pocos milisegundos.

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

Answer 3

Las consultas espaciales son, sin duda, lo que hay que utilizar.

Con PostGIS yo probaría primero algo simplista como esto 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 los puntos (en realidad sus cajas delimitadoras) utilizando el índice espacial, por lo que debería ser rápido. Otro enfoque que se me ocurre es almacenar en el buffer su ubicación y luego intersecar ese buffer con los datos originales, lo que puede ser aún más eficiente.

Answer 4

MySQL Spatial

Aquí todo el mundo te dice cómo hacerlo con PostgreSQL usando KNN, sin decirte las ventajas. Usando MySQL no puedes determinar el vecino más cercano sin calcular la distancia para todo de los vecinos. Eso es extremadamente lento. Con PostgreSQL esto se puede hacer en un índice. Ni MySQL ni MariaDB soportan actualmente KNN