Long optimizer runtimes due slow cardinality estimation

[dey4ss]

While working on #2590, we noticed that the optimizer runtimes for TPC-C are quite high and often, predicate reordering takes long (especially for TPC-C and JOB, see below). After some investigation, we found that cardinality estimation is a bottleneck for TPC-C queries.

One problem is that we copy histograms every time we scale or slice them, which could be improved with a histogram that references an original one (like a ReferenceSegment) and adds a selectivity and/or bucket ranges to perform estimations.

Join ordering and chunk pruning are also heavy hitters and guess what, these rules also do a lot of cardinality estimation (join ordering) or statistics pruning/slicing (chunk pruning).

Benchmarks are conducted on 8783047 (after already speeding up predicate reordering a bit).

TPC-C

tpcc_master_breakdown.pdf

tpcc_master_optimizer_breakdown.pdf

TPC-DS

tpcds_master_breakdown.pdf

tpcds_master_optimizer_breakdown.pdf

JOB

job_master_breakdown.pdf

job_master_optimizer_breakdown.pdf

SSB

ssb_master_breakdown.pdf

ssb_master_optimizer_breakdown.pdf

TPC-H SF 10

tpch_master_breakdown.pdf

tpch_master_optimizer_breakdown.pdf

TPC-H SF 0.01

TBD