ConceptDBISProofread

Query Plan

A query plan is a sequence of table operations (equivalently a nested expression or a tree) that computes the result of a SQL query; its estimated cost is the sum of the estimated costs of its operations.

Join Graph#

Given $n$ tables, compute the adjaciency lists as follows:

If $T_1$ can be joined with $T_2$ , add $T_2$ to the adjecency list of $T_1$

Cost function#

$size(A \bowtie B) = min\{size(A), size(B)\}$
$cost(A \bowtie B) = cost(A) + Cost(B) + size(A\bowtie B)$

Optimal Cost#

Given a set of operatins $S=\{A,B,...,C\}$ Then find the minimum over all partitions $S_1, S_2$ where $S_1 \cup S_2 =S \land S_1 \cap S_2 = \emptyset \land |S_1| > 0 \land |S_2| >0$

cost*(S) = \min\{ cost*(S_1) + cost(S_2) + cost*(S_1 \bowtie S_2)\}

This is a recursive formular, that can be computed efficently using dynamic programming.

TodoSuggested by Claude

The note does not define a query plan itself (VL04): a sequence of operations computing a SQL query, writable as a sequence, a nested expression or a tree; its cost is the sum of the estimated operation costs, with row/column estimates propagated from the leaves (Relational Algebra > Cost and size estimates, Slides 04, p. 19–29). No H1 and no ## Sources.
The optimal-cost formula has two errors: $cost(S_2)$ should be $cost^*(S_2)$ , and the last term should be $size(S_1 \bowtie S_2)$ , not $cost^*(S_1 \bowtie S_2)$ (the slide has the same typo, see DBIS_VL06 > Computing the optimal query plan).
dynamic programming does not resolve to a note; the DP over subsets is described in Query Optimization, which duplicates the join graph and cost function sections here.
The Catalan number $C_{n-1}$ counts binary tree shapes with $n$ leaves (not $C_n$ ); external Wikipedia link instead of a note.
Typos: “thos”, “Catelan”, “adjaciency”, “operatins”, “formular”, “efficently”, “Cost(B)”.

Connections

Required by builds on this1

Query Optimization

Mentioned in inline links8

Query Optimization
Given $n$ input tables $A, B, C, \ldots$ that a SQL query combines by binary joins, query optimization is the problem of finding, among all possible query plans, one with minimal total cost. A plan is a parenthesised expression such as… §
A binary tree with $n$ leaves has $n - 1$ inner nodes; the number of tree shapes is the Catalan number $C_{n-1}$ , with $C_m = \frac{1}{m+1}\binom{2m}{m}$ ( $C_1, \ldots, C_5 = 1, 2, 5, 14, 42$ ). With the tables assigned to the leaves there… §
Relational Algebra
A sequence of operations can be written as a list of assignments, as one nested expression, or as a tree (leaves = input tables, inner nodes = operations, root = result); see Query Plan. §
Relational Model
The operations on tables (Relational Algebra: projection, selection, Cartesian Product, Join, Grouping) take tables and return a table, so they can be composed into query plans. SQL references columns by name $c_j$ ; the formal operations r… §
SQL Query Structure
“Cross-product, then filter, then pick columns” defines what the query returns, not how an RDBMS computes it. Computing the full Cartesian product of several tables is far too expensive; the RDBMS chooses a cheaper equivalent Query Plan (s… §
VL04 – Query Planning Basics
A single SQL query has many sequences of operations that compute its result. Regarding the result they are all equivalent (up to a permutation of the columns), but their processing time can differ greatly (Slide 19). Choosing a good sequen… §
The scratchpad links the Query Plan note under “Query planning”. Its content goes beyond this lecture and is covered in Lecture 6 (see Query Optimization): §
VL05 – Joins and more SQL
Cartesian product vs. join (Slide 9). The query above can be evaluated by two query plans in the operations of Relational Algebra: §
These estimates extend the per-operation cost model of query plans from Lecture 4. §
VL06 – Indexing, Query Optimization, ACID
Recap (Slide 13). A query plan is a sequence of operations that computes the result table from the input tables. Its cost is estimated per operation from the size estimates of its inputs (Lectures 4 and 5, ES4 and ES5). Goal now: find the… §
Query Plan — plans as parenthesised expressions / binary trees with the total-cost function §
SQL and Query Planning
Query Plan — a sequence/expression/tree of operations with its estimated total cost §
Cost models by lecture. All of them are sums over the operations of a Query Plan, with sizes propagated from the leaves: §

Search in these mentions →