Join Tree Typen in Ausführungsplänen

Kyle Hailey liefert in seinem Blog eine kompakte Erläuterung zu den drei Join Tree Typen:

• Left Deep
• Right Deep
• Bushy

Dabei beschreiben die Bezeichner die Anordnung der Elemente in einem klassisch arrangierten Ausführungsplan: beim right deep Plan stehen die am weitesten unten im Plan erscheinenden Operationen auch am weitesten rechts. Beim left deep plan hingegen steht das unterste Element relativ weit links - eine Postion versetzt zum aufrufenden (Join-)Element. Verständlicher wird der Zusammenhang mit den Abbildungen, die man bei Kyle Hailey findet, und die nachzuzeichnen ich mir hier spare. Entscheidend ist dabei, dass der right deep Plan dazu führt, dass erste Ergebnisse schneller geliefert werden können:

All of this boils down to the point that a right deep HJ can return rows earlier than a left deep HJ. A left deep HJ has to wait for each join to finished completely so that the result set can be hashed before the next step can probe it. On the other hand, in a right deep HJ, it’s not the result sets that are being hashed, but a table at each level, thus each table can be hashed without waiting for intermediary results and once these hashes are complete a probed row can flow all the way through the join tree, from bottom to top, similar to how a nested loop can start giving results early. The Left Deep HJs only have two open work areas at a time where as the Right Deep can have multiple work areas open. One of the key thing to keep in mind is how much data we have to hash. If the intermediate result sets are large (and/or growing each level) then that represents more work each step of the way.

Right deep Pläne gibt es dabei nur für Hash Joins während Nested Loops Joins immer eine left deep Anordnung besitzen. Der bushy tree schließlich ergibt sich beim Einsatz von Views oder Subqueries, die als non mergeable gekennzeichnet sind, und in solchen Plänen existieren mehr als zwei Datenquellen auf der am weitesten eingerückten Ebene (was wiederum in der Abbildung klarer wird als in meinem Verbalisierungsversuch).

Der Artikel umfasst zusätzlich noch eine Darstellung der untersuchten Pläne in VST Diagrammen (VST = Visual SQL Tuning, die Darstellungsform des Embarcadero DB Optimizers) und schließt mit dem wichtigen Hinweis, dass die Semantik der Hints USE_HASH und USE_NL sich insofern unterscheidet, dass immer die innere Tabelle des Joins angegeben wird, was allerdings im Fall des NL in Hinblick auf die Ausführungsreihenfolge die zweite Tabelle ist, während es für den HJ die erste Tabelle ist (die als Hash Map in den Speicher geladen wird).