Re: SQL Query Question

On Mon, 14 May 2001 15:26:07 GMT,
"Joshua" == JRStern <JRStern_at_gte.net> wrote:

Joshua> On 14 May 2001 10:00:39 +0100, Philip Lijnzaad <lijnzaad_at_ebi.ac.uk> Joshua> wrote:
>> And the join takes O(R+S), R
>> the number of result rows, S the number of the smallest table.

Joshua> That's what I'm not clear on, I think you're doing a cartesian product
Joshua> internally, possibly several in your one-table version, I don't think
Joshua> anybody's optimizer is going to be smart enough to avoid.

You mean because of ``WHERE f2.n > f1.n'' (as opposed to a ``WHERE a.id = b.id'') ? I think you're right and I am wrong; I overlooked this! I think most indexes can still be used with a '>'-operator, so it might not be so bad. I think (but am not sure) that without an index, the theta-join would still be O(log^2(N)) (or at the worst N^2); the cost of explicit enumeration would be proportional to the sum of the sizes of all the gaps. So it depends, as usual :-) Cheers,

                                                                      Philip

-- 
If you have a procedure with 10 parameters, you probably missed some. (Kraulis)
-----------------------------------------------------------------------------
Philip Lijnzaad, lijnzaad_at_ebi.ac.uk \ European Bioinformatics Institute,rm A2-08
+44 (0)1223 49 4639                 / Wellcome Trust Genome Campus, Hinxton
+44 (0)1223 49 4468 (fax)           \ Cambridgeshire CB10 1SD,  GREAT BRITAIN
PGP fingerprint: E1 03 BF 80 94 61 B6 FC  50 3D 1F 64 40 75 FB 53