ein superfetter Job für mysql?

Hallo miteinander,

ich denke gerade über ein Projekt nach und habe keine Ahnung, ob das
überhaupt ansatzweise mit mysql lösbar ist.

Folgendes:

Ich habe 1 Mio Datensätze (oder Objekte oder Entitäten)

Jeder Datensatz hat 10 Attribute, die jeweils eine Integerzahl
beinhalten.

Jetzt sollen mit den 1 Mio Datensätze jeder mit jedem verglichen
werden
(Party-Problem - jeder soll mit jedem anstossen - wie oft wird
angestossen?)

Wenn ich mich recht erinnere war die Formel hierfür n*(n-1)/2
also ca. 500 Milliarden Vergleichsvorgänge

Vergleichen bedeutet, dass jeweils die Integerzahlen subtrahiert
werden sollen und die Beträge der Differenz multipliziert werden.

tja, sowohl was Storage als auch CPU Zeit angeht sieht das Problem
unlösbar aus.

Selbst bei nur 100 000 Datensätzen.

Gewisse Heuristiken könnten die Zahl weiter reduzieren.

Wie aber implementiert man so ein Ding auf mysql ?

Ein Server pakt das nicht ansatzweise - eher 50 - 500

Wer hat schon einmal sowas gemacht?

Wer hat Lust auf so ein Monster?

pierre
pierre-at-kerchner.de

Re: ein superfetter Job fuer mysql

Pierre Kerchner wrote:
>
> ich denke gerade über ein Projekt nach und habe keine Ahnung, ob das
> überhaupt ansatzweise mit mysql lösbar ist.
>
> Ich habe 1 Mio Datensätze (oder Objekte oder Entitäten)
>
> Jeder Datensatz hat 10 Attribute, die jeweils eine Integerzahl
> beinhalten.
>
> Jetzt sollen mit den 1 Mio Datensätze jeder mit jedem verglichen
> werden
> (Party-Problem - jeder soll mit jedem anstossen - wie oft wird
> angestossen?)
>
> Wenn ich mich recht erinnere war die Formel hierfür n*(n-1)/2
> also ca. 500 Milliarden Vergleichsvorgänge
>
> Vergleichen bedeutet, dass jeweils die Integerzahlen subtrahiert
> werden sollen und die Beträge der Differenz multipliziert werden.
>
> tja, sowohl was Storage als auch CPU Zeit angeht sieht das Problem
> unlösbar aus.

Wieso? Das sind 5 Billionen Integer-Subtraktionen und Multiplikationen
(letztere aber wohl eher Fließkomma, wegen der möglichen Überläufe).
Eine aktuelle CPU sollte die Daten schon in wenigen Stunden verdaut
haben. Wenn du das Ergebnis in FLOATs ablegst, sind das auch nur 2TB.

> Wie aber implementiert man so ein Ding auf mysql ?

Wenn die Tabelle mit den 1.000.000 Dings schon da ist, schreibt man ein
Mini-Progrämmchen, das zwei SELECTs ineinander schachtelt und die 500
Milliarden INSERTs in die andere Tabelle macht.

Wenn die Daten erst nach und nach auflaufen, macht man passende Trigger
auf die Dings-Tabelle und berechnet für jedes neue Dings jeweils die
Abstände zu den schon vorhandenen.

> Ein Server pakt das nicht ansatzweise - eher 50 - 500

Das dürfte noch sehr vom Server abhängen. Ein paar TB Festplatten-
kapazität sind per RAID schnell zusammengestöpselt.

> Wer hat schon einmal sowas gemacht?

*Genau* so was? Wohl keiner. Warum auch?

> Wer hat Lust auf so ein Monster?

Eine intellektuelle Herausforderung ist das ja nun weiß Gott nicht.
Wenn man Geld für Rechenleistung und Plattenplatz verbraten will,
fallen mir eine Menge sinnvollerer Dinge ein.


XL

Re: ein superfetter Job fuer mysql

> Wieso? Das sind 5 Billionen Integer-Subtraktionen und Multiplikationen
> (letztere aber wohl eher Fließkomma, wegen der möglichen Überläuf=
e).
> Eine aktuelle CPU sollte die Daten schon in wenigen Stunden verdaut
> haben. Wenn du das Ergebnis in FLOATs ablegst, sind das auch nur 2TB.
>

Are you sure?

Wenn eine Vergleichsoperation nur 0,001 Sekunden dauert
(was mit Plattenzugriff usw etc fast nicht möglich ist) komme ich auf
5787 Tage Rechenzeit

Wirf mal Dein Excel an oder Taschenrechner an

ok, der Rechner liesst pro Lesezugriff nicht nur ein Objekt ein

selbst wenn er 2 Mio Vergleichsoperationen/s schafft, was enorm wäre -
würde er noch 2,9 Tage brauchen (das wäre zu lang)

vom Storagebedarf will ich gar nicht sprechen (wer will hier
freiwillig rechnen?)

das Problem muss man also mit nem Cluster angehen.

Ich glaube nicht, dass man das einfach so nebenbei in 5 Tage
Entwicklungszeit eintütet

pierre

Re: ein superfetter Job fuer mysql

Pierre Kerchner wrote:
>
>> Wieso? Das sind 5 Billionen Integer-Subtraktionen und Multiplikationen
>> (letztere aber wohl eher Fließkomma, wegen der möglichen Überläufe).
>> Eine aktuelle CPU sollte die Daten schon in wenigen Stunden verdaut
>> haben. Wenn du das Ergebnis in FLOATs ablegst, sind das auch nur 2TB.
>
> Are you sure?
>
> Wenn eine Vergleichsoperation nur 0,001 Sekunden dauert
> (was mit Plattenzugriff usw etc fast nicht möglich ist) komme ich auf
> 5787 Tage Rechenzeit
>
> Wirf mal Dein Excel an oder Taschenrechner an

Wirf du mal dein Hirn an. Die 1.000.000 Dingse bestehen aus 11 INTs
(Nummer und 10 Eigenschaften). Das macht summa summarum 44 MB und paßt
somit *locker* ins RAM. Dafür muß man die Platte genau einmal anfassen,
danach stehen die Daten im RAM.

Ansonsten laufen aktuelle CPUs mit 2GHz (und mehr). Das sind
2.000.000.000 Zyklen pro Sekunde. Eine Integer-Subtraktion sollte mit
allem Drum und Dran nicht länger als 10 Takte brauchen, die Float-
Multiplikation vielleicht 20. Das macht also 300 Zyklen pro Vergleich.
Rechnen wir großzügig mit 1000. Dann sind das immer noch 2.000.000
Vergleiche pro Sekunde, nicht 1000 wie von dir angenommen. Aus deinen
6000 Tagen werden also nicht mal 3 Tage.

> ok, der Rechner liesst pro Lesezugriff nicht nur ein Objekt ein
> selbst wenn er 2 Mio Vergleichsoperationen/s schafft, was enorm wäre -
> würde er noch 2,9 Tage brauchen (das wäre zu lang)

Warum soll das zu lang sein? Wie oft willst du das machen? Und warum?

> vom Storagebedarf will ich gar nicht sprechen (wer will hier
> freiwillig rechnen?)

Was gibts da groß zu rechnen? Das Ergebnis besteht aus 2 INTs (die
Nummern der beiden Dingse) und einem FLOAT (dem Abstand). Macht
12 Byte. Mal 500 Mrd. macht 6TB Rohdaten. Mit dem Overhead für die
Speicherung in einer Datenbank-Tabelle (nur warum?) wahrscheinlich
etwa das doppelte.

Also gehst du los und kaufst 20 schnuckelige 750GB Festplatten.
Oder eher 40 (wegen der Datensicherheit). Da machst du ein schickes
RAID draus und packst deine Daten drauf.

> Ich glaube nicht, dass man das einfach so nebenbei in 5 Tage
> Entwicklungszeit eintütet

Die Entwicklungszeit dürfte eher bei 5 Stunden liegen. Der Aufbau
der Hardware dauert natürlich länger.

Die Frage die sich stellt ist vielmehr: Warum sollte man so etwas
(Entschuldigung) Bescheuertes machen, alle Distanzen zwischen den
Dingens zu tabellieren, wenn doch das Berechnen einer Distanz nur
0.5 Mikrosekunden dauert?

Rechenleistung ist spottbillig geworden. RAM desgleichen.

Und warum sollte man dazu eine SQL-Datenbank verwenden? Die 1 Mio
Dingse passen locker ins RAM, die 44MB nimmt sich schon dein Web-
browser wenn du ihn startest. Die Datenbasis lädt dein Programm
in den ersten paar Sekunden nach dem Start und danach *rechnet* es
dir jede Frage nach Distanzen live aus. Das ist deutlich schneller,
als in 12TB Festplatten danach zu suchen.


XL

Re: ein superfetter Job für mysql?

Pierre Kerchner schrieb:
> Ich habe 1 Mio Datensätze (oder Objekte oder Entitäten)
>
> Jeder Datensatz hat 10 Attribute, die jeweils eine Integerzahl
> beinhalten.
>
> Jetzt sollen mit den 1 Mio Datensätze jeder mit jedem verglichen
> werden
> (Party-Problem - jeder soll mit jedem anstossen - wie oft wird
> angestossen?)
>
> Wenn ich mich recht erinnere war die Formel hierfür n*(n-1)/2
> also ca. 500 Milliarden Vergleichsvorgänge

Das ist schon ein bisschen arg viel.

Eine Optimierung können wir nur empfehlen, wenn wir wissen, welche
Vergleichspaare im Endergebnis erhalten bleiben sollen.


Grüße
Jo