## Query processing

### Query Processor
- Query: Declarative DB language  (Mapping to RA)
- Evaluation: Translate to execution plan (physical level)
- Physical relational algebra: Extend with primitives for internal structures

![](images/queryprocessor.png)
![](images/queryprocessing.png)
### Query Parser
- Translator:
	- Translate to internal form (query is declarative)
- Scanner:
	- Tokenize query (DB language keywords, table/attribute names)
- Parser:
	- Check syntax
	- Verify relations
	- Attributes
	- Data types
- Translation to RA to evaluate query
	- RA allows symbolic calculation
	- Evaluation primitives: Annotate operators with execution algorithms

### Query Translator (cf. VL 06)
- Translation query to RA
	- Decomposition into query blocks (1 SELECT, 1 FROM, at most 1 where, group by, having)
	- No nesting (optimize subqueries independently -> parallel)
	- Query normalization (WHERE in conjunctive normal form)
	- RA allows symbolic calculation
- Result: Operator Tree
	- Leafs: Relations
	- Internal nodes: Operators

### Operator execution (cf. VL 06)
- Algebraic operator abstraction of algorithm (=> eval. primitive)
- Operator writes result into temp. table
	- Intermediate result can be large
	- Materialization expensive
- Evaluation primitives
	- Tuple scan
	- Tuple selection
	- Index scan
	- Various join operators (nested loop, block nested loop, index nested loop, merge, hash)
	- Sort operator
	- Duplicate elimination operator

### Relational Algebra
- Edgar Codd in 1970
- Lead to SQL
- Important for Query optimization (undecidability of equivalence)
- Operators: Selection, Projection, Cartesian Product, Set Union, Set Difference, Rename
- Important: Union-compatibility
- Joins: Theta Join <- Equijoin <- Natural join

### Query Execution
- Task: Evaluate operator tree
- Challenge: Each operator different algorithms
	- Evaluation plan: Annotated with evaluation strategy
- Operator cost: Total elapsed time (disk access, CPU time (often ignored), network)
- Disk access
	- \#Seeks * avg. seek cost
	- \#Block reads * avg. block read cost
	- \#Block writes * avg. block write cost (higher because of reading for verification)
- Operator result: temporary file (expensive but sometimes necessary)
- Usually: Algorithms for sequences of operations (joins, dynamic algorithms)

#### Select operator
- Primitives:
	- Relation scan
	- Index scan
	- Relation scan with comparison
	- Complex selections

##### Relation scan
- Linear search
	- Fetch all pages —> scan each record
	- Cost: \#Pages with records (0.5 * \#Pages for PK)
- Binary Search (ordered attribute, equality select)
	- Assumption: Continuously stored
	- Fetch median page for start
	- Cost estimate: `$ \log_2(\text{\#pages with records}) $` (cost for first tuple)

##### Index scan
- Selection condition on search key
- Equality selection on primary index:
	- Height of tree / 1 for hash index
- Equality selection on cluster index:
	- Height of tree / 1 for hash index + \#pages overflow list
- Equality selection on secondary index: 
	- Not stored continuously
	- Cost unique attribute: Height of tree / 1 for hash index
	- Cost non-unique attribute: Height of tree / 1 for hash index * \#Records

##### Comparison scan
- Simple scan/binary search
- Primary index available
	- `$ > $`: Find first and scan rest of relation
	- `$ < $`: Scan relation until found
- Secondary index available
	- `$ > $`: First first value and scan rest of index (find pointers)
	- `$ < $`: Find pointers until value found
- EVERY records must be fetched
- Linear scan can be cheaper

##### Complex selection
- Use of junctors: AND, OR, NOT
	- Combination of simpler selections
	- Conjunction: Start with smallest selectivity
	- Disjunction: Only fetch blocks once
	- Negation: Linear scan necessary

#### Sorting
- Why?
	- ORDER BY
	- Increase performance for more complex algorithms
- Secondary index on sort key
	- Read in-order
	- Inefficient
- Relation in main memory: No problem -> Quicksort
- Relation too big -> External sorting
- Solution: Merge-Sort / n-ary sort
	- Divide relation into runs, sort each run, write run to disk
	- Read runs -> integrate to result

#### Projection operator
- Projection on each tuple
	- Complete relation scan (relations horizontally split, row storage)
	- Duplicate elimination for non-unique fields
		- Sorting -> Identical records adjacent
		- Merge-Sort: Eliminate duplicates in runs

#### Set operations
- First sort relations
- Scan relations
- Create result
	- Union: return just one record
	- Intersection: Only records in both
	- Difference: Retain only records that are absent in other relation
- Cost: \#Pages first + \#Pages second + Sorting cost (if necessary)
- Alternative implementation:
	- Partition using hash function
	- Build in-memory hash index
	- Scan first partition, use hash index to find record

#### Join operators
- Special type cartesian product
- Two relations
	- Only record with counterpart in other relation is in result set
- Size estimation: Selectivity of condition, overlap of distinct values
- Implementations
	- Nested loop join
	- Block nested loop join
	- Index nested loop join
	- Merge join
	- Hash join

##### Nested loop join
- Simplest join
- Algorithm:
	- For each record r1 in T1 (outer loop)
		- 	For each record r2 in T2 (inner loop)
		- 	Compare
- Cost buffer size = 1: \#Num records left * (\#num blocks right + 1)

##### Block nested loop join
- Idea: Reduce block reads with prefetching with window w
- Algorithm:
	- 1. For every w records in T1
	- 1.1. Prefetch w records into windows
	- 1.1.1. For each record r1 in window
	- 1.1.1.1. For each record r2 in T2:
	- 1.1.1.1.1. Compare 
- Cost b=1: `$ |T_1|/2 * (|T_2|+1) $`

##### Index nested loop join
- Idea: Use index for inner loop (avoid scanning)
	- Index can exist/temporary/just be created
	- Use with block nested algorithm (window)
- Algorithm
	- For each record r1 in T1 (outer loop)
	- Compare r1 with index lookup on T2

##### Merge join
- Idea: Adapt technique from merge-sort, only for equijoin/natural join
- Algorithm
	- Sort T1 and T2
	- Linear scan and compare
- Cost: Sorting + Blocks of both (depends on buffer)

##### Hash join
- Idea: Only useable for Equijoin/natural join
- Algorithm
	- hash tuples from T1 and T2 on join attribute
		- For each bucket b
			- Compare tuples from T1 with T2