Dear all, thanks for the feedback! We had a closer look at the previous patches and the CustomScan infrastructure.
Compared to the previous patch, we do not (directly) focus on joins with the overlap (&&) condition in this patch. Instead we consider joins with containment (@>) between a range and an element, and joins with conditions over scalars of the form "right.element BETWEEN left.start AND left.end", and more generally left.start >(=) right.element AND right.element <(=) left.end. We call such conditions range conditions and these conditions can be combined with equality conditions in the Range Merge Join. The Range Merge Join can use (optional) equality conditions and one range condition of the form shown above. In this case the inputs are sorted first by the attributes used for equality and then one input by the range (or start in the case of scalars) and the other input by the element. The Range Merge Join is then a simple extension of the Merge Join that in addition to the (optional) equality attributes also uses the range condition in the merge join states. This is similar to an index-nested loop with scalars for cases when the relation containing the element has an index on the equality attributes followed by the element. The Range Merge Join uses sorting and thus does not require the index for this purpose and performs better. The patch uses the optimizer estimates to evaluate if the Range Merge Join is beneficial as compared to other execution strategies, but when no equality attributes are present, it becomes the only efficient option for the above range conditions. If a join contains multiple range conditions, then based on the estimates the most effective strategy is chosen for the Range Merge Join. Although we do not directly focus on joins with the overlap (&&) condition between two ranges, we show in [1] that these joins can be evaluated using the union (UNION ALL) of two joins with a range condition, where intuitively, one tests that the start of one input falls within the range of the other and vice versa. We evaluated this using regular (B-tree) indices and compare it to joins with the overlap (&&) condition using GiST, SP-GiST and others, and found that it performs better. The Range Merge Join would improve this further and would not require the creation of an index. We did not consider an implementation as a CustomScan, as we feel the join is rather general, can be implemented using a small extension of the existing Merge Join, and would require a substantial duplication of the Merge Join code. Kind regards, Thomas, Anton, Johann, Michael, Peter [1] https://doi.org/10.1007/s00778-021-00692-3 (open access) Am Di., 5. Okt. 2021 um 02:30 Uhr schrieb Jaime Casanova < jcasa...@systemguards.com.ec>: > > On Mon, Oct 04, 2021 at 04:27:54PM -0500, Jaime Casanova wrote: > >> On Thu, Jun 10, 2021 at 07:14:32PM -0700, Jeff Davis wrote: > >> > > >> > I'll start with the reason I set the work down before: it did not work > >> > well with multiple join keys. That might be fine, but I also started > >> > thinking it was specialized enough that I wanted to look into doing it > >> > as an extension using the CustomScan mechanism. > >> > > >> > Do you have any solution to working better with multiple join keys? > And > >> > do you have thoughts on whether it would be a good candidate for the > >> > CustomScan extension mechanism, which would make it easier to > >> > experiment with? > >> > > >> > >> Hi, > >> > >> It seems this has been stalled since jun-2021. I intend mark this as > >> RwF unless someone speaks in the next hour or so. > >> > > Thomas <thomasmannhar...@gmail.com> wrote me: > > > Hi, > > > > I registered this patch for the commitfest in july. It had not been > reviewed and moved to the next CF. I still like to submit it. > > > > Regards, > > Thomas > > > > Just for clarification RwF doesn't imply reject of the patch. > Nevertheless, given that there has been no real review I will mark this > patch as "Waiting on Author" and move it to the next CF. > > Meanwhile, cfbot (aka http://commitfest.cputube.org) says this doesn't > compile. Here is a little patch to fix the compilation errors, after > that it passes all tests in make check-world. > > Also attached a rebased version of your patch with the fixes so we turn > cfbot entry green again > > -- > Jaime Casanova > Director de Servicios Profesionales > SystemGuards - Consultores de PostgreSQL >
postgres.patch
Description: Binary data
