11.04.2012 19:09, unordained wrote: > a) for every row in A (regardless of order), do a PK lookup in B [which, > ignoring index-caching, or some implementation tweak to remember where > in the > index you "last were" as a best-guess for the next lookup, is wasteful, > as it would restart from the root of the index each time]
This is known as a nested loop join. And "restart from the root" costs just a couple of page reads that are likely to be satisfied using the cache. Not something really wasteful. > b) indexed join, as I was once forced to implement by hand in Cobol, > using two > pre-sorted streams, keeping track of which one is "ahead" and advancing > the one > that is "behind" (I do not at all remember what that's called in theory, > I'm sure it has a nice name.) It depends on what is hidden behind "pre-sorted". There are two options: 1) Streams are read naturally and re-sorted by the join key, this is what's known as sort/merge join in Firebird. The extra sorting cost makes this option more expensive than the nested loop join. Firebird defaults to this option only if there is nothing better available. 2) Streams are read in the index order that allows to avoid an extra sorting. But navigating the whole tables in the index order will cause extremely random I/O (at least for the FK driven table) so it's also going to be expensive. Firebird never chooses such an option at all. > I assume (b) is what you're saying FB3 does for full-outer-joins (yay! > [that > explains why I've sometimes been forced to do unions of left, inner, and > right > joins]), but why wouldn't (b) be a valid strategy for other join types too? It would for left/right joins and perhaps could for full outer joins. Not supported at the moment though. > (That's what I was trying to convince FB to do with a PLAN. I never use > explicit PLANs, is there syntactic magic to it?) It rejects everything it doesn't support. > Still, this doesn't explain why I do see it sometimes using an index to > support a starts-with join, and he doesn't. I can hardly guess without a test case. Dmitry ------------------------------------ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Visit http://www.firebirdsql.org and click the Resources item on the main (top) menu. Try Knowledgebase and FAQ links ! Also search the knowledgebases at http://www.ibphoenix.com ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Yahoo! Groups Links <*> To visit your group on the web, go to: http://groups.yahoo.com/group/firebird-support/ <*> Your email settings: Individual Email | Traditional <*> To change settings online go to: http://groups.yahoo.com/group/firebird-support/join (Yahoo! ID required) <*> To change settings via email: [email protected] [email protected] <*> To unsubscribe from this group, send an email to: [email protected] <*> Your use of Yahoo! Groups is subject to: http://docs.yahoo.com/info/terms/
