phpBB.de

phpBB.de - Die deutsche phpBB-Community
https://www.phpbb.de/community/

SQL: Umkreissuche realisieren ...

https://www.phpbb.de/community/viewtopic.php?t=222648

Seite 3 von 4

Re: SQL: Umkreissuche realisieren ...

Verfasst: 10.05.2012 17:39
von Wuppi
Hi

achso ... ja ok dann klappt es so:

Code: Alles auswählen

SELECT uov.userid, gl.country, gl.plz,

( 6371 * SQRT(2*(1-cos(RADIANS(gl.lat)) * cos(0.88895378390603) * (sin(RADIANS(gl.lon)) * sin(0.12130038301361) + cos(RADIANS(gl.lon)) * cos(0.12130038301361)) - sin(RADIANS(gl.lat)) * sin(0.88895378390603)))) 
AS Distance 
FROM geodb_locations gl 
 
JOIN user_option_value uov ON (uov.userOption65 = gl.plz AND uov.userOption85 = gl.country ) 

WHERE 6371 * SQRT(2*(1-cos(RADIANS(gl.lat)) * cos(0.88895378390603) * (sin(RADIANS(gl.lon)) * sin(0.12130038301361) + cos(RADIANS(gl.lon)) * cos(0.12130038301361)) - sin(RADIANS(gl.lat)) * sin(0.88895378390603))) <= 50 

group by uov.userid order by Distance
mhh
Zeige Datensätze 0 - 49 ( 52 insgesamt, Die Abfrage dauerte 0.5257 Sekunden)
bei 50km ... 0,5sek ... ist ja schon was :( ... kann man das pimpen? ;)
(wenn ich mir mehr Spalten anzeigen lasse, sogar noch mehr :( )

Was meinst du mit Subquery? Könnte das bissel mehr Performance bringen? Bzw. was könnte ich noch in Sachen Performance machen?

Ich muss das ganze vermutlich sogar noch mal wg. Pagination machen ... damit hab ich mich aber noch nicht beschäftigt wie das läuft. Die Pagination die ich kenne, verlangen den SQL-String um nen Start=xyz zu setzen (phpbb3 macht das ja auch so; ok man braucht hier nicht alle Spalten zu ermitteln)

Mir scheint als würde das group by die meiste Performance schlucken. Würde also schon mal sinn machen die GeoDB aufzuräumen (hab das ja nur wg. doppelter PLZ in einem Land) - dann könnte ich das group by einfach weglassen ... bin ich immer noch bei ca. 0,25sek.

Re: SQL: Umkreissuche realisieren ...

Verfasst: 10.05.2012 20:22
von gn#36
Das Problem ist, wie ich schon sagte, dass das Query die Berechnung ja auf allen Einträgen der DB durchgeführt werden muss. Damit das nicht so ist solltest du zusätzlich die Distanz mit einem Quadrat bestimmen. D.h. du bestimmst für beide Koordinaten minimal und Maximalwerte und grenzt hiermit im WHERE Teil der Abfrage zusätzlich ein. Dann kann die DB die Daten vorselektieren anhand der Grenzen (mit index) und muss dann nur innerhalb des Quadrats nach Städten suchen, die im gesuchten Umkreis sind.

Ein Subquery ist meiner Erfahrung nach meist eher langsamer.

EDIT: Schau mal hier, das ist im Prinzip genau das gleiche: viewtopic.php?f=6&t=222430#p1269671

Re: SQL: Umkreissuche realisieren ...

Verfasst: 10.05.2012 23:25
von Wuppi
von 21.000 auf 12.000 Datensätze reduziert. Keine dupletten mehr. Unnötige Spalten entfernt.
Abfrage jetzt max. 0.3s ... und wg. neuer Daten ist das Ergebnis jetzt viel genauer (Stadtteil sind jetzt nicht mehr 0km entfernt)

aber das ja immer noch zu lang ... also kommen wir zur Quadratlösung ... und zu dem Problem das Mathe nicht gerade meine Stärke ist :/ Ich versteh schon die einfache Umkreissuche nicht - wie soll ich da jetzt noch nen Quadrat nutzen.

Also ... erster Schritt: meine LAT / LON ermitteln (DB-Abfrage). Das ganze dann noch umrechnen (lon bwz. lat / 180 * M_PI)
Jetzt sag ich für lon und lat das mir da jetzt 100km drauf gerechnet werden sollen (php)
Ergebnis z.b.: LAT 100 bis 104 und LON 50 bis 54
Und jetzt einfach die Abfrage wonach mir alles ausgeben werden sollte was zwischen ( lat BETWEEN 100 AND 104 ) ist (sql) ... dazu muss ich dann noch sagen das er mir das nach Entfernung sortieren soll - dann der abgleich mit der UserDB.

Soviel zur Theorie ... in der Praxis ... keine Ahnung wie ich das umsetze.

Re: SQL: Umkreissuche realisieren ...

Verfasst: 11.05.2012 13:35
von gn#36
Das Quadrat ist eigentlich ziemlich einfach: Du nimmst bei jeder der beiden Koordinaten den aktuellen Wert und addierst nach Umrechnung der Einheit einfach den gewünschten Umkreis auf (Obergrenze) bzw. ziehst ihn ab (Untergrenze).

Das muss auch nicht völlig exakt werden, in Lat Richtung (also N/S) könntest du z.B. pro 110 km 1 rad annehmen, in Long Richtung (W/E) etwa pro 110 km * cos(latitude des mittelpunkts) oder noch einfacher 110 km * cos(latitude des nördlichsten Punktes). Also z.B. 1 rad pro 110 km * cos(53.6°) was etwa 65,28 km sind. Wichtig ist nur, dass dein Viereck größer wird als der Kreis (und natürlich nicht zu groß, dann kannst du es dir auch sparen). Da musst du auch keine zusätzliche Abfrage realisieren (es sei denn du kennst vorher die Koordinaten des Mittelpunkts noch nicht).

Also wenn du z.B. in einem Umkreis von 110 km um den Punkt 52°N, 9°E (einige km neben Dettmold) schauen möchtest, dann würdest du in Lat Richtung von 51° bis 53° N schauen, in Long Richtung entweder vereinfacht von 9-1.69 (=7.31°E) bis 9+1.69 (=10.69°E) schauen, oder das etwas genauer berechnen (also 110*cos(52°) = 67.7 km, also 9-1.62 bis 9+1.62).

Das fügst du dann einfach per AND an deine WHERE Bedingung an, also z.B.

Code: Alles auswählen

WHERE (lat >= 51 AND lat <= 53 AND long >= 7.31 AND long <= 10.69) 
      AND (...bisherige Bedingungen mit Berechnung ...)
Die 110 km für die Nord/Süd Richtung sind mit Absicht etwas kleiner als der tatsächliche Abstand der Breitengrade, so dass man das Viereck tendenziell etwas größer wählt (weil die Daten ja in Grad angegeben werden).

Re: SQL: Umkreissuche realisieren ...

Verfasst: 13.05.2012 22:45
von Wuppi
dieser Post hat sich erledigt

Re: SQL: Umkreissuche realisieren ...

Verfasst: 14.05.2012 09:24
von Wuppi
Hi

so bissel getestet ...

ist das richtig?

Code: Alles auswählen

SELECT gl.country, gl.plz, ACOS( SIN(RADIANS(gl.lat)) * SIN(RADIANS(51.941887)) + COS(RADIANS(gl.lat)) * COS(RADIANS(51.941887)) * COS(RADIANS(gl.lon) - RADIANS(8.872081)) ) * 6371 AS Distance FROM 

(SELECT * FROM geodb_locations_long WHERE (lat >= 51 AND lat <= 53 AND lon >= 7.31 AND lon <= 10.69) ) as gl
Having Distance <= 75 ORDER BY Distance
=>0.0149 Sekunden
wie gesagt: die genaue Berechnung der Zahlen ist erstmal außen vor ... wir gehen mal davon aus das alle genannten Zahlen richtig sind ;)


Die komplette Abfrage (mit Querverweis auf die andere Tabelle), sieht dann vermutlich so aus:

Code: Alles auswählen

SELECT uov.userid, gl.country, gl.plz,

ACOS( SIN(RADIANS(gl.lat)) * SIN(RADIANS(51.941887)) + COS(RADIANS(gl.lat)) * COS(RADIANS(51.941887)) * COS(RADIANS(gl.lon) - RADIANS(8.872081)) ) * 6371 AS Distance FROM 

(SELECT lat,lon FROM geodb_locations_long WHERE (lat >= 51 AND lat <= 53 AND lon >= 7.31 AND lon <= 10.69) ) as gl

JOIN wcf1_user_option_value uov ON (uov.userOption65 = gl.plz AND uov.userOption85 = gl.country ) Having Distance <= 75 ORDER BY Distance
=> aber hier scheint nen Fehler zu sein ... Abfrage dauert wieder gute 0,35s. Das reine "quadrieren" kostet 0.0019 Sekunden mit Umkreisberechnung 0.0149 Sekunden ... das ich ein Ergebnis mit 307 PLZ dann gegen 2000 User laufen lasse - 0,3sek? Da stimmt irgendwas nicht ... War vorher auf 0,5x Sekunden - konnte das reduzieren in dem ich die KOLLATION der PLZ/Ort-Spalte auf UTF8 gestellt habe ... versteh ich jetzt nicht wirklich - aber ok ...

--------------------------

Nachtrag Edit:
Das mit dem ausrechnen versteh ich noch nicht so ganz ... habe aber jetzt folgende Berechnung für SQL gefunden (für diese GIS-Erweiterung):

Code: Alles auswählen

SET @breite_nord = @ibk_breite + (@umkreis / 111);
SET @breite_sued = @ibk_breite - (@umkreis / 111);
SET @laenge_west = @ibk_laenge -
    (@umkreis / ABS(COS(RADIANS(@ibk_breite))) * 111);
SET @laenge_ost = @ibk_laenge +
    (@umkreis / ABS(COS(RADIANS(@ibk_breite))) * 111);
bei der länge fehlt noch ne () - aber danach sieht es passend aus.

111 = Abstand Breitengrad.

Werte sähen dann z. B. so aus:
Länge 8,872081
Breite 51,941887
Umkreis 110
=
Breite-Nord 52,93287799
Breite-Süd 50,95089601
Länge-West 7,264530901
Länge-Ost 10,4796311
kann mir jemand bestätigen das die Ergebnisse richtig sind? Ich hab wie gesagt davon NULL Ahnung und setze hier gefährliches Halbwissen ein ;) [wenns den wenigstens die Hälfte wäre *G*]

Mit welchen Werten sollte man bei der Größe des Quadrates arbeiten (was ja wohl eher nen Rechteck ist!?)? Der Kreis muss ja ins Quadrat/Rechteck passen - und den nicht überlappen. Wenn ich also Umkreis von 100km haben möchte - rechne ich beim Quadrat dann mit 110km? Also pauschal 10% drauf? Oder bin da falsch?

Bei den Werten von dir @gn#36 bekomme ich z. B. PLZ bis 135km angezeigt. (nach meinem oberen SQL-String) ... jeder km drüber, zeigt keine weiteren Treffer - "Quadrat" ausgeschöpft ;)

Quelle für die SQL-Berechnung: http://mysqladmin.at/2012/04/11/wo-ist-die-nachste-bar/
und hier weitere Werte http://www.koordinaten.de/informationen ... tenmodell/

Gruß

Re: SQL: Umkreissuche realisieren ...

Verfasst: 14.05.2012 23:33
von gn#36
Du solltest die beiden Abfragen besser kombinieren statt ein Subselect zu nutzen. Ansonsten sieht die aber gut aus.

Code: Alles auswählen

SELECT gl.country, gl.plz, ACOS( SIN(RADIANS(gl.lat)) * SIN(RADIANS(51.941887)) + COS(RADIANS(gl.lat)) * COS(RADIANS(51.941887)) * COS(RADIANS(gl.lon) - RADIANS(8.872081)) ) * 6371 AS Distance FROM
geodb_locations_long as gl
WHERE (lat >= 51 AND lat <= 53 AND lon >= 7.31 AND lon <= 10.69)  
Having Distance <= 75 ORDER BY Distance
Ist doch eh nur eine Tabelle. Beim Join gilt das gleiche.

Dein SQL Code für die Berechnung sieht fast genau so aus wie ich das beschrieben habe, sofern du in ibk_breite den Breitengrad des Ortes füllst, um den herum du suchen willst und in ibk_laenge den Längengrad (und umkreis den Suchradius). Hier wird zunächst der maximale und minimale Breitengrad berechnet, indem du den Radius des Kreises direkt von km in Breitengrade umrechnest (geteilt durch 110 bzw. 111). Anschließend wird der grobe minimale und maximale Längengrad berechnet (hängt vom Breitengrad ab über /(cos(breitengrad) * 110)).

Das ist auch die Stelle die in meinen Augen so nicht stimmt wie sie in deinem Code berechnet wird: Einheitentechnisch kommt bei der Berechnung von laenge_west und laenge_ost km²/° heraus, denn die 111 ist ja der Umrechnungsfaktor mit der Einheit km/°. Das kann daher so nicht stimmen und passt auch nicht zu den Werten die du drunter berechnet hast (zur Kontrolle: Der Betrag des Cosinus liegt immer zwischen 0 und 1, bei der Division wird das Ergebnis kleiner, je größer der Divisor ist. Also nimm an, dass beim Cosinus eine 1 herauskam, dann multiplizierst du 110 mit 111 um deinen Längengrad zu bekommen. Das geht im Ergebnis mehrfach um die Erdkugel herum. Wenn der Cosinus nicht 1 war, dann wird das Ergebnis nur noch größer). Die 111 gehört noch mit in den Nenner damit es stimmt (also umkreis/(cos(breitengrad) * 110)).

Außerdem hast du 111 km zwischen zwei Breitengraden angesetzt statt 110 bei mir. Hierdurch wird dein Quadrat möglicherweise ein winziges bisschen zu schmal. Das ist aber vermutlich egal, man könnte auch anfangen sich zu streiten ob der Abstand geradlinig oder geodätisch (also entlang der Oberfläche der Erdkugel statt durch sie hindurch) gemeint ist. Wie gesagt, hier würde ich einfach 110 ansetzen und du bist auf der sicheren Seite.

Es ist übrigens weder ein Quadrat noch ein Rechteck, denn sowohl Längen- als auch Breitengrade verlaufen ja entlang einer Kugeloberfläche und sind deshalb gekrümmt (und zwei Längengrade laufen auf dem Weg zum Äquator auseinander). ;)

Meine Werte waren im Prinzip Beispielrechnungen, die du bis auf obigen Fehler auch mit dem SQL Code machen könntest den du gefunden hast (oder du machst es in PHP, geht ja auch). Die berechnete Nordgrenze musst du nur als Obergrenze für den Breitengrad nutzen, die berechnete Südgrenze als Untergrenze. Bei den Längengraden genauso, hier ist West die Untergrenze und Ost die Obergrenze (zum Glück bleiben wir komplett auf einer Seite des Nullmeridians, sonst müsstest du mit Ost und West Längengraden aufpassen).

Re: SQL: Umkreissuche realisieren ...

Verfasst: 15.05.2012 13:29
von Wuppi
ich glaub ich splitte mal .. erstmal das SQL-Thema beenden, dann das Mathethema (da ist mir nämlich weiterhin etwas nicht klar - ich brösel deinen Post aber erst noch mal in ruhe auseinander) - sonst wird es zu unübersichtlich.

Ich habe jetzt mal deine Variante gegen meine Subselect laufen lassen:
Meine: => 0,0152sek
Deine: => 0,0476sek

bei deiner hab ich aber ein gedankliches Problem:
Meine kann ich als DB-Noob nachvollziehen:
from (select ......) as gl <- damit bau ich mir eine "temporäre" Tabelle mit dem namen "gl". Mit der Abfrage davor (select gl.country ..... acos ... radians(gl.lat)..... from <gl>) frage ich diese temporäre Tabelle ab. Die Temporäre Tabelle enthält bei 100km Umkreis ca. 800 PLZ von diesen 800PLZ rechne ich jetzt nur noch die Entfernungen aus und schmeiße alles über 75km weg. Da bleiben dann ca. 300.

Bei deiner hab ich das Problem das mir die nicht klar ist:
Mir scheint als ob ich erstmal die ganze Tabelle penetriere - mathematisch - jetzt hab ich 14.000 LAT/LON/PLZ mit Entfernung und sage dann nur "zeig mir nur die mit folgenden lat/lon-Werten an wo die Distance nicht größer 75 ist" - hier bleiben dann 300 über. Oder hast du hier beim schnell tippern nen fehler gemacht? Das dein Query fast 3x solange dauert wie meiner lässt den Schluss zu?


... Am ende werden das 4 Tabellen sein die ich mit einer Abfrage abfrühstücke ... Ich brauche halt in der Ausgabe: Entfernung (Tabelle 1), Userspezifische Daten (Tabelle 2), Username (Tabelle 3 - keine Ahnung warum der nicht in Tabelle 1 ist - nervig!), Userfoto (nicht Avatar; Tabelle 4). Mit meinem Aufruf zur Entfernung hab ich das komplette query zwischenzeitlich hinbekommen (man sieht das übel aus ...) ... Dauer: 0.2905 Sekunden [Version 2 oder 3 wird auf jedenfall eine eigene Tabelle - dann sind die Querys wenigstens Human ...). Ist das trotzdem ein guter Wert? Ich kann das null einschätzen. (14000 PLZ, 2000 User; Tabelle 4 hat aber derzeit kaum Einträge ... muss ich noch generieren)

Hier mal das komplette Query ... ich weiß net mehr was ich da optimieren kann. Der reine "Umkreis"-Berechnungspart braucht ja nur 0.0152sek ... wo vernichte ich die restlichen 0.28sek?! Ich lasse da doch nur noch 300 PLZ mit 2000 Usern abgleichen... 0.28sek find ich da sehr viel.

Code: Alles auswählen

SELECT uov.userID, uov.userOption7, uov.userOption8, uov.userOption9, uov.userOption52, uov.userOption66, uov.userOption84, uov.userOption85, uov.userOption86, up.userpicID, up.userpicExtension, u.userName, ACOS( SIN( RADIANS( gl.lat ) ) * SIN( RADIANS( 51.941887 ) ) + COS( RADIANS( gl.lat ) ) * COS( RADIANS( 51.941887 ) ) * COS( RADIANS( gl.lon ) - RADIANS( 8.872081 ) ) ) *6371 AS Distance
FROM (

SELECT *
FROM geodb_locations_long
WHERE (
lat >= 50.95089601
AND lat <= 52.93287799
AND lon >= 7.264530901
AND lon <= 10.4796311
)
) AS gl
JOIN wcf1_user_option_value uov ON ( uov.userOption65 = gl.plz
AND uov.userOption85 = gl.country )
LEFT OUTER JOIN wcf1_user_pictures up ON uov.userID = up.userID
LEFT OUTER JOIN wcf1_user u ON uov.userID = u.userID
HAVING Distance <=75
ORDER BY Distance
... das Berechnungsthema später

... und übrigens vielen Dank für deine mühe!

Re: SQL: Umkreissuche realisieren ...

Verfasst: 15.05.2012 16:06
von gn#36
Dass dein Query mit dem Subselect schneller ist wundert mich, möglicherweise hängt das aber mit der eigentlich nicht ganz standardkonformen Verwendung von "HAVING" zusammen. Eigentlich sollte die Datenbank die Abfrage optimieren können wenn man alles in ein Query schreibt anstatt die Optimierung von Hand vorzugeben (wie du es mit dem Subselect machst). Eigentlich sollte die DB nämlich erst die WHERE Bedingungen abklopfen bevor sie beginnt irgendwelche Berechnungen auf den Daten auszuführen, die sie aus der DB holt.

Mein Tipp wäre, dass das auch der Grund ist, warum das Query plötzlich langsamer wird, wenn noch eine weitere Tabelle ins Spiel kommt: Die DB kann das Query nicht mehr beliebig optimieren, weil du vorgibst, dass zunächst Daten in eine temporäre Tabelle geschrieben werden müssen. Mit der verheiratest du dann Daten einer anderen Tabelle, aber vermutlich liegen auf der temporären Tabelle keine Indizes und deshalb geht dieser JOIN dann viel langsamer, als man das sonst erwarten würde. Hast du mal meine Variante im großen Query getestet (also dem mit JOIN)? Ich habe in der Vergangenheit eigentlich immer das Gefühl gehabt, dass Subselects sehr viel langsamer laufen als ein einfacher JOIN, spätestens wenn die Abfragen komplexer werden.

Dabei fällt mir auf: Müsstest du den JOIN nach AS gl nicht durch einen RIGHT JOIN ersetzen können? Es reicht ja ein Ort pro User, dann muss die DB nicht alle Kombinationen aus Usern und PLZ durchsehen. Oder können User mehr als einen Ort angeben (in dem Fall muss es so bleiben, wenn du alle Kombinationen willst). Ist ein Schnellschuss, möglicherweise ist das auch kontraproduktiv.

Re: SQL: Umkreissuche realisieren ...

Verfasst: 15.05.2012 18:30
von Pyramide
Dass das ganze nicht besonders schnell ist, liegt vermutlich an den fehlenden Indexen.
Wuppi hat geschrieben:Indize sind in der Tabelle nur auf die userID - und wie gesagt: die Tabelle wird von einem System verwaltet. K.a. was da passiert wenn ich da indize setze und dann kommt nen update was mir das alles wieder zurücksetzt.
Alle Zeiten sind UTC+02:00
Seite 3 von 4

Powered by phpBB® Forum Software © phpBB Limited

Deutsche Übersetzung durch phpBB.de