W jaki sposób Yelp efektywnie oblicza odległość w bazie danych?

Powiedzmy na przykład, że mam tabelę:

Business(BusinessID, Lattitude, Longitude)

Wszystkie są oczywiście indeksowane. Jest też 1 milion rekordów

Powiedzmy, że chcę znaleźć firmy najbliższe 106,5, na przykład, jak mam to zrobić?

Jeśli zrobię

SELECT *
FROM Business
WHERE (Some formula to compute distance here) < 2000

na przykład lub jeśli tak

SELECT *
FROM Business
TOP 20

Teoretycznie komputer będzie musiał obliczyć odległość dla wszystkich dziwactw, podczas gdy w praktyce tylko te z szerokością i długością geograficzną w określonym zakresie, który powinien być obliczony.

Jak mogę zrobić to, co chcę, na przykład w PhP lub SQL?

Jestem wdzięczny za dotychczasową odpowiedź. Używam mysql i nie mają nic bardziej wydajnego niż oczywiste rozwiązanie. Przestrzeń MySQL również nie ma funkcji obliczania odległości.

— użytkownik4951
źródło

Odpowiedzi:

Jeśli dobrze rozumiem pytanie (i nie jestem pewien, czy rozumiem), martwisz się obliczeniami "(Some formula to compute distance here)"dla każdego wiersza w tabeli za każdym razem, gdy wykonujesz zapytanie?

To może być w pewnym stopniu złagodzone za pomocą indeksów latitudei longitudetak mamy tylko do obliczania odległości do „pudełka” punktów zawierających krąg rzeczywiście ma:

select * from business
where (latitude>96 and latitude<116) and 
      (longitude>-5 and longitude<15) and 
      (Some formula to compute distance here) < 2000

Gdzie 96, 116 itd. Są wybrane, aby dopasować jednostkę wartości „2000” i punkt na kuli ziemskiej, z którego obliczasz odległości.

Dokładne wykorzystanie indeksów będzie zależeć od systemu RDBMS i wyborów dokonywanych przez jego planistę.

Ogólnie rzecz biorąc, jest to prymitywny sposób optymalizacji rodzaju wyszukiwania najbliższego sąsiada . Jeśli twój RDBMS obsługuje indeksy GiST , takie jak postgres , powinieneś rozważyć ich użycie.

— Jack mówi, że spróbuj topanswers.xyz
źródło

Użyłem mysql. Jednak niektóre silniki mysql obsługują dane geoprzestrzenne, ale nie są dostępne.

— user4951

Czy mam rację, że nie masz opcji zmiany z MySQL? W takim przypadku proszę otagować pytanie mysql

— Jack mówi: spróbuj topanswers.xyz

Właściwie teraz dodaję teraz tabelę pomocniczą w moim myisam, jak mam to zrobić efektywnie?

— user4951

Cóż, mogę użyć mongodb. Nie zdecydowałem tego. Najbardziej jednak znam mysql.

— user4951

Radzę zapoznać się z postgres, jeśli w ogóle jest to możliwe - w porównaniu z MongoDB jest znacznie bardziej podobny do MySQL i ma solidną historię z danymi przestrzennymi, a twoje komentarze w innych miejscach wskazują, że wolisz „darmowy”.

— Jack mówi, że spróbuj topanswers.xyz

(Ujawnienie: Jestem facetem z Microsoft SQL Server, więc mam na to wpływ.)

Aby naprawdę to zrobić skutecznie, potrzebujesz dwóch rzeczy: buforowania i natywnej obsługi danych przestrzennych. Obsługa danych przestrzennych pozwala przechowywać dane geograficzne i geometryczne bezpośrednio w bazie danych bez wykonywania intensywnych / kosztownych obliczeń w locie, a także umożliwia tworzenie indeksów w celu bardzo szybkiego znalezienia najbliższego punktu Twojej bieżącej lokalizacji (lub najbardziej wydajnej trasy lub cokolwiek innego).

Buforowanie jest ważne, jeśli chcesz skalować, kropka. Najszybsze zapytanie jest tym, którego nigdy nie wykonałeś. Ilekroć użytkownik prosi o najbliższe rzeczy, przechowujesz jego lokalizację i zestaw wyników w pamięci podręcznej, takiej jak Redis lub zapisany w pamięci przez okres godzin. Lokalizacje firm nie zmienią się przez 4 godziny - cóż, mogą, jeśli ktoś edytuje firmę, ale niekoniecznie musi to być natychmiast aktualizowane we wszystkich zestawach wyników.

— Brent Ozar
źródło

Nie mogę ustalić z twojego łącza, czy SQL Server rzeczywiście indeksuje dane przestrzenne w sposób przydatny do uzyskania listy pobliskich punktów - prawda?

— Jack mówi, że spróbuj topanswers.xyz

Wygląda na to,

— Jack mówi, spróbuj wypróbować topanswers.xyz

Chodzi o to, że używam mysql i sprawdziłem, że nie mają żadnego algorytmu bardziej wydajnego niż zalecił Jack Douglas. Zastanawiam się, czy mysql zrobi coś takiego jak buforowanie. Microsoft SQL jest płatny, a mysql jest darmowy

— 4951

Lokalizacja firmy nie zmieni się przez cały czas, jednak zmieni się także lokalizacja ludzi.

— user4951

Yelp prawdopodobnie korzysta z GIS

PostgreSQL ma implementację referencyjną dla GIS z PostGIS . Yelp może używać MySQL, który pod każdym względem jest gorszy . W przypadku czegoś takiego jak Yelp prawie na pewno zachowują współrzędne dla,

Użytkownik
Potencjalne miejsca docelowe

Te współrzędne są prawie na pewno w WGS84 i są przechowywane jako typ geograficzny. W PostgreSQL i PostGIS wyglądałoby to mniej więcej tak,

CREATE TABLE businesses (
  id   int               GENERATED BY DEFAULT AS IDENTITY PRIMARY KEY,
  name text,
  geog geography(point)
);
CREATE INDEX ON businesses USING gist(geog);
.... fill table
ANALYZE businesses;

Wypełnią ten stół. Następnie pobierają współrzędne WGS84 z telefonu i generują zapytanie, takie jak to za pomocą SQL Alchemy (w przypadku Yelp),

SELECT *
FROM businesses AS b
WHERE ST_DWithin( b.geog, ST_MakePoint(userLong,userLat) );

Aby uzyskać więcej informacji, zobacz nasze przestrzennyi sprawdź Geographic Information Systems @ StackExchange

— Evan Carroll
źródło