Query Processing (2019)

Question 1

Query Processing:

Basic Steps

Answer 1

1. Query
   
   • User inputs a query
2. Parser and Translator
   
   • Translates query from human readable form to something DBMS understands, such as Relational Algebra Expression
3. Optimizer
   
   • Finds optimized equivalent to RA expression
   • Creates Execution Plan
4. Evaluation Engine
   
   • Runs the Execution Plan to perform the query
5. Query Output
   
   • Results returned to user

Question 2

Query Processing:

Diagram of the Basic Steps

Answer 2

*See Diagram

Question 3

Query Processing Steps:

Query

Answer 3

User inputs a query in some

human readable language,

such as SQL.

This query is passed to the Parser and Translator

Question 4

Query Processing Steps:

Parser and Translator

Answer 4

• Recieves Query in some human readable form, such as SQL.
• Performs Syntax Checks
• Translates to a language that the DBMS understands internally(RA)
• Generates Relational Algebra Expression

Question 5

Query Processing Steps:

Optimizer

Answer 5

• Recieves Relational Algebra Expression from Parser/Translator
• Finds an equivalent statement that is more optimal
  
  • Same results, with less time and resources used
• From this optimal statement, generates an Execution Plan to be run by the Evaluation Engine

Question 6

Query Processing Steps:

Evaluation Engine

Answer 6

• Receives an Execution Plan from the Optimizer
• Performs it on the Database, obtaining results to be output to the user
• Returns Query Output to the User

Question 7

Cost of a Query

Answer 7

• Typical Measure is Total Elapsed Time
• Factors:
  
  • Disk Access
  • CPU
  • Network Communication
• Disk access is usually the “bottleneck”

Question 8

Disk Access:

How Relations are Stored on Disk

Answer 8

• DBMS stores its data in Files
• Files are broken into Blocks
• The number of tuples per block varies
• B(R) is the number of blocks used for relation R
• T(R) is the number of tuples used in relation R

Question 9

Three Factors of

Disk Access cost

Answer 9

• Number of Seeks
• Number of Block Reads
• Number of Block Writes

Question 10

Disk Access:

Why are Block Writes

more expensive than

Block Reads?

Answer 10

A block must be read again after writing,

so the actual time is:

(Time to Write) + (Time to Read)

Question 11

Seek Time:

Basic Idea

Answer 11

The time spent

spinning the disk

to get to the specified data area

Question 12

Seek Time:

Two types of Indices on Disk

Answer 12

• Clustered Index
  
  • Data is stored in sorted order
  • Data is very close together on disk
  • Less Seek Time -> Faster
• Unclustered Index
  
  • Data is stored farther apart
  • More Seek Time -> Slower

Question 13

Types of

External Memory Joins

(Extended) (9)

Answer 13

• Nested Join
• Nested Loop Join
• Block-Nest Loop Join
• Index Nested Loop Join
• Improved Nest Loop Join
• Reservoir Sampling
• Reservoir Join Sampling
• Hash Join
• Partitioned Hash Join

Question 14

Three Types of

Join Algorithms (External Memory)

Answer 14

Nested Loop Joins

Hash Joins

Sort-Merge Joins

Question 15

External Memory Join Algorithms:

Nested Loop Joins

General Cost

Answer 15

Nested Loop Joins

cost = O( |R| |S| )

Question 16

External Memory Join Algorithms:

Hash Joins

General Cost

Answer 16

Hash Joins

Cost = O( |S| )

if |R| < |S|

*I believe R = read cost, S=search Cost

Question 17

External Memory Join Algorithms:

Sort-Merge Joins

General Cost

Answer 17

Sort-Merge Joins

Cost = O( |S| * log(|s|) )

if |R| < |S|

*I believe R = read cost, S=search Cost

Question 18

Query Costs:

External Memory Joins

Answer 18

• Happens when at least one relation does not fit into memory
• I/O Cost is the dominating factor
• Call the memory limit M
• Cost is depended on the Memory Join Algorithm used
• Internal Memory Joins are Simple:
  
  • B(s) + B(s)

Question 19

Nested Loop Join:

Overview

Answer 19

For each block of a relation R, and for each tuple r in block:

For each block of a relation S, and for each tuple s in block:

Output rs if the join condition evaluates to true

• R is called the Outer Table
• S is called the Inner Table

Cost = B(R) +T(R)*B(S)

Memory: 4 Blocks, if double buffering

Question 20

Block-Nest Loop Join:

Overview

Answer 20

For each block of R and for each block of S:

For each tuple r of R and s of S:

Output rs if join condition evaluates to true.

R is the outer table, S is the inner table

Cost:

B(R) + B(R)*B(S)

Memory:

4 Blocks (If double buffering)

Question 21

Improved Nest Loop Join

Answer 21

Outer table R and inner table S

• Use available memory, read M-2 blocks from table R
• Read blocks of S sequentially, join with R in Main Memory

Cost:

B(R) + B(R)*B(S) / (M-2)

Memory:

M Blocks

Question 22

Nested Join

Answer 22

Joining Outer table R and inner table S

(Used if B(R) + B(S) < M) (fits in memory)

• Scan R, sort in Main Memory
• Scan S, sort in Main Memory
• Merge R and S

Cost: B(R) + B(S)

Question 23

Index Nested Join

Answer 23

R has an index over the Join Attribute

• Scan S:
  
  • For each tuple of S, find matching tuples of R

V(R,a) = number of distinct values of a in R

Cost:

• If data clustered
  
  • Cost = B(S) + T(S)*B(R) / V(R,a)
• If data unclustered
  
  • Cost = B(S) + T(S)*T(R) / V(R,a)

Question 24

Selection:

Two Types of Scans

+ Their Costs

Answer 24

Scanning Without Index:

Cost = B(R) + Seek Time

Scanning With Index:

If there is an index over the attribute, use a function F to determine the # of I/O operations

Data Clustered:

Cost = F(R,a)*B(R)

Data Unclustered:

Cost = F(R,a)*T(R)

Question 25

Selection on Indexed Attribute: I/O Cost Functions for possible selection conditions

Answer 25

_Equals_ : **σ_a=v (R)** **F(R,a)** = 1 / **V(R,a)** Less Than: **σ_{a (R)}** **F(R,a) = (v - min(R,a) ) / (max(R,a) - min(R,a) )** Range: **σ_{x (R)}** **F(R,a) = (v - x ) / (max(R,a) - min(R,a) )**

Question 26

Assumption about I/O Cost Function F for most DBMS Applications

Answer 26

Most DBMSs use a **B+ Tree**, so for searching on a _Clustered Index_, we can use the _Height of the B+ tree._ **Cost = H + B(R)**

Question 27

Sampling: Overview

Answer 27

* Can be used to save time on large Databases * Sample from tables, join based on the sample instead * Less accurate, but much faster * Two Types: * Reservoir Sampling * Reservoir Join Sampling

Question 28

Sampling: Reservoir Sampling

Answer 28

**W** \<- 0 start with 0 weight Initialize reservoir array **A[**1..**r]** with dummy values. While tuple streams in: * Get next tuple **t** with weight **w(t)** * **W** \<- **W** + **w(t)** //increase the weight * for **j**=1 to **r** * set **A[j]** to **t** with probability **w(t)/W**

Question 29

Sampling: Reservoir Join Sampling

Answer 29

**W** \<- 0 start with 0 weight Initialize reservoir array **A**[1..**r**] with dummy values. For each **Candidate Network(CN)** and every tuple **t** in **CN**: If **A** has dummy values, Insert **k** copies of **t** into **A** Else **W** \<- **W** + **w(t)** for i = 1 to **k**: Insert **t** into **A[i]** with probability **w(t)/W** Terminate if copy of **t** is inserted

Question 30

Hash Join Overview

Answer 30

* Scan R, build buckets in Main Memory * Scan S, then Join Notes: * Build the hash table on whichever table is smaller: **min**( **B(R)**, **B(S)** ) * Only works if **min**( **B(R)**, **B(S)** ) \<= M-2 * It has to fit inside of main memory **Cost = B(R) + B(S)**

Question 31

Partitioned Hash Join

Answer 31

Used when a relation cannot fit into memory. * Using the first Hash Function, **H₁** : * Hash **R** into **M**-1 buckets, store on disk * Hash **S** into **M**-1 buckets, store on disk * Read one partition(bucket) of R into Main Memory * Join like normal hash join, using a second, separate hash function, **H₂** Cost: **3B(R) + 3B(S)** Memory: Smaller bucket must fit in memory Bucket size = **B(R) / (M-1)**