Optimization

Example:

• SELECT SNAME FROM SP NATURAL JOIN S WHERE PID = 'P2';
• assume that
  • there are much more shipments than suppliers
  • only a small fraction of shipments are of part P2

Compare two strategies:

1. evaluate query 'directly':
   • read shipments and find matching suppliers
   • restrict the result to part P2
   • project over SNAME
2. different procedure:
   • read shipments and restrict to P2
   • find matching suppliers
   • project over SNAME

Differences:

1. constructs large intermediate table which is then restricted i.e. most rows are thrown away
2. constructs much smaller intermediate table and accesses only suppliers needed for final result

Stages:

1. cast query to internal form
   • query tree, abstract syntax tree
   • i.e. internalized form of relational algebra
2. convert to canonical form
   • canonical i.e. 'reduced to essentials'
   • query transformation using rules
3. choose candidate low-level procedures
   • implementation options
   • cost formula, usually measured in disk IO
4. generate query plan
   • generate possible plans
   • reduce search space
   • choose cheapest plan

Query Transformation

Transformation rules: convert query into equivalent but more efficient form

The following sections show some examples for each type.

Restrictions and Projections

• ( A WHERE restriction1 ) WHERE restriction2 ⇒ A WHERE restriction1 AND restriction2
• ( restrict A ) project ⇒ ( project A ) restrict
• ( A JOIN B ) WHERE restriction_on_A ⇒ ( A WHERE restriction_on_A ) JOIN B
  'do restrictions early'

Distributivity

E.g. sqrt(x * y) = sqrt(x) * sqrt(y)

• ( A UNION B ) { C } ⇒ A { C } UNION B { C }
• ( A INTERSECT B ) { C } ⇒ A { C } INTERSECT B { C }
• ( A JOIN B ) { C } ⇒ ( A { AC } ) JOIN ( B { BC } )
  with
  • AC = (attributes common to A and B) union (attributes in C that appear in A only)
  • BC = (attributes common to A and B) union (attributes in C that appear in B only)
  'do projections early'

Semantic Transformations

Integrity constraints can be used in semantic optimization, e.g. referential constraint:

( SP JOIN S ) { PID } ⇒ SP { PID }

DB Statistics

used in stage 3 and 4, some examples:

• tables:
  • cardinality
  • size in physical units of disk storage
    • block/page, smallest unit of read/write on disk
    • e.g. 1 page = one 4K sector on disk (physical sector size)
    • or 1 page = 8 sectors of 512 bytes
• columns:
  • number of distinct values
  • min, max, avg value

Updated according to some scheme, not with each SQL operation

Query decomposition

Allow for execution in parallel or distributed environment

Implementation of Relational Operators

E.g. R JOIN S with common attribute(s) C, m = cardinality(R), n = cardinality(S):

Brute Force ('nested loops'):

for i = 1 to m:
  for j = 1 to n:
    if R[i].C == S[j].C: output R[i], S[j]

• p tuples per page (block) for R
• q tuples per page for S
• m = 100, p = 1
• n = 10000, q = 10

• R outer, S inner: m/p + (m * n)/q = 100100
• S outer, R inner: n/q + (n * m)/p = 1001000

Index Lookup: assume index X on S.C

for i = 1 to m:
  js = lookup R[i].C in X
  for j in js:
    output R[i], S[j]

• d = number of distinct values of C in S = 100
• uniform value distribution of S.C i.e. expect n/d tuples with given value C
• every tuple read to S is a separate page read (worst case)

• m/p + m * n / d = 10100
• Index lookup:
  • very low, e.g. m * x for index with x levels, but
  • first or more levels of index stay in memory

Hash: Similar to Index Lookup, but build hash table on demand instead

• First pass over S, build hash table H on S.C
• Second pass over R, check join attribute R.C

for j = 1 to n:
  k = hash S[j].C
  add j to H[k] 
for i = 1 to m:
  js = lookup R[i].C in H
  for j in js:
    if S[j].C == R[i].C: output R[i], S[j]

• lookup possibly/probably faster than index
• but first pass overhead
• note that different C may evaluate to the same hash k

Here is an illustration for a very simple indexing scheme implemented in a C program:

• A data file for a table with 30 million records is created, each with
  • a 200 byte random text,
  • an 8 byte text containing the decimal record number,
  • another 3 byte random text,
  • and a newline.

  The data file is too large to fit into memory on the host running the program.

• An index file contains the first 4 bytes of the first text field, and the 4 byte binary representation of the record number, resulting in 8 bytes per index entry. This file fits into memory.

% time db0 create 30000000 200

First the data file is scanned sequentially for lines starting with ABCD:

% time db0 df
ABCDWLMHIBYBTSQCQNJWUB...GDD  422524BFI
ABCDBAQJGUAQXCQAAVLPHD...WPI  589062MDR
ABCDNQMKOJVWKFSAXYICVZ...RAT  631901GGI
...

real	1m28.125s

Next the index is used to find matching rows which are then retrieved from the data file by seeking directly to the desired position:

% time db0 idx seek 
ABCD 422524
ABCDWLMHIBYBTSQCQNJWUB...GDD  422524BFI
ABCD 589062
ABCDBAQJGUAQXCQAAVLPHD...WPI  589062MDR
...

real	0m5.987s

A second run finds the index file still in buffer memory, so the performance is improved:

% time db0 idx seek 
ABCD 422524
ABCDWLMHIBYBTSQCQNJWUB...GDD  422524BFI
ABCD 589062
ABCDBAQJGUAQXCQAAVLPHD...WPI  589062MDR
...

real	0m1.072s

For 50 million records the data file is 9.9 GB. The index is 380 MB which still fits into memory. The timings are: