> 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
diff --git a/src/backend/executor/nodeMergejoin.c b/src/backend/executor/nodeMergejoin.c index 2dccba24b3..d18b4a4605 100644 --- a/src/backend/executor/nodeMergejoin.c +++ b/src/backend/executor/nodeMergejoin.c @@ -294,7 +294,7 @@ MJCreateRangeData(List *rangeclause, { RangeData data; - Assert(list_legth(node->rangeclause) < 3); + Assert(list_length(rangeclause) < 3); data = (RangeData) palloc0(sizeof(RangeJoinData)); diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c index 8a2778485c..24ee41b9ed 100644 --- a/src/backend/optimizer/path/costsize.c +++ b/src/backend/optimizer/path/costsize.c @@ -3440,8 +3440,8 @@ final_cost_mergejoin(PlannerInfo *root, MergePath *path, /* Protect some assumptions below that rowcounts aren't zero */ - if (inner_path_rows <= 0) - inner_path_rows = 1; + if (inner_path_rows <= 0) + inner_path_rows = 1; /* Mark the path with the correct row estimate */ if (path->jpath.path.param_info)
diff --git a/src/backend/commands/explain.c b/src/backend/commands/explain.c index 10644dfac4..9b7503630c 100644 --- a/src/backend/commands/explain.c +++ b/src/backend/commands/explain.c @@ -1206,8 +1206,16 @@ ExplainNode(PlanState *planstate, List *ancestors, pname = sname = "Nested Loop"; break; case T_MergeJoin: - pname = "Merge"; /* "Join" gets added by jointype switch */ - sname = "Merge Join"; + if(((MergeJoin *) plan)->rangeclause) + { + pname = "Range Merge"; /* "Join" gets added by jointype switch */ + sname = "Range Merge Join"; + } + else + { + pname = "Merge"; /* "Join" gets added by jointype switch */ + sname = "Merge Join"; + } break; case T_HashJoin: pname = "Hash"; /* "Join" gets added by jointype switch */ @@ -1948,6 +1956,8 @@ ExplainNode(PlanState *planstate, List *ancestors, case T_MergeJoin: show_upper_qual(((MergeJoin *) plan)->mergeclauses, "Merge Cond", planstate, ancestors, es); + show_upper_qual(((MergeJoin *) plan)->rangeclause, + "Range Cond", planstate, ancestors, es); show_upper_qual(((MergeJoin *) plan)->join.joinqual, "Join Filter", planstate, ancestors, es); if (((MergeJoin *) plan)->join.joinqual) diff --git a/src/backend/executor/nodeMergejoin.c b/src/backend/executor/nodeMergejoin.c index b41454ab6d..d18b4a4605 100644 --- a/src/backend/executor/nodeMergejoin.c +++ b/src/backend/executor/nodeMergejoin.c @@ -93,11 +93,15 @@ #include "postgres.h" #include "access/nbtree.h" +#include "catalog/pg_operator.h" #include "executor/execdebug.h" #include "executor/nodeMergejoin.h" #include "miscadmin.h" +#include "nodes/nodeFuncs.h" +#include "utils/rangetypes.h" #include "utils/lsyscache.h" #include "utils/memutils.h" +#include "utils/typcache.h" /* @@ -140,6 +144,18 @@ typedef struct MergeJoinClauseData SortSupportData ssup; } MergeJoinClauseData; +/* + * Runtime data for the range clause + */ +typedef struct RangeJoinData +{ + ExprState *startClause; + ExprState *endClause; + ExprState *rangeExpr; + ExprState *elemExpr; + +} RangeJoinData; + /* Result type for MJEvalOuterValues and MJEvalInnerValues */ typedef enum { @@ -269,6 +285,57 @@ MJExamineQuals(List *mergeclauses, return clauses; } +/* + * MJCreateRangeData + */ +static RangeData +MJCreateRangeData(List *rangeclause, + PlanState *parent) +{ + RangeData data; + + Assert(list_length(rangeclause) < 3); + + data = (RangeData) palloc0(sizeof(RangeJoinData)); + + data->startClause = NULL; + data->endClause = NULL; + data->rangeExpr = NULL; + data->elemExpr = NULL; + + if(list_length(rangeclause) == 2) + { + data->startClause = ExecInitExpr(linitial(rangeclause), parent); + data->endClause = ExecInitExpr(lsecond(rangeclause), parent); + } + else + { + OpExpr *qual = (OpExpr *) linitial(rangeclause); + ExprState *lexpr; + ExprState *rexpr; + + /* + * Prepare the input expressions for execution. + */ + lexpr = ExecInitExpr((Expr *) get_leftop(qual), parent); + rexpr = ExecInitExpr((Expr *) get_rightop(qual), parent); + + if(qual->opno == OID_RANGE_CONTAINS_ELEM_OP) + { + data->rangeExpr = lexpr; + data->elemExpr = rexpr; + } + else + { + Assert(qual->opno == OID_RANGE_ELEM_CONTAINED_OP); + data->rangeExpr = rexpr; + data->elemExpr = lexpr; + } + } + + return data; +} + /* * MJEvalOuterValues * @@ -445,6 +512,73 @@ MJCompare(MergeJoinState *mergestate) } +/* + * MJCompareRange + * + * Compare the rangejoinable values of the current two input tuples + * and return 0 if they are equal (ie, the outer interval contains the inner), + * >0 if outer > inner, <0 if outer < inner. + */ +static int +MJCompareRange(MergeJoinState *mergestate) +{ + int result = 0; + bool isNull; + MemoryContext oldContext; + RangeData rangeData = mergestate->mj_RangeData; + ExprContext *econtext = mergestate->js.ps.ps_ExprContext; + ExprState *endClause = rangeData->endClause, + *startClause = rangeData->startClause, + *rangeExpr = rangeData->rangeExpr, + *elemExpr = rangeData->elemExpr; + + /* + * Call the comparison functions in short-lived context, in case they leak + * memory. + */ + ResetExprContext(econtext); + + oldContext = MemoryContextSwitchTo(econtext->ecxt_per_tuple_memory); + + econtext->ecxt_outertuple = mergestate->mj_OuterTupleSlot; + econtext->ecxt_innertuple = mergestate->mj_InnerTupleSlot; + + if (endClause != NULL) + { + Assert(startClause != NULL); + + if (!ExecEvalExprSwitchContext(endClause, econtext, &isNull)) + result = -1; + else if (!ExecEvalExprSwitchContext(startClause, econtext, &isNull)) + result = 1; + } + else + { + Datum rangeDatum, + elemDatum; + Oid rangeType; + TypeCacheEntry *typecache; + + Assert(rangeExpr != NULL && elemExpr != NULL); + + rangeDatum = ExecEvalExprSwitchContext(rangeExpr, econtext, &isNull); + elemDatum = ExecEvalExprSwitchContext(elemExpr, econtext, &isNull); + + rangeType = exprType((Node *) rangeExpr->expr); + typecache = lookup_type_cache(rangeType, TYPECACHE_RANGE_INFO); + + if (elem_after_range_internal(typecache, elemDatum, DatumGetRangeTypeP(rangeDatum))) + result = -1; + else if (elem_before_range_internal(typecache, elemDatum, DatumGetRangeTypeP(rangeDatum))) + result = 1; + } + + MemoryContextSwitchTo(oldContext); + + return result; +} + + /* * Generate a fake join tuple with nulls for the inner tuple, * and return it if it passes the non-join quals. @@ -604,6 +738,7 @@ ExecMergeJoin(PlanState *pstate) ExprState *otherqual; bool qualResult; int compareResult; + int compareRangeResult; PlanState *innerPlan; TupleTableSlot *innerTupleSlot; PlanState *outerPlan; @@ -611,6 +746,7 @@ ExecMergeJoin(PlanState *pstate) ExprContext *econtext; bool doFillOuter; bool doFillInner; + bool isRangeJoin; CHECK_FOR_INTERRUPTS(); @@ -624,6 +760,7 @@ ExecMergeJoin(PlanState *pstate) otherqual = node->js.ps.qual; doFillOuter = node->mj_FillOuter; doFillInner = node->mj_FillInner; + isRangeJoin = node->mj_RangeJoin; /* * Reset per-tuple memory context to free any expression evaluation @@ -891,8 +1028,23 @@ ExecMergeJoin(PlanState *pstate) compareResult = MJCompare(node); MJ_DEBUG_COMPARE(compareResult); - if (compareResult == 0) - node->mj_JoinState = EXEC_MJ_JOINTUPLES; + if(compareResult == 0) + { + if(isRangeJoin) + { + compareRangeResult = MJCompareRange(node); + + if (compareRangeResult == 0) + node->mj_JoinState = EXEC_MJ_JOINTUPLES; + else + { + Assert(compareRangeResult < 0); + node->mj_JoinState = EXEC_MJ_NEXTOUTER; + } + } + else + node->mj_JoinState = EXEC_MJ_JOINTUPLES; + } else { Assert(compareResult < 0); @@ -1085,7 +1237,19 @@ ExecMergeJoin(PlanState *pstate) /* we need not do MJEvalInnerValues again */ } - node->mj_JoinState = EXEC_MJ_JOINTUPLES; + if(isRangeJoin) + { + compareRangeResult = MJCompareRange(node); + + if(compareRangeResult == 0) + node->mj_JoinState = EXEC_MJ_JOINTUPLES; + else if(compareRangeResult < 0) + node->mj_JoinState = EXEC_MJ_SKIPOUTER_ADVANCE; + else /* compareRangeResult > 0 */ + node->mj_JoinState = EXEC_MJ_SKIPINNER_ADVANCE; + } + else + node->mj_JoinState = EXEC_MJ_JOINTUPLES; } else { @@ -1184,12 +1348,28 @@ ExecMergeJoin(PlanState *pstate) if (compareResult == 0) { - if (!node->mj_SkipMarkRestore) - ExecMarkPos(innerPlan); - - MarkInnerTuple(node->mj_InnerTupleSlot, node); - - node->mj_JoinState = EXEC_MJ_JOINTUPLES; + if(isRangeJoin) + { + compareRangeResult = MJCompareRange(node); + if(compareRangeResult == 0) + { + if (!node->mj_SkipMarkRestore) + ExecMarkPos(innerPlan); + MarkInnerTuple(node->mj_InnerTupleSlot, node); + node->mj_JoinState = EXEC_MJ_JOINTUPLES; + } + else if(compareRangeResult < 0) + node->mj_JoinState = EXEC_MJ_SKIPOUTER_ADVANCE; + else /* compareRangeResult > 0 */ + node->mj_JoinState = EXEC_MJ_SKIPINNER_ADVANCE; + } + else + { + if (!node->mj_SkipMarkRestore) + ExecMarkPos(innerPlan); + MarkInnerTuple(node->mj_InnerTupleSlot, node); + node->mj_JoinState = EXEC_MJ_JOINTUPLES; + } } else if (compareResult < 0) node->mj_JoinState = EXEC_MJ_SKIPOUTER_ADVANCE; @@ -1532,6 +1712,17 @@ ExecInitMergeJoin(MergeJoin *node, EState *estate, int eflags) ExecInitQual(node->join.joinqual, (PlanState *) mergestate); /* mergeclauses are handled below */ + /* + * initialize range join + */ + if(node->rangeclause) + { + mergestate->mj_RangeData = MJCreateRangeData(node->rangeclause, (PlanState *) mergestate); + mergestate->mj_RangeJoin = true; + } + else + mergestate->mj_RangeJoin = false; + /* * detect whether we need only consider the first matching inner tuple */ diff --git a/src/backend/nodes/copyfuncs.c b/src/backend/nodes/copyfuncs.c index 228387eaee..bc76c69bda 100644 --- a/src/backend/nodes/copyfuncs.c +++ b/src/backend/nodes/copyfuncs.c @@ -2349,6 +2349,8 @@ _copyRestrictInfo(const RestrictInfo *from) COPY_SCALAR_FIELD(norm_selec); COPY_SCALAR_FIELD(outer_selec); COPY_NODE_FIELD(mergeopfamilies); + COPY_NODE_FIELD(rangeleftopfamilies); + COPY_NODE_FIELD(rangerightopfamilies); /* EquivalenceClasses are never copied, so shallow-copy the pointers */ COPY_SCALAR_FIELD(left_ec); COPY_SCALAR_FIELD(right_ec); diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c index 2e5ed77e18..6b478b31d6 100644 --- a/src/backend/nodes/outfuncs.c +++ b/src/backend/nodes/outfuncs.c @@ -765,6 +765,7 @@ _outMergeJoin(StringInfo str, const MergeJoin *node) WRITE_BOOL_FIELD(skip_mark_restore); WRITE_NODE_FIELD(mergeclauses); + WRITE_NODE_FIELD(rangeclause); numCols = list_length(node->mergeclauses); @@ -2243,6 +2244,7 @@ _outMergePath(StringInfo str, const MergePath *node) _outJoinPathInfo(str, (const JoinPath *) node); WRITE_NODE_FIELD(path_mergeclauses); + WRITE_NODE_FIELD(path_rangeclause); WRITE_NODE_FIELD(outersortkeys); WRITE_NODE_FIELD(innersortkeys); WRITE_BOOL_FIELD(skip_mark_restore); @@ -2559,6 +2561,8 @@ _outRestrictInfo(StringInfo str, const RestrictInfo *node) WRITE_FLOAT_FIELD(norm_selec, "%.4f"); WRITE_FLOAT_FIELD(outer_selec, "%.4f"); WRITE_NODE_FIELD(mergeopfamilies); + WRITE_NODE_FIELD(rangeleftopfamilies); + WRITE_NODE_FIELD(rangerightopfamilies); /* don't write left_ec, leads to infinite recursion in plan tree dump */ /* don't write right_ec, leads to infinite recursion in plan tree dump */ WRITE_NODE_FIELD(left_em); diff --git a/src/backend/nodes/readfuncs.c b/src/backend/nodes/readfuncs.c index abf08b7a2f..1e71f26eb7 100644 --- a/src/backend/nodes/readfuncs.c +++ b/src/backend/nodes/readfuncs.c @@ -2173,6 +2173,7 @@ _readMergeJoin(void) READ_BOOL_FIELD(skip_mark_restore); READ_NODE_FIELD(mergeclauses); + READ_NODE_FIELD(rangeclause); numCols = list_length(local_node->mergeclauses); diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c index 1e4d404f02..3a97b9951b 100644 --- a/src/backend/optimizer/path/costsize.c +++ b/src/backend/optimizer/path/costsize.c @@ -3419,6 +3419,7 @@ final_cost_mergejoin(PlannerInfo *root, MergePath *path, double inner_path_rows = inner_path->rows; List *mergeclauses = path->path_mergeclauses; List *innersortkeys = path->innersortkeys; + List *allclauses; Cost startup_cost = workspace->startup_cost; Cost run_cost = workspace->run_cost; Cost inner_run_cost = workspace->inner_run_cost; @@ -3435,7 +3436,10 @@ final_cost_mergejoin(PlannerInfo *root, MergePath *path, rescannedtuples; double rescanratio; - /* Protect some assumptions below that rowcounts aren't zero */ + allclauses = list_concat(list_copy(mergeclauses), path->path_rangeclause); + + + /* Protect some assumptions below that rowcounts aren't zero */ if (inner_path_rows <= 0) inner_path_rows = 1; @@ -3466,7 +3470,7 @@ final_cost_mergejoin(PlannerInfo *root, MergePath *path, * Compute cost of the mergequals and qpquals (other restriction clauses) * separately. */ - cost_qual_eval(&merge_qual_cost, mergeclauses, root); + cost_qual_eval(&merge_qual_cost, allclauses, root); cost_qual_eval(&qp_qual_cost, path->jpath.joinrestrictinfo, root); qp_qual_cost.startup -= merge_qual_cost.startup; qp_qual_cost.per_tuple -= merge_qual_cost.per_tuple; @@ -3490,7 +3494,7 @@ final_cost_mergejoin(PlannerInfo *root, MergePath *path, * Get approx # tuples passing the mergequals. We use approx_tuple_count * here because we need an estimate done with JOIN_INNER semantics. */ - mergejointuples = approx_tuple_count(root, &path->jpath, mergeclauses); + mergejointuples = approx_tuple_count(root, &path->jpath, allclauses); /* * When there are equal merge keys in the outer relation, the mergejoin diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c index 6407ede12a..19c697402f 100644 --- a/src/backend/optimizer/path/joinpath.c +++ b/src/backend/optimizer/path/joinpath.c @@ -16,6 +16,7 @@ #include <math.h> +#include "catalog/pg_operator.h" #include "executor/executor.h" #include "foreign/fdwapi.h" #include "nodes/nodeFuncs.h" @@ -24,6 +25,7 @@ #include "optimizer/pathnode.h" #include "optimizer/paths.h" #include "optimizer/planmain.h" +#include "utils/lsyscache.h" #include "utils/typcache.h" /* Hook for plugins to get control in add_paths_to_joinrel() */ @@ -84,6 +86,9 @@ static List *select_mergejoin_clauses(PlannerInfo *root, List *restrictlist, JoinType jointype, bool *mergejoin_allowed); +static List *select_rangejoin_clauses(RelOptInfo *outerrel, + RelOptInfo *innerrel, + List *restrictlist); static void generate_mergejoin_paths(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *innerrel, @@ -147,6 +152,7 @@ add_paths_to_joinrel(PlannerInfo *root, extra.restrictlist = restrictlist; extra.mergeclause_list = NIL; + extra.rangeclause_list = NIL; extra.sjinfo = sjinfo; extra.param_source_rels = NULL; @@ -207,6 +213,7 @@ add_paths_to_joinrel(PlannerInfo *root, * it's a full join. */ if (enable_mergejoin || jointype == JOIN_FULL) + { extra.mergeclause_list = select_mergejoin_clauses(root, joinrel, outerrel, @@ -215,6 +222,12 @@ add_paths_to_joinrel(PlannerInfo *root, jointype, &mergejoin_allowed); + if (jointype == JOIN_INNER || jointype == JOIN_LEFT) + extra.rangeclause_list = select_rangejoin_clauses(outerrel, + innerrel, + restrictlist); + } + /* * If it's SEMI, ANTI, or inner_unique join, compute correction factors * for cost estimation. These will be the same for all paths. @@ -777,6 +790,7 @@ try_mergejoin_path(PlannerInfo *root, Path *inner_path, List *pathkeys, List *mergeclauses, + List *rangeclause, List *outersortkeys, List *innersortkeys, JoinType jointype, @@ -850,6 +864,7 @@ try_mergejoin_path(PlannerInfo *root, pathkeys, required_outer, mergeclauses, + rangeclause, outersortkeys, innersortkeys)); } @@ -926,6 +941,7 @@ try_partial_mergejoin_path(PlannerInfo *root, pathkeys, NULL, mergeclauses, + NIL, outersortkeys, innersortkeys)); } @@ -1107,7 +1123,8 @@ sort_inner_and_outer(PlannerInfo *root, Path *inner_path; Path *cheapest_partial_outer = NULL; Path *cheapest_safe_inner = NULL; - List *all_pathkeys; + List *merge_pathkeys; + List *range_pathkeys; ListCell *l; /* @@ -1207,25 +1224,80 @@ sort_inner_and_outer(PlannerInfo *root, * some heuristics behind it (see that function), so be sure to try it * exactly as-is as well as making variants. */ - all_pathkeys = select_outer_pathkeys_for_merge(root, - extra->mergeclause_list, - joinrel); - foreach(l, all_pathkeys) + range_pathkeys = select_outer_pathkeys_for_range(root, + extra->rangeclause_list); + + merge_pathkeys = select_outer_pathkeys_for_merge(root, + extra->mergeclause_list, + joinrel); + + if(merge_pathkeys == NIL && enable_mergejoin) + { + foreach(l, range_pathkeys) + { + PathKey *range_pathkey = (PathKey *) lfirst(l); + List *outerkeys = list_make1(range_pathkey); + List *innerkeys = NIL; + List *rangeclauses; + ListCell *lc; + + rangeclauses = find_rangeclauses_for_outer_pathkeys(root, + outerkeys, + NIL, + extra->rangeclause_list); + + foreach(lc, rangeclauses) + { + List *rangeclause = (List *) lfirst(lc); + PathKey *range_inner_pathkey = + make_inner_pathkey_for_range(root, + rangeclause); + + innerkeys = lappend(innerkeys, range_inner_pathkey); + + merge_pathkeys = build_join_pathkeys(root, joinrel, jointype, + outerkeys); + + /* + * And now we can make the path. + * + * Note: it's possible that the cheapest paths will already be sorted + * properly. try_mergejoin_path will detect that case and suppress an + * explicit sort step, so we needn't do so here. + */ + try_mergejoin_path(root, + joinrel, + outer_path, + inner_path, + merge_pathkeys, + NIL, + rangeclause, + outerkeys, + innerkeys, + jointype, + extra, + false); + } + } + } + + + foreach(l, merge_pathkeys) { List *front_pathkey = (List *) lfirst(l); List *cur_mergeclauses; List *outerkeys; List *innerkeys; - List *merge_pathkeys; + List *mergejoin_pathkeys; /* Make a pathkey list with this guy first */ - if (l != list_head(all_pathkeys)) + if (l != list_head(merge_pathkeys)) outerkeys = lcons(front_pathkey, - list_delete_nth_cell(list_copy(all_pathkeys), - foreach_current_index(l))); + list_delete_ptr(list_copy(merge_pathkeys), + front_pathkey)); else - outerkeys = all_pathkeys; /* no work at first one... */ + outerkeys = merge_pathkeys; /* no work at first one... */ /* Sort the mergeclauses into the corresponding ordering */ cur_mergeclauses = @@ -1242,7 +1314,7 @@ sort_inner_and_outer(PlannerInfo *root, outerkeys); /* Build pathkeys representing output sort order */ - merge_pathkeys = build_join_pathkeys(root, joinrel, jointype, + mergejoin_pathkeys = build_join_pathkeys(root, joinrel, jointype, outerkeys); /* @@ -1256,8 +1328,9 @@ sort_inner_and_outer(PlannerInfo *root, joinrel, outer_path, inner_path, - merge_pathkeys, + mergejoin_pathkeys, cur_mergeclauses, + NIL, outerkeys, innerkeys, jointype, @@ -1273,12 +1346,88 @@ sort_inner_and_outer(PlannerInfo *root, joinrel, cheapest_partial_outer, cheapest_safe_inner, - merge_pathkeys, + mergejoin_pathkeys, cur_mergeclauses, outerkeys, innerkeys, jointype, extra); + + foreach(l, range_pathkeys) + { + PathKey *range_outer_pathkey = (PathKey *) lfirst(l); + List *range_outerkeys = list_copy(outerkeys); + List *range_innerkeys; + List *rangeclauses; + ListCell *lc; + + if(list_member_ptr(range_outerkeys, range_outer_pathkey)) + { + if(!equal(llast(range_outerkeys), range_outer_pathkey)) + continue; + } + else + range_outerkeys = lappend(range_outerkeys, range_outer_pathkey); + + /* Sort the mergeclauses into the corresponding ordering */ + cur_mergeclauses = + find_mergeclauses_for_outer_pathkeys(root, + range_outerkeys, + extra->mergeclause_list); + + /* Should have used them all... */ + Assert(list_length(cur_mergeclauses) == list_length(extra->mergeclause_list)); + + /* Build sort pathkeys for the inner side */ + range_innerkeys = make_inner_pathkeys_for_merge(root, + cur_mergeclauses, + range_outerkeys); + + rangeclauses = find_rangeclauses_for_outer_pathkeys(root, + range_outerkeys, + cur_mergeclauses, + extra->rangeclause_list); + + foreach(lc, rangeclauses) + { + List *cur_rangeclause = (List *) lfirst(lc); + PathKey *range_inner_pathkey; + + range_inner_pathkey = make_inner_pathkey_for_range(root, cur_rangeclause); + + if(list_member_ptr(range_innerkeys, range_inner_pathkey)) + { + if(!equal(llast(range_innerkeys), range_inner_pathkey)) + continue; + } + else + range_innerkeys = lappend(range_innerkeys, range_inner_pathkey); + + + mergejoin_pathkeys = build_join_pathkeys(root, joinrel, jointype, + range_outerkeys); + + /* + * And now we can make the path. + * + * Note: it's possible that the cheapest paths will already be sorted + * properly. try_mergejoin_path will detect that case and suppress an + * explicit sort step, so we needn't do so here. + */ + try_mergejoin_path(root, + joinrel, + outer_path, + inner_path, + mergejoin_pathkeys, + cur_mergeclauses, + cur_rangeclause, + range_outerkeys, + range_innerkeys, + jointype, + extra, + false); + } + } } } @@ -1364,6 +1513,7 @@ generate_mergejoin_paths(PlannerInfo *root, merge_pathkeys, mergeclauses, NIL, + NIL, innersortkeys, jointype, extra, @@ -1462,6 +1612,7 @@ generate_mergejoin_paths(PlannerInfo *root, newclauses, NIL, NIL, + NIL, jointype, extra, is_partial); @@ -1506,6 +1657,7 @@ generate_mergejoin_paths(PlannerInfo *root, newclauses, NIL, NIL, + NIL, jointype, extra, is_partial); @@ -2272,3 +2424,138 @@ select_mergejoin_clauses(PlannerInfo *root, return result_list; } + +/* + * range_clause_order + */ +static int +range_clause_order(RestrictInfo *first, + RestrictInfo *second) +{ + /* + * Extract details from first restrictinfo + */ + Node *first_left = get_leftop(first->clause), + *first_right = get_rightop(first->clause); + bool first_outer_is_left = first->outer_is_left; + int first_strategy = get_op_opfamily_strategy(((OpExpr *) first->clause)->opno, + (linitial_oid(first->rangeleftopfamilies))); + bool first_less = (first_strategy == BTLessStrategyNumber || + first_strategy == BTLessEqualStrategyNumber); + + /* + * Extract details from second restrictinfo + */ + Node *second_left = get_leftop(second->clause), + *second_right = get_rightop(second->clause); + bool second_outer_is_left = second->outer_is_left; + int second_strategy = get_op_opfamily_strategy(((OpExpr *) second->clause)->opno, + (linitial_oid(second->rangeleftopfamilies))); + bool second_less = (second_strategy == BTLessStrategyNumber || + second_strategy == BTLessEqualStrategyNumber); + + /* + * Check for rangeclause + */ + if (first_less && second_less) + { + if (!first_outer_is_left && second_outer_is_left && + equal(first_left, second_right)) + return 2; + else if (first_outer_is_left && !second_outer_is_left && + equal(first_right, second_left)) + return 1; + } + else if (!first_less && !second_less) + { + if (!first_outer_is_left && second_outer_is_left && + equal(first_left, second_right)) + return 1; + else if (first_outer_is_left && !second_outer_is_left && + equal(first_right, second_left)) + return 2; + } + else if (first_less && !second_less) + { + if (!first_outer_is_left && !second_outer_is_left && + equal(first_left, second_left)) + return 2; + else if (first_outer_is_left && second_outer_is_left && + equal(first_right, second_right)) + return 1; + } + else if (!first_less && second_less) + { + if (!first_outer_is_left && !second_outer_is_left && + equal(first_left, second_left)) + return 1; + else if (first_outer_is_left && second_outer_is_left && + equal(first_right, second_right)) + return 2; + } + + return 0; +} + +/* + * select_rangejoin_clauses + */ +static List * +select_rangejoin_clauses(RelOptInfo *outerrel, + RelOptInfo *innerrel, + List *restrictlist) +{ + List *result_list = NIL; + ListCell *l; + List *range_candidates = NIL; + + foreach(l, restrictlist) + { + RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l); + OpExpr *clause = (OpExpr *) restrictinfo->clause; + + /* Check that clause is a rangejoinable operator clause */ + if (restrictinfo->rangeleftopfamilies == NIL) + continue; /* not rangejoinable */ + + /* + * Check if clause has the form "outer op inner" or "inner op outer". + */ + if (!clause_sides_match_join(restrictinfo, outerrel, innerrel)) + continue; /* no good for these input relations */ + + if (restrictinfo->rangeleftopfamilies == restrictinfo->rangerightopfamilies) + { + ListCell *lc; + List *range_clause; + + foreach(lc, range_candidates) + { + RestrictInfo *candidate = (RestrictInfo *) lfirst(lc); + + switch (range_clause_order(restrictinfo, candidate)) + { + case 1: + range_clause = list_make2(restrictinfo, candidate); + result_list = lappend(result_list, range_clause); + break; + + case 2: + range_clause = list_make2(candidate, restrictinfo); + result_list = lappend(result_list, range_clause); + break; + default: + break; + } + } + range_candidates = lappend(range_candidates, restrictinfo); + } + else if ((clause->opno == OID_RANGE_CONTAINS_ELEM_OP && restrictinfo->outer_is_left) || + (clause->opno == OID_RANGE_ELEM_CONTAINED_OP && !restrictinfo->outer_is_left)) + { + result_list = lappend(result_list, list_make1(restrictinfo)); + } + } + list_free(range_candidates); + return result_list; +} diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c index 216dd26385..f82e760658 100644 --- a/src/backend/optimizer/path/pathkeys.c +++ b/src/backend/optimizer/path/pathkeys.c @@ -19,6 +19,7 @@ #include "access/stratnum.h" #include "catalog/pg_opfamily.h" +#include "catalog/pg_operator.h" #include "nodes/makefuncs.h" #include "nodes/nodeFuncs.h" #include "nodes/plannodes.h" @@ -1214,6 +1215,60 @@ initialize_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo) true); } +/* + * initialize_rangeclause_eclasses + */ +void +initialize_rangeclause_eclasses(PlannerInfo *root, + RestrictInfo *restrictinfo) +{ + Expr *clause = restrictinfo->clause; + Oid lefttype, + righttype, + opno; + + /* Should be a rangeclause ... */ + Assert(restrictinfo->rangeleftopfamilies != NIL && + restrictinfo->rangerightopfamilies != NIL); + /* ... with links not yet set */ + Assert(restrictinfo->left_ec == NULL); + Assert(restrictinfo->right_ec == NULL); + + opno = ((OpExpr *) clause)->opno; + + /* Need the declared input types of the operator */ + op_input_types(opno, &lefttype, &righttype); + + if(opno == OID_RANGE_CONTAINS_ELEM_OP) + righttype = exprType(get_rightop(clause)); + + else if(opno == OID_RANGE_ELEM_CONTAINED_OP) + lefttype = exprType(get_leftop(clause)); + + + /* Find or create a matching EquivalenceClass for each side */ + restrictinfo->left_ec = + get_eclass_for_sort_expr(root, + (Expr *) get_leftop(clause), + restrictinfo->nullable_relids, + restrictinfo->rangeleftopfamilies, + lefttype, + ((OpExpr *) clause)->inputcollid, + 0, + NULL, + true); + restrictinfo->right_ec = + get_eclass_for_sort_expr(root, + (Expr *) get_rightop(clause), + restrictinfo->nullable_relids, + restrictinfo->rangerightopfamilies, + righttype, + ((OpExpr *) clause)->inputcollid, + 0, + NULL, + true); +} + /* * update_mergeclause_eclasses * Make the cached EquivalenceClass links valid in a mergeclause @@ -1347,6 +1402,64 @@ find_mergeclauses_for_outer_pathkeys(PlannerInfo *root, return mergeclauses; } +/* + * find_rangeclauses_for_outer_pathkeys + */ +List * +find_rangeclauses_for_outer_pathkeys(PlannerInfo *root, + List *pathkeys, + List *mergeclauses, + List *rangeclauses) +{ + ListCell *i; + RestrictInfo *mergeclause = NULL; + List *result_list = NIL; + + if(mergeclauses) + mergeclause = llast(mergeclauses); + + foreach(i, pathkeys) + { + PathKey *pathkey = (PathKey *) lfirst(i); + EquivalenceClass *pathkey_ec = pathkey->pk_eclass; + ListCell *j; + + if(mergeclause != NULL) + { + if(mergeclause->outer_is_left) + { + if(mergeclause->left_ec != pathkey_ec) + continue; + } + else if(mergeclause->right_ec != pathkey_ec) + continue; + } + + foreach(j, rangeclauses) + { + List *rangeclause = (List *) lfirst(j); + RestrictInfo *rinfo = (RestrictInfo *) linitial(rangeclause); + EquivalenceClass *clause_ec; + + clause_ec = rinfo->outer_is_left ? + rinfo->left_ec : rinfo->right_ec; + + if (clause_ec == pathkey_ec) + result_list = lappend(result_list, rangeclause); + } + + /* + * Was it the last possible pathkey? + */ + if(mergeclause == NULL) + break; + else + mergeclause = NULL; + + } + return result_list; +} + /* * select_outer_pathkeys_for_merge * Builds a pathkey list representing a possible sort ordering @@ -1522,6 +1635,37 @@ select_outer_pathkeys_for_merge(PlannerInfo *root, return pathkeys; } +/* + * select_outer_pathkeys_for_range + */ +List * +select_outer_pathkeys_for_range(PlannerInfo *root, + List *rangeclauses) +{ + EquivalenceClass *ec; + PathKey *pathkey; + List *pathkeys = NIL; + ListCell *lc; + + foreach(lc, rangeclauses){ + List *rangeclause = lfirst(lc); + RestrictInfo *rinfo = linitial(rangeclause); + + if (rinfo->outer_is_left) + ec = rinfo->left_ec; + else + ec = rinfo->right_ec; + + pathkey = make_canonical_pathkey(root, + ec, + linitial_oid(ec->ec_opfamilies), + BTLessStrategyNumber, + false); + pathkeys = lappend(pathkeys, pathkey); + } + return pathkeys; +} + /* * make_inner_pathkeys_for_merge * Builds a pathkey list representing the explicit sort order that @@ -1621,6 +1765,35 @@ make_inner_pathkeys_for_merge(PlannerInfo *root, return pathkeys; } +/* + * make_inner_pathkey_for_range + */ +PathKey * +make_inner_pathkey_for_range(PlannerInfo *root, + List *rangeclause) +{ + EquivalenceClass *ec; + PathKey *pathkey; + RestrictInfo *rinfo; + + if(rangeclause == NIL) + return NULL; + + rinfo = linitial(rangeclause); + + if (rinfo->outer_is_left) + ec = rinfo->right_ec; + else + ec = rinfo->left_ec; + + pathkey = make_canonical_pathkey(root, + ec, + linitial_oid(ec->ec_opfamilies), + BTLessStrategyNumber, + false); + return pathkey; +} + /* * trim_mergeclauses_for_inner_pathkeys * This routine trims a list of mergeclauses to include just those that diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c index 3dc0176a51..49cc8d16d6 100644 --- a/src/backend/optimizer/plan/createplan.c +++ b/src/backend/optimizer/plan/createplan.c @@ -246,6 +246,7 @@ static Hash *make_hash(Plan *lefttree, static MergeJoin *make_mergejoin(List *tlist, List *joinclauses, List *otherclauses, List *mergeclauses, + List *rangeclause, Oid *mergefamilies, Oid *mergecollations, int *mergestrategies, @@ -4301,6 +4302,7 @@ create_mergejoin_plan(PlannerInfo *root, List *joinclauses; List *otherclauses; List *mergeclauses; + List *rangeclause; List *outerpathkeys; List *innerpathkeys; int nClauses; @@ -4355,6 +4357,9 @@ create_mergejoin_plan(PlannerInfo *root, mergeclauses = get_actual_clauses(best_path->path_mergeclauses); joinclauses = list_difference(joinclauses, mergeclauses); + rangeclause = get_actual_clauses(best_path->path_rangeclause); + joinclauses = list_difference(joinclauses, rangeclause); + /* * Replace any outer-relation variables with nestloop params. There * should not be any in the mergeclauses. @@ -4365,6 +4370,8 @@ create_mergejoin_plan(PlannerInfo *root, replace_nestloop_params(root, (Node *) joinclauses); otherclauses = (List *) replace_nestloop_params(root, (Node *) otherclauses); + rangeclause = (List *) + replace_nestloop_params(root, (Node *) rangeclause); } /* @@ -4581,6 +4588,7 @@ create_mergejoin_plan(PlannerInfo *root, joinclauses, otherclauses, mergeclauses, + rangeclause, mergefamilies, mergecollations, mergestrategies, @@ -5883,6 +5891,7 @@ make_mergejoin(List *tlist, List *joinclauses, List *otherclauses, List *mergeclauses, + List *rangeclause, Oid *mergefamilies, Oid *mergecollations, int *mergestrategies, @@ -5909,6 +5918,7 @@ make_mergejoin(List *tlist, node->join.jointype = jointype; node->join.inner_unique = inner_unique; node->join.joinqual = joinclauses; + node->rangeclause = rangeclause; return node; } diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.c index e25dc9a7ca..847b9dc124 100644 --- a/src/backend/optimizer/plan/initsplan.c +++ b/src/backend/optimizer/plan/initsplan.c @@ -16,6 +16,7 @@ #include "catalog/pg_class.h" #include "catalog/pg_type.h" +#include "catalog/pg_operator.h" #include "nodes/makefuncs.h" #include "nodes/nodeFuncs.h" #include "optimizer/clauses.h" @@ -77,6 +78,7 @@ static bool check_equivalence_delay(PlannerInfo *root, RestrictInfo *restrictinfo); static bool check_redundant_nullability_qual(PlannerInfo *root, Node *clause); static void check_mergejoinable(RestrictInfo *restrictinfo); +static void check_rangejoinable(RestrictInfo *restrictinfo); static void check_hashjoinable(RestrictInfo *restrictinfo); static void check_memoizable(RestrictInfo *restrictinfo); @@ -1877,6 +1879,8 @@ distribute_qual_to_rels(PlannerInfo *root, Node *clause, */ check_mergejoinable(restrictinfo); + check_rangejoinable(restrictinfo); + /* * If it is a true equivalence clause, send it to the EquivalenceClass * machinery. We do *not* attach it directly to any restriction or join @@ -1962,6 +1966,13 @@ distribute_qual_to_rels(PlannerInfo *root, Node *clause, } } + if(restrictinfo->rangeleftopfamilies) + { + Assert(restrictinfo->rangerightopfamilies); + + initialize_rangeclause_eclasses(root, restrictinfo); + } + /* No EC special case applies, so push it into the clause lists */ distribute_restrictinfo_to_rels(root, restrictinfo); } @@ -2677,6 +2688,50 @@ check_mergejoinable(RestrictInfo *restrictinfo) */ } +/* + * check_rangejoinable + */ +static void +check_rangejoinable(RestrictInfo *restrictinfo) +{ + OpExpr *clause = (OpExpr *) restrictinfo->clause; + Oid opno = clause->opno; + + if (!restrictinfo->can_join) + return; + if (contain_volatile_functions((Node *) clause)) + return; + + if (opno == OID_RANGE_CONTAINS_ELEM_OP || + opno == OID_RANGE_ELEM_CONTAINED_OP) + { + Node *leftarg = get_leftop(clause), + *rightarg = get_rightop(clause); + + Oid lefttype = exprType(leftarg), + righttype = exprType(rightarg); + + TypeCacheEntry *left_typecache = lookup_type_cache(lefttype, TYPECACHE_CMP_PROC), + *right_typecache = lookup_type_cache(righttype, TYPECACHE_CMP_PROC); + + restrictinfo->rangeleftopfamilies = + lappend_oid(restrictinfo->rangeleftopfamilies, + left_typecache->btree_opf); + + restrictinfo->rangerightopfamilies = + lappend_oid(restrictinfo->rangerightopfamilies, + right_typecache->btree_opf); + } + else + { + List *opfamilies = get_rangejoin_opfamilies(opno); + + restrictinfo->rangeleftopfamilies = opfamilies; + restrictinfo->rangerightopfamilies = opfamilies; + + } +} + /* * check_hashjoinable * If the restrictinfo's clause is hashjoinable, set the hashjoin diff --git a/src/backend/optimizer/plan/setrefs.c b/src/backend/optimizer/plan/setrefs.c index 6ccec759bd..c309a3e114 100644 --- a/src/backend/optimizer/plan/setrefs.c +++ b/src/backend/optimizer/plan/setrefs.c @@ -2038,6 +2038,14 @@ set_join_references(PlannerInfo *root, Join *join, int rtoffset) (Index) 0, rtoffset, NUM_EXEC_QUAL((Plan *) join)); + + mj->rangeclause = fix_join_expr(root, + mj->rangeclause, + outer_itlist, + inner_itlist, + (Index) 0, + rtoffset, + NUM_EXEC_QUAL((Plan *) join)); } else if (IsA(join, HashJoin)) { diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c index e53d381e19..f8490fa4ef 100644 --- a/src/backend/optimizer/util/pathnode.c +++ b/src/backend/optimizer/util/pathnode.c @@ -2502,6 +2502,7 @@ create_mergejoin_path(PlannerInfo *root, List *pathkeys, Relids required_outer, List *mergeclauses, + List *rangeclause, List *outersortkeys, List *innersortkeys) { @@ -2530,6 +2531,7 @@ create_mergejoin_path(PlannerInfo *root, pathnode->jpath.innerjoinpath = inner_path; pathnode->jpath.joinrestrictinfo = restrict_clauses; pathnode->path_mergeclauses = mergeclauses; + pathnode->path_rangeclause = rangeclause; pathnode->outersortkeys = outersortkeys; pathnode->innersortkeys = innersortkeys; /* pathnode->skip_mark_restore will be set by final_cost_mergejoin */ @@ -4134,6 +4136,7 @@ do { \ REPARAMETERIZE_CHILD_PATH(jpath->innerjoinpath); ADJUST_CHILD_ATTRS(jpath->joinrestrictinfo); ADJUST_CHILD_ATTRS(mpath->path_mergeclauses); + ADJUST_CHILD_ATTRS(mpath->path_rangeclause); new_path = (Path *) mpath; } break; diff --git a/src/backend/optimizer/util/restrictinfo.c b/src/backend/optimizer/util/restrictinfo.c index aa9fb3a9fa..8887341d74 100644 --- a/src/backend/optimizer/util/restrictinfo.c +++ b/src/backend/optimizer/util/restrictinfo.c @@ -201,6 +201,8 @@ make_restrictinfo_internal(PlannerInfo *root, restrictinfo->outer_selec = -1; restrictinfo->mergeopfamilies = NIL; + restrictinfo->rangeleftopfamilies = NIL; + restrictinfo->rangerightopfamilies = NIL; restrictinfo->left_ec = NULL; restrictinfo->right_ec = NULL; diff --git a/src/backend/utils/adt/rangetypes.c b/src/backend/utils/adt/rangetypes.c index 815175a654..3972480519 100644 --- a/src/backend/utils/adt/rangetypes.c +++ b/src/backend/utils/adt/rangetypes.c @@ -2507,6 +2507,66 @@ range_contains_elem_internal(TypeCacheEntry *typcache, const RangeType *r, Datum return true; } +/* + * Test whether range r is right of a specific element value. + */ +bool +elem_before_range_internal(TypeCacheEntry *typcache, Datum val, const RangeType *r) +{ + RangeBound lower; + RangeBound upper; + bool empty; + int32 cmp; + + range_deserialize(typcache, r, &lower, &upper, &empty); + + if (empty) + return true; + + if (!lower.infinite) + { + cmp = DatumGetInt32(FunctionCall2Coll(&typcache->rng_cmp_proc_finfo, + typcache->rng_collation, + lower.val, val)); + if (cmp > 0) + return true; + if (cmp == 0 && !lower.inclusive) + return true; + } + + return false; +} + +/* + * Test whether range r is left of a specific element value. + */ +bool +elem_after_range_internal(TypeCacheEntry *typcache, Datum val, const RangeType *r) +{ + RangeBound lower; + RangeBound upper; + bool empty; + int32 cmp; + + range_deserialize(typcache, r, &lower, &upper, &empty); + + if (empty) + return true; + + if (!upper.infinite) + { + cmp = DatumGetInt32(FunctionCall2Coll(&typcache->rng_cmp_proc_finfo, + typcache->rng_collation, + upper.val, val)); + if (cmp < 0) + return true; + if (cmp == 0 && !upper.inclusive) + return true; + } + + return false; +} + /* * datum_compute_size() and datum_write() are used to insert the bound diff --git a/src/backend/utils/cache/lsyscache.c b/src/backend/utils/cache/lsyscache.c index 4ebaa552a2..f6cc0cdb8a 100644 --- a/src/backend/utils/cache/lsyscache.c +++ b/src/backend/utils/cache/lsyscache.c @@ -389,6 +389,40 @@ get_mergejoin_opfamilies(Oid opno) return result; } +/* + * get_rangejoin_opfamilies + */ +List * +get_rangejoin_opfamilies(Oid opno) +{ + List *result = NIL; + CatCList *catlist; + int i; + + /* + * Search pg_amop to see if the target operator is registered as the "<", + * "<=", ">" or ">=" operator of any btree opfamily. + */ + catlist = SearchSysCacheList1(AMOPOPID, ObjectIdGetDatum(opno)); + + for (i = 0; i < catlist->n_members; i++) + { + HeapTuple tuple = &catlist->members[i]->tuple; + Form_pg_amop aform = (Form_pg_amop) GETSTRUCT(tuple); + + if (aform->amopmethod == BTREE_AM_OID && + (aform->amopstrategy == BTLessStrategyNumber || + aform->amopstrategy == BTLessEqualStrategyNumber || + aform->amopstrategy == BTGreaterStrategyNumber || + aform->amopstrategy == BTGreaterEqualStrategyNumber)) + result = lappend_oid(result, aform->amopfamily); + } + + ReleaseSysCacheList(catlist); + + return result; +} + /* * get_compatible_hash_operators * Get the OID(s) of hash equality operator(s) compatible with the given diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h index 37cb4f3d59..c96d59b48f 100644 --- a/src/include/nodes/execnodes.h +++ b/src/include/nodes/execnodes.h @@ -1948,6 +1948,7 @@ typedef struct NestLoopState */ /* private in nodeMergejoin.c: */ typedef struct MergeJoinClauseData *MergeJoinClause; +typedef struct RangeJoinData *RangeData; typedef struct MergeJoinState { @@ -1969,6 +1970,8 @@ typedef struct MergeJoinState TupleTableSlot *mj_NullInnerTupleSlot; ExprContext *mj_OuterEContext; ExprContext *mj_InnerEContext; + RangeData mj_RangeData; + bool mj_RangeJoin; } MergeJoinState; /* ---------------- diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h index 2a53a6e344..9aa3b5fe77 100644 --- a/src/include/nodes/pathnodes.h +++ b/src/include/nodes/pathnodes.h @@ -1647,6 +1647,7 @@ typedef struct MergePath { JoinPath jpath; List *path_mergeclauses; /* join clauses to be used for merge */ + List *path_rangeclause; /* join clause to be used for range merge */ List *outersortkeys; /* keys for explicit sort, if any */ List *innersortkeys; /* keys for explicit sort, if any */ bool skip_mark_restore; /* can executor skip mark/restore? */ @@ -2102,6 +2103,8 @@ typedef struct RestrictInfo /* valid if clause is mergejoinable, else NIL */ List *mergeopfamilies; /* opfamilies containing clause operator */ + List *rangeleftopfamilies; + List *rangerightopfamilies; /* cache space for mergeclause processing; NULL if not yet set */ EquivalenceClass *left_ec; /* EquivalenceClass containing lefthand */ @@ -2528,6 +2531,7 @@ typedef struct JoinPathExtraData { List *restrictlist; List *mergeclause_list; + List *rangeclause_list; bool inner_unique; SpecialJoinInfo *sjinfo; SemiAntiJoinFactors semifactors; diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h index 01a246d50e..5fdc45faf9 100644 --- a/src/include/nodes/plannodes.h +++ b/src/include/nodes/plannodes.h @@ -754,6 +754,7 @@ typedef struct MergeJoin Oid *mergeCollations; /* per-clause OIDs of collations */ int *mergeStrategies; /* per-clause ordering (ASC or DESC) */ bool *mergeNullsFirst; /* per-clause nulls ordering */ + List *rangeclause; /* rangeclause as expression tree */ } MergeJoin; /* ---------------- diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h index f704d39980..365d8b809e 100644 --- a/src/include/optimizer/pathnode.h +++ b/src/include/optimizer/pathnode.h @@ -167,6 +167,7 @@ extern MergePath *create_mergejoin_path(PlannerInfo *root, List *pathkeys, Relids required_outer, List *mergeclauses, + List *rangeclause, List *outersortkeys, List *innersortkeys); diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h index f1d111063c..0acfd297eb 100644 --- a/src/include/optimizer/paths.h +++ b/src/include/optimizer/paths.h @@ -231,17 +231,27 @@ extern List *make_pathkeys_for_sortclauses(PlannerInfo *root, List *tlist); extern void initialize_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo); +extern void initialize_rangeclause_eclasses(PlannerInfo *root, + RestrictInfo *restrictinfo); extern void update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo); extern List *find_mergeclauses_for_outer_pathkeys(PlannerInfo *root, List *pathkeys, List *restrictinfos); +extern List *find_rangeclauses_for_outer_pathkeys(PlannerInfo *root, + List *pathkeys, + List *mergeclauses, + List *rangeclauses); extern List *select_outer_pathkeys_for_merge(PlannerInfo *root, List *mergeclauses, RelOptInfo *joinrel); +extern List *select_outer_pathkeys_for_range(PlannerInfo *root, + List *rangeclauses); extern List *make_inner_pathkeys_for_merge(PlannerInfo *root, List *mergeclauses, List *outer_pathkeys); +extern PathKey *make_inner_pathkey_for_range(PlannerInfo *root, + List *rangeclause); extern List *trim_mergeclauses_for_inner_pathkeys(PlannerInfo *root, List *mergeclauses, List *pathkeys); diff --git a/src/include/utils/lsyscache.h b/src/include/utils/lsyscache.h index 77871aaefc..a47beb8be5 100644 --- a/src/include/utils/lsyscache.h +++ b/src/include/utils/lsyscache.h @@ -79,6 +79,7 @@ extern bool get_ordering_op_properties(Oid opno, extern Oid get_equality_op_for_ordering_op(Oid opno, bool *reverse); extern Oid get_ordering_op_for_equality_op(Oid opno, bool use_lhs_type); extern List *get_mergejoin_opfamilies(Oid opno); +extern List *get_rangejoin_opfamilies(Oid opno); extern bool get_compatible_hash_operators(Oid opno, Oid *lhs_opno, Oid *rhs_opno); extern bool get_op_hash_functions(Oid opno, diff --git a/src/include/utils/rangetypes.h b/src/include/utils/rangetypes.h index 04c302c619..51bdc5308b 100644 --- a/src/include/utils/rangetypes.h +++ b/src/include/utils/rangetypes.h @@ -95,6 +95,8 @@ typedef struct */ extern bool range_contains_elem_internal(TypeCacheEntry *typcache, const RangeType *r, Datum val); +extern bool elem_before_range_internal(TypeCacheEntry *typcache, Datum val, const RangeType *r); +extern bool elem_after_range_internal(TypeCacheEntry *typcache, Datum val, const RangeType *r); /* internal versions of the above */ extern bool range_eq_internal(TypeCacheEntry *typcache, const RangeType *r1,