MSSQL - INSERT - kartesisches Produkt

[Froschkoenig84]

Ich habe eine Datentabelle mit Städten und LAT/LON Werten (~100K Einträge)

DESTINATIONS {
 id,
 lat,
 lon,
 ...
}

Nun sollen die Distanzen errechnet und in eine neue Tabelle geschrieben werden...

DISTANCES {
 id_a,
 id_b,
 distance
}

Die Ermittlung der Distanzen (in Metern) stellt generell kein Problem dar...

ROUND(111045
 * DEGREES(ACOS(COS(RADIANS(A.lat))
 * COS(RADIANS(B.lat))
 * COS(RADIANS(A.lon) - RADIANS(B.lon))
 + SIN(RADIANS(A.lat))
 * SIN(RADIANS(B.lat)))),0)
AS 'distance'

Aber hier bin ich ausgestiegen...

1. Ich brauche eigentlich nicht das vollständige kartesische Produkt, sondern nur die 100 nächstgelegenen.
2. Keine Duplikate (a_id+b_id == b_id+a_id), z.B.besitzt [Berlin:München] die gleiche Entfernung wie [München:Berlin]
3. Keine Abfragen auf die gleiche ID (a_id != b_id), denn es sind immer 0 Meter von [Berlin:Berlin]

Egal ob mit INSERT-SELECT oder mit JOINs oder wie auch immer, ich bekomme schon den ersten Punkt (die 100 nächstgelegenen) nicht auf die Reihe.

Kann mir jemand einen Ansatz geben?

 

[Froschkoenig84]

//nur kurz als Ergänzung, da es in einem anderen Forum anscheinend missverstanden wurde... ich will nicht nur 100 Einträge, ich will [jedes * 100]

 

[akretschmer]

Ich brauche eigentlich nicht das vollständige kartesische Produkt, sondern nur die 100 nächstgelegenen.

Das ist sicherlich machbar, aber ganz ehrlich gesagt denke ich, das ist der falsche Weg. Deine DB wächst explosionsartig an. Besser ist hier, die Entfernung dann zu berechnen, wenn diese benötigt wird. Für Umkreissuche bietet sich KNN (Nächste-Nachbarn-Klassifikation – Wikipedia) an, manche DB's haben das auch implementiert.

 

[akretschmer]

Um Dir einen Ansatz zu zeigen:

2 und 3 erreichst Du, daß Du nur z.B. kleiner a_id als b_id zuläßt. Um die Top N dann je gruppe zu ermitteln gibt es Row_number. Mit künstlich erzeigten Daten:

test=*# create table alle_abstaende as select x, y, random()*10000 as abstand from generate_series(1,100) x cross join generate_series(1,100) y where x<y;
SELECT 4950

Daraus die Top 3:

test=*# create table top_3 as select * from (select x,y,abstand, row_number() over (partition by x order by abstand asc) from alle_abstaende) foo where row_number <= 3 ;
SELECT 294

sieht so aus:

test=*# select * from top_3 limit 20;
 x | y  |  abstand  | row_number
---+----+------------------+------------
 1 |  4 | 39.3241690471768 |  1
 1 | 78 | 209.234217181802 |  2
 1 | 22 |  574.3224080652 |  3
 2 | 68 |  108.52821636945 |  1
 2 | 76 | 252.223261632025 |  2
 2 | 52 | 398.665275424719 |  3
 3 | 92 | 116.192628629506 |  1
 3 | 66 | 164.031824097037 |  2
 3 | 40 | 230.207149870694 |  3
 4 | 78 | 24.2612278088927 |  1
 4 | 26 | 192.913748323917 |  2
 4 | 50 | 197.168891318142 |  3
 5 | 19 |  10.787989012897 |  1
 5 | 78 | 14.3856834620237 |  2
 5 | 86 | 507.271643728018 |  3
 6 | 38 | 213.845274411142 |  1
 6 | 67 | 219.477587379515 |  2
 6 |  9 | 531.952395103872 |  3
 7 | 22 | 394.686423242092 |  1
 7 | 60 |  400.8320113644 |  2
(20 rows)

Wie gesagt: mit KNN-fähigen Systemen kommst hier insgesamt sehr sicher besser.

 

[ukulele]

Ich bin kein Mathe-Genie, aber ich denke das ich zur Ermittlung der 100 nähsten Städte eine Abkürzung brauche und nicht erst die Entfernung von Stadt A zu allen 100k Städten berechnen kann um diese dann zu sortieren. Also konkret ein Join von 100k * 100k Einträgen der sortiert werden will, das würde ja enorme Laufzeiten verursachen.

Kann ich da vieleicht nach A_lat-B_lat+A_lon-B_lon rechnen und für die sagen wir dann für die 200 kleisten Werte das kartesische Produkt bestimmen? Poste am besten mal 10 Beispieldatensätze.

 

[Froschkoenig84]

Beispieldatensätze...

id    name    geo_lat    geo_lon
12    Berlin    52,5138    13,3501
14    Frankfurt am Main    50,1088    8,66565
15    Kiel    54,3233    10,1396
16    München    48,1398    11,5601
17    Mainz    49,9991    8,27243
18    Osnabrück    52,2759    8,04471
20    Bielefeld    52,023    8,53309
21    Braunschweig    52,2636    10,5212
22    Dresden    51,0519    13,7402
23    Augsburg    48,3689    10,8978
24    Aachen    50,7764    6,08391
25    Düsseldorf    51,219    6,77704
26    Essen    51,457    7,01249

 

[ukulele]

-- Testdaten
WITH destinations(id,name,lat,lon) AS (
SELECT   12,'Berlin',52.5138,13.3501
UNION ALL
SELECT   14,'Frankfurt am Main',50.1088,8.66565
UNION ALL
SELECT   15,'Kiel',54.3233,10.1396
UNION ALL
SELECT   16,'München',48.1398,11.5601
UNION ALL
SELECT   17,'Mainz',49.9991,8.27243
UNION ALL
SELECT   18,'Osnabrück',52.2759,8.04471
UNION ALL
SELECT   20,'Bielefeld',52.023,8.53309
UNION ALL
SELECT   21,'Braunschweig',52.2636,10.5212
UNION ALL
SELECT   22,'Dresden',51.0519,13.7402
UNION ALL
SELECT   23,'Augsburg',48.3689,10.8978
UNION ALL
SELECT   24,'Aachen',50.7764,6.08391
UNION ALL
SELECT   25,'Düsseldorf',51.219,6.77704
UNION ALL
SELECT   26,'Essen',51.457,7.01249
     )

-- Abfrage
SELECT   t3.id_a,
     t3.id_b,
     t3.name_a,
     t3.name_b,
     t3.distance
FROM   (
SELECT   ROW_NUMBER() OVER (PARTITION BY t2.distance ORDER BY t2.id_a) AS duplikat,
     t2.id_a,
     t2.id_b,
     t2.name_a,
     t2.name_b,
     t2.distance
FROM   (
SELECT   ROW_NUMBER() OVER (PARTITION BY t1.id_a ORDER BY t1.distance) AS top10,
     t1.*
FROM   (
SELECT   A.id AS id_a,
     B.id AS id_b,
     A.name AS name_a,
     B.name AS name_b,
     ROUND(111045
      * DEGREES(ACOS(COS(RADIANS(A.lat))
      * COS(RADIANS(B.lat))
      * COS(RADIANS(A.lon) - RADIANS(B.lon))
      + SIN(RADIANS(A.lat))
      * SIN(RADIANS(B.lat)))),0) AS distance
FROM   DESTINATIONS A
INNER JOIN DESTINATIONS B
ON     A.id != B.id --Anforderung 3)
     ) t1
     ) t2
WHERE   t2.top10 <= 10 --Anforderung 1) nur eben auf die ersten 10 Datensätze
     ) t3
WHERE   t3.duplikat = 1 --Anforderung 2) keine "Duplikate"
ORDER BY t3.id_a,t3.distance ASC

Das würde zunächst mal die von dir gewünschten Daten liefern. Dadurch das ich mehrfach ROW_NUMBER() einsetze und darauf eine Bedingung anwende habe ich jetzt sehr viel geschachtelt. Außerdem berechne ich im ersten Schritt für alle Datensätze die Dinstanz zu allen Datensätzen um danach zu sortieren. Bei 10 Datensätzen kein Ding, bei 100k könnte das sehr sehr lange dauern.

 

[Froschkoenig84]

Genau das ist das Problem.

Obwohl die SQL-Abfrage bereits getuned bis zum Äußersten ist und keinerlei unbenötighte ("leere") Berechnungen mehr durchführt. Schafft er pro Minute nicht einmal 1'000 Ergebnisse. Damit diese Sortierung / Berechnung / Dublettenvermeidung auch funktioniert, müsste sie im Stück durchlaufen.

Bei 100K * 100K /2 - 100K wären das immer noch 4'999'900'000. Nun brauchen wir nur maximal die 100 nächstgelegenen Ergebnisse, was aber immer noch: 34,7215 Tage dauern würde. :/

Da die meisten dieser Ergebnisse irgendwelche Käffer in Sibirien sind, die vermutlich niemals ernsthaft abgefragt werden... habe ich mich nun - genau wie oben bereits vorgeschlagen - für die C-B-C (Calc-By-Call) Variante entschieden. Hatte das am Montag (als ich davon erfahren habe, ein kartesisches Produkt von 100K Datensätzen zu erzeugen) bereits im Hinterkopf, wollte es aber gerne einfach mal probieren.

Ich werde es auf Anforderung programmseitig lösen. Also wird bei Aufruf einer Destination eine SQL-Routine (Prozedur) abgefragt, die ermittelt, welche 100 Destinationen sich nächstliegend befinden.

Diese werden über eine weitere (Sub-) Routine (Prozedur) dann in die Distanzentabelle geschrieben, bzw. ausgegeben.
Beim nächsten Abruf (falls nicht bereits älter als [ZEITLIMIT], kann dann vorher bereits geprüft werden, ob in der Distanzentabelle bereits vorhandene Ergebnisse existieren oder ob es erst noch errechnet werden muss.


Generell bin ich ein Freund davon möglichst viel Rechenarbeit im Vorfeld zu leisten, um die Programme in deren Ausführungszeiten zu beschleunigen, da wir hier aber von Datensätzen reden, die sich auch verändern könnten oder gelöscht/hinzugefügt werden, würden sich diese Veränderungen auf große Bereiche der Distanzentabelle auswirken. Sollte es irgendwann mal eine Pflegemaste/CMS für die Destinations geben, könnte man diese Erstberechnung auch immer dann durchführen, wenn man einen Datensatz anlegt/verändert/löscht.


Nur kurz als Info, das war meine SQL-Code:

INSERT INTO [DISTANCES] (id_a, id_b, distance)
    SELECT
        A.id,
        B.id,
        ROUND(111045 * DEGREES(ACOS(COS(RADIANS(A.geo_lat)) * COS(RADIANS(B.geo_lat)) * COS(RADIANS(A.geo_lon) - RADIANS(B.geo_lon)) + SIN(RADIANS(A.geo_lat)) * SIN(RADIANS(B.geo_lat)))),0)
    FROM [DESTINATIONS] AS A
    INNER JOIN [DESTINATIONS] AS B
        ON b.id IN(
            SELECT TOP 100
                C.id
            FROM [DESTINATIONS] AS C
            WHERE
                A.id < C.id
            ORDER BY ROUND(111045 * DEGREES(ACOS(COS(RADIANS(A.geo_lat)) * COS(RADIANS(B.geo_lat)) * COS(RADIANS(A.geo_lon) - RADIANS(B.geo_lon)) + SIN(RADIANS(A.geo_lat)) * SIN(RADIANS(B.geo_lat)))),0) ASC
        )

 

[Froschkoenig84]

Bei dieser Gelegenheit, ... ich habe in meinem ganzen Leben noch nie mit MSSQL-Prozeduren gearbeitet. - Ich vermute, sie funktionieren ähnlich wie TRIGGER ,nur eben nicht eventgesteuert, sondern als Methode abrufbar.

Ich lese mich erst mal kurz ein - aber kann ich bei Problemen noch mal auf euch zurückkommen?

 

[ukulele]

Abgesehen davon das deine DB und möglicherweise auch deine TempDB ganz gut voll laufen, das sollte man beachten.

Helfen könnten dir eventuell auch noch Indexe, aber das ist mir dann auch etwas zu komplex.

 

[ukulele]

Darf ich fragen woher die Koordinaten stammen, sind die von OpenGeoDB?

 

[Froschkoenig84]

Die Daten stammen direkt vom Kunden (die Tabelle ist ein "unveränderbarer" Dump)

 

[akretschmer]

Bei 100K * 100K /2 - 100K wären das immer noch 4'999'900'000. Nun brauchen wir nur maximal die 100 nächstgelegenen Ergebnisse, was aber immer noch: 34,7215 Tage dauern würde. :/

Ich nannte Dir einen Weg.

 

[Froschkoenig84]

Ja, das stimmt. CBC reicht mir aber vollkommen. Aktuell kämpfe ich mich aber durch die Prozeduren. Vermutlich werde ich morgen die ein oder andere Frage haben.

 

[Froschkoenig84]

»PROCEDURES«

Okay, die erste Prozedur, die ich je geschrieben habe, gibt mir 100 Destination-IDs und mit je einer Distanz zur übergeben/abgefragten Destination-ID zurück. (via SELECT)

Ich übergebe ID, LAT, LON und MARKET, damit ich keine weitere Abfrage benötige (die Daten der ausgewählten Destination liegen im Client-Objekt sowieso vor...

EXEC [GetDistancesBetweenDestinations] 12, 52.5138, 13.3501, 'de';

Okay, wenn ich nun also jenen Code ausführe, wird meine Prozedur gestartet:

USE [MyDatabase]
GO
/****** Object:  StoredProcedure [dbo].[GetDistancesBetweenDestinations]    Script Date: 12/09/2015 11:47:37 ******/
SET ANSI_NULLS ON
GO
SET QUOTED_IDENTIFIER ON
GO
ALTER PROCEDURE [dbo].[GetDistancesBetweenDestinations]
    @id INT,
    @geo_lat FLOAT,
    @geo_lon FLOAT,
    @market CHAR(2),
    @limit INT = 25,
    @meter INT = 111045
AS
BEGIN
    SELECT TOP 250
        --@id AS 'id_a',
        [id] AS 'id_b',
        ROUND(@meter * DEGREES(ACOS(COS(RADIANS(@geo_lat)) * COS(RADIANS(geo_lat)) * COS(RADIANS(@geo_lon) - RADIANS(geo_lon)) + SIN(RADIANS(@geo_lat)) * SIN(RADIANS(geo_lat)))),0) AS 'distance'
    FROM
        [MyDatabase].[dbo].[Destinations]
    WHERE
        [is_country] <> 1 AND
        [market] = @market AND
        [geo_lat] IS NOT NULL AND [geo_lat] <> 0 AND [geo_lat] <> @geo_lat AND
        [geo_lon] IS NOT NULL AND [geo_lon] <> 0 AND [geo_lon] <> @geo_lon AND
        [count_pois] >= 2 AND
        [tg_core_region_priority_rank] BETWEEN 1 AND 1000
    ORDER BY
        'distance' ASC;
END

Was ist nun sinnvoller...

A) eine Prozedur, die einen INSERT (SELECT) macht - && - anschließend einen clientseitigen SELECT auf jenen INSERT?
B) eine Prozedur, die erst einen SELECT macht (und clientseitig ausgibt) und diesen über eine zweite Prozedur (serverseitig) zu einem INSERT ausführt?
C) ganz anders??

Mein Programm soll die Daten erhalten. Es wäre aber schön, wenn direkt mit der Ausgabe (am besten nicht über das Programm/Client, sondern sql-server-seitig) ein INSERT in die neue Distances-Tabelle geschieht. Um beim nächsten mal einfach schneller abfragen zu können. Klappt das mit einer Prozedur oder benötige ich mehrere? Kann ich einen INSERT machen und die Daten dennoch zurückgeben?