Query Optimizer (Raptor)

[joocer]

Query optimization is likely to exist as a rule engine which takes a plan and (if available) table statistics, and performs optimisations.

This should be implemented as a battery with multiple passes (and some sort of flap detection) where the inputs are run through each optimization rule, until no changes have been made (the event of multiple rules doing and undoing optimisations should be captured).

Verbose logging should be used to capture the AST, the original plan and the final plan.

Some randomisation should be included to allow for comparison of plans, for example randomly not applying a specific optimization, the order being random and/or the number of cycles being random). This should result in some minor variations in the plans which can then be compared to identify optimal order or coexistence of optimisations.

The Optimizer will be given the name Optimizer in the code, but referred to as Raptor

[joocer]

Optimizations

See An Overview of the Starburst Trino Query Optimizer

predicate pushdown
Filter data before joins
This could be both simple pushdowns (just moving the predicate) or inferred, for example, if we know the left table only has values 1-10 but the right table has values 1-100, we can create our own filter to apply and run either on-read or pre-join.

limit pushdowns
In some circumstances, we can push down LIMITS

add predicates

SELECT * FROM A INNER JOIN B ON A.x = B.y WHERE A.x = 10

We know a condition on A.x, we can apply that some condition on B.y

join reorders
Swap left and right, including when there are more than two joins - so the left (in memory) table is the smaller.

Include row estimates and filter estimations (min/max and centiles - e.g. we know at most 50% of records are greater than n), including - if possible - an estimate of the matches from a previous join:

[joocer]

query.optimizer

.plan_contains(operation) -> name
.insert_operation(before_name, operation)
.replace_operation(operation_name, operation)
.remove_operation(operation_name)

(Select before join)
If plan contains a join and a filter
Try to push the filter to before the join
This needs to be able to identify which table the filters come from, so either needs to know the schema (usually post read) or the fields to be qualified or to be part of the join
If the filter is equalling two identifiers, this should probably be added to the join condition

We already do projection pushdown

[joocer]

This should also include the ability to run SET statements in order to provide hints to the Optimizer.

There should be a way to say not to optimise, we should run performance tests, optimized queries should be on average faster than unoptimized queries and never more than 5% slower.

[joocer]

SET $ENABLE_OPTIMIZATION=FALSE
SET $ENABLE_OPTIMIZATION_RULE_(name) = FALSE

[joocer]

The first optimization will simply be to split commutative predicates in the WHERE and HAVING clauses into individual expressions.

This should have a minor performance benefit without any further changes.

This lends itself to two subsequent optimisations

1. ordering predicates to remove records quickly
2. pushing predicates down closer to the reads

[joocer]

https://dev.mysql.com/doc/internals/en/optimizer-primary-optimizations.html

Contains a set of rule-based optimizations.

[joocer]

https://dev.mysql.com/doc/internals/en/optimizer-primary-optimizations.html

Contains a set of rule-based optimizations.

[joocer]

https://www.cockroachlabs.com/blog/building-cost-based-sql-optimizer/