Wie kann ich Ergebnisse von einer JPA-Entität erhalten, die nach Entfernung sortiert ist?

Ich schreibe gerade eine mobile Anwendung, wo der Benutzer einen Ort aus einer list auswählen muss. Alle Standorte werden in einer Postgres-database mit JPA aus einer Play App gespeichert.

Ich möchte den Standort des Nutzers in der App abrufen und dann eine Anfrage stellen, um die ersten 20 oder 50 Orte zu erhalten, die diesem Nutzer am nächsten sind.

Wenn ich hierfür meine eigene datastruktur verwenden würde, würde ich einen KD-Tree verwenden. Ich bin jedoch sehr neu in JPA / Play / PostgreSQL, so dass ich nicht sicher bin, wie man data persistent manuell behandelt.

Das einzige, was ich mit meinem derzeitigen Wissen denken könnte, wäre, jeden Ort zu betrachten und seine Entfernung zu bestimmen, aber das wäre unglaublich langsam in einer so riesigen database.

Gibt es eine Frage, die ich ausführen kann, um zu sagen: "Gib mir die X ersten Ergebnisse nach Entfernung von dieser Breite und Länge geordnet?

EDIT: Ich benutze Heroku und da die Anwendung in den frühen Phasen der Entwicklung ist, würde ich lieber nicht die $ 200 / Monat Heroku benötigt, wenn Sie PostGIS mit Ihrer App verwenden möchten.

Solutions Collecting From Web of "Wie kann ich Ergebnisse von einer JPA-Entität erhalten, die nach Entfernung sortiert ist?"

Sie möchten wirklich nicht Ihre eigene datastruktur dafür rollen, aber glücklicherweise verwenden Sie PostgreSQL, also haben Sie Glück. Verwenden Sie PostGIS . Es wird Größenordnungen schneller als alles, was Sie in einer angemessenen time erstellen können.

Dies ist eine weitgehend vereinfachte Version einer function, die ich in einer App verwende, die vor etwa 3 Jahren erstellt wurde. Angepasst an die vorliegende Frage.

  • Sucht mithilfe eines Kästchens Orte im Umkreis eines Punkts. Man könnte dies mit einem Kreis tun, um genauere Ergebnisse zu erhalten, aber dies soll nur eine Annäherung sein, um damit zu beginnen.

  • Ignoriert die Tatsache, dass die Welt nicht flach ist. Meine Bewerbung war nur für eine lokale Region gedacht, einige 100 Kilometer. Und der Suchbereich reicht nur wenige Kilometer. Die Welt flach zu machen ist gut genug für den Zweck. (Todo: Eine bessere Annäherung für das Verhältnis lat / lon abhängig von der Geolokalisierung könnte helfen.)

  • Arbeitet mit Geocodes, wie Sie es von Google Maps bekommen.

  • Arbeitet mit PostgreSQL Standard ohne Erweiterung (kein PostGis erforderlich), getestet auf PostgreSQL 9.1 und 9.2.

Ohne Index müsste man die Entfernung für jede Zeile in der Basistabelle berechnen und die nächsten filtern. Extrem teuer mit großen Tischen.

Bearbeiten:
Ich überprüfte und die aktuelle Implementierung ermöglicht einen GisT-Index nach Punkten (Postgres 9.1 oder höher). Vereinfachte den Code entsprechend.

Der Haupttrick besteht darin, einen funktionellen GiST-Index von Boxen zu verwenden , obwohl die Spalte nur ein Punkt ist. Dies ermöglicht die Nutzung der vorhandenen GiST-Implementierung .

Mit einer solchen (sehr schnellen) search können wir alle Orte in einer Box finden. Das verbleibende Problem: Wir kennen die Anzahl der Zeilen, aber wir wissen nicht, wie groß die Box ist, in der sie sich befinden. Das ist so, als wüsste man einen Teil der Antwort, aber nicht die Frage.

Ich verwende einen ähnlichen Reverse-Lookup- Ansatz für den, der in dieser verwandten Antwort auf dba.SE genauer beschrieben wird. (Nur, ich verwende hier keine Teilindizes – könnte auch funktionieren).

Iterate durch eine Reihe von vordefinierten Suchschritten, von sehr klein bis "gerade groß genug, um mindestens genug Standorte zu halten". Das bedeutet, dass wir einige (sehr schnelle) Abfragen ausführen müssen, um zu der Größe für das Suchfeld zu gelangen.

Durchsuchen Sie dann die Basistabelle mit diesem Feld und berechnen Sie die tatsächliche Entfernung für nur die wenigen Zeilen, die vom Index zurückgegeben werden. Es wird in der Regel einen Überschuss geben, da wir festgestellt haben, dass die Box mindestens genug Positionen hat. Indem wir die nächsten nehmen, runden wir effektiv die Ecken der Box ab. Sie könnten diesen Effekt erzwingen, indem Sie die Box um eine Kerbe größer machen (multiplizieren Sie den radius in der function mit sqrt (2), um völlig genaue Ergebnisse zu erhalten, aber ich würde nicht alles herausnehmen, da dies ungefähr der Anfang ist).

Dies wäre mit einem SP GiST- Index, der in der neuesten Version von PostgreSQL verfügbar ist, noch schneller und einfacher. Aber ich weiß nicht, ob das noch möglich ist. Wir würden eine tatsächliche Implementierung für den datatyp benötigen, und ich hatte nicht die time, mich darauf einzulassen. Wenn Sie einen path finden, versprechen Sie, sich zu melden!

Angesichts dieser vereinfachten Tabelle mit einigen Beispielwerten ( adr .. Adresse):

 CREATE TABLE adr(adr_id int, adr text, geocode point); INSERT INTO adr (adr_id, adr, geocode) VALUES (1, 'adr1', '(48.20117,16.294)'), (2, 'adr2', '(48.19834,16.302)'), (3, 'adr3', '(48.19755,16.299)'), (4, 'adr4', '(48.19727,16.303)'), (5, 'adr5', '(48.19796,16.304)'), (6, 'adr6', '(48.19791,16.302)'), (7, 'adr7', '(48.19813,16.304)'), (8, 'adr8', '(48.19735,16.299)'), (9, 'adr9', '(48.19746,16.297)'); 

Der Index sieht so aus:

 CREATE INDEX adr_geocode_gist_idx ON adr USING gist (geocode); 

-> SQLfiddle

Sie müssen den Home-Bereich, die Schritte und den Skalierungsfaktor an Ihre Bedürfnisse anpassen. Solange Sie in Kisten von einigen Kilometern um einen Punkt suchen, ist eine flache Erde eine gute Annäherung.

Sie müssen plpgsql gut verstehen, um damit zu arbeiten. Ich fühle, dass ich hier genug getan habe.

 CREATE OR REPLACE FUNCTION f_find_around(_lat double precision, _lon double precision, _limit bigint = 50) RETURNS TABLE(adr_id int, adr text, distance int) AS $func$ DECLARE _homearea CONSTANT box := '(49.05,17.15),(46.35,9.45)'::box; -- box around legal area -- 100m = 0.0008892 250m, 340m, 450m, 700m,1000m,1500m,2000m,3000m,4500m,7000m _steps CONSTANT real[] := '{0.0022,0.003,0.004,0.006,0.009,0.013,0.018,0.027,0.040,0.062}'; -- find optimum _steps by experimenting geo2m CONSTANT integer := 73500; -- ratio geocode(lon) to meter (found by trial & error with google maps) lat2lon CONSTANT real := 1.53; -- ratio lon/lat (lat is worth more; found by trial & error with google maps in (Vienna) _radius real; -- final search radius _area box; -- box to search in _count bigint := 0; -- count rows _point point := point($1,$2); -- center of search _scalepoint point := point($1 * lat2lon, $2); -- lat scaled to adjust BEGIN -- Optimize _radius IF (_point <@ _homearea) THEN FOREACH _radius IN ARRAY _steps LOOP SELECT INTO _count count(*) FROM adr a WHERE a.geocode <@ box(point($1 - _radius, $2 - _radius * lat2lon) , point($1 + _radius, $2 + _radius * lat2lon)); EXIT WHEN _count >= _limit; END LOOP; END IF; IF _count = 0 THEN -- nothing found or not in legal area EXIT; ELSE IF _radius IS NULL THEN _radius := _steps[array_upper(_steps,1)]; -- max. _radius END IF; _area := box(point($1 - _radius, $2 - _radius * lat2lon) , point($1 + _radius, $2 + _radius * lat2lon)); END IF; RETURN QUERY SELECT a.adr_id ,a.adr ,((point (a.geocode[0] * lat2lon, a.geocode[1]) <-> _scalepoint) * geo2m)::int4 AS distance FROM adr a WHERE a.geocode <@ _area ORDER BY distance, a.adr, a.adr_id LIMIT _limit; END $func$ LANGUAGE plpgsql; 

Anruf:

 SELECT * FROM f_find_around (48.2, 16.3, 20); 

Gibt eine list von $3 Standorten zurück, wenn genug in dem definierten maximalen Suchbereich vorhanden ist.
Sortiert nach der tatsächlichen Entfernung.

Weitere Verbesserungen

Erstellen Sie eine function wie:

 CREATE OR REPLACE FUNCTION f_geo2m(double precision, double precision) RETURNS point AS $BODY$ SELECT point($1 * 111200, $2 * 111400 * cos(radians($1))); $BODY$ LANGUAGE sql IMMUTABLE; COMMENT ON FUNCTION f_geo2m(double precision, double precision) IS 'Project geocode to approximate metric coordinates. SELECT f_geo2m(48.20872, 16.37263) --'; 

Die (wörtlich) globalen Konstanten 111200 und 111400 sind für mein Gebiet (Österreich) aus der Länge eines Längengrads und der Länge eines Breitengrads optimiert, funktionieren aber grundsätzlich nur auf der ganzen Welt.

Verwenden Sie diese Option, um der Basistabelle einen skalierten Geocode hinzuzufügen, idealerweise eine generierte Spalte, wie in dieser Antwort beschrieben:
Wie machst du Date Mathe, die das Jahr ignoriert?
Siehe 3. Black Magic Version, wo ich dich durch den process führe.
Dann können Sie die function etwas vereinfachen: Skalieren Sie die Eingabewerte einmal und entfernen Sie überflüssige Berechnungen.