When two tables join with equation conditions, and one side has predicate on join key, new predicate can be generated and pushed to the other side. The core of this rule is to filtering unused data as early as possible. Predicates on both sides of inner/semi join can be propagated. Predicates on left side of left/anti join can be propagated.

-- before
SELECT 1 FROM t1 JOIN t2 ON t1.c1 = t2.c2 AND t1.c1 > 0;

-- after
SELECT 1 FROM t1 JOIN t2 ON t1.c1 = t2.c2 AND t1.c1 > 0 AND t2.c2 > 0;

Some times the predicate is not located in join condition, and the push may cross multiple query blocks with many operators.

-- before 
SELECT * 
FROM (SELECT c1, count(*) as s1 FROM t1 WHERE c1 > 0 GROUP BY c1) t1 
JOIN (SELECT c2, count(*) as s2 FROM t2 GROUP BY c2) t2
ON t1.c1 = t2.c2;

-- after
SELECT * 
FROM (SELECT c1, count(*) as s1 FROM t1 WHERE c1 > 0 GROUP BY c1) t1 
JOIN (SELECT c2, count(*) as s2 FROM t2 WHERE c2 > 0 GROUP BY c2) t2
ON t1.c1 = t2.c2;

And the subquery case is similar.

-- before 1
SELECT c1 FROM t1 WHERE EXISTS (SELECT 1 FROM t2 where c2 = t1.c1 and c2 > 0);

-- before 2
SELECT c1 FROM t1 WHERE c1 > 0 AND EXISTS (SELECT 1 FROM t2 where c2 = t1.c1);

-- after
SELECT c1 FROM t1 WHERE c1 > 0 AND EXISTS (SELECT 1 FROM t2 where c2 = t1.c1 and c2 > 0);

The implementation should try to cover such scenarios as much as possible.

close #68 close #52

The rule of predicate pullup also includes some functionality of predicate propagate. remove duplicates and fold predicates are left for future improvement.

close #30

The rule is implemented by collecting null rejecting predicates and traverse child queries to change join types. The predicates are not really pushed down in this optimization.

close #48

Add join graph operator with optimize rule to initialize it. Refactor predicate pushdown to effectively push predicate down to and through join graph.

This rule is to unfold flat derived table containing only simple projections. For example:

SELECT * FROM (SELECT c0, c1 + 1 as cc FROM t1) x1 WHERE f(cc+1) > 0 

could be unfolded and translate to equivalent SQL like below:

SELECT c0, c1 + 1 as cc FROM t1 WHERE f(c1 + 1 + 1) > 0

The benefits are not only further optimizations like expression simplify, but also more tables involved in join reorder. In some scenarios, users specify bushy join via derived table:

SELECT 1 FROM t1 JOIN t2 JOIN (SELECT * FROM t3 JOIN t4)

With this rule applied, we could reorder 4 tables instead of 3. Althrough SQL does not allow such syntax:

SELECT 1 FROM t1 JOIN t2 JOIN (t3 JOIN t4)

More advanced unfolding is left for future improvements, e.g. certain patterns of aggr+join involved in derived table could also be unfolded.

Usually we can encode date as u32, 2 bytes for year, 1 byte for month, 1 byte for day. Truncation codec may improve filter performance, that means we store minimum date on block level, then compact the offsets as u8 or u16 to speed up SIMD.

As draft version of join reorder algorithm is done, the plan module should work with fake cost model and cardinality estimations. To implement the estimator and cost model, the underlying storage and execution layers are required. I decided to build a MVP(Minimal Viable Product) end-to-end data flow first. The initial version will include:

1. A read-only block-based storage.
2. An async executor.
3. A command line tool to execute single query.

SELECT c1 FROM t1
LEFT JOIN t2
ON t1.c1 = t2.c2
WHERE t2.c2 IS NULL

Above SQL uses LeftJoin to achieve the AntiJoin Semantics. We remove the WHERE clause and convert it to AntiJoin.