dynamobi/dynamobi — Issue #146: [LDB-176] Non-optimal query plans can be chosen because of limitations in join result estimates when join inputs are filtered
Author: dynamobi-build
Created: 2011-12-30 02:16:55+00:00
State: open
Labels: LDB, Optimizer

[reporter="zfong", created="Fri, 20 Jun 2008 08:41:43 -0500 (GMT-05:00)"]
An example of this is query 8 in TPC-H. In that query, ORDERS can be processed using a chained semijoin with CUSTOMER, NATION, and REGION. For a 1G scale, the filtered size of that join input is ~91K rows. LINEITEM can be processed using a semijoin with PART. The filtered size of that join input is ~43K rows. The input sizes estimated by the optimizer using sampled statistics are ~60K and ~30K, which aren't too bad. Using computed stats doesn't make these estimates much better.

The problem though is that the current code for estimating the result size of a join uses the following formula:

(# rows in left input) * (# rows in right input) / max(# distinct join keys in left, # distinct join keys in right)

(See LoptMetadataProvider.computeRowCountGivenConds to see the actual code.)

The estimate of the # of distinct join keys in both inputs is the same as the number of rows, (which matches with reality). So, the estimated size ends up being 30K. However, the actual join result size is only 2603. In other words, the overlapping join keys between the two join inputs does not match up with the formula currently being used, which assumes that the join keys in one input are a subset of those in the other.

To address this, we need a much more sophisticated formula that looks at the actual range of key values each join input encompasses and then examines which ranges overlap between the two inputs.