Dites que je veux trouver les 20 entreprises les plus proches de chez moi.

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           

Il y a 1,6 million de biz. Bien sûr, il est stupide de calculer la distance pour chacun d'eux, puis de la trier.

C'est là que l'index géospatial entre en jeu, non?

Alors, quel comman SQL je dois lancer?

Remarque:

1. J'utilise MySQL MyISAM index spatial. Cependant, je n'ai pas précisé cela auparavant. Je vais donc accepter ceux qui y répondent pour montrer mon appréciation et poser une autre question.
2. Je ne veux pas calculer la distance pour toute la table
3. Je ne veux calculer la distance pour aucune région encore inefficace
4. Je veux calculer la distance pour un nombre raisonnable de points parce que je veux trier les points par distance et pouvoir afficher les points 1-20, 21-40, 41-60, etc.

Les requêtes spatiales sont certainement la chose à utiliser.

Avec PostGIS, j'essaierais d'abord quelque chose de simpliste comme celui-ci et modifierais la plage selon les besoins:

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

Cela comparerait des points (en fait leurs boîtes englobantes) en utilisant l'index spatial, donc cela devrait être rapide. Une autre approche qui vient à l'esprit est la mise en mémoire tampon de votre emplacement, puis l'intersection de cette mémoire tampon avec les données d'origine, ce qui peut être encore plus efficace.

Si tout ce que vous recherchez sont des recherches de points de proximité (requêtes de voisins les plus proches), vous ne voulez pas utiliser les anciens ST_DWithin ou ST_Distance + ORDER BY pour cela.

Plus maintenant.

Maintenant que PostGIS 2.0 est livré, vous devez utiliser la prise en charge de l'index knngist (une fonctionnalité native de PostgreSQL). Ce sera des ordres de grandeur plus rapidement.

Un extrait de cette entrée de blog qui décrit comment utiliser knn gist sans 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)

Assez intéressant, la traversée d'index renverra les caractéristiques par ordre de proximité, donc pas besoin de faire un tri (c'est-à-dire par ordre) pour les résultats!

Cependant, si vous souhaitez l'utiliser avec PostGIS, c'est désormais très simple. Suivez simplement ces instructions .

La partie pertinente est la suivante:

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

Mais ne me croyez pas sur parole. Temps vous-même :)

Avec PostGIS 2.0 sur PostgreSQL 9.1, vous pouvez utiliser l'opérateur de voisin le plus proche indexé KNN , par exemple:

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

Ce qui précède devrait interroger en quelques millisecondes.

Pour les prochains multiples de 20, à modifier OFFSET 20, OFFSET 40etc ...

MySQL Spatial

Tout le monde ici vous explique comment le faire avec PostgreSQL en utilisant KNN, sans vous en dire les avantages. En utilisant MySQL, vous ne pouvez pas déterminer le voisin le plus proche sans calculer la distance pour tous les voisins. C'est extrêmement lent. Avec PostgreSQL, cela peut être fait sur un index. Ni MySQL ni MariaDB ne prennent actuellement en charge KNN