Part 1 The basics

X - cartesian product : joins each row in both tables, the joining of selected tables ‘from’ SQL

σ - select : the where command, ‘where’ command from SQL

П - project : the showing of the rows selected, ‘select’ command from SQL

⋈ - theta join : inner join, ‘join’ command from SQL

SELECT c.row1, d.row1

FROM table1 c JOIN table2 d ON c.row1 = d.row1

WHERE c.row2 > 100;

П c.row1, d.row1 (

((σ c.row2 > 100 (table1 c)))

⋈ c.row1 = d.row1 (table2 d)

)

Part 2 Query Trees

Rules:

1. Selects next to each other can merge

2. Select can commute with Project

3. Select can commute with other Selects

4. Theta Join and Cartesian Product and Select and project can commute

5. When multiple Projects in a row, only the last one is needed

Best order of operation

1. Selects

2. Cartesian Product

3. Join

4. Project

Part 3 Basics of Cost Estimation

What are the main factors?

• Disk IO

• Computation cost

• Memory usage

• Communication costs over a distributed system

Quick facts just to note

• Calculations are done for blocks

• tuples - row

• table - relation

Attributes to note

R is a table

• nRows(R) - number of rows

• bFactor(R) - number of rows in a block

• nBlocks(R) - number of blocks needed to store R

• nDistinct a(R) - number of rows that have a certain value ‘a’

• SC a(R) - number of rows that satisfy the condition ‘a’

• nLevels a(I) - number of levels of a multi-level index on a

Part 4 Select (linear search)

Cost:

Cost PK:

Part 5 Join

Cost:

Part 6 Projection

Cost: