[meta] Join performance improvements

[mfussenegger]

There are several issues labeled with joins and performance.
This is a meta issue to give a high level view on the topics, problems and opportunities.

Optimizer improvements

General

• Introduce Cost Model for Query Optimization #14146
• DPhyp Join Order Algorithm #14158
• Improve cardinality estimates
• More optimisation rules

Concrete examples

• Bad table swap/join ordering: Poor query performance with numerous (outer) joins #13855

• Consider table stats/cardinality when choosing hash join. A case where hash join leads to bad results: Hash join where right side is empty/has no match: Build phase of left side is run and expensive, see INNER JOIN on empty selection takes really long and/or fails with CurcuitBreaker #11050.

• Transitive closure join optimization: Transitive Closure JOIN Optimization #10208

• max/min values from table functions: Optimise join performance involving generate_series #11417

• Allow hints around the type and order of JOIN operations #13283

• Optimizer rule for pushing down correlated joins beneath outer multi joins #13671

Execution strategies/engine

• Sorted merge join (https://en.wikipedia.org/wiki/Sort-merge_join)

• Group join

  • https://link.springer.com/content/pdf/10.1007/s00778-022-00765-x.pdf
  • http://www.vldb.org/pvldb/vol4/p843-moerkotte.pdf

• Lookup join (Client side joins are significantly faster in some cases #11183)

• Vectorized join execution

  • Everything You Always Wanted to Know About
    Compiled and Vectorized Queries But Were Afraid to Ask
  • DRAFT: Vectorized execution engine #10063

• Hashing strategies, bloom filters, disk-spill-over, temp tables

  • https://kudu.apache.org/2021/01/15/bloom-filter-predicate.html

• Range join optimizations (https://duckdb.org/2022/05/27/iejoin.html)

Unclassified

• Slow execution of a NestedLoopJoin with GenericFunctionQuery #13184
• Poor performance with several joins / unnest #11850
• Slow performance with multiple joins #11851
• Very Slow Performance with multiple LEFT JOINs with high cardinality #14101

Correlated sub-queries

• Improve performance of correlated sub-queries (decorrelation) #13337