Laufzeit mit Entfernungstabelle verkürzen?

[Gast]

Hallo,

MySQL berechnet Entfernungen zwischen Orten aufgrund der geografischen Koordinaten. Das sieht dann so aus:

SELECT  
...  
,ROUND( 6366.19773095 * ACOS( SIN(0.869112880969) *SIN(RADIANS(ort1.geo_breite)) +COS(0.869112880969) *COS(RADIANS(ort1.geo_breite)) *COS(RADIANS(ort1.geo_laenge) -0.173359191277 ))) distanz  
...

Weil ich dabei bin, die Programmlaufzeiten zu verkürzen, habe ich überlegt, ob die distanz zwischen zwei Orten schneller ermittelt wird, wenn ich eine Entfernungstabelle anlege.

Also erst in die Entfernungstabelle schauen (mit JOIN), ob Distanz vorhanden. Wenn nicht, ausrechnen und speichern. Ist zu Beginn natürlich aufwändiger.

Bitte um Meinungen, ob das laufzeitmäßig lohnt. Es geht um eine Seite, die sehr oft aufgerufen wird.

Gruß, Gast

[Tom]

Hello,

MySQL berechnet Entfernungen zwischen Orten aufgrund der geografischen Koordinaten. Das sieht dann so aus:

SELECT

...
,ROUND( 6366.19773095 * ACOS( SIN(0.869112880969) *SIN(RADIANS(ort1.geo_breite)) +COS(0.869112880969) *COS(RADIANS(ort1.geo_breite)) *COS(RADIANS(ort1.geo_laenge) -0.173359191277 ))) distanz
...

>   
> Weil ich dabei bin, die Programmlaufzeiten zu verkürzen, habe ich überlegt, ob die distanz zwischen zwei Orten schneller ermittelt wird, wenn ich eine Entfernungstabelle anlege.  
>   
> Also erst in die Entfernungstabelle schauen (mit JOIN), ob Distanz vorhanden. Wenn nicht, ausrechnen und speichern. Ist zu Beginn natürlich aufwändiger.  
>   
> Bitte um Meinungen, ob das laufzeitmäßig lohnt. Es geht um eine Seite, die sehr oft aufgerufen wird.  
  
Wenn Du mal das komplette Statement und die Tabellendefinitionen dazu hättest?  
Vermutlich berechnest Du auch noch jede Entfernung zweimal?  
  
  
  
  
  
Liebe Grüße aus dem schönen Oberharz  
  
  
Tom vom Berg  
![](http://selfhtml.bitworks.de/Virencheck.gif)  
  

-- 
 ☻\_  
/▌  
/ \ Nur selber lernen macht schlau  
<http://bergpost.annerschbarrich.de>

[Gast]

Hello,

Wenn Du mal das komplette Statement und die Tabellendefinitionen dazu hättest?
Vermutlich berechnest Du auch noch jede Entfernung zweimal?

Wieso?

Ich hole mir genau einen Ort mit Koordinaten:

SELECT  
 name  
,geo_laenge  
,geo_breite  
FROM orte  
WHERE id = 561  
...

berechne longitude und latitude einmal:

$rad_lon1 = deg2rad( $row_zentrum['geo_laenge'] ); // = 0.173359191277  
$rad_lat1 = deg2rad( $row_zentrum['geo_breite'] ); // = 0.869112880969

uns setze die in die Formel für die anderen Orte ein:

SELECT  
...  
,ROUND( 6366.19773095 * ACOS( SIN(0.869112880969) *SIN(RADIANS(ort1.geo_breite)) +COS(0.869112880969) *COS(RADIANS(ort1.geo_breite)) *COS(RADIANS(ort1.geo_laenge) -0.173359191277 ))) distanz  
...  
GROUP BY ...  
ORDER BY dist_km

Tabelle orte:

 `id` int(11) NOT NULL auto_increment,  
  `owner_id` int(11) NOT NULL default '0',  
  `land_kz` varchar(3) collate utf8_unicode_ci default NULL,  
  `name` varchar(50) collate utf8_unicode_ci NOT NULL,  
  `geo_laenge` float default NULL,  
  `geo_breite` float default NULL,  
  `plz` varchar(10) collate utf8_unicode_ci NOT NULL,  
...  
  `last_modified` timestamp NOT NULL default CURRENT_TIMESTAMP on update CURRENT_TIMESTAMP,  
  PRIMARY KEY  (`id`),  
  UNIQUE KEY `land_plz_name` (`land_kz`,`plz`,`name`),  
  KEY `plz` (`plz`)  
)

Würde ein Key auf Länge und Breite die Berechnung beschleunigen?

MfG Gast

[fastix®]

Moin!

Würde ein Key auf Länge und Breite die Berechnung beschleunigen?

Nein. Du machst vermutlich eine Umkreissuche und Vincenz hat richtig ausgeführt, dass MySQL keine funktionalen Indizes kennt.

Wenn es wirklich sehr viele Abfragen sind (wird ja wohl der Kern Deines Skriptes sein), dann lohnt es sich eine Tabelle anzulegen, die jeweils die Entfernungen zwischen den Locations beinhaltet:

LOC_ID_1; LOC_ID_2 ENTF
12200;123567;556.45

Dann kannst Du Mit einem

SELECT LOC_ID_1, LOC_ID_2, FROM entfernungen
WHERE
ENTF <= $entf
AND (
(LOC_ID_1 = $intLOC)
OR
(LOC_ID_2 = $intLOC)
);

Deine Datentabelle hat dann zwar eine ganze Menge Einträge, aber den Speicher zu investieren lohnt sich.

Noch zwei Tipps für das Anlegen der Tabelle:

1.) Bereits angelegte Paare solltest Du nicht nochmals anlegen. Mach also sowas:

for $ort_1 = 1 To end
{
  for $ort2 = ($ort_1+1) to end
  {

// Berechnen und Einpflegen der Daten in Mysql
  }
}

2. Es handelt sich um das Anlegen einer großen Anzahl von Datensätzen. Lege die Indizies  für diese Tabelle (alle 3 Spalten)erst nach dem Befüllen an. Das ist deutlich(!) schneller.

MFFG (Mit freundlich- friedfertigem Grinsen)

fastix

[Tom]

Hello,

Wenn es wirklich sehr viele Abfragen sind (wird ja wohl der Kern Deines Skriptes sein), dann lohnt es sich eine Tabelle anzulegen, die jeweils die Entfernungen zwischen den Locations beinhaltet:

LOC_ID_1; LOC_ID_2 ENTF
12200;123567;556.45

Dann kannst Du Mit einem

SELECT LOC_ID_1, LOC_ID_2, FROM entfernungen
WHERE
ENTF <= $entf
AND (
(LOC_ID_1 = $intLOC)
OR
(LOC_ID_2 = $intLOC)
);

Deine Datentabelle hat dann zwar eine ganze Menge Einträge, aber den Speicher zu investieren lohnt sich.

Das löst aber immer noch nicht das Problem der Duplizität der Paare. Ich gehe davon aus, dass "Entfernung" hier der Absolutwert eines Skalars ist und keine gerichtete Größe (Vektor).

Es muss also einen Mechanismus geben (Stored Procedure), der zum Abfragen und zum Eintragen eines Paares erst eine Ordnung in das Paar bringt, also z.B. den alphanumerisch kleineren Ort immer auf der linken Seite nennt.

Sonst wären nachher doch alle Paare doppelt vorhanden

A - B
  B - A

Liebe Grüße aus dem schönen Oberharz

Tom vom Berg

[fastix®]

Moin!

Das löst aber immer noch nicht das Problem der Duplizität der Paare.

Das löste der folgende Pseudocode:

1.) Bereits angelegte Paare solltest Du nicht nochmals anlegen. Mach also sowas:
for $ort_1 = 1 To end
{
   for $ort_2 = ($ort_1+1) to end
   {
        // Berechnen und Einpflegen der Daten in Mysql
   }
}

Danach gibt es jede Paarung nur einmal.

MFFG (Mit freundlich- friedfertigem Grinsen)

fastix

[Tom]

Hello,

Moin!

Das löst aber immer noch nicht das Problem der Duplizität der Paare.

Das löste der folgende Pseudocode:

1.) Bereits angelegte Paare solltest Du nicht nochmals anlegen. Mach also sowas:
for $ort_1 = 1 To end
{
   for $ort_2 = ($ort_1+1) to end
   {
        // Berechnen und Einpflegen der Daten in Mysql
   }
}

Danach gibt es jede Paarung nur einmal.

Und wie findet man die dann später wieder?
Irgendwie verstehe ich das jetzt nicht, wie Du das meinst.

Ein Kombinationsschlüssel muss doch eindeutig reproduzierbar sein.

Liebe Grüße aus dem schönen Oberharz

Tom vom Berg

[fastix®]

Moin!

Beim Anlegen einmalig:

Trage für jeden Ort die Enfernungen für alle in der Liste folgenden Orte zu diesem in die Datenbank ein.

Beim Abfragen

Gib ort 1, ort 2 aus, WENN (ort 1  = dem gesetztem Ort ODER ort2 = dem gesetztem Ort) UND (die Entfernung < X)  ist.

MFFG (Mit freundlich- friedfertigem Grinsen)

fastix

[Tom]

Hello,

Beim Abfragen

Gib ort 1, ort 2 aus, WENN (ort 1  = dem gesetztem Ort ODER ort2 = dem gesetztem Ort) UND (die Entfernung < X)  ist.

Stimmt das so wirklich?

Müsste das nicht heißen:

Gib ort 1, ort 2, Entfernung aus,
WENN (ort_1  = dem gesetztem Ort(A) UND ort_2 = dem gesetztem Ort(B))
ODER (ort_2 = dem gesetztem Ort(A) UND ort_1 = dem gesetztem Ort(B))
UND Entfernung < gesuchter Entfernung ist.

Und das ist dann schon ganz schön aufwändig. Ob die Datenbankmaschine da eine sinnvolle Optimierung finden kann, ist fraglich.

Daher sollte man gleich beim Eintragen der Pärchen für eine Ordnung sorgen.

Liebe Grüße aus dem schönen Oberharz

Tom vom Berg

[fastix®]

Moin!

Gib ort 1, ort 2 aus, WENN (ort 1  = dem gesetztem Ort ODER ort2 = dem gesetztem Ort) UND (die Entfernung < X)  ist.

Stimmt das so wirklich?

Ja.

Müsste das nicht heißen:

Gib ort 1, ort 2, Entfernung aus,
WENN (ort_1  = dem gesetztem Ort(A) UND ort_2 = dem gesetztem Ort(B))
ODER (ort_2 = dem gesetztem Ort(A) UND ort_1 = dem gesetztem Ort(B))
UND Entfernung < gesuchter Entfernung ist.

Nein. Definitiv nicht. Das würde kein Ergebnis bringen. Es gibt bei einer Umkreissuche immer nur _einen_ gesetzten Ort, das ist der Ausgangsort, gesucht werden die mit der passenden Entfernung.

Und das ist dann schon ganz schön aufwändig. Ob die Datenbankmaschine da eine sinnvolle Optimierung finden kann, ist fraglich.

Wieso sollte die Datenbank das nicht können?

MFFG (Mit freundlich- friedfertigem Grinsen)

fastix

[Vinzenz Mai]

Hallo,

Also erst in die Entfernungstabelle schauen (mit JOIN), ob Distanz vorhanden. Wenn nicht, ausrechnen und speichern. Ist zu Beginn natürlich aufwändiger.

Bitte um Meinungen, ob das laufzeitmäßig lohnt. Es geht um eine Seite, die sehr oft aufgerufen wird.

ja, selbstverständlich wird es sich laufzeitmäßig lohnen. Die Kombination der beiden Verweisspalten mit einem eindeutigen Index versehen und auf die Reihenfolge achten, damit Du maximal n*(n-1)/2 Datensätze speichern musst, wenn n die Anzahl der Orte ist.

Freundliche Grüße

Vinzenz

[Matti Maekitalo]

Tach auch.

Also erst in die Entfernungstabelle schauen (mit JOIN), ob Distanz vorhanden. Wenn nicht, ausrechnen und speichern. Ist zu Beginn natürlich aufwändiger.

ja, selbstverständlich wird es sich laufzeitmäßig lohnen. Die Kombination der beiden Verweisspalten mit einem eindeutigen Index versehen und auf die Reihenfolge achten, damit Du maximal n*(n-1)/2 Datensätze speichern musst, wenn n die Anzahl der Orte ist.

Würde ich so erstmal nicht aussagen. Die im OP angegebene Formel kann IMHO in O(1) berechnet werden. Das Nachschlagen wird, wenn mich nicht alles täuscht, mit O(log N) zu Buche schlagen.

Lieber Gast: bist du sicher, dass der angegebene Ausdruck langsam ist?
Falls meine Vermutung mit O(1) falsch sein sollte, ist der Ansatz, welchen du wählst, sicherlich nicht allzu falsch.

Bis die Tage,
Matti

[Vinzenz Mai]

Hallo Matti,

Würde ich so erstmal nicht aussagen. Die im OP angegebene Formel kann IMHO in O(1) berechnet werden. Das Nachschlagen wird, wenn mich nicht alles täuscht, mit O(log N) zu Buche schlagen.

ja und :-) Soviel zur Theorie.

Lieber Gast: bist du sicher, dass der angegebene Ausdruck langsam ist?

klar ist der Ausdruck langsam. Und warum spielt O(1) in der Praxis keine Rolle? Warum nutzt man Quicksort, was im Original miserabel langsam sein *kann*?
Warum hat man bis vor ca. 30 Jahren noch mit Logarithmentafeln gearbeitet?
Warum haben früher exzellente Mathematiker einen Großteil ihrer Arbeit in das Erstellen solcher Tafeln gesteckt? Weil Nachschlagen schneller sein kann als Berechnen :-)

Haufenweise trigonometrische Funktionen, die *sehr* aufwendig sein werden.

Falls meine Vermutung mit O(1) falsch sein sollte, ist der Ansatz, welchen du wählst, sicherlich nicht allzu falsch.

Ich gehe von einer dünn besetzten Matrix aus. Da schlägt die Praxis die Theorie. Sprich: O(log N) mit knappem inneren Code ist schneller als O(1).

Freundliche Grüße

Vinzenz

[Vinzenz Mai]

Hallo,

Ich gehe von einer dünn besetzten Matrix aus. Da schlägt die Praxis die Theorie. Sprich: O(log N) mit knappem inneren Code ist schneller als O(1).

und spätestens bei einer Umkreissuche schlägt selbst die voll besetzte Nachschlagematrix die Berechnung in MySQL, da MySQL keine funktionalen Indexe kennt.

Freundliche Grüße

Vinzenz

[ChrisB]

Hi,

SELECT

...
,ROUND( 6366.19773095 * ACOS( SIN(0.869112880969) *SIN(RADIANS(ort1.geo_breite)) +COS(0.869112880969) *COS(RADIANS(ort1.geo_breite)) *COS(RADIANS(ort1.geo_laenge) -0.173359191277 ))) distanz
...

>   
> Weil ich dabei bin, die Programmlaufzeiten zu verkürzen, habe ich überlegt, ob die distanz zwischen zwei Orten schneller ermittelt wird, wenn ich eine Entfernungstabelle anlege.  
  
Ich würde erst mal versuchen, die Anzahl der Berechungen, die für jeden Datensatz ausgeführt werden müssen, zu reduzieren.  
  
„Feste“ Bestandteile wie `6366.19773095 * ACOS( SIN(0.869112880969)`{:.language-sql} müsste MySQL zwar m.E. optimieren können (ob es das tut, weiß ich aber nicht) - aber z.B.  
`SIN(RADIANS(ort1.geo_breite)) +COS(0.869112880969) *COS(RADIANS(ort1.geo_breite)) *COS(RADIANS(ort1.geo_laenge)`{:.language-sql}  
muss für jeden Datensatz einzeln ausgerechnet werden, und dabei RADIANS(ort1.geo\_breite) auch noch doppelt, einmal im SIN und einmal im COS.  
  
Wenn in dieser Formel nichts drin steckt, was sich pro Query ändert, sondern alles nur von festen Werten, die in jedem Datensatz drin stecken, abhängt - dann könnte man das Ergebnis der gesamten Formel in einer zusätzlichen Spalte ablegen.  
Die einmal per UPDATE für alle Datensätze befüllt - dann braucht man nachher beim Auslesen der Daten nur noch diesen einen Spaltenwert auslesen, anstatt die Berechnung jedes Mal durchzuführen.  
Und einen Index kann man auch noch darauf setzen, wenn die Dsstanz als Selektions-/Sortierkriterium verwendet werden soll.  
  
MfG ChrisB  
  

-- 
RGB is totally confusing - I mean, at least #C0FFEE should be brown, right?

[Gast]

Hi,

Wenn in dieser Formel nichts drin steckt, was sich pro Query ändert, sondern alles nur von festen Werten, die in jedem Datensatz drin stecken, abhängt - dann könnte man das Ergebnis der gesamten Formel in einer zusätzlichen Spalte ablegen.

Pro Programmlauf sind die hier genannten Werte

$rad_lon1 = deg2rad( $row_zentrum['geo_laenge'] ); // = 0.173359191277
$rad_lat1 = deg2rad( $row_zentrum['geo_breite'] ); // = 0.869112880969

konstant, aber beim nächsten Lauf (anderer Ausgangsort) sind sie anders.

Die einmal per UPDATE für alle Datensätze befüllt - dann braucht man nachher beim Auslesen der Daten nur noch diesen einen Spaltenwert auslesen, anstatt die Berechnung jedes Mal durchzuführen.

Das passt wohl nicht.

MfG Gast

[ChrisB]

Hi,

Pro Programmlauf sind die hier genannten Werte

$rad_lon1 = deg2rad( $row_zentrum['geo_laenge'] ); // = 0.173359191277
$rad_lat1 = deg2rad( $row_zentrum['geo_breite'] ); // = 0.869112880969

konstant, aber beim nächsten Lauf (anderer Ausgangsort) sind sie anders.

Die mit diesen Werten berechneten SIN- und COS-Werte müssen nicht alle in der Query berechnet werden, sondern das kann PHP teilweise vorher schon einmalig machen.

Die einmal per UPDATE für alle Datensätze befüllt - dann braucht man nachher beim Auslesen der Daten nur noch diesen einen Spaltenwert auslesen, anstatt die Berechnung jedes Mal durchzuführen.

Das passt wohl nicht.

Zumindest die Bestandteile, in denen ort1.geo_breite/ort1.geo_laenge (direkt) vorkommen, ändern sich nicht, können also im Voraus berechnet werden.

Wenn du das machst, kannst du die eigentliche Berechnung innerhalb der Query von einem *Haufen* jedes Mal auszuwertender trigonometrischer Funktionen („teuer“!) auf ein paar Multiplikationen und Additionen „bekannter“, bereits vorliegender Werte plus je *einen* Aufruf von ACOS() und COS() herunterschrauben.

ROUND(  
  6366.19773095  
  *  
  ACOS( -- muss als Gesamtwert dynamisch berechnet werden  
    SIN(0.869112880969) -- vorher per PHP ermittelbar -> konstanter Wert  
    *  
    SIN(RADIANS(ort1.geo_breite)) -- vorher ermittelbar -> kann in extra Spalte liegen  
    +  
    COS(0.869112880969) -- vorher per PHP ermittelbar -> konstanter Wert  
    *  
    COS(RADIANS(ort1.geo_breite)) -- vorher ermittelbar -> kann in extra Spalte liegen  
    *  
    COS( -- muss als Gesamtwert dynamisch berechnet werden  
      RADIANS(ort1.geo_laenge) -- vorher ermittelbar -> kann in extra Spalte liegen  
      -  
      0.173359191277  
    )  
  )  
)

MfG ChrisB

[Gast]

Hi,

ROUND(

6366.19773095
  *
  ACOS( -- muss als Gesamtwert dynamisch berechnet werden
    SIN(0.869112880969) -- vorher per PHP ermittelbar -> konstanter Wert
    *
    SIN(RADIANS(ort1.geo_breite)) -- vorher ermittelbar -> kann in extra Spalte liegen
    +
    COS(0.869112880969) -- vorher per PHP ermittelbar -> konstanter Wert
    *
    COS(RADIANS(ort1.geo_breite)) -- vorher ermittelbar -> kann in extra Spalte liegen
    *
    COS( -- muss als Gesamtwert dynamisch berechnet werden
      RADIANS(ort1.geo_laenge) -- vorher ermittelbar -> kann in extra Spalte liegen
      -
      0.173359191277
    )
  )
)

  
Danke für die Anregung. Muss mal nachdenken, ob eine "verkürzte" Entfernungsberechnung oder eine fertige Entfernungstabelle mehr Vorteile hat.  
  
Bei einer Entfernungstabelle könnte ich nach Entfernung direkt sortieren und bekomme die nächsten 20 Orte. Beim Berechnen werden jedoch immer alle 9.000 Orte (okay, wg. Randbedingungen vielleicht nur 1.000) berechnet, um nur 20 rauszufiltern.  
  
MfG Gast

[Bademeister]

Hi.

Pro Programmlauf sind die hier genannten Werte

$rad_lon1 = deg2rad( $row_zentrum['geo_laenge'] ); // = 0.173359191277
$rad_lat1 = deg2rad( $row_zentrum['geo_breite'] ); // = 0.869112880969

konstant, aber beim nächsten Lauf (anderer Ausgangsort) sind sie anders.

Ist die Distanz zwischen zwei Orten nicht konstant?? Offenbar ist sie es, wenn Du sie in die Entfernungstabelle speichern willst. Was hat es mit dem "Ausgangsort" auf sich?

Viele Grüße,
der Bademeister

[Andreas Pflug]

Hallo,

ich sehe oben eine Handvoll trigonometrischer Operatoren. Ein heutiger Prozessor der untersten Kategorie mit 2+ GHz bzw. 3+ GFlops rechnet das in der Zeit, in der MySQL eine weitere Datenbanktabelle abfragt und dazu evtl. den langsamen Hauptspeicher oder gar die Festplatte bemühen muss, viele tausend mal durch (*). Abgesehen davon wird zusätzlicher Speicher in der DB verbraten.

Nach meiner Erfahrung wird ein Programm äußerst selten schneller, in dem man mit zusätzlichen Tabellen weiteren Speicher belegt. Am schnellsten sind CPUs, wenn alle Rechengrößen im Prozessor-Cache vorliegen.

MfG

Andreas

(*) Es könnte natürlich sein, dass die Durchführung mathematischer Berechnungen in MySQL sehr ineffizient implementiert ist, was ich aber nicht glauben mag...

[Kay]

Hallo Gast,

Weil ich dabei bin, die Programmlaufzeiten zu verkürzen, habe ich überlegt, ob die distanz zwischen zwei Orten schneller ermittelt wird, wenn ich eine Entfernungstabelle anlege.

»»

Wenn Du es richtig machst, ja sehr viel.

Bitte um Meinungen, ob das laufzeitmäßig lohnt. Es geht um eine Seite, die sehr oft aufgerufen wird.

Gruß, Gast

Was heißt "die sehr oft aufgerufen wird"? 15.000 mal die Minute, die Stunde, am Tag, in der Woche, im Monat oder im Jahr?

Welche Genauigkeit wird benötigt?

Wenn es um Geschwindikeit bei Koordinaten geht ist MySQL bestimmt nicht die erste Wahl.

Das Thema kann sehr komplex werden.

http://de.wikipedia.org/wiki/Orthodrome

http://en.wikipedia.org/wiki/R-tree

Geospatial Indexing ... und und und

Ich wünsch Dir noch viel Spass beim Thema

Kay