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