What problem does this PR solve?

Re-implement partition pruning for better performance.

The old partition pruning's implementation uses an algorithm we called constraint propagate which is powerful, yet slow.

It works like this:

For each partition:
    construct EXPR =  (partition's expression AND query's expression)
    if FixPoint(constraint propagate EXPR) == AlwaysFalse
            Prune

It's powerful as it can propagate something like a > b and b > 3 => a > 3 and it also include some propagate rules for functions x > const1, f(x) < const2, f is monotonous => false.

It's possible to handle some cases like:

create table t (a int, b int) partition by (a) ...
select * from t where a > b and b > 3;

But the process is slow because constructing new expressions involve too many object allocation, and the constraint propagation process is also heavy. If there are many partitions, 2048 for example, the whole time spent on partition pruning would be significant.

What is changed and how it works?

The new partition pruning algorithm is much faster by using binary search and avoid constructing expressions.

The query expression would be abstract to f(col) op const, where op is one of > < = >= <=, in the code it's represent as dataForPrune.

The 'partition p0 less than xxx, partition p1 less than xxx, ...' forms an array [p0 p1 p2 ... maxvalue], represented as the lessThanData.

The new algorithm uses a binary search pruneUseBinarySearch to locate const in the array.

A simple benchmark,
Before:

session git:(partition-prune) ✗ go test -test.bench BenchmarkPartitionPruning -test.run Ignore
BenchmarkPartitionPruning-4   	       8	 128010294 ns/op

After:

session git:(partition-prune) ✗ go test -test.bench BenchmarkPartitionPruning -test.run Ignore
BenchmarkPartitionPruning-4   	      21	  57979203 ns/op

Some side notes:

1. As null values are all located in the first partition, the first partition expression in the old implementation is val < xxx or val is null. The or val is null condition is hard to eliminate so we can't prune the first partition in many cases.
   The new implementation doesn't consider the null value, so the first partition is pruned.

2. There is a relax operation during the pruning, and it may lead to less accurate pruning results.
   For example,

create table t (a datetime) partition by to_days(a) ...

This condition doesn't always hold:

a < const => to_days(a) < to_days(const)

A counterexample is:

2020-02-12 10:08:00 < 2020-02-12 23:59:59 => to_days(2020-02-12 10:08:00) = to_days(2020-02-12 23:59:59)

So we have to relax < to <= to handle functions.

a < const => to_days(a) <= to_days(const)

Check List

Tests

• Unit test

Related changes

• Need to cherry-pick to the release branch

Release note

• Write release note for bug-fix or new feature.