# Re: Functions and Relations

Date: 22 Nov 2006 07:40:44 -0800

Message-ID: <1164210044.346676.98020_at_m73g2000cwd.googlegroups.com>

On Nov 21, 5:39 pm, "Aloha Kakuikanu" <aloha.kakuik..._at_yahoo.com>
wrote:

*> select x,y from T
*

> where x=1 and y=x+1

*>
**> is
**>
**> `x=1` /\ `y=x+1` /\ T
**>
**> Therefore we have 6 join orders to evaluate:
**> 1. `y=x+1` -> T -> `x=1`
**> that is:scan the `y=x+1` relation, then ... Stop right there. Scanning
**> the whole `y=x+1` takes the infinite cost.
**> 2. `y=x+1` -> `x=1` -> T
**> scan the `y=x+1` relation, then ... Same reason.
**> 3. T -> `x=1` -> `y=x+1`
**> scan the T relation, then find matching tuples from `x=1`, then join
**> with `y=x+1`. Mediocre cost.
**> 4. T -> `y=x+1` -> `x=1`
**> scan the T relation, then find matching tuples from `y=x+1`, then join
**> with `x=1`. Similar to the previous case.
**> 5. `x=1` -> `y=x+1` -> T
**> scan the `x=1` relation, then do indexed nested loops join with T, then
**> find matching tuples from `y=x+1`. Not bad.
**> 6. `x=1` -> `y=x+1` -> T
**> scan the `x=1` relation, then find matching tuples from `y=x+1`, then
**> do indexed nested loops join with T. The winner.
*

Awesome!

(5 has a typo, yes? Should be `x=1` -> T -> `y=x+1`)

I don't know much about query optimization, but it's quite interesting to see this laid out this way. I note that in 6, the second loop (y=x+1) is only cardinality 1 because the first loop bound x. Otherwise it would be infinite. Does this ordinarily arise in query optimization, or is it specific to this manner of analysis?

Marshall Received on Wed Nov 22 2006 - 16:40:44 CET