Effiziente Generierung und Ausfuehrung von DAG-strukturierten Anfragegraphen

Abstract

Datenbanksysteme verwenden traditionell baumstrukturierte Pläne für die Anfragebearbeitung. Einige Optimierungstechniken wie Faktorisierung lassen sich mit Bäumen aber nicht gut formulieren. Eine attraktive Möglichkeit, die Pläne ausdrucksstärker zu machen, ist die Verallgemeinerung von Bäumen zu gerichteten azyklischen Graphen (DAGs). Existierende Ansätze betrachten DAGs nur in Spezialfällen, sie sind nicht voll in die Anfrageoptimierung integriert. Der hier vorgestellte Plangenerator ist der erste, der generisch optimale DAG-strukturierte Pläne erzeugt. Die experimentellen Ergebnisse zeigen, dass die so erzeugten Pläne teilweise deutlich effizienter sind.