Query Optimization
CS 245 14
Outline
What can we optimize?
Rule-based optimization
Data statistics
Cost models
Cost-based plan selection
CS 245 15
Outline
What can we optimize?
Rule-based optimization
Data statistics
Cost models
Cost-based plan selection
CS 245 16
What Can We Optimize?
Operator graph: what operators do we run,
and in what order?
Operator implementation: for operators with
several impls (e.g. join), which one to use?
Access paths: how to read each table?
» Index scan, table scan, C-store projections,
…
CS 245 17
Typical Challenge
There is an exponentially large set of
possible query plans
Access paths Access paths Algorithms Algorithms
for table 1 ⨯ for table 2 ⨯ for join 1 ⨯ for join 2 ⨯…
Result: we’ll need techniques to prune the
search space and complexity involved
CS 245 18
Outline
What can we optimize?
Rule-based optimization
Data statistics
Cost models
Cost-based plan selection
CS 245 19
What is a Rule?
Procedure to replace part of the query plan
based on a pattern seen in the plan
Example: When I see expr OR TRUE for an
expression expr, replace this with TRUE
CS 245 20
Implementing Rules
Each rule is typically a function that walks
through query plan to search for its pattern
node
void replaceOrTrue(Plan plan) { Or
for (node in [Link]) {
if (node instanceof Or) { [Link] [Link]
if ([Link] == Literal(true)) {
[Link](node, Literal(true)); expr TRUE
break;
}
// Similar code if [Link] == Literal(true)
}
}
}
CS 245 21
Implementing Rules
Rules are often grouped into phases
» E.g. simplify Boolean expressions, pushdown
selects, choose join algorithms, etc
Each phase runs rules till they no longer apply
plan = originalPlan;
while (true) {
for (rule in rules) {
[Link](plan);
}
if (plan was not changed by any rule) break;
}
CS 245 22
Result
Simple rules can work together to optimize
complex query plans (if designed well):
SELECT * FROM users WHERE
(age>=16 && loc==CA) || (age>=16 && loc==NY) || age>=18
(age>=16) && (loc==CA || loc==NY) || age>=18
(age>=16 && (loc IN (CA, NY)) || age>=18
age>=18 || (age>=16 && (loc IN (CA, NY))
CS 245 23
Common Rule-Based
Optimizations
Simplifying expressions in select, project, etc
» Boolean algebra, numeric expressions, string
expressions, etc
» Many redundancies because queries are
optimized for readability or produced by code
Simplifying relational operator graphs
» Select, project, join, etc
These relational optimizations have the most impact
CS 245 27
Common Rule-Based
Optimizations
Selecting access paths and operator Also very
implementations in simple cases high impact
» Index column predicate ⇒ use index
» Small table ⇒ use hash join against it
» Aggregation on field with few values ⇒ use
in-memory hash table
Rules also often used to do type checking
and analysis (easy to write recursively)
CS 245 28
Common Relational Rules
Push selects as far down the plan as possible
Recall:
σp(R ⨝ S) = σp(R) ⨝ S if p only references R
σq(R ⨝ S) = R ⨝ σq(S) if q only references S
σp∧q(R ⨝ S) = σp(R) ⨝ σq(S) if p on R, q on S
Idea: reduce # of records early to minimize work
CS 245in later ops; enable index access paths 29
Common Relational Rules
Push projects as far down as possible
Recall:
Px(σp(R)) = Px(σp(Px∪z(R))) z = the fields in p
Px∪y(R ⨝ S) = Px∪y ((Px∪z (R)) ⨝ (Py∪z (S)))
x = fields in R, y = in S, z = in both
Idea: don’t process fields you’ll just throw away
CS 245 30
Project Rules Can Backfire!
Example: R has fields A, B, C, D, E
p: A=3 ∧ B=“cat”
x: {E}
Px(σp(R)) vs Px(σp(P{A,B,E}(R)))
CS 245 31
What if R has Indexes?
A=3 B = “cat”
Intersect buckets to get
pointers to matching tuples
In this case, should do σp(R) first!
CS 245 32
Bottom Line
Many valid transformations will not always
improve performance
Need more info to make good decisions
» Data statistics: properties about our input or
intermediate data to be used in planning
» Cost models: how much time will an operator
take given certain input data statistics?
CS 245 33