Example

The optimizer picks an inferior plan for TPC-E q05 (15x slower than optimal plan); it's because of incorrect estimates for join selectivities. We currently compute 1/NDV(join key) on only one side: whichever collection is smaller, making the assumption that the smaller collection is the PK side. This is an example where that heuristic fails, because TPC-E has referencing tables which are smaller than the lookup tables. For this query specifically, the main mistake happens for the ex_ad_id = ad_id edge. Exchange has 4 records and Address is the PK side with 7504 records. We estimate a selectivity of 1/4 instead of 1/7504 which is 1876x too high.

Solution

Update equality-join selectivity to use both inputs: 1.0 / max(ndv_left, ndv_right). This fixes overestimation when the larger input has the higher NDV. We didn't do this initially because the extra NDV calculations would be too expensive, but we should implement this now that we have HLL for NDV.