Databases

Lecture 11: Relational algebra and query compilation

• Notes: chapter 6
• Book: chapters 2, 5, 16

Earlier

Relational data modelling (Notes: chapter 4)

Relational databases are based on ideas from discrete math

• Sets, S = {t₁, t₂, …, t_n}
• Cartesian products, S₁ × S₂ = {⟨x,y⟩ | x∈S₁, y∈S₂}
• Relations are sets of tuples, R ⊆ S₁ × … × S_n
• Operations on sets and relations: ∩, ∪, −, ×
• Operations from relational algebra: π, σ, ⨝

Today

• SQL Query processing
• Relational Algebra
• Translation from SQL to Relational Algebra
• Query optimization
• Query execution and optimization in a real-world example

SQL Query processing

A DBMS processes a query in several steps

• Lexing
• Parsing
• Type checking
• Logical query plan generation
  • Translate SQL query to a relational algebra expression
• Optimization
  • Simplifying relational algebra expressions
• Physical query plan generation
• Query execution

Relational Algebra overview

Operators that transform a relation

• R ::=

  relname
  σc R	selecting rows	WHERE c, HAVING c
  πp R	projection	SELECT p
  ρr R	renaming	AS
  γg R	grouping	GROUP BY
  τa+ R	sorting	ORDER BY a+
  δ R	removing duplicates	DISTINCT
  …

Relational Algebra overview

Operations from set theory that combine two relations

• R ::=

  …
  R × R	cartesian product	FROM, CROSS JOIN
  R ∪ R	union	UNION
  R ∩ R	intersection	INTERSECT
  R − R	difference	EXCEPT
  …

Relational Algebra overview

Join operations

• R ::=

  …
  R ⨝ R		NATURAL JOIN
  R ⨝a+ R		INNER JOIN USING (a+)
  R ⨝c R	theta join	JOIN ON
  R ⨝oa+ R		FULL OUTER JOIN
  R ⨝oLa+ R		LEFT OUTER JOIN
  R ⨝oRa+ R		RIGHT OUTER JOIN

Relational Algebra as syntax trees

• π_A.name (σ_{A.name=B.capital} (ρ_A Countries × ρ_B Countries))

  

• (Created with the SQL to Relational Algebra translator that is part of Query Converter online.)

Presentation

To make large relational algebra expressions more readable

• Write them over several lines and use indentation to show the structure.
  • π_A.name
      (σ_{A.name=B.capital}
        (ρ_A Countries × ρ_B Countries))
• Split them in to several named parts.
  • R1 = ρ_A Countries × ρ_B Countries
  • R2 = σ_{A.name=B.capital} R1
  • Result = π_A.name R2

From SQL to Relational Algebra

• …
• Logical query plan generation
  • Translate SQL query to a relational algebra expression
• …

From SQL to Relational Algebra

Basic queries

• SQL		Relational Algebra
  SELECT projections FROM Table1,…,Tablen WHERE condition	⟹	πprojections     σcondition         (Table1 × … × Tablen)

From SQL to Relational Algebra

Tables are relations

• SQL		Relational Algebra
  SELECT * FROM Countries	⟹	Countries
  SELECT * FROM Countries WHERE name='UK'	⟹	σname='UK' Countries

• Table names can be used directly (SELECT * disappears)

From SQL to Relational Algebra

What happens with expressions?

• SQL		Relational Algebra
  SELECT capital,area/1000 FROM Countries WHERE name='UK'	⟹	πcapital,area/1000     σname='UK' Countries

• The expressions and conditions are just copied

From SQL to Relational Algebra

Renaming columns

• SQL		Relational Algebra
  SELECT name AS country,        population/area AS density FROM Countries WHERE continent='EU'	⟹	πname→country, population/area→density     σcontinent='EU'         Countries

• The AS keyword turns into an arrow (→)

From SQL to Relational Algebra

Renaming tables (relations)

• SQL		Relational Algebra
  SELECT A.name FROM Countries AS A,      Countries AS B WHERE A.name = B.capital	⟹	πA.name     σA.name=B.capital         (ρA Countries × ρB Countries)

From SQL to Relational Algebra

Sorting

• SQL		Relational Algebra
  SELECT name, capital FROM Countries ORDER BY name	⟹	πname, capital τname Countries
  	⟹	τname πname, capital Countries
  SELECT name FROM Countries ORDER BY population	⟹	πname τpopulation Countries

• One can not sort by an attribute that has already been discarded by a projection.

From SQL to Relational Algebra

Removing duplicates

• SQL		Relational Algebra
  SELECT currency FROM Countries	⟹	πcurrency Countries
  SELECT DISTINCT currency FROM Countries	⟹	δ (πcurrency Countries)

From SQL to Relational Algebra

Grouping

• SQL		Relational Algebra
  SELECT currency, COUNT(name) FROM Countries GROUP BY currency	⟹	γcurrency,COUNT(name) Countries

From SQL to Relational Algebra

Grouping with several aggregation functions

• SQL		Relational Algebra
  SELECT currency,SUM(population) FROM Countries GROUP BY currency HAVING COUNT(name)>1	⟹	πcurrency,SUM(population)     σCOUNT(name)>1         γcurrency,SUM(population),COUNT(name)             Countries

• Aggregation functions from different parts of the SQL query appear together in the same γ operator in relational algebra.
• Both WHERE cond and HAVING cond turn into σ_cond.

SQL Query processing

A DBMS processes a query in several steps

• …
• Logical query plan generation
  • Translate SQL query to a relational algebra expression
• Optimization
  • Simplifying relational algebra expressions
• …

Query Optimization

Algebraic laws and algebraic manipulation

• This is something that should be familiar from math. Example:
  • a(b+c) = ab+ac
  • (a+b)² = a² + 2ab + b²
  • x+b+x-b = 2x
• The same idea can be applied also in relational algebra!

Query Optimization

Practical benefits of query optimization

• There are often different ways of writing queries to solve a particular task.
• Since DBMSs contain a query optimizer that tries to transform each query into its most efficient form…
• …we can focus on formulating or SQL queries in a way that makes them easy for humans understand, and rely on the DBMS to make them run efficiently.

Query Optimization

Example: repeated selection

• σ_c₁ (σ_c₂ R) = σ_{c₁ AND c₂} R

Query Optimization

Example: repeated projection

• π_p₁(π_p₂ R) = π_p₁ R
  • Example:
    • π_name (π_{name,population} Countries) = π_name Countries
• Seems obvious.

Query Optimization → Example: repeated projection

• π_p₁(π_p₂ R) = π_p₁ R
• It only works if p₂ is a plain projection.
• Counter example:
  • π_name,density (π_{name,capital,population/area→density} Countries) ≠ π_name,density Countries

Query Optimization

Pushing selection inside a cartesian product

• σ_c(R₁ × R₂) = (σ_c R₁) × R₂
  • (if c only uses attributes from R₁)
• σ_{c1 AND c2}(R₁ × R₂) = (σ_c1 R₁) × (σ_c2 R₂)
  • (if c1 & c2 only uses attributes from R₁ & R₂, respectively.)
• This can dramatically reduce the number of rows in the cartesian product!

Query Optimization

Doing a join instead of a cartesian product

• σ_c(R₁ × R₂) = R₁ ⋈_c R₂
• If the join is using the primary keys,
  • we can quickly find matching rows in R₁ and R₂.
  • the resulting table will not have more rows than R₁ or R₂.

Real-world example

• A quick look at query execution and query optimization in action.
• Using data from the Internet Movie Database (IMDb).

  IMDB downloaded tables and sizes

  Name_Basic	9.8 million rows
  Title_Basics	6.4 million rows
  Title_Principals	37.2 million rows
  Title_Ratings	1.0 million rows

• A subset of the data be downloaded from:
  • https://www.imdb.com/interfaces/
• SQL schemas for the IMDb data: movies.sql
• Example queries: examples.sql

Query optimization example

• Query: Find movies and TV series in which Frida Hallgren has appeared.
• SQL query:

• SELECT T.startYear,T.endYear,T.titleType,T.originalTitle
  FROM Title_Principals AS P,Name_basics AS N,Title_Basics AS T
  WHERE T.titleType IN ('movie','tvSeries')
    AND N.primaryName='Frida Hallgren'
    AND N.nconst = P.nconst
    AND T.tconst = P.tconst ;
  

• Note: the cartesian product in the FROM line is a table with 37e6*9.8e6*6.4e6 = 2.3e21 rows!

Query optimization example

First step: translate to Relational Algebra

• π_{T.startYear, T.endYear, T.titleType, T.originalTitle} σ_{T.titleType IN ('movie', 'tvSeries') AND N.primaryName='Frida Hallgren' AND N.nconst=P.nconst AND T.tconst=P.tconst} (ρ P Title_Principals × ρ T Title_Basics × ρ N Name_Basics)

Query optimization example

• π_{T.startYear, T.endYear, T.titleType, T.originalTitle} σ_{T.titleType IN ('movie', 'tvSeries') AND N.primaryName='Frida Hallgren' AND N.nconst=P.nconst AND T.tconst=P.tconst} (P × N × T)
• Leaving out the long table names. Pretend they are still there!

Query optimization example

• π_{T.startYear, T.endYear, T.titleType, T.originalTitle} σ_{N.nconst=P.nconst AND T.tconst=P.tconst} (P × σ_{primaryName='Frida Hallgren'} N × σ_{T.titleType IN ('movie', 'tvSeries')} T)
• Pushing selections inside the cartesian product
• Table size now: 37e6 * 1 * 716610 = 2.66e13
  • 88e6 times reduction!

Query optimization example

• π_{T.startYear, T.endYear, T.titleType, T.originalTitle} σ_{T.tconst=P.tconst} ((P ⋈ σ_{primaryName='Frida Hallgren'} N) × σ_{t.titletype IN ('movie', 'tvSeries')} t)
• The σ_primaryName selects 1 of 9.8e6 names.
• The condition N.nconst=P.nconst can be converted into a natural join.
• The join selects 60 of 37e6 rows from P.
• Without indexes, the above two steps would need to examine 9.8e6 + 37e6 = 47e6 table rows
• The × creates a table with 60 * 716610 = 43e6 rows

Query optimization example

• π_{T.startYear, T.endYear, T.titleType, T.originalTitle} ((P ⋈ σ_{primaryname='Frida Hallgren'} N) ⋈ σ_{T.titleType IN ('movie', 'tvSeries')} T)
• The second ⋈ is a join of subsets of P and T, using tconst.
• tconst is (part of) the primary key in both p and t.
• By using the indexes, the DBMS can create a physical query plan to do this efficiently.

Query optimization example

Translating back to SQL

• π_{T.startYear, T.endYear, T.titleType, T.originalTitle} ((P ⋈ σ_{primaryName='Frida Hallgren'} N) ⋈ σ_{T.titleType IN ('movie', 'tvSeries')} T)

• WITH
    Names AS (SELECT * FROM Name_Basics
              WHERE primaryName='Frida Hallgren'),
    Titles AS (SELECT * FROM Title_Basics
               WHERE titleType IN ('movie','tvSeries'))
  SELECT startYear, endYear, titleType, originalTitle
  FROM Title_Principals NATURAL JOIN Names NATURAL JOIN Titles ;
  

Query optimization example

Another way to write the same query in SQL

• SELECT startYear, endYear, titleType, originalTitle
  FROM Title_Principals NATURAL JOIN Name_Basics
                        NATURAL JOIN Title_Basics 
  WHERE titletype IN ('movie','tvSeries')
    AND primaryName = 'Frida Hallgren';
  

The end

• See also Jonas Duregård's slides.
• What's next:
  • Wednesday: Exercise: JSON
  • Thursday: Lecture CANCELLED
  • Monday: Lecture: Recap and exam preparation