QueryProcessing

Question 1

What is query processing?

Answer 1

The range of activities involved in extracting data from a database, including translation of high-level database language queries into expressions usable at the physical file system level

Question 2

What are the three main steps in query processing?

Answer 2

1. Parsing and translation
2. Optimization
3. Evaluation

Question 3

What is a query-execution plan?

Answer 3

A sequence of primitive operations that can be used to evaluate a query. Each operation is annotated with instructions specifying how to evaluate it

Question 4

What is typically the dominant cost factor in query evaluation for large databases?

Answer 4

I/O cost (disk access) dominates other costs like CPU time and communication

Question 5

How is the cost of an operation that transfers b blocks and performs S random I/O accesses calculated?

Answer 5

b * tT + S * tS seconds where tT is time to transfer a block and tS is block-access time

Question 6

Why are block writes typically more expensive than block reads on magnetic disks?

Answer 6

Block writes are about twice as expensive because disk systems read sectors back after writing to verify the write was successful

Question 7

What percentage of B+-tree nodes are typically non-leaf nodes?

Answer 7

About 1% of nodes are non-leaf nodes

Question 8

What is the difference between materialized evaluation and pipelined evaluation?

Answer 8

Materialized evaluation creates and stores temporary results between operations while pipelined evaluation passes results directly from one operation to the next without storing intermediate results

Question 9

What are the two types of pipelining?

Answer 9

1. Demand-driven pipeline: operations wait for requests to produce tuples
2. Producer-driven pipeline: operations eagerly generate tuples without waiting for requests

Question 10

What is a blocking operation in query processing?

Answer 10

An operation that cannot output any results until all input tuples have been examined (e.g. sorting)

Question 11

What are the three main algorithms for computing joins?

Answer 11

1. Nested-Loop Join
2. Merge Join
3. Hash Join

Question 12

What is the main advantage of Block Nested-Loop Join over basic Nested-Loop Join?

Answer 12

In Block Nested-Loop Join each block of the inner relation is read only once for each block of the outer relation instead of once for each tuple

Question 13

When can Indexed Nested-Loop Join be used?

Answer 13

When computing equi-join or natural join and there exists an index on the join attribute

Question 14

What are the two main phases of external sort-merge?

Answer 14

1. Creation of sorted runs
2. Merging of runs

Question 15

What is a bitmap index scan in PostgreSQL?

Answer 15

An algorithm that first creates a bitmap marking blocks containing matching records then only fetches and scans those specific blocks avoiding reading unnecessary blocks

Question 16

What are the two main metrics used to estimate query costs in disk-based systems?

Answer 16

1. Number of blocks transferred from storage
2. Number of random I/O accesses

Question 17

How does a hybrid merge-join algorithm work?

Answer 17

It merges a sorted relation with the leaf entries of a secondary B+-tree index producing a result file containing tuples from the sorted relation and addresses for tuples of the unsorted relation

Question 18

What is the basic idea behind hash join?

Answer 18

Partition tuples of both relations using a hash function on the join attributes so that matching tuples will be in the same partition and only tuples in corresponding partitions need to be compared

Question 19

What are the steps in implementing duplicate elimination using sorting?

Answer 19

1. Sort the relation
2. Scan the sorted result
3. Remove all but one copy of identical tuples that appear adjacent to each other

Question 20

What is partial aggregation optimization?

Answer 20

Combining tuples in the same group during run generation and intermediate merges by computing partial aggregate values. Only works for commutative and associative operations (count min max sum)

Question 21

What are the three functions provided by an iterator in demand-driven pipelining?

Answer 21

1. open()
2. next()
3. close()

Question 22

What happens in the parsing and translation step of query processing?

Answer 22

The system translates the query into its internal form and performs syntax checking and verification of relations

Question 23

What is query optimization?

Answer 23

The task of constructing a query-evaluation plan that minimizes the cost of query evaluation

Question 24

What special consideration is needed for joins with spatial data?

Answer 24

Spatial joins require special comparison operators for containment and overlap and usually use indexed nested loops join with spatial indices since no simple sort order exists

Question 25

What is the purpose of double buffering in materialized evaluation?

Answer 25

It allows the algorithm to execute more quickly by performing CPU activity in parallel with I/O activity

Question 26

In hash join what is the build input and probe input?

Answer 26

The relation s is the build input (used to build in-memory hash index) and r is the probe input

Question 27

How is the hash join fudge factor typically calculated?

Answer 27

f is typically around 1.2 used to account for some skewness of the join values

Question 28

What is the key advantage of demand-driven pipelining over producer-driven pipelining?

Answer 28

It is easier to implement though producer-driven pipelining can be more efficient on modern CPUs

Question 29

What happens in the build-probe phase of hash join?

Answer 29

The algorithm loads si into memory builds an in-memory hash index then reads ri tuples and locates matching tuples using the index

Question 30

What is an evaluation primitive?

Answer 30

A relational-algebra operation annotated with instructions specifying how to evaluate it

Question 31

When is producer-driven pipelining particularly useful?

Answer 31

In parallel processing systems

Question 32

What are the two main components of disk access cost?

Answer 32

1. Block transfer time (tT)
2. Block access/seek time (tS)

Question 33

How can joins with conjunctive conditions be implemented?

Answer 33

Either using hash join with multiple hash functions or by computing one simple join first and then filtering results with remaining conditions

Question 34

How can set difference be implemented efficiently?

Answer 34

By first sorting both relations then scanning through each of the sorted relations once to produce the result

Question 35

What is the main advantage of implementing aggregation with partial aggregation?

Answer 35

It reduces the amount of data that needs to be stored and processed in subsequent steps

Question 36

What determines the number of runs in external sort-merge?

Answer 36

The size of the relation (br) divided by the memory available (M): ⌈br/M⌉

Question 37

What is the main limitation of implementing full outer join using nested-loop join?

Answer 37

It is difficult to extend the nested-loop join algorithm to compute full outer join

Question 38

What happens if B+-tree internal nodes don’t fit in memory?

Answer 38

A traversal of the index will require multiple I/O operations significantly increasing access cost

Question 39

How can disjunctive join conditions be implemented?

Answer 39

By computing the union of the records from individual joins for each condition

Question 40

What is the best case for nested-loop join cost?

Answer 40

When one relation fits entirely in memory requiring only br + bs block transfers and two seeks

Question 41

How does sorted merge join work?

Answer 41

Once relations are sorted tuples with same join attribute values are consecutive allowing a single pass through both files