dynamobi/dynamobi — Issue #231: [LDB-90] Semijoin selectivity does not take into account case where the cardinality of the fact table is different from the cardinality of the dimension table
Author: dynamobi-build
Created: 2011-12-30 02:23:22+00:00
State: open
Labels: LDB, Optimizer

[reporter="zfong", created="Mon, 1 May 2006 11:57:27 -0500 (GMT-05:00)"]
Currently, computeRowCountGivenConds() takes into account the fact and dimension tables having different cardinalities on the join keys and computes the row count accordingly. computeSemiJoinSelectivity(), however, only takes into consideration the characteristics of the dimension table, assuming the cardinalities of the fact and dimension tables on the join keys are the same. There are cases where this is not true. So, there is inconsistency between computeRowCountGivenConds() and computeSemiJoinSelectivity(). Some of the logic in the former should be moved to the latter.

The following email from JVS has some background that uncovered this issue:

I have this working via translation to a join against VALUES (1,2,3).

Actually it's a semijoin, but I didn't want to rock the boat by

introducing SemiJoinRel during translation. So, the translator creates

it as a normal JoinRel with a projection on top and distinct on the

right, so select * from t where x in (1,2,3) becomes something like

with v(x) as select distinct * from (values(1,2,3))

select t.* from t inner join v on t.x=v.x;

I can already get it to use a hash join; I'm wondering if I can get it

to use an index semijoin.

Broadbase takes a different approach: it preserves the IN as a

predicate and then converts it to a BBRangeSet, yielding a normal index

search instead of a join (unless it's a subquery rather than a values

list). This is nice for small IN lists, because it can use stats to get

a very good selectivity estimate. However, this requires extra work in

rex and sarg, so I want to see if there's a simple way to get it working

with semijoins. The effort would carry over to IN with uncorrelated

subquery. And for the enormous IN clauses sometimes generated by

Mondrian, considering only index search isn't necessarily optimal.

Currently, LoptSemiJoinOptimizer doesn't insert a semijoin for this case

(even if I insert 100 distinct values into t and then ANALYZE TABLE).

The reason is that it only estimates the selectivity based on filters

for the dimension table (v), ignoring correlation with the fact table

(t). The Broadbase join-filtering logic we've inherited focuses only on

the case of a star schema with referential integrity between the two

tables. That's wrong for this example, where it's clear that if there

are only three rows coming from v, and there are 100 distinct values in

t (the fact table), then the join itself is likely to achieve a lot of

filtering (absent skew). But since there aren't any filters on v,

LoptSemiJoinOptimizer thinks there's no selectivity.

We could apply the more general logic from computeRowCountGivenConds to

get the right answer, but only if we could first detect that it was safe

to drop the referential integrity assumption. Maybe if we see that the

number of distinct values on the dimension side is much smaller than the

number on the fact side (in cases where we have estimates for both)?