9.3 Pre-proposal: Range Merge Join
От | Jeff Davis |
---|---|
Тема | 9.3 Pre-proposal: Range Merge Join |
Дата | |
Msg-id | 1334554850.10878.52.camel@jdavis обсуждение исходный текст |
Ответы |
Re: 9.3 Pre-proposal: Range Merge Join
Re: 9.3 Pre-proposal: Range Merge Join Re: 9.3 Pre-proposal: Range Merge Join Re: 9.3 Pre-proposal: Range Merge Join |
Список | pgsql-hackers |
I hope this is not an inappropriate time for 9.3 discussions. The flip side of asking for submissions in the first couple commitfests means that I need to submit proposals now. What is a Range Join? See attached SQL for example. The key difference is that the join condition is not equality, but overlaps (&&). Problem statement: slow. Nested loops are the only option, although they can benefit from an inner GiST index if available. But if the join is happening up in the plan tree somewhere, then it's impossible for any index to be available. Proposed solution: a modified merge join that can handle ranges. 1. Order the ranges on both sides by the lower bound, then upper bound. Empty ranges can be excluded entirely. 2. Left := first range on left, Right := first range on right 3. If Left or Right is empty, terminate. 4. If lower(Left) > upper(Right), discard Right, goto 2 5. If lower(Right) > upper(Left), discard Left, goto 2 6. return (Left, Right) as joined tuple 7. Right := next range on right 8. goto 3 If we get step 4 or step 5 keeps getting triggered, and a btree index is available (ordered by lower bound), we can re-probe to go to the correct position, and consider that the new top range on that side. This is an optimization for the case where there are large numbers of ranges with no match on the other side. Thanks to Nathan Boley for helping me devise this algorithm. However, any bugs are mine alone ;) Weaknesses: I haven't thought through the optimization, but I suspect it will be hard to be very accurate in the costing. That might be OK, because there aren't very many options anyway, but I'll need to think it through. Questions: * Is this idea sane? -- that is, are ranges important enough that people are willing to maintain a new operator? * The more general problem might be "spatial joins" which can operate in N dimensions, and I doubt this would work very well in that case. Does someone know of a spatial join algorithm (without IP claims) that would be as good as this one for ranges? * Other thoughts? Regards, Jeff Davis
Вложения
В списке pgsql-hackers по дате отправления: