{"issue":{"milestone":null,"title":"[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","created_at":"2011-12-30T02:23:22Z","user":{"login":"dynamobi-build","id":1123017,"url":"https://api.github.com/users/dynamobi-build","avatar_url":"https://secure.gravatar.com/avatar/cb215b3d786be20761071a562a56af64?d=https://a248.e.akamai.net/assets.github.com%2Fimages%2Fgravatars%2Fgravatar-140.png","gravatar_id":"cb215b3d786be20761071a562a56af64"},"updated_at":"2011-12-30T02:23:23Z","labels":[{"name":"LDB","url":"https://api.github.com/repos/dynamobi/dynamobi/labels/LDB","color":"e2b9bd"},{"name":"Optimizer","url":"https://api.github.com/repos/dynamobi/dynamobi/labels/Optimizer","color":"455e65"}],"state":"closed","id":2685424,"closed_at":"2011-12-30T02:23:23Z","pull_request":{"patch_url":null,"html_url":null,"diff_url":null},"html_url":"https://github.com/dynamobi/dynamobi/issues/231","body":"<b><i>[reporter=\"zfong\", created=\"Mon, 1 May 2006 11:57:27 -0500 (GMT-05:00)\"]</i></b>\nCurrently, 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.<br/>\n<br/>\nThe following email from JVS has some background that uncovered this issue:<br/>\n<br/>\nI have this working via translation to a join against VALUES (1,2,3). <br/>\nActually it's a semijoin, but I didn't want to rock the boat by <br/>\nintroducing SemiJoinRel during translation.  So, the translator creates <br/>\nit as a normal JoinRel with a projection on top and distinct on the <br/>\nright, so select * from t where x in (1,2,3) becomes something like<br/>\n<br/>\nwith v(x) as select distinct * from (values(1,2,3))<br/>\nselect t.* from t inner join v on t.x=v.x;<br/>\n<br/>\nI can already get it to use a hash join; I'm wondering if I can get it <br/>\nto use an index semijoin.<br/>\n<br/>\nBroadbase takes a different approach:  it preserves the IN as a <br/>\npredicate and then converts it to a BBRangeSet, yielding a normal index <br/>\nsearch instead of a join (unless it's a subquery rather than a values <br/>\nlist).  This is nice for small IN lists, because it can use stats to get <br/>\na very good selectivity estimate.  However, this requires extra work in <br/>\nrex and sarg, so I want to see if there's a simple way to get it working <br/>\nwith semijoins.  The effort would carry over to IN with uncorrelated <br/>\nsubquery.  And for the enormous IN clauses sometimes generated by <br/>\nMondrian, considering only index search isn't necessarily optimal.<br/>\n<br/>\nCurrently, LoptSemiJoinOptimizer doesn't insert a semijoin for this case <br/>\n(even if I insert 100 distinct values into t and then ANALYZE TABLE). <br/>\nThe reason is that it only estimates the selectivity based on filters <br/>\nfor the dimension table (v), ignoring correlation with the fact table <br/>\n(t).  The Broadbase join-filtering logic we've inherited focuses only on <br/>\nthe case of a star schema with referential integrity between the two <br/>\ntables.  That's wrong for this example, where it's clear that if there <br/>\nare only three rows coming from v, and there are 100 distinct values in <br/>\nt (the fact table), then the join itself is likely to achieve a lot of <br/>\nfiltering (absent skew).  But since there aren't any filters on v, <br/>\nLoptSemiJoinOptimizer thinks there's no selectivity.<br/>\n<br/>\nWe could apply the more general logic from computeRowCountGivenConds to <br/>\nget the right answer, but only if we could first detect that it was safe <br/>\nto drop the referential integrity assumption.  Maybe if we see that the <br/>\nnumber of distinct values on the dimension side is much smaller than the <br/>\nnumber on the fact side (in cases where we have estimates for both)?<br/>\n","number":231,"url":"https://api.github.com/repos/dynamobi/dynamobi/issues/231","comments":0,"assignee":null},"action":"closed"}