jak skutecznie znaleźć 20 najbliższych punktów [zamknięte]

9

Powiedz, że chcę znaleźć 20 najbliższych firm w pobliżu mnie.

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           

Istnieje 1,6 miliona biz. Oczywiście głupio jest obliczyć odległość dla wszystkich, a następnie posortować ją.

Tam właśnie zaczyna się indeks geograficzny.

Więc co komendę SQL muszę rzucić?

Uwaga:

  1. Używam mysql myisam indeks przestrzenny. Jednak nie sprecyzowałem tego wcześniej. Przyjmuję więc tych, którzy odpowiedzą na to pytanie, aby okazać moje uznanie i zadać kolejne pytanie.
  2. Nie chcę obliczać odległości dla całego stołu
  3. Nie chcę obliczać odległości dla żadnego regionu, który jest nadal nieefektywny
  4. Chcę obliczyć odległość dla rozsądnej liczby punktów, ponieważ chcę sortować punkty według odległości i móc wyświetlać punkty 1-20, 21-40, 41-60 itp.
użytkownik4951
źródło
3
cross post dba.stackexchange.com/questions/19595/... (Wydaje się również, że złe juju ma pytanie, gdzie każda odpowiedź dotyczy PostGIS)
Evan Carroll

Odpowiedzi:

7

Kwerendy przestrzenne są zdecydowanie najlepszym rozwiązaniem.

W PostGIS najpierw spróbuję czegoś takiego uproszczonego i odpowiednio dostosuję zakres:

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

Spowodowałoby to porównanie punktów (a właściwie ich obwiedni) za pomocą indeksu przestrzennego, więc powinno być szybkie. Innym podejściem, które przychodzi na myśl, jest buforowanie Twojej lokalizacji, a następnie przecięcie tego bufora z oryginalnymi danymi, co może być jeszcze bardziej wydajne.

lynxlynxlynx
źródło
9

Jeśli wszystko, czego szukasz, to wyszukiwanie punktów bliskości (zapytania najbliższego sąsiada), nie chcesz do tego używać starych ST_DWithin lub ST_Distance + ORDER BY.

Nigdy więcej.

Po dostarczeniu PostGIS 2.0 powinieneś używać obsługi indeksu knngist (natywna funkcja PostgreSQL). Będzie to rząd wielkości szybciej.

Fragment tego wpisu na blogu, opisujący sposób użycia knn gist bez 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)

Interesujące jest to, że przejście indeksu zwróci funkcje w kolejności bliskości, więc nie trzeba sortować (tzn. Sortować według) wyników!

Jeśli jednak chcesz używać go razem z PostGIS, teraz jest to naprawdę łatwe. Postępuj zgodnie z tymi instrukcjami .

Odpowiednia część to:

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

Ale nie wierz mi na słowo. Czas to sam :)

Ragi Yaser Burhum
źródło
To będzie dobra odpowiedź. Używam jednak mysql myisam. Zapomniałem to dodać.
user4951
Więc +1, ale nie mogę wybrać tego jako mojej odpowiedzi. Czy powinienem utworzyć kolejne pytanie?
user4951
@JimThio MySQL nie ma indeksu najbliższego sąsiada, więc będziesz musiał polegać na podejściu podobnym do PostGIS, zanim pojawi się zapytanie o najbliższego sąsiada (ST_Dw ramach ORDER BY ST_Distance). Witamy z powrotem w średniowieczu :)
Ragi Yaser Burhum
Więc muszę iść do Mongodb? Niech zgadnę. Jaki jest sens posiadania indeksu przestrzennego na mysql, jeśli nie można nawet najprostszej rzeczy, jak znaleźć 20 najbliższych punktów?
user4951
1
Możesz znaleźć najbliższy punkt za pomocą okna. To samo dotyczy każdej innej przestrzennej bazy danych opisanej przez @lynxlynxlynx. Możesz ciągle zwiększać okno, mnożąc je przez dwa. Tak, to samo dotyczy Mongo lub dowolnej innej bazy danych. Chodzi o to, że ograniczyłeś większość innych funkcji. Poza tym wszyscy wiedzą, że do niedawna MySQL nigdy nie był poważnym pretendentem do czegoś przestrzennego.
Ragi Yaser Burhum
8

Dzięki PostGIS 2.0 na PostgreSQL 9.1 możesz użyć indeksowanego przez KNN operatora najbliższego sąsiada , np .:

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

Powyższe powinno wykonać zapytanie w ciągu kilku milisekund.

Przez następne wielokrotności 20, aby modyfikować OFFSET 20, OFFSET 40itp ...

Mike T.
źródło
Czy mogę wiedzieć, co to znaczy <->? Dzięki.
północdrzewa
<->jest operatorem, który zwraca odległość 2D.
Mike T
1

MySQL Spatial

Wszyscy tutaj mówią ci, jak to zrobić z PostgreSQL przy użyciu KNN, bez informowania o zaletach. Za pomocą MySQL nie można ustalić najbliższego sąsiada bez obliczenia odległości dla wszystkich sąsiadów. To bardzo wolno. Z PostgreSQL można tego dokonać na indeksie. Ani MySQL, ani MariaDB nie obsługują obecnie KNN

Evan Carroll
źródło