Query Processing

Question 1

Query Processing

Answer 1

This is where we look at the query compiler, and execution engine. This is responsible for transforming SQL queries into sequences of database operations and then execute the queries.

Question 2

Queries

Answer 2

In queries, we typically tell the DBMS what we want, not how we want it.
We’re typically going to look at select statements.

Question 3

Relational Algebra

Answer 3

Set of operations that can be applied to relations to compute new relations (things like select, projection, natural join, union etc).

Question 4

Relational Algebra Expression

Answer 4

Often called a logical query plan, and are often represented as trees.

Question 5

Logical Query Plan example

Answer 5

SELECT department, name
FROM Stores, Employees
WHERE department=worksAt AND city=’Liverpool’

can be converted to

π_(department, name)(σ_(department=worksAt AND city=’Liverpool’)(Stores x Employees)

Question 6

σ

Answer 6

Selection, used for conditions.

Question 7

π

Answer 7

Projection, restricts attributes in attribute list.

Question 8

ρ

Answer 8

Renaming, very simply used for representing one thing as another (like using AS in SQL).

Question 9

✕

Answer 9

Cartesian product, pairs each tuple together (like using SELECT DISINCT * FROM _)

Question 10

Query Plan steps

Answer 10

• Compute an intermediate result for each node
• For a leaf labeled with relation R, the intermediate result is R
• For an inner node labeled with operator op, get the intermediate result by applying op to the children’s intermediate results.
• Result of query -> intermediate result of the root.

Question 11

Equijoins

Answer 11

Represented as R ⋈_a=b S.
Joins things together based upon attributes given (in this case, a and b).

Question 12

Merging (merge sort)

Answer 12

Way of understanding equijoin:
1) Check values of a and b. If a is smaller than b, move down in a, and if b is smaller than a, move down in b.
2) If a and b are equal, we merge the cell of a and b, and move down in b.
3) Repeat
If there are duplicates in a, we remember that they are duplicates and repeat the b table again

Question 13

Fast Join Algorithms

Answer 13

There is a fast join algorithm which is the sort join algorithm, and can be a fast way of computing R ⋈_a=b S.

Question 14

Other Join Algorithms

Answer 14

• Index join
• Hash join
• Multiway join

Question 15

Relations on disk

Answer 15

Relations are stored on disk, and RAM is not often big enough to store everything, but if we stored everything on disk then it would take longer than if on RAM.

Question 16

Disk parameters

Answer 16

• B = size of the disk block (512 to 4096 bytes)
• M = number of disk blocks that fit into available RAM.

Question 17

Reading a relation R

Answer 17

No. of elementary operations =
O(|R|)
No. of disk access =
O(|R|/ B)

Question 18

Sorting R on attribute A

Answer 18

No. of elementary operations =
O(|R| log_2 |R|)
No. of disk access =
O((|R|/ B) log_2 (|R|/ B))

Question 19

O(|R|)

Answer 19

Since we are reading them one by one linearly.

Question 20

O(|R| log_2 |R|)

Answer 20

O(n log n), based upon sort join algorithm.

Question 21

O(|R|/B)

Answer 21

We can just read the blocks instead. Since it under the presumption that each record has a constant size.

Question 22

O((|R|/ B) log_2 (|R|/ B))

Answer 22

We are sorting all disk blocks, not individual records.

Question 23

Index

Answer 23

Given the values for one or more attributes of a relation R, provides quick access to the tuples with these values.

Question 24

Types of index

Answer 24

Primary -> defines how data is sorted on disk.
Secondary -> merely points to location records on disk.

Question 25

Forms of index

Answer 25

B+ Trees
Hash Tables

Question 26

B+ Trees

Answer 26

Good if select condition specifies a range, and it most widely used.

Question 27

Hash Tables

Answer 27

Good if selection involves equality only.

Question 28

Virtual Columns

Answer 28

If we have indices over multiple columns (instead of doing one column, like year, we can do two columns, like programme), we create a virtual column which concatenates both of them, with the first one being priority over the second one (like using GROUP BY).

Question 29

Heuristics

Answer 29

• Push selections as far down the tree as possible
• Push projections as far down as possible, or insert projections where appropriate.
• Where possible, introduce equijoins for cross product followed by selections.

Question 30

Physical Query Plan

Answer 30

Adds information required to execute the optimised query plan.
Things like:
- Which algorithm to use for execution of operators (naive selection or index selection, nested block join or sort join or hash join)
- How to pass information from one operator to another (write to disk, keep in memory, pipelining operators)
- Good ordering for computer joins, unions etc
- Additional operations such as sorting
are all considered.

Question 31

Using physical query plans for cost

Answer 31

We generate many different physical query plans and estimate the cost of execution for each plan (time, disk access, memory etc). From then, we select the lowest cost.

Question 32

Estimation cost of execution

Answer 32

Relies on number of disk access operations.

Question 33

Number of disk operations influences

Answer 33

Number of disk accesses are influenced by many factors:
- Selection of algorithms for the individual operators.
- Method for passing information.
- Size of intermediate results.

Question 34

Disk access operation parameters

Answer 34

• Size of relations
• Number of distinct items per attribute per relation.

Question 35

Projection example

Answer 35

For σ_a=b(R)
|R| / number of distinct values in column a of relation R.

Question 36

Joins example

Answer 36

For R ⋈ S, we have:
(|R| x |S|) / max number of distinct values for A in R or S.

Question 37

How to generate physical query plans?

Answer 37

A sensible approach is to go either top-down or bottom-up:
- Selection for a suitable algorithm for each operator based upon size of intermediate result
- Select of a good join order based upon size of intermediate result

Question 38

Passing Information

Answer 38

Either materialisation or pipelining.