[SQL] Join-Optimierung

[Azdak]

Hallo,

ich habe ein kleines Laufzeitproblem und hoffe Ihr könnt mir vieleicht helfen.

Ich habe 2 Tabellen. Eine Tabelle mit einer Zeitreihe und eine Tabelle mit Ereignissen (von / bis).
Nun brauche ich als Ergebniss die Anzahl an Ereignissen zu den Zeiten aus der Zeitreihe.

select zeit, count(*) 
from Zeitreihe z left join Ereignisse e on z.zeit between e.von and e.bis
group by zeit

Mein Problem ist nun, dass durch das "between" der join immer als nested loop ausgeführt werden muss und das führt zu zu langen Laufzeiten.
Gibt es eine Möglichkeit das Statement umzuformen um die Komplexität zu reduzieren (oder gar einen ganz anderen Ansatz)?
Mir fällt irgendwie keine bessere Lösung ein.

Gruß
Azdak

P.S.: DB ist ein MS SQL-Server 2005, Zeitreihe hat pro Auswertung ~50k Zeilen und Ereignisse ~2mio Zeilen

 

[streilu]

Wie sieht denn die Tabellenstruktur aus?
Ich gehe mal davon aus, dass Zeitreihe zum Beispiel Elemente enthält wie ein Stundenplan, also von 8 bis 9 und Ereignisse zum Beispiel das Fach, das zu dieser Zeit unterrichtet wird.

Wenn ich das Problem richtig verstehe, würde ich dies mit Primary und Foreign Keys lösen.
Sollte doch einen enormen Geschwindigkeitsschub bringen.

 

[ice-breaker]

Mein Problem ist nun, dass durch das "between" der join immer als nested loop ausgeführt werden muss und das führt zu zu langen Laufzeiten.

bist du dir da sicher?
Ich würde viel eher vermuten, dass die Ergebnissmenge generell ohne das group by schon so groß ist, dass der Query einfach einige Zeit benötigt.

 

[BerniG]

Das "z.zeit between e.von and e.bis" kann man natürlich auch durch "z.zeit >= e.von and z.zeit <= e.bis" ausdrücken aber das sollte normal gleichwertig sein.

Evtl. kann man Indexe setzen so dass alles per Indexaccess gelöst werden kann.

Überlegenswert wäre auch eine Materialized View oder die Aufnahme eines Attributes in die Ereignisse-Tabelle um den Join zu vereinfachen (entweder direkt zeit oder eine entsprechende ID)

 

[Azdak]

Ich gehe mal davon aus, dass Zeitreihe zum Beispiel Elemente enthält wie ein Stundenplan, also von 8 bis 9 und Ereignisse zum Beispiel das Fach, das zu dieser Zeit unterrichtet wird.

Die Zeitreihe ist etwas feiner, sie geht bis auf Minuten herrunter. Und die "Fächer" sind nicht immer "eine Stunde" sondern mal 2, mal 1,5 ...
Die Fragestellung währe dann in etwa: "wieviele Chemiekurse können es knallen lassen am 11.11 11:11?" Da wüste ich jetzt nicht wie ich von den Ereignissen zu den Zeitreihen sinvoll Fremdschlüsselbeziehungen anlegen könnte. (und ja, in meinem Fall geht es um etwas anderes )

bist du dir da sicher?

Relativ sicher. Durch das größer/kleiner ist es ein contitional join und damit kann ich andere Join-Algrorithmen wie Hash- oder Merge-Join nicht nutzen, die einen equal join verlangen.

Ich würde viel eher vermuten, dass die Ergebnissmenge generell ohne das group by schon so groß ist, dass der Query einfach einige Zeit benötigt.

Überlegenswert wäre auch eine Materialized View oder die Aufnahme eines Attributes in die Ereignisse-Tabelle um den Join zu vereinfachen (entweder direkt zeit oder eine entsprechende ID)

Das hat mich aber auf eine "Lösung" gebracht.
Zu erst einmal habe ich das Problem einen Tick zuweit herrunter gebrochen.
Die Gruppierung läuft nicht nur auf der Zeit (und einem Filter) sondern auch über die Ereignissklasse. Also so:

select zeit, ereignissklasse, count(*) 
from Zeitreihe z left join Ereignisse e on z.zeit between e.von and e.bis
where <filter>
group by zeit, ereignissklasse

Ohne die Ereignissklasse mußte die Datenbank zwar immer noch einen nested loop machen, konnte das ganze aber Paralellisieren. Mit der 2ten Gruppierung konnte die DB das dann nicht mehr.

Meine Überlegung war, wie ich die Paralellisierung wieder herstellen könnte und bin zu folgender Lösung gekommen.
Ich erstelle eine Zwischenergebnisstabelle mit Zeitreihe und Ereigniss_id (eindeutig) und Indiziere sie anschließend günstig. Das dauert zwar einen Moment und braucht Platz, aber Platz ist günstig und die Zeit ist im Vorfeld da. Die Vorarbeiten dauern ~10min und ~0,5GB Platz. Die Filterattribute für die Ereignisse kann ich mir nun effizient heranjoinen und auf der Zwischentabelle läuft nur noch ein Clustered Index Seek.

insert into Zwischentabelle
select zeit, ereigniss_id
from Zeitreihe z inner join Ereignisse e on z.zeit between e.von and e.bis

create clustered unique index ix on Zwischentabelle (zeit asc, ereigniss_id asc)

Und die Auswertungen dann

select zeit, ereignissklasse, count(*) 
from Zwischentabelle z left join Ereignisse e on z.ereigniss_id=e.ereigniss_id
where <filter>
group by zeit, ereignissklasse

Zeit für eine Gesammtauswertung vorher ~1,6h, jetzt ~40sec
Zeit für eine typische Auswertung vorher ~30sek, jetzt < 2sec

Vielen dank für den Gedankenanschub.

Gruß
Azdak

 

[ice-breaker]

Die Zeitreihe ist etwas feiner, sie geht bis auf Minuten herrunter. Und die "Fächer" sind nicht immer "eine Stunde" sondern mal 2, mal 1,5 ...
Die Fragestellung währe dann in etwa: "wieviele Chemiekurse können es knallen lassen am 11.11 11:11?" Da wüste ich jetzt nicht wie ich von den Ereignissen zu den Zeitreihen sinvoll Fremdschlüsselbeziehungen anlegen könnte. (und ja, in meinem Fall geht es um etwas anderes )

sicher, dass du wirklich auf Minuten die Einträge brauchst? Eine Start- und Endzeit ist fast immer komplett ausreichend.
Wenn (dein Beispiel) ein Chemiekurs heute um 8.00 startet und um 9.40 zu Ende ist und ich möchte wissen, ob um 9.20 da was passieren kann, weiß ich, dass mein Zeitpunkt innerhalb einer Time-Range liegt in der in dem Raum eine Veranstaltung ist.
Oder habe ich dich nur falsch verstanden?

Relativ sicher. Durch das größer/kleiner ist es ein contitional join und damit kann ich andere Join-Algrorithmen wie Hash- oder Merge-Join nicht nutzen, die einen equal join verlangen.

Ich meine damit, dass du dich in deiner Problemursache viel zu sehr auf den Join-Algorithmus fixierst, natürlich hätte ein Hash-Join wunderbare Vorteile aber wenn du dir anschaust, dass MySQL z.B. bisher nur Nested-Loop-Joins kann und man auch dort das alles wunderbar hinbekommt, finde ich eben du fixierst dich viel zu sehr und suchst nicht nach dem wahren Grund.

 

[Azdak]

sicher, dass du wirklich auf Minuten die Einträge brauchst? Eine Start- und Endzeit ist fast immer komplett ausreichend.
...
Oder habe ich dich nur falsch verstanden?

Das Beispiel ist vieleicht etwas ungünstig gewählt. Ich wollte damit nur Streilus Gedanken aufgreifen. Die Ereignisse sind im Prinzip Messergebnisse. Am Ende werden dann besonders Peaks und Ruhephasen gesucht um diese dann genauer zu Untersuchen. Es gibt auch noch genug Auswertungen über die Start- und Endzeiten gemacht. Es war einfach der einzige harte Brocken, den ich nicht gut genug umsetzen konnte. Ich kann hier leider nicht genauer auf unsere echte Fragestellung eingehen.

Ich meine damit, dass du dich in deiner Problemursache viel zu sehr auf den Join-Algorithmus fixierst, ... dass MySQL [...] alles wunderbar hinbekommt, ...

Ich kann leider keinen Einfluss auf die Fragestellung nehmen, ich muß sie nur umsetzen. Unsere Datenmengen werden wohl noch einiges größer und die Komplexität verschiedener Algorithmen sind dann einfach ungünstig. Der Join ist bei mir als letzter großer Zeitfresser übrig geblieben. Oder aber, ich hab einen völlig falschen Ansatz um die Verteilungen auf zu bauen.
MySQL ist ein tolles DBMS, aber alles UND wunderbar würde ich soooo nicht unterschreiben.

 

[ice-breaker]

MySQL ist ein tolles DBMS, aber alles UND wunderbar würde ich soooo nicht unterschreiben.

ja gut es ist eben wirklich nur für das Web wunderbar geeignet, statistische Auswertungen, was ich nun aus deiner Antwort herauslese, natürlich nicht.
Dadurch dass du auf das Problem aber eben auch nicht richtig eingehen kannst, kann man dir gar nicht helfen Denn wenn es um DB-Optimierung geht, braucht man eben Details.