Databases (TDA357 / DIT621)

Relational algebra and query compilation

• Notes: chapter 6
• Book: chapters 2, 5, 16
• Lecture given by: Thomas Hallgren

Last week

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 as sets of tuples, R ⊆ S₁ × S₂
• Operations on sets and relations: ∩, ∪, −, ×
• Operations from relational algebra: π, σ, ⨝

Today

• SQL Query processing
• From SQL to Relational Algebra
• Query optimization
• Indexes
• 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

• Introduced last week
• R ::=

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

Relational Algebra overview

Operations from set theory

• R ::=

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

Relational Algebra overview

Join operations

• R ::=

  …
  R ⨝ R		NATURAL JOIN
  R ⨝a+ R		INNER JOIN
  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, B.capital} σ_{A.name=B.capital} (ρ_A Countries × ρ_B Countries)

  

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

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, B.capital FROM Countries AS A,      Countries AS B WHERE A.name = B.capital	⟹	πA.name, B.capital     σ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

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 BY 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.

Query Optimization

Algebraic manipulation

• Something that is familiar from math. Example:
  • a+b*0+a = 2*a
• This idea can be applied also in relational algebra
• This can be used make execution of queries more efficient

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 pure 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, the resulting table will not have more rows than R₁ or R₂.

Indexes

• DBMSs automatically add indexes for primary keys
• You can add indexes for other attributes...
  • CREATE INDEX indexname ON tablename (attribute+)?
• ...and remove them:
  • DROP INDEX indexname
• Advantage: indexes speed up selection and join operations involving those attributes
• Disadvantage: creating and maintaining indexes requires extra time and space.

Real-world examples

• A quick look at query execution and query optimization in action.
• Using data from the Internet Movie Database (IMDb).
• 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 9e6*5.5e6*32e6 = 1.6e21 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: 32e6 * 1 * 667802 = 2.14e13
  • 50e6 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 σ in the join selects 1 of 9e6 names
• The join selects 58 of 32e6 rows from p using that name
• The above two steps probably need to examine 9e6 + 32e6 = 41e6 table rows (which takes ~2.2 seconds on my computer)
• The × creates a table with 58 * 667802 = 38.7e6 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.
• The DBMS can probably create a physical query plan to do this efficiently.