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<v> (R)</v>}

F(R,a) = (v - min(R,a) ) / (max(R,a) - min(R,a) )

Range: σ_{x<a> (R)</a>}

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)