Keenwa

Cost-based query optimizer (WIP).

Features

• Basic algorithm based on Cascades/Columbia papers.
• Basic logical/physical plans.
• Basic implementation/transformation rules.
• Basic physical properties/enforcers.
• Basic cost-model.
• Basic statistics.
• Basic catalog API.
• Basic constraints.

Physical properties/Enforcers

• Ordering.
• Partitioning.
• TODO

TODO

• Search space pruning (upper bound/lower bound etc).
• Parameter placeholders/Prepared statements.
• multi-stage optimization setup (logical rewrites -> cost-based -> .. etc.).
• generate plans that can be changed at runtime (configurable access-path selection, etc.).
• Termination: timeout
• Detect cycles in Optimizer::optimize.
• Fallback mechanism to build the remaining physical operators when the optimizer fails to build a logical plan.
• ...

---

Relational operators

• Select/Filter.
• Projection.
• Scan.
• Join.
• Union/Except/Intersect (ALL).
• Limit/Offset
• Fetch
• VALUES operator.
• Distinct option in SELECT
• TODO

Aggregation

• Basic aggregation functions.
• GROUP BY.
• AGGR(..) FILTER (WHERE _).
• AGGR(DISTINCT _).
• count not null.
• count all.
• Window functions.
• User-defined Aggregate functions.
• GROUPING SET.

Implementation

• HashAggregate
• StreamingAggregate.
• TODO

Window functions

• Basic implementation
• ordering within partition
• expressions in PARTITION BY clause

Joins

• Inner

• Left

• Right

• Full

• Cross

• Semi

• Anti (NOT IN ..)

• Lateral

• Basic transformation rules: AxB -> BxA, (AxB)xC -> Ax(BxC)

Implementation

• HashJoin
• MergeSortJoin
• NestedLoopJoin
• TODO

Subqueries

• Basic support.
• Correlated subqueries: EXISTS, IN (cases where an input operator is a restriction(filter/select) or a projection).
• Transform correlated subqueries (EXISTS, IN ) into semi-joins.
• Transform correlated subqueries (NOT EXISTS, NOT IN) into anti-joins.

Scalar expressions

• Basic scalar expressions.
• Basic aggregate functions.
• Basic sub queries.
• Basic identifiers (table.column, etc)
• Compound identifiers (schema.object.whatever, etc)
• Functions expressions.
• IS NULL/IS NOT NULL.
• IN/NOT IN (list).
• IN/NOT IN <subquery>.
• EXISTS/NOT EXISTS <subquery>.
• ANY/ALL <subquery>.
• BETWEEN.
• CASE expression.
• LIKE/NOT LIKE
• Tuples.
• Array access.
• Window functions.
• User-defined aggregate functions.
• TODO

Binary operators

• Basic operators (AND, OR, =, !=, >, <, >=, >=, +, -, /, *, %, ).
• Bitwise operators.

Data types

• Basic data type (string, int32, bool).
• Floating point types.
• Decimal types.
• Byte arrays.
• Date (Days)
• Time (Hours, Minutes, Seconds, Millis) without time zone.
• Time with time zone.
• Timestamp without time zone.
• Timestamp with time zone.
• Time intervals: Year, Year to Month, Month, Day, Day to Hour, Day to Minute, Day to Second.
• Arrays.
• Tuples.

Functions

• Additional String functions.
• Additional numeric functions.
• Additional date/time functions.
• Additional interval functions.
• Additional array functions.

Constraints

• Unique.
• Not null.
• Default value.
• Check expression.

---

Logical rewrites (Experimental)

• Basic logical rewrites API.
• Predicate push-down.
• Redundant projections removal.
• TODO

---

Catalog

• Basic tables.
• Basic indexes.
• Table constraints.
• More index types.
• User-defined functions
• TODO

Statistics

• row count.
• predicate selectivity.
• TODO

---

Cost model

• basic cost model (row count, predicate selectivity).
• compute predicate selectivity.
• TODO

---

Data manipulation operators

TODO

---

SQL-support (sqlparser-rs)

See test cases in sql/*_tests.yaml.

• Basic operators.

• Basic subqueries.

• Joins: Inner, Left, Right, Full, Cross

• SELECT DISTINCT

• LIMIT/OFFSET

• FETCH

• EXPLAIN/ANALYZE

• ALIAS (column list)

• AGGREGATE DISTINCT

• VALUES(..)

• NOT IN/ IN <subquery>

• EXISTS/NOT EXISTS <subquery>.

• WITH (Common table expressions)

• WITH RECURSIVE (Recursive common table expressions)

Basic DML operators

TODO

Basic DDL operators

TODO

---