TopicDBISAI-written · not yet proofread

SQL and Query Planning

How relational data is stored and queried with SQL, how a query is translated into table operations, and how the cheapest query plan is chosen (joins, indexes, join ordering), plus transactions.

Concepts#

Relational Modeltables $(C, D, R)$ as multisets of rows, primary and foreign keys start here
SQL Query Structureclauses SELECT … FROM … WHERE … GROUP BY … HAVING … ORDER BY … LIMIT and their evaluation order
Cartesian Productall row combinations; semantics of FROM, columns add up and rows multiply
Relational Algebraprojection, selection, product and their cost/size estimates; query as sequence/tree of operations
Join $T_1 \bowtie T_2$equi-join as a product + selection computed without the product; outer and natural joins, hash join
Merge Joinjoin of sorted join columns by the Zipper algorithm
group-by(T, cols, agg)group-by with aggregation functions and HAVING
OrderingORDER BY, LIMIT, OFFSET
Subquerya SELECT query used in place of a table
Query Plana sequence/expression/tree of operations with its estimated total cost
B+ Treeindex with $O(\log n)$ lookup, sorted leaves; basis of index-based joins
Query Optimizationjoin graph and $\text{cost}^*(S)$ by dynamic programming over subsets
ACIDtransaction guarantees (mentioned only, not exam-relevant)

How it fits together#

From a query to a result. A query SELECT … FROM … WHERE … is defined by a chain of operations on tables: the FROM tables are combined by the Cartesian Product, the WHERE expression selects rows ( $\sigma$ ), the SELECT list projects columns ( $\Pi$ ). GROUP BY/HAVING, ORDER BY/LIMIT and subqueries extend this chain; a subquery works because every operation takes tables and returns a table (Relational Model > Closure). This definition says what is computed, not how: the RDBMS is free to compute any equivalent plan.

From definition to efficient plan.

Step	Problem	Remedy	Concept
1	Product materialises $n_1 n_2 (k_1 + k_2)$ values	push $\sigma$ and $\Pi$ below the product; combine small tables first	Relational Algebra
2	Product + equality selection is still too large	single-column equi-join, never materialising the product	Join
3	Join needs a fast way to find matches	hash join (hash map), or merge join on sorted columns	Join, Merge Join
4	Sorted columns / fast lookups are needed	index B+ tree: lookup $O(\log n)$ , leaves in sorted order	B+ Tree
5	Many tables: which join order?	join graph, $\text{cost}^*(S)$ by dynamic programming	Query Optimization

Cost models by lecture. All of them are sums over the operations of a Query Plan, with sizes propagated from the leaves:

Lecture	Operation	cost	rows	cols
VL04	$\Pi$	$n k'$	$n$	$k'$
VL04	$\sigma$	$n k$	$n/2$	$k$
VL04	$\times$	$n_1 n_2 (k_1 + k_2)$	$n_1 n_2$	$k_1 + k_2$
VL05	hash/merge join	$n_1 + n_2 + \min(n_1, n_2) k$	$\min(n_1, n_2)$	$k$
VL05	group-by	$n k$	$n/2$	$k$
VL06	join (total cost, size only)	$\text{cost}(A) + \text{cost}(B) + \text{size}$	$\min(\text{size}(A), \text{size}(B))$	–

Which one to use depends on the task: the exam gives the VL04 estimates (select/project/product) for plan comparison; the VL06 model with $\text{cost}^*$ is for join ordering of many tables.

Joins and indexes.

	Hash join	Merge Join	Index lookup (SQLite3)
Needs	nothing	both join columns sorted	B+ Tree on one join column (temporary one if none)
Time	$C_I n_1 + C_L n_2 + C_C n k$	$C_M (n_1 + n_2 + n) + C_C n k$	$n_1$ lookups of $O(\log n_2)$
Note	simple default	faster ( $C_M \ll C_I$ ); fed by B+ tree leaves	an index on both columns does not help further

When SQL needs more than one clause. “Per group, a value” → Grouping; “per group, the row with the extreme value” (argmax) cannot be done by GROUP BY alone and needs a Subquery joined back to the table. WHERE filters rows before grouping, HAVING filters groups after aggregation. NATURAL JOIN joins on all equally named columns, so tracing a natural join with a subquery means checking which names the two tables share.

Related. Basic SPARQL queries translate mechanically into the joins above (SPARQL and Knowledge Graphs).

Key Formulas#

$\text{cost}(T_1 \times T_2) \sim n_1 n_2 (k_1 + k_2)$ , $\text{cost}(\sigma) \sim nk$ , $\text{cost}(\Pi) \sim nk'$ (Relational Algebra)
$\#\text{cols}(T_1 \times \dots \times T_k) = \sum_i \#\text{cols}(T_i)$ , $\#\text{rows} = \prod_i \#\text{rows}(T_i)$ (Cartesian Product)
$\text{cost}(A \bowtie B) = \text{cost}(A) + \text{cost}(B) + \min\{\text{size}(A), \text{size}(B)\}$ (Query Plan)
$\text{cost}^*(S) = \min_{S_1 \cup S_2 = S}\{\text{cost}^*(S_1) + \text{cost}^*(S_2) + \text{size}(S_1 \bowtie S_2)\}$ , $\text{cost}^*(\{T\}) = 0$ (Query Optimization)
B+ tree lookup: depth $\le \lceil \log_d n \rceil$ , time $O(\log n)$ (B+ Tree)

Exercises & Exam Questions#

QuestionQ1: Write SQL queries for a movie database (WS 23/24, T2.1)

Given schema:

movies(id, title, release_year)
persons(id, name)
actors(movie_id, person_id)
streaming(movie_id, platform, views)

(a) Titles of all movies released in the 20th century. (b) Top 10 movies by total views on “Netflix” and “Amazon Prime” combined. (c) For each movie with at least 10 actors: title and comma-separated list of actor names.

SuccessSolution Q1

(a)

SELECT title FROM movies
WHERE release_year > 1900 AND release_year <= 2000;

(b)

SELECT movies.title, SUM(streaming.views) AS total_views
FROM movies, streaming
WHERE movies.id = streaming.movie_id
  AND streaming.platform IN ("Netflix", "Amazon Prime")
GROUP BY movies.id
ORDER BY total_views DESC
LIMIT 10;

(c)

SELECT movies.title, GROUP_CONCAT(persons.name, ', ')
FROM movies, actors, persons
WHERE movies.id = actors.movie_id
  AND actors.person_id = persons.id
GROUP BY movies.id
HAVING COUNT(actors.person_id) >= 10;

SuccessSolution Q2

Plan 1: $40 + 40 + 300 + 300 = 680$

select(A): $10 \cdot 4 = 40$ (5 rows out)
select(B): $20 \cdot 2 = 40$ (10 rows out)
cross product: $5 \cdot 10 \cdot 6 = 300$ (50 rows out)
project: $50 \cdot 6 = 300$

Plan 2: $1200 + 1200 + 600 + 300 = 3300$

cross product: $10 \cdot 20 \cdot 6 = 1200$ (200 rows out)
select: $200 \cdot 6 = 1200$ (100 rows out)
select: $100 \cdot 6 = 600$ (50 rows out)
project: $50 \cdot 6 = 300$

Plan 2 can be cheaper if one table is empty (0 rows): then cross product costs 0 in Plan 2, but Plan 1 still pays for the selection on the non-empty table.

SuccessSolution Q3

Subquery computes max score per year: (2021, 8.3), (2022, 8.2), (2023, 8.4)
NATURAL JOIN matches on both year AND score – only movies whose score equals the max for their year survive
Result after ORDER BY score DESC:
- (2023, Oppenheimer, 8.4), (2021, Spider-Man, 8.3), (2022, Top Gun, 8.2)

Natural language: For each year, the movie with the highest score, ordered by score descending.

SuccessSolution Q4

Computes each employee’s name together with the name of their supervisor (self-join on supervisor = id); $R$ is $100 \times 2$ .

Original: $100 \cdot 100 \cdot 6 + 10\,000 \cdot 6 + 100 \cdot 2 = 60\,000 + 60\,000 + 200 = 120\,200$ .

Better: project both copies before the product: $E' = \Pi_{(2,3)}(E)$ , $E'' = \Pi_{(1,2)}(E)$ , $C = E' \times E''$ , $S = \sigma_{\text{row}[2] = \text{row}[3]}(C)$ , $R = \Pi_{(1,4)}(S)$ . Cost: $200 + 200 + 100 \cdot 100 \cdot 4 + 10\,000 \cdot 4 + 200 = 80\,600$ .

SuccessSolution Q5

SELECT person
FROM founded_by NATURAL JOIN based_in NATURAL JOIN born_in;

The first natural join is on company, giving (company, person, city); joining born_in is on person and city. Equivalent: explicit JOIN … ON f.company = b.company and JOIN born_in n ON f.person = n.person AND b.city = n.city, or three tables in FROM with the three equalities in WHERE.

SuccessSolution Q6

(2) A subquery with GROUP BY e_id, title HAVING COUNT(*) > 1 yields the qualifying pairs, joined with employees:

SELECT DISTINCT e.name
FROM employees AS e, (
  SELECT e_id, title FROM positions
  GROUP BY e_id, title HAVING COUNT(*) > 1
) AS p
WHERE e.id = p.e_id;

(3) A subquery computes MAX(start_date) per employee and is joined back on employee and date:

SELECT e.name, p.title
FROM employees AS e, positions AS p, (
  SELECT e_id, MAX(start_date) AS latest_date
  FROM positions GROUP BY e_id
) AS pmax
WHERE e.id = p.e_id AND p.e_id = pmax.e_id
  AND p.start_date = pmax.latest_date;

Exam occurrences#

Semester	Task	Points	Subtopics
DBIS Exam WS1314 (not published)	T6	20	SPARQL-to-SQL translation, efficient query processing with indexes
DBIS Exam WS1516 (not published)	T6	20	SQL for knowledge base queries, inverted index size formula
DBIS Exam WS1617 (not published)	T6	20	SQL for knowledge base, maximum entropy proof
DBIS Exam WS2324 (not published)	T2	20	SQL queries on movie schema, query plan cost comparison
DBIS Exam WS2324 (not published)	T3	20	SQL/SPARQL translation, NATURAL JOIN step-by-step
DBIS Exam WS2324-2 (not published)	T2	20	SQL queries with subqueries on employees schema, self-join query plan cost
DBIS Exam WS2324-2 (not published)	T3	20	SPARQL-to-SQL, subquery with `GROUP BY` and `AVG`

Lectures#

DBIS_VL03 — relational model, SQLite3, database design with keys, SELECT … FROM … WHERE … via the cross-product
DBIS_VL04 — projection, selection, Cartesian product, query planning and cost estimates
DBIS_VL05 — join (hash, merge, outer, natural), group-by and HAVING, ORDER BY, LIMIT/OFFSET, subqueries
DBIS_VL06 — index B+ tree, optimal query plan by dynamic programming, ACID
DBIS_VL13 — exam example task on query plan costs

SPARQL and Knowledge Graphs — SPARQL queries translate into the joins of this topic