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.

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.

(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.

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