MySQL Mengenlehre

Von Zeit zu Zeit brauche ich Herausforderungen. Gerade steht wieder eine an und zwar ein High-Performance-System, das mit großen Datenmengen arbeiten soll. Einer der Knackpunkte ist die Gruppierung von zur Verarbeitung anstehenden Datensätzen einer MySQL-Datenbank, doch ich wünschte, es wäre eine MongoDB, die nativ Arrays und MapReduce unterstützt.

Gegeben ist eine Liste von Datensätzen, bei denen zwei Felder besonders interessant sind. Beide enthalten jeweils eine Liste von Einträgen aus einer mehr oder weniger begrenzten Gruppe. Da die tatsächlichen Daten Firmen-internas sind, muss ein Beispiels genügen:

Für die Verarbeitung wird jeweils ein beliebiger Wert aus A und B benötigt (also beispielsweise "foo" und "eins" für id 1, 3, 4 und 5). Welcher der zur Auswahl stehenden Werte Anwendung findet, ist dabei nicht relevant.

MySQL unterstützt keine Arrays, also bleibt nur, die Werte der Spalten A und B als Liste mit Trennzeichen in einem VARCHAR zu speichern oder eine entsprechende Mappingtabelle je Spalte zu erstellen.

Das Grundproblem bleibt aber unabhängig von der Speicherart bestehen: Für die Abwicklung werden möglichst gleichmäßige Gruppen benötigt und halbwegs effizient soll die Auswahl nebenbei auch noch erfolgen.

Ginge es nur um einen Wert, könnte ich in einer Mappingtabelle alle id + Wert - Kombinationen abspeichen und dort einfach gruppieren. Dann müsste zwar noch ausgeschlossen werden, dass ein id (der in mehreren Gruppen vorkommen wird), mehrfach verarbeitet wird, aber mit einem entsprechenden Locking ist das sogar Prozess- und Serverübergreifend kein ernsthaftes Problem.

Bei zwei Gruppen gibt es allerdings eine viel größere Anzahl von möglichen Kombinationen. Nur die fünf Zeilen im Beispiel ermöglichen schon eine breite Auswahl:

• foo, eins
• foo, zwei
• foo, drei
• foo, vier
• foo, fünf
• bar, eins
• bar, zwei
• bar, drei
• bar, vier
• bar, fünf
• baz, eins
• baz, drei
• baz, vier
• baz, fünf

In der Realität gibt es allerdings etwa 400 verschiedene Werte für A und mindestens einige tausend für B. Die Tabelle umfasst dann auch einige Hunderttausend oder sogar Millionen Zeilen. Die Anzahl der möglichen Kombinationen will ich gar nicht erst ausrechnen...

Bisher habe ich noch keine auch nur halbwegs schöne Lösung gefunden. Viel mehr, als nach dem häufigsten A zu suchen und dann alle möglichen B's zu gruppieren um dort am Ende wieder den häufigsten Wert zu nutzen, ist mir leider noch nicht eingefallen, aber wer weiß, vielleicht kommt die Erleuchtung über Nacht (oder ein netter Kommentator steuert die zündende Idee bei).