LectureDBISAI-written · not yet proofread

VL05 Joins and more SQL

The join operation and its computation via hash join and merge join, outer/natural/non-equi joins, the formal group-by operation with HAVING, and ORDER BY, LIMIT/OFFSET and subqueries in SQL.

Held Tue 18 Nov 2025 Source lecture-05

Organisation#

Join operation#

Motivation (Slide 5). A very frequent pattern in SQL queries: two tables $T_1, T_2$ in the FROM clause and a condition T1.col1 = T2.col2 in the WHERE clause. The query from Lecture 4 contains it twice:

SELECT movies.title, persons.name
FROM movies, persons, roles
WHERE roles.person_id = persons.id
AND roles.movie_id = movies.id;

A table is a triple $T = (D, C, R)$ in the sense of the Relational Model: $C$ the tuple of column names, $D$ the tuple of domains, $R$ the multiset of rows.

DefinitionSingle-column equi-join (Slide 6)

Signature: $\mathrm{join}(T_1, T_2, j_1, j_2)$ or $T_1 \bowtie_{j_1, j_2} T_2$ , where

$T_1 = (D_1, C_1, R_1)$ and $T_2 = (D_2, C_2, R_2)$ are two tables,
$j_1 \in \{1, \dots, |C_1|\}$ and $j_2 \in \{1, \dots, |C_2|\}$ are column indices (the join columns).

Result: a table $T = (D, C, R)$ with $C = (C_1, C_2)$ , $D = (D_1, D_2)$ and

R = \{ (r_1, r_2) : r_1 \in R_1,\ r_2 \in R_2,\ r_1[j_1] = r_2[j_2] \},

where $r[j]$ is the value in column $j$ of row $r$ and $(r_1, r_2)$ is the concatenation of the two rows.

See Join.

Exampleprofs ⋈ studis (Slide 7)

CREATE TABLE profs(prof TEXT, course TEXT);
CREATE TABLE studis(student TEXT, course TEXT);
SELECT * FROM profs, studis
WHERE profs.course = studis.course;

Operation: $T_1 =$ profs, $T_2 =$ studis, $\mathrm{join}(T_1, T_2, 2, 2)$ . With profs = {(Brox, V720), (Hutter, V2040), (Bast, V1304), (Burgard, V2040)} and studis = {(7383436, V1304), (3487464, V2040), (3344637, V2040), (3347343, V2060), (5634555, V2040), (7537345, S1303)}, the result has 7 rows: each of Hutter and Burgard paired with each of the three V2040 students, plus (Bast, V1304, 7383436, V1304).

Why the name? (Slide 8)

Single-column: the equality constraint concerns only one column of each table. A multi-column join (same number of columns from each table) can be defined analogously.
Equi-join: the condition is equality of the values in column $j_1$ of $T_1$ and $j_2$ of $T_2$ . Other conditions are possible.

Cartesian product vs. join (Slide 9). The query above can be evaluated by two query plans in the operations of Relational Algebra:

$T_1 = \text{cartesian-product}(\texttt{profs}, \texttt{studis})$ , then $T_2 = \mathrm{select}(T_1, r \mapsto r[2] = r[4])$ .
$T_1 = \mathrm{join}(\texttt{profs}, \texttt{studis}, 2, 2)$ .

Both give the same table, but the second never materialises the Cartesian product.

Join processing#

Hash join#

DefinitionHash join (Slide 10)

A simple and reasonably efficient implementation when nothing is known about the tables. Compute $X \bowtie_{j_1, j_2} Y$ :

Let $x_1, \dots, x_{n_1}$ be the rows of the first table $X$ in any order.
Let $K = \{x_1[j_1], \dots, x_{n_1}[j_1]\}$ be the set of distinct values in the join column $j_1$ of $X$ .
Compute a hash map $H$ that maps each $k \in K$ to the set of indices of the rows of $X$ containing $k$ in the join column.
Let $y_1, \dots, y_{n_2}$ be the rows of the second table $Y$ in any order.
For each row $y_j$ : if $y = y_j[j_2] \in K$ , then for each $i \in H[y]$ add the row $(x_i, y_j)$ to the result.

ExampleHash join on profs ⋈ studis (Slide 11)

$X =$ profs with rows $x_1, \dots, x_4$ = Brox, Hutter, Bast, Burgard; $Y =$ studis with rows $y_1, \dots, y_6$ in the order listed above.

$K = \{\text{V720}, \text{V2040}, \text{V1304}\}$
$H$ : V720 $\mapsto \{1\}$ , V2040 $\mapsto \{2, 4\}$ , V1304 $\mapsto \{3\}$
Iterate over $Y$ : $y_1$ (V1304) matches $x_3$ ; $y_2$ (V2040) matches $x_2, x_4$ ; $y_3$ (V2040) matches $x_2, x_4$ ; $y_4$ (V2060) and $y_6$ (S1303) match nothing; $y_5$ (V2040) matches $x_2, x_4$ .
Result rows in output order: (Bast, $y_1$ ), (Hutter, $y_2$ ), (Burgard, $y_2$ ), (Hutter, $y_3$ ), (Burgard, $y_3$ ), (Hutter, $y_5$ ), (Burgard, $y_5$ ).

Merge join#

ExampleMerge join on profs ⋈ studis (Slide 14)

Sorted (lexicographically, so V1304 < V2040 < V2060 < V720):

$L_X = (\text{V1304}, 3), (\text{V2040}, 2), (\text{V2040}, 4), (\text{V720}, 1)$
$L_Y = (\text{S1303}, 6), (\text{V1304}, 1), (\text{V2040}, 2), (\text{V2040}, 3), (\text{V2040}, 5), (\text{V2060}, 4)$

Zipper merge yields the triples (value, row in $X$ , row in $Y$ ): (V1304, 3, 1), (V2040, 2, 2), (V2040, 4, 2), (V2040, 2, 3), (V2040, 4, 3), (V2040, 2, 5), (V2040, 4, 5). Each triple $(v, i, j)$ produces the result row $(x_i, y_j)$ , e.g. (Bast, V1304, 7383436, V1304).

Cost estimates for ES5#

These estimates extend the per-operation cost model of query plans from Lecture 4.

Particularities of SQLite3#

(Slide 17)

SQLite3 has no hash join. Its documentation (https://www.sqlite.org/optoverview.html) claims, dubiously, that “an automatic index is about the same thing as a hash join”.
SQLite3 does not perform a merge join either. It always iterates over the values of one join column and searches them in the other, using an index if one exists or building a temporary index otherwise (more in Lecture 6).
A typical RDBMS supports both merge and hash joins; choosing between them is part of query planning.

More join operations#

Inner and outer joins (Slide 18). The join defined above only includes rows whose join value occurs in both tables: an inner join (the default). Variants:

Left outer join: additionally include the rows of $T_1$ (“left”) whose join value does not occur in $T_2$ ; the missing columns are filled with NULL.
Right outer join: analogously for the rows of $T_2$ .
(Full) outer join: both left and right.

These are not defined formally in the lecture, only by example.

ExampleRight outer join (Slide 20)

SELECT * FROM profs RIGHT JOIN studis ON profs.course = studis.course;

Result: the 7 rows of the inner join plus (NULL, NULL, 3347343, V2060) and (NULL, NULL, 7537345, S1303), since no professor teaches V2060 or S1303.

The following three queries are equivalent:

SELECT * FROM profs, studis WHERE profs.course = studis.course;  -- traditional
SELECT * FROM profs JOIN studis ON profs.course = studis.course; -- most modern
SELECT * FROM profs NATURAL JOIN studis;                         -- join columns (too) implicit

Non-equi join (Slide 22). The join condition need not be equality. Example, a spatial join: all restaurants within 500 m of a bus stop.

CREATE TABLE bus_stops(name TEXT, loc POINT);
CREATE TABLE restaurants(name TEXT, loc POINT);
SELECT * FROM bus_stops JOIN restaurants
ON ST_Distance(bus_stops.loc, restaurants.loc) < 500;

The exact syntax depends on the database; SQLite3 needs the SpatiaLite extension.

Grouping#

Motivation (Slide 23). Many queries group the rows of a table by a common value and compute something per group, e.g. all movies by the same director and their average IMDb score (a variant is on ES5).

Definitiongroup-by (Slide 24)

Signature: $\text{group-by}(T, \mathit{cols}, \mathit{agg})$ , where

$T = (C, D, R)$ is an arbitrary table with $k$ columns,
$\mathit{cols}$ is a sequence $(g_1, \dots, g_m)$ with each $g_j \in \{1, \dots, k\}$ (the grouping columns),
$\mathit{agg}$ is a sequence $((a_1, f_1), \dots, (a_n, f_n))$ of pairs with each $a_j \in \{1, \dots, k\}$ and each $f_j : \mathcal{P}(D_{a_j}) \to D'_{a_j}$ a function (the aggregation function for column $a_j$ ),
the sets $\{g_1, \dots, g_m\}$ and $\{a_1, \dots, a_n\}$ are disjoint, and $m \ge 1$ .

Here $\mathcal{P}(X)$ denotes the power set of $X$ , meant as the set of all multi-subsets of $X$ (a group may contain the same value several times).

Result: a table $T' = (C', D', R')$ with

C' = (c_{g_1}, \dots, c_{g_m}, c_{a_1}, \dots, c_{a_n}), \qquad D' = (D_{g_1}, \dots, D_{g_m}, D'_{a_1}, \dots, D'_{a_n}),

R' = \{ (r_{g_1}, \dots, r_{g_m}, r'_{a_1}, \dots, r'_{a_n}) : r \in \mathrm{project}(T, (g_1, \dots, g_m), \top) \},

r'_{a_j} = f_j\big(\{ r''_{a_j} : (r''_1, \dots, r''_k) \in R \wedge r''_{g_i} = r_{g_i} \text{ for all } i \}\big).

$\mathrm{project}(T, \mathit{cols}, \top)$ is the projection of Lecture 4 with $\mathit{distinct} =$ true, so there is one result row per distinct combination of grouping values; $r'_{a_j}$ aggregates column $a_j$ over all rows of that group.

The slide uses $j$ for both the aggregate index and the “for all” quantifier; here $i$ is used for the latter. See Grouping.

ExampleGROUP BY (Slide 25)

CREATE TABLE movies(title TEXT, year INT, score REAL);
SELECT year, MAX(score) AS max_score
FROM movies GROUP BY year;

Operation: $\text{group-by}(\texttt{movies}, (2), ((3, \max)))$ .

title	year	score
Oppenheimer	2023	8.5
Kashmir files	2022	8.6
Western Front	2022	7.8
The Whale	2022	7.7
Dune	2021	8.0
King Richard	2021	7.5

Result: (2023, 8.5), (2021, 8.0), (2022, 8.6).

HAVING (Slide 26). To keep only groups with max_score > 8.0, a WHERE condition does not work: max_score is not a column of the original table but is created by the GROUP BY. Conditions on the results of aggregate functions are written in the HAVING clause.

ExampleGROUP BY with HAVING (Slide 27)

SELECT year, MAX(score) AS max_score
FROM movies GROUP BY year HAVING max_score > 8.0;

Operation: $\text{group-by}(\texttt{movies}, (2), ((3, \max)), r \mapsto r[2] > 8.0)$ . Groups: 2021: max 8.0 (dropped, not $> 8.0$ ); 2022: max 8.6 (kept); 2023: max 8.5 (kept). Result: (2023, 8.5), (2022, 8.6).

Implementation and cost estimates (Slide 28). The straightforward implementation uses a hash map from grouping values to groups (part of ES5, Exercise 1). For an input table with $n$ rows and an output table with $k$ columns:

\text{cost} \sim n \cdot k, \qquad \text{rows} \sim n/2, \qquad \text{cols} = k.

Assumptions: the average group size is 2 (arbitrary and unrealistic); insertion into a hash map takes constant time (realistic); evaluating $f_j$ takes time linear in the number of arguments (often realistic).

Limits of GROUP BY (Slide 29). “For each year, the movie with the highest score and its title” needs a GROUP BY but cannot be expressed with GROUP BY alone. The query above yields the maximum score per year, but GROUP BY aggregates per column, while here the title is needed from the row that has a property (highest score) in another column.

NoteBeyond the lecture

One standard solution combines the grouped result with the original table via a subquery (see below) and a join:

SELECT movies.year, movies.title, movies.score
FROM movies
JOIN (SELECT year, MAX(score) AS max_score FROM movies GROUP BY year) AS best
ON movies.year = best.year AND movies.score = best.max_score;

Ties yield several rows per year. (SQLite3 also has a non-standard shortcut: with a single MAX/MIN aggregate, bare columns in the SELECT take values from the row containing the maximum.)

More SQL#

(Slide 30) The SQL standard (ISO/IEC 9075:2023) has hundreds of pages; the course covers only the most important operations (see https://sqlite.org/lang.html). The following three are explained by example only, without formal operations. All are needed frequently and on ES5. Their position in a query is summarised in SQL Query Structure.

ORDER BY#

(Slide 31) By the definition from Lecture 4, tables are multisets of rows and have no inherent order. An order for the final result is requested with ORDER BY <expression> [ASC|DESC] at the end of the SELECT query. With a GROUP BY, the ORDER BY comes after it.

SELECT * FROM movies ORDER BY score DESC;

SELECT year, MAX(score) AS max_score FROM movies
GROUP BY year ORDER BY year ASC;

LIMIT and OFFSET#

(Slide 32) Given an order, LIMIT restricts the result to a prefix of the sorted rows, and OFFSET skips rows to select a segment in the middle.

-- the 10 movies with the highest scores
SELECT title, score FROM movies
ORDER BY score DESC LIMIT 10;

-- the 5 movies after the top 10
SELECT title, score FROM movies
ORDER BY score DESC LIMIT 5 OFFSET 10;

Clause order: GROUP BY → ORDER BY → LIMIT / OFFSET.

Subqueries#

(Slide 33) All operations take tables as arguments and a SELECT query produces a table. Hence, wherever SQL expects a table, a whole SELECT query in parentheses can be written instead.

SELECT title FROM movies
JOIN directors ON movies.movie_id = directors.movie_id
JOIN (
  SELECT DISTINCT person_id FROM awards
  WHERE award_name LIKE 'Academy Awards%'
) AS awardees ON directors.person_id = awardees.person_id;

Explanation (Slide 34). The subquery yields a one-column table with the person IDs of all Oscar winners. Effectively the query runs on

CREATE TABLE movies(movie_id INT, title TEXT, ...);
CREATE TABLE directors(movie_id INT, person_id INT);
CREATE TABLE awardees(person_id INT);

and is equivalent to

SELECT title FROM movies
NATURAL JOIN directors NATURAL JOIN awardees;

i.e. the titles of all movies directed by Oscar winners.

References#

(Slide 35) Wikipedia: Relational algebra (other joins), Hash join, Sort-merge join, SQL. SQLite3: why there are no merge joins (https://www.sqlite.org/optoverview.html#hash_joins), SELECT syntax (https://sqlite.org/lang_select.html).

Concepts#

Join — single-column equi-join, its hash/merge join computation, and the inner/outer/natural/spatial variants
Grouping — formal group-by operation, HAVING, hash-map implementation and cost estimate
SQL Query Structure — JOIN … ON, GROUP BY/HAVING, ORDER BY, LIMIT/OFFSET and subqueries in a SELECT query
Relational Algebra — Cartesian product + select as the join-free alternative; project with distinct inside the group-by definition
Query Plan — cost/size estimates for join and group-by used to compare query plans on ES5
List Intersection — the Zipper algorithm underlying the merge join
Cartesian Product — all row combinations of two tables, the basis of the join-free formulation
Ordering — ORDER BY, with LIMIT and OFFSET selecting a segment of the sorted rows
Hash Join — join via a hash map over one table’s join column
Merge Join — join of sorted join columns via the Zipper algorithm
Outer Join — left/right/full join keeping unmatched rows with NULLs
Natural Join — equi-join on all equally named columns
Subquery — a SELECT query used in place of a table