Re: Functions and Relations

From: Aloha Kakuikanu <>
Date: 22 Nov 2006 10:58:28 -0800
Message-ID: <>

vc wrote:
> Representing predicates as relations for optimization purposes is an
> interesting idea that was explored by Chaudhuri in 1989 in the LDL
> project. He mentions the method drawbacks in his later article
> "Optimization of queries with user defined predicates". You may be
> interested in reading it.

The combinatorial explosion of the search space is obvious. This is something optimization folks grudgingly accepted as unavoidable in their area. Cost based subquery unnesting, for example, increases the chances of getting better plan at the cost of exloring much larger search space. The tradeoff between having better plan quality vs. doing more optimization job is unavoidable.

IMO, it is better to have a simpler optimization framework. Then, it is easier to troubleshoot a problem of optimizer not finding a good plan due to some heuristic which limits search space, rather that to debug a query within monster optimiser codebase that has one ad-hock solution on the top of the other.

Next, there goes the problem of linear join order. Consider

`x=1` /\ R1(x,z) /\ `y=1` /\ R2(y,z)

LDL critics suggested that the best execution strategy is the bushy plan

[`x=1` /\ R1(x,z)] /\ [`y=1` /\ R2(y,z)]

Is this bushy plan such a good idea? First, the general objection to bushy plans applies here as well -- bushy plans are not pipelined. (This is yet another reason why I don't like HJ, which is a blocking operator). Second, R2 is assumed to be big, so we'd better have an index on R2(y). Then, I suggest to extend it to a composite index R2(y,z)!

The linear execution plan

{[`x=1` /\ R1(x,z)] /\ `y=1`} /\ R2(y,z)

with last join performed as an indexed NL would be the first challenger of the bushy plan above. The symmetric case

{[`y=1` /\ R2(y,z)] /\ `x=1`} /\ R1(x,z)

is one more contender. I suggest that all three plans have comparable performance. Received on Wed Nov 22 2006 - 19:58:28 CET

Original text of this message