<aside> 💡 Heuristics / Rules

Rewrite the query to remove stupid / inefficient things.

These techniques may need to examine catalog, but they do not need to examine data.

</aside>

<aside> 💡 Cost-based Search

Use a model to estimate the cost of executing a plan.

Evaluate multiple equivalent plans for a query and pick the one with the lowest cost.

</aside>

<aside> 💡 Logical plan roughly equivalent to the relational algebra expressions in the query.

The optimizer generates a mapping of a logical algebra expression to the optimal equivalent physical algebra expression.

</aside>

<aside> 💡 Physical plans may depend on the physical format of the data that is processed (i.e. sorting, compression).

Physical operators define a specific execution strategy using an access path for the different operators in the query plan.

</aside>

There does not always exist a one-to-one mapping from logical to physical plans.

1. Relational Algebra Equivalences

Two relational algebra expressions are equivalent if they generate the same set of tuples

Query Rewriting → technique of transforming the underlying relational algebra representation of a logical plan

2. Logical Query Optimization

The goal is to increase the likelihood of enumerating the optimal plan in the search.

• Cannot compare plans because there is no cost model
• But can "direct" a transformation to a preferred side.

1. Selection Optimizations
   1. Predicate Pushdown → Perform filters as early as possible
   2. Reorder predicates so that the DBMS applies the most selective one first.
   3. Split Conjunctive Predicates → Breakup a complex predicate and pushing it down
   4. Replace Cartesian Products → Replace all Cartesian Products with inner joins using the join predicates.
2. Projection Optimizations
   1. Projection Pushdown → Perform projections as early as possible to create smaller tuples and reduce intermediate results
   2. Project out all attributes except the ones requested or requires.

3. Nested Queries

Approach #1: Rewrite

Re-write the query by de-correlating and / or flattening it.

Rewriting The former query can be rewritten as the latter query by rewriting the subquery as a JOIN. Removing a level of nesting in this way effectively flattens the query.

Approach #2: Decompose