Range Merge Join v1
Started by Jeff Davisalmost 9 years ago13 messages
========
Example:
========
Find different people using the same website at the same time:
create table session(sessionid text, username text, during tstzrange);
SELECT s1.username, s2.username, s1.during * s2.during
FROM session s1, session s2
WHERE s1.during && s2.during AND s1.username < s2.username
=====================================
Brief summary of previous discussion:
=====================================
/messages/by-id/1334554850.10878.52.camel@jdavis
- can indexes solve it already (parameterized paths, etc.)?
- planner complexity (track path keys, mergejoinable equality, etc.)
- spatial join algorithm choice
- compare range merge join against existing indexes to see if any
indexing approach is viable
==========
Externals:
==========
No new syntax or other externals. Just improved execution strategy for
joining ranges using the overlaps operator (&&).
New syntax is possible, but I don't see a strong reason to support
special range join syntax at this time.
=============
Optimizer Design
=============
I took the path of least resistance, so if I am doing something wrong
please let me know. I hardwired it to look for the range overlaps
operator when checking if it could do a merge join, and then add
range_ops to restrictinfo->mergeopfamilies.
Then, I have to suppress adding it as an equivalence class, because
overlaps is not equality. It still adds single-member ECs to
restrictinfo->right_ec and left_ec, but (I think) that's OK.
Also, I have to prevent generating paths for right/full join, because
the range join algorithm can't (currently) handle those.
=============
Costing
=============
Needs more consideration. Seems to do reasonable things in the few
examples I tried.
=============
Executor Design
=============
See detailed comments in nodeMergejoin.c
=============
Performance
=============
Seems much better than index nest loop join when the join is not
selective. I will post detailed numbers soon.
If no index is available, range merge join is the only reasonable way
to execute a range join. For instance, if the inner is not a leaf in
the plan.
=============
Alternatives:
=============
It was suggested that I approach it as a general spatial-join
problem. That has merit, but I rejected it for now because the
algorithm that I think has the most promise is range-oriented
anyway. By that I mean we would need to extract all of the dimensions
into ranges first, and then perform the join. With that in mind, it
makes sense to implement range joins first; and then later provide the
APIs to get at the spatial dimensions so that we can implement other
spatial joins as range joins.
Another suggestion was to base it on hash join, but I never understood
that proposal and it didn't seem to map very well to a spatial join.
Yet another suggestion was to use some kind of temporary index. Some
brief experiments I did indicated that it would be fairly slow (though
more investigation might be useful here). Also, it doesn't provide any
alternative to the nestloop-with-inner-index we already offer at the
leaf level today.
Regards,
Jeff Davis
Attachments:
rangejoin-v1.patchtext/x-patch; charset=US-ASCII; name=rangejoin-v1.patchDownload
diff --git a/src/backend/commands/explain.c b/src/backend/commands/explain.c
index a18ab43..1110c1e 100644
*** a/src/backend/commands/explain.c
--- b/src/backend/commands/explain.c
***************
*** 909,915 **** ExplainNode(PlanState *planstate, List *ancestors,
pname = sname = "Nested Loop";
break;
case T_MergeJoin:
! pname = "Merge"; /* "Join" gets added by jointype switch */
sname = "Merge Join";
break;
case T_HashJoin:
--- 909,919 ----
pname = sname = "Nested Loop";
break;
case T_MergeJoin:
! if (((MergeJoin*)plan)->mergeRangeJoin)
! pname = "Range Merge"; /* "Join" gets added by jointype switch */
! else
! pname = "Merge"; /* "Join" gets added by jointype switch */
!
sname = "Merge Join";
break;
case T_HashJoin:
diff --git a/src/backend/executor/nodindex 62784af..f3375c3 100644
*** a/src/backend/executor/nodeMergejoin.c
--- b/src/backend/executor/nodeMergejoin.c
***************
*** 89,102 ****
--- 89,151 ----
* proceed to another state. This state is stored in the node's
* execution state information and is preserved across calls to
* ExecMergeJoin. -cim 10/31/89
+ *
+ * RANGE MERGE JOIN
+ *
+ * Range Merge Join is a generalization of merge join. When a join
+ * predicate involves the range overlaps operator (&&), a merge join
+ * becomes a range join.
+ *
+ * The input ranges must be ordered by (lower-bound, upper-bound), which
+ * is the ordinary range_ops operator class. MJCompare must not simply
+ * use the operator class's comparison semantics though; instead it
+ * follows these rules:
+ *
+ * - return 0 if the outer range overlaps the inner range
+ * - return <0 if the outer range is strictly left-of the inner range
+ * - return >0 if the outer range is strictly right-of the inner range
+ *
+ * Another way to understand these rules is that 0 indicates a match, >0
+ * indicates that a later inner tuple may match, and <0 means that no
+ * later inner tuple could possibly match. Importantly, >0 does *not*
+ * imply that no earlier inner tuple matches.
+ *
+ * Example:
+ *
+ * OUTER INNER
+ * ... [1,9] matches current outer
+ * [4,5] [2,3] no match
+ * ... [3,5] matches current outer
+ * ... [7,9] no match and no later matches for current outer
+ *
+ * Outer tuple [4,5] does not match [2,3], but it matches (overlaps with)
+ * the earlier tuple [1,9] and the later tuple [3,5]. But once we
+ * encounter [7,9], we know that no later inner tuple can possibly match
+ * the outer. This logic extends to multiple join conditions without
+ * additional complexity.
+ *
+ * When doing a range join, we lose two merge join optimizations:
+ *
+ * 1. Ordinary merge join only restores to the mark if it's equal to the
+ * new outer. For range join, we must always restore to the mark
+ * because there may be matches after the mark and before the current
+ * inner tuple.
+ * 2. After restoring to the mark, ordinary merge join immediately moves
+ * to JOINTUPLES. Range join must move to SKIP_TEST first.
+ *
+ * Additionally, range merge join is unable to implement RIGHT/FULL joins.
*/
#include "postgres.h"
#include "access/nbtree.h"
+ #include "catalog/pg_operator.h"
#include "executor/execdebug.h"
#include "executor/nodeMergejoin.h"
+ #include "nodes/nodeFuncs.h"
#include "utils/lsyscache.h"
#include "utils/memutils.h"
+ #include "utils/rangetypes.h"
+ #include "utils/typcache.h"
/*
***************
*** 137,142 **** typedef struct MergeJoinClauseData
--- 186,195 ----
* stored here.
*/
SortSupportData ssup;
+
+ /* needed for Range Join */
+ bool isrange;
+ TypeCacheEntry *range_typcache;
} MergeJoinClauseData;
/* Result type for MJEvalOuterValues and MJEvalInnerValues */
***************
*** 177,182 **** MJExamineQuals(List *mergeclauses,
--- 230,236 ----
Oid *mergecollations,
int *mergestrategies,
bool *mergenullsfirst,
+ bool *israngejoin,
PlanState *parent)
{
MergeJoinClause clauses;
***************
*** 184,189 **** MJExamineQuals(List *mergeclauses,
--- 238,245 ----
int iClause;
ListCell *cl;
+ *israngejoin = false;
+
clauses = (MergeJoinClause) palloc0(nClauses * sizeof(MergeJoinClauseData));
iClause = 0;
***************
*** 195,200 **** MJExamineQuals(List *mergeclauses,
--- 251,257 ----
Oid collation = mergecollations[iClause];
StrategyNumber opstrategy = mergestrategies[iClause];
bool nulls_first = mergenullsfirst[iClause];
+ Oid eq_opno;
int op_strategy;
Oid op_lefttype;
Oid op_righttype;
***************
*** 220,227 **** MJExamineQuals(List *mergeclauses,
elog(ERROR, "unsupported mergejoin strategy %d", opstrategy);
clause->ssup.ssup_nulls_first = nulls_first;
/* Extract the operator's declared left/right datatypes */
! get_op_opfamily_properties(qual->opno, opfamily, false,
&op_strategy,
&op_lefttype,
&op_righttype);
--- 277,308 ----
elog(ERROR, "unsupported mergejoin strategy %d", opstrategy);
clause->ssup.ssup_nulls_first = nulls_first;
+ /*
+ * If a range join, the original operator must be "&&" rather than
+ * "=". Set eq_opno to the range equality operator for the purposes of
+ * setting up the merge clause, but mark it as a range.
+ */
+ if (qual->opno == OID_RANGE_OVERLAP_OP)
+ {
+ Oid rngtypid = exprType((Node*)clause->lexpr->expr);
+ Assert(exprType((Node*)clause->lexpr->expr) ==
+ exprType((Node*)clause->rexpr->expr));
+ eq_opno = OID_RANGE_EQ_OP;
+ clause->isrange = true;
+ clause->range_typcache = lookup_type_cache(rngtypid,
+ TYPECACHE_RANGE_INFO);
+ *israngejoin = true;
+ }
+ else
+ {
+ eq_opno = qual->opno;
+ clause->isrange = false;
+ clause->range_typcache = NULL;
+ }
+
+
/* Extract the operator's declared left/right datatypes */
! get_op_opfamily_properties(eq_opno, opfamily, false,
&op_strategy,
&op_lefttype,
&op_righttype);
***************
*** 378,383 **** MJEvalInnerValues(MergeJoinState *mergestate, TupleTableSlot *innerslot)
--- 459,491 ----
}
/*
+ * Return 0 if ranges overlap, <0 if the first range is left-of the second, or
+ * >0 if the first range is right-of the second. See comment at the top of the
+ * file for explanation.
+ */
+ static int
+ ApplyRangeMatch(Datum ldatum, bool lisnull, Datum rdatum, bool risnull,
+ SortSupport ssup, TypeCacheEntry *typcache)
+ {
+ Assert(!lisnull || !risnull);
+
+
+ if (lisnull)
+ return ssup->ssup_nulls_first ? -1 : 1;
+ if (risnull)
+ return ssup->ssup_nulls_first ? 1 : -1;
+
+ if (range_before_internal(typcache, DatumGetRangeType(ldatum),
+ DatumGetRangeType(rdatum)))
+ return ssup->ssup_reverse ? 1 : -1;
+ else if (range_overlaps_internal(typcache, DatumGetRangeType(ldatum),
+ DatumGetRangeType(rdatum)))
+ return 0;
+ else
+ return ssup->ssup_reverse ? -1 : 1;
+ }
+
+ /*
* MJCompare
*
* Compare the mergejoinable values of the current two input tuples
***************
*** 417,425 **** MJCompare(MergeJoinState *mergestate)
continue;
}
! result = ApplySortComparator(clause->ldatum, clause->lisnull,
clause->rdatum, clause->risnull,
! &clause->ssup);
if (result != 0)
break;
--- 525,538 ----
continue;
}
! if (clause->isrange)
! result = ApplyRangeMatch(clause->ldatum, clause->lisnull,
clause->rdatum, clause->risnull,
! &clause->ssup, clause->range_typcache);
! else
! result = ApplySortComparator(clause->ldatum, clause->lisnull,
! clause->rdatum, clause->risnull,
! &clause->ssup);
if (result != 0)
break;
***************
*** 532,538 **** check_constant_qual(List *qual, bool *is_const_false)
return true;
}
-
/* ----------------------------------------------------------------
* ExecMergeTupleDump
*
--- 645,650 ----
diff --git a/src/backend/optimizer/path/joiindex de7044d..34b0d45 100644
*** a/src/backend/optimizer/path/joinpath.c
--- b/src/backend/optimizer/path/joinpath.c
***************
*** 440,445 **** try_mergejoin_path(PlannerInfo *root,
--- 440,458 ----
Relids required_outer;
JoinCostWorkspace workspace;
+ /* RIGHT/FULL joins don't support range join */
+ if (jointype == JOIN_RIGHT || jointype == JOIN_FULL)
+ {
+ ListCell *lc;
+
+ foreach(lc, mergeclauses)
+ {
+ RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(lc);
+ if (restrictinfo->rangejoin)
+ return;
+ }
+ }
+
if (is_partial)
{
try_partial_mergejoin_path(root,
diff --git a/src/backend/optimizer/path/pathindex 2c26906..617e383 100644
*** a/src/backend/optimizer/path/pathkeys.c
--- b/src/backend/optimizer/path/pathkeys.c
***************
*** 922,928 **** initialize_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
Oid lefttype,
righttype;
- /* Should be a mergeclause ... */
Assert(restrictinfo->mergeopfamilies != NIL);
/* ... with links not yet set */
Assert(restrictinfo->left_ec == NULL);
--- 922,927 ----
diff --git a/src/backend/optimizer/plan/initindex ebd442a..86021c0 100644
*** a/src/backend/optimizer/plan/initsplan.c
--- b/src/backend/optimizer/plan/initsplan.c
***************
*** 14,19 ****
--- 14,20 ----
*/
#include "postgres.h"
+ #include "catalog/pg_operator.h"
#include "catalog/pg_type.h"
#include "nodes/nodeFuncs.h"
#include "optimizer/clauses.h"
***************
*** 1940,1946 **** distribute_qual_to_rels(PlannerInfo *root, Node *clause,
*/
if (restrictinfo->mergeopfamilies)
{
! if (maybe_equivalence)
{
if (check_equivalence_delay(root, restrictinfo) &&
process_equivalence(root, restrictinfo, below_outer_join))
--- 1941,1947 ----
*/
if (restrictinfo->mergeopfamilies)
{
! if (maybe_equivalence && !restrictinfo->rangejoin)
{
if (check_equivalence_delay(root, restrictinfo) &&
process_equivalence(root, restrictinfo, below_outer_join))
***************
*** 2594,2599 **** check_mergejoinable(RestrictInfo *restrictinfo)
--- 2595,2606 ----
opno = ((OpExpr *) clause)->opno;
leftarg = linitial(((OpExpr *) clause)->args);
+ if (opno == OID_RANGE_OVERLAP_OP)
+ {
+ restrictinfo->rangejoin = true;
+ opno = OID_RANGE_EQ_OP;
+ }
+
if (op_mergejoinable(opno, exprType(leftarg)) &&
!contain_volatile_functions((Node *) clause))
restrictinfo->mergeopfamilies = get_mergejoin_opfamilies(opno);
diff --git a/src/backend/optimizer/util/restrindex 6f79f96..623e284 100644
*** a/src/backend/optimizer/util/restrictinfo.c
--- b/src/backend/optimizer/util/restrictinfo.c
***************
*** 186,191 **** make_restrictinfo_internal(Expr *clause,
--- 186,192 ----
restrictinfo->outer_selec = -1;
restrictinfo->mergeopfamilies = NIL;
+ restrictinfo->rangejoin = false;
restrictinfo->left_ec = NULL;
restrictinfo->right_ec = NULL;
diff --git a/src/backend/utils/adt/selfuncs.c b/index f5cffcb..1fda117 100644
*** a/src/backend/utils/adt/selfuncs.c
--- b/src/backend/utils/adt/selfuncs.c
***************
*** 2863,2869 **** mergejoinscansel(PlannerInfo *root, Node *clause,
*right;
VariableStatData leftvar,
rightvar;
- int op_strategy;
Oid op_lefttype;
Oid op_righttype;
Oid opno,
--- 2863,2868 ----
diff --git a/src/include/catalog/pg_opeindex fe8795a..1f1ffb4 100644
*** a/src/include/catalog/pg_operator.h
--- b/src/include/catalog/pg_operator.h
***************
*** 1748,1753 **** DESCR("greater than or equal");
--- 1748,1754 ----
/* generic range type operators */
DATA(insert OID = 3882 ( "=" PGNSP PGUID b t t 3831 3831 16 3882 3883 range_eq eqsel eqjoinsel ));
DESCR("equal");
+ #define OID_RANGE_EQ_OP 3882
DATA(insert OID = 3883 ( "<>" PGNSP PGUID b f f 3831 3831 16 3883 3882 range_ne neqsel neqjoinsel ));
DESCR("not equal");
DATA(insert OID = 3884 ( "<" PGNSP PGUID b f f 3831 3831 16 3887 3886 range_lt rangesel scalarltjoinsel ));
diff --git a/src/include/nodes/plannodesindex a2dd26f..4d768f1 100644
*** a/src/include/nodes/plannodes.h
--- b/src/include/nodes/plannodes.h
***************
*** 695,700 **** typedef struct MergeJoin
--- 695,701 ----
Oid *mergeCollations; /* per-clause OIDs of collations */
int *mergeStrategies; /* per-clause ordering (ASC or DESC) */
bool *mergeNullsFirst; /* per-clause nulls ordering */
+ bool mergeRangeJoin; /* is this a range merge join? */
} MergeJoin;
/* ----------------
diff --git a/src/include/nodes/relatindex fc53eb1..e7b93a6 100644
*** a/src/include/nodes/relation.h
--- b/src/include/nodes/relation.h
***************
*** 1764,1769 **** typedef struct RestrictInfo
--- 1764,1772 ----
/* valid if clause is mergejoinable, else NIL */
List *mergeopfamilies; /* opfamilies containing clause operator */
+ /* is a rangejoin clause? */
+ bool rangejoin;
+
/* cache space for mergeclause processing; NULL if not yet set */
EquivalenceClass *left_ec; /* EquivalenceClass containing lefthand */
EquivalenceClass *right_ec; /* EquivalenceClass containing righthand */
diff --git a/src/test/regress/expecnew file mode 100644
index 0000000..d406177
*** /dev/null
--- b/src/test/regress/expected/rangejoin.out
***************
*** 0 ****
--- 1,94 ----
+ create table rangejoin1_left(i1 int, ir1 int4range);
+ create table rangejoin1_right(i2 int, ir2 int4range);
+ insert into rangejoin1_left values
+ (1001, int4range(10, 80)),
+ (1002, int4range(20, 30)),
+ (1003, int4range(21, 25)),
+ (1004, int4range(22, 35)),
+ (1005, int4range(40, 60)),
+ (1006, int4range(50, 60));
+ insert into rangejoin1_right values
+ (2001, int4range( 2, 4)),
+ (2002, int4range(10, 12)),
+ (2003, int4range(11, 14)),
+ (2004, int4range(20, 45)),
+ (2005, int4range(24, 28)),
+ (2006, int4range(85, 90));
+ explain select i1, ir1, i2, ir2
+ from rangejoin1_left, rangejoin1_right
+ where ir1 && ir2;
+ QUERY PLAN
+ ---------------------------------------------------------------------------------
+ Range Merge Join (cost=176.34..303.67 rows=8064 width=72)
+ Merge Cond: (rangejoin1_left.ir1 && rangejoin1_right.ir2)
+ -> Sort (cost=88.17..91.35 rows=1270 width=36)
+ Sort Key: rangejoin1_left.ir1
+ -> Seq Scan on rangejoin1_left (cost=0.00..22.70 rows=1270 width=36)
+ -> Sort (cost=88.17..91.35 rows=1270 width=36)
+ Sort Key: rangejoin1_right.ir2
+ -> Seq Scan on rangejoin1_right (cost=0.00..22.70 rows=1270 width=36)
+ (8 rows)
+
+ select i1, ir1, i2, ir2
+ from rangejoin1_left, rangejoin1_right
+ where ir1 && ir2;
+ i1 | ir1 | i2 | ir2
+ ------+---------+------+---------
+ 1001 | [10,80) | 2002 | [10,12)
+ 1001 | [10,80) | 2003 | [11,14)
+ 1001 | [10,80) | 2004 | [20,45)
+ 1001 | [10,80) | 2005 | [24,28)
+ 1002 | [20,30) | 2004 | [20,45)
+ 1002 | [20,30) | 2005 | [24,28)
+ 1003 | [21,25) | 2004 | [20,45)
+ 1003 | [21,25) | 2005 | [24,28)
+ 1004 | [22,35) | 2004 | [20,45)
+ 1004 | [22,35) | 2005 | [24,28)
+ 1005 | [40,60) | 2004 | [20,45)
+ (11 rows)
+
+ explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin1_left left join rangejoin1_right
+ on (ir1 && ir2);
+ QUERY PLAN
+ -------------------------------------------------------------
+ Range Merge Left Join
+ Merge Cond: (rangejoin1_left.ir1 && rangejoin1_right.ir2)
+ -> Sort
+ Sort Key: rangejoin1_left.ir1
+ -> Seq Scan on rangejoin1_left
+ -> Sort
+ Sort Key: rangejoin1_right.ir2
+ -> Seq Scan on rangejoin1_right
+ (8 rows)
+
+ select i1, ir1, i2, ir2
+ from rangejoin1_left left join rangejoin1_right
+ on (ir1 && ir2);
+ i1 | ir1 | i2 | ir2
+ ------+---------+------+---------
+ 1001 | [10,80) | 2002 | [10,12)
+ 1001 | [10,80) | 2003 | [11,14)
+ 1001 | [10,80) | 2004 | [20,45)
+ 1001 | [10,80) | 2005 | [24,28)
+ 1002 | [20,30) | 2004 | [20,45)
+ 1002 | [20,30) | 2005 | [24,28)
+ 1003 | [21,25) | 2004 | [20,45)
+ 1003 | [21,25) | 2005 | [24,28)
+ 1004 | [22,35) | 2004 | [20,45)
+ 1004 | [22,35) | 2005 | [24,28)
+ 1005 | [40,60) | 2004 | [20,45)
+ 1006 | [50,60) | |
+ (12 rows)
+
+ -- FULL JOIN doesn't support range join
+ explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin1_left full join rangejoin1_right
+ on (ir1 && ir2);
+ ERROR: FULL JOIN is only supported with merge-joinable or hash-joinable join conditions
+ select i1, ir1, i2, ir2
+ from rangejoin1_left full join rangejoin1_right
+ on (ir1 && ir2);
+ ERROR: FULL JOIN is only supported with merge-joinable or hash-joinable join conditions
+ drop table rangejoin1_left;
+ drop table rangejoin1_right;
diff --git a/src/test/regress/parallel_schedulindex 9f95b01..8bb9c80 100644
*** a/src/test/regress/parallel_schedule
--- b/src/test/regress/parallel_schedule
***************
*** 109,115 **** test: select_views portals_p2 foreign_key cluster dependency guc bitmapops combo
# NB: temp.sql does a reconnect which transiently uses 2 connections,
# so keep this parallel group to at most 19 tests
# ----------
! test: plancache limit plpgsql copy2 temp domain rangefuncs prepare without_oid conversion truncate alter_table sequence polymorphism rowtypes returning largeobject with xml
# event triggers cannot run concurrently with any test that runs DDL
test: event_trigger
--- 109,115 ----
# NB: temp.sql does a reconnect which transiently uses 2 connections,
# so keep this parallel group to at most 19 tests
# ----------
! test: plancache limit plpgsql copy2 temp domain rangefuncs rangejoin prepare without_oid conversion truncate alter_table sequence polymorphism rowtypes returning largeobject with xml
# event triggers cannot run concurrently with any test that runs DDL
test: event_trigger
diff --git a/src/test/regress/serial_scheindex e026b7c..3b80f75 100644
*** a/src/test/regress/serial_schedule
--- b/src/test/regress/serial_schedule
***************
*** 164,169 **** test: copy2
--- 164,170 ----
test: temp
test: domain
test: rangefuncs
+ test: rangejoin
test: prepare
test: without_oid
test: conversion
Re: Range Merge Join v1
Version 2 attached. Fixed a few issues, expanded tests, added docs.
A simple performance test (script attached) shows about a 5X
improvement when comparing against a nested loop with an inner
index-only scan over a gist index.
Even better, this doesn't require an index, so it will work even if
the input relations are subqueries.
Regards,
Jeff Davis
Show quoted text
On Thu, Apr 6, 2017 at 1:43 AM, Jeff Davis <pgsql@j-davis.com> wrote:
========
Example:
========Find different people using the same website at the same time:
create table session(sessionid text, username text, during tstzrange);
SELECT s1.username, s2.username, s1.during * s2.during
FROM session s1, session s2
WHERE s1.during && s2.during AND s1.username < s2.username=====================================
Brief summary of previous discussion:
=====================================/messages/by-id/1334554850.10878.52.camel@jdavis
- can indexes solve it already (parameterized paths, etc.)?
- planner complexity (track path keys, mergejoinable equality, etc.)
- spatial join algorithm choice
- compare range merge join against existing indexes to see if any
indexing approach is viable==========
Externals:
==========No new syntax or other externals. Just improved execution strategy for
joining ranges using the overlaps operator (&&).New syntax is possible, but I don't see a strong reason to support
special range join syntax at this time.=============
Optimizer Design
=============I took the path of least resistance, so if I am doing something wrong
please let me know. I hardwired it to look for the range overlaps
operator when checking if it could do a merge join, and then add
range_ops to restrictinfo->mergeopfamilies.Then, I have to suppress adding it as an equivalence class, because
overlaps is not equality. It still adds single-member ECs to
restrictinfo->right_ec and left_ec, but (I think) that's OK.Also, I have to prevent generating paths for right/full join, because
the range join algorithm can't (currently) handle those.=============
Costing
=============Needs more consideration. Seems to do reasonable things in the few
examples I tried.=============
Executor Design
=============See detailed comments in nodeMergejoin.c
=============
Performance
=============Seems much better than index nest loop join when the join is not
selective. I will post detailed numbers soon.If no index is available, range merge join is the only reasonable way
to execute a range join. For instance, if the inner is not a leaf in
the plan.=============
Alternatives:
=============It was suggested that I approach it as a general spatial-join
problem. That has merit, but I rejected it for now because the
algorithm that I think has the most promise is range-oriented
anyway. By that I mean we would need to extract all of the dimensions
into ranges first, and then perform the join. With that in mind, it
makes sense to implement range joins first; and then later provide the
APIs to get at the spatial dimensions so that we can implement other
spatial joins as range joins.Another suggestion was to base it on hash join, but I never understood
that proposal and it didn't seem to map very well to a spatial join.Yet another suggestion was to use some kind of temporary index. Some
brief experiments I did indicated that it would be fairly slow (though
more investigation might be useful here). Also, it doesn't provide any
alternative to the nestloop-with-inner-index we already offer at the
leaf level today.Regards,
Jeff Davis
Attachments:
rangejoin-v2.patchtext/x-patch; charset=US-ASCII; name=rangejoin-v2.patchDownload
diff --git a/doc/src/sgml/rangetypes.sgml b/doc/src/sgml/rangetypes.sgml
index 9557c16..84578a7 100644
*** a/doc/src/sgml/rangetypes.sgml
--- b/doc/src/sgml/rangetypes.sgml
***************
*** 522,525 **** INSERT 0 1
--- 522,595 ----
</programlisting>
</para>
</sect2>
+ <sect2 id="rangetypes-join">
+ <title>Range Join</title>
+
+ <indexterm>
+ <primary>range type</primary>
+ <secondary>join</secondary>
+ </indexterm>
+
+ <para>
+ A Range Join is a join where one of the join conditions is the range
+ overlaps operator (see <xref linkend="range-operators-table">). In other
+ words, rather than returning rows where corresponding fields are equal, it
+ returns rows where the corresponding fields overlap.
+ </para>
+ <para>
+ For instance, to find users who were active on a website at the same time
+ as they were using a mobile app, you might issue a query like:
+ <programlisting>
+ CREATE TABLE web_session(
+ web_session_id text primary key,
+ username text,
+ during tstzrange);
+ CREATE TABLE app_session(
+ app_session_id text primary key,
+ username text,
+ during tstzrange);
+ INSERT INTO web_session VALUES
+ ('0cc175b9c0f1b6a8', 'user1', '[2017-02-01 09:30, 2017-02-01 10:45)'),
+ ('92eb5ffee6ae2fec', 'user2', '[2017-02-01 09:30, 2017-02-01 10:45)'),
+ ('4a8a08f09d37b737', 'user3', '[2017-02-01 09:30, 2017-02-01 10:45)');
+ INSERT INTO app_session VALUES
+ ('8277e0910d750195', 'user1', '[2017-02-01 10:30, 2017-02-01 11:45)'),
+ ('b448797616e091ad', 'user3', '[2017-02-01 09:00, 2017-02-01 11:00)'),
+ ('95649038408b5f33', 'user4', '[2017-02-01 09:30, 2017-02-01 10:45)');
+
+ SELECT w.username,
+ w.during * a.during AS both_during
+ FROM web_session w, app_session a
+ WHERE w.username = a.username
+ AND w.during && a.during;
+ username | both_during
+ ----------+-----------------------------------------------------
+ user1 | ["2017-02-01 10:30:00-08","2017-02-01 10:45:00-08")
+ user3 | ["2017-02-01 09:30:00-08","2017-02-01 10:45:00-08")
+ (2 rows)
+ </programlisting>
+ </para>
+ <para>
+ In addition to the general execution strategies available, Postgres also
+ has special support for a variant of Merge Join called Range Merge Join:
+ <programlisting>
+ EXPLAIN (costs off) SELECT w.username,
+ w.during * a.during AS both_during
+ FROM web_session w, app_session a
+ WHERE w.username = a.username
+ AND w.during && a.during;
+ QUERY PLAN
+ ----------------------------------------------------------------------
+ Range Merge Join
+ Merge Cond: ((w.during && a.during) AND (w.username = a.username))
+ -> Sort
+ Sort Key: w.during, w.username
+ -> Seq Scan on web_session w
+ -> Sort
+ Sort Key: a.during, a.username
+ -> Seq Scan on app_session a
+ (8 rows)
+ </programlisting>
+ </para>
+ </sect2>
</sect1>
diff --git a/src/backend/commands/eindex 9359d0a..1010668 100644
*** a/src/backend/commands/explain.c
--- b/src/backend/commands/explain.c
***************
*** 909,915 **** ExplainNode(PlanState *planstate, List *ancestors,
pname = sname = "Nested Loop";
break;
case T_MergeJoin:
! pname = "Merge"; /* "Join" gets added by jointype switch */
sname = "Merge Join";
break;
case T_HashJoin:
--- 909,919 ----
pname = sname = "Nested Loop";
break;
case T_MergeJoin:
! if (((MergeJoin*)plan)->mergeRangeJoin)
! pname = "Range Merge"; /* "Join" gets added by jointype switch */
! else
! pname = "Merge"; /* "Join" gets added by jointype switch */
!
sname = "Merge Join";
break;
case T_HashJoin:
diff --git a/src/backend/executor/nodindex 8c483bf..bd312e6 100644
*** a/src/backend/executor/nodeMergejoin.c
--- b/src/backend/executor/nodeMergejoin.c
***************
*** 89,102 ****
--- 89,155 ----
* proceed to another state. This state is stored in the node's
* execution state information and is preserved across calls to
* ExecMergeJoin. -cim 10/31/89
+ *
+ * RANGE MERGE JOIN
+ *
+ * Range Merge Join is a generalization of merge join. When a join
+ * predicate involves the range overlaps operator (&&), a merge join
+ * becomes a range join.
+ *
+ * The input ranges must be ordered by (lower-bound, upper-bound), which
+ * is the ordinary range_ops operator class. MJCompare must not simply
+ * use the operator class's comparison semantics though; instead it
+ * follows these rules:
+ *
+ * - return 0 if the outer range overlaps the inner range
+ * - return <0 if the outer range is strictly left-of the inner range
+ * - return >0 if the outer range is strictly right-of the inner range
+ *
+ * NB: the above is a simplification considering only a single merge
+ * clause. When there are multiple merge clauses, it's possible that one
+ * tuple is neither right-of, nor left-of, nor matching. For instance, if
+ * an earlier range merge clause matches (overlaps), but a later clause
+ * fails. In that case, MJCompare returns 0 but sets "noMatch=true". See
+ * MJCompare.
+ *
+ * If MJCompare returns >0, later or earlier tuples on the inner side may
+ * match. For example:
+ *
+ * OUTER INNER
+ * ... [1,9] matches current outer
+ * [4,5] [2,3] no match
+ * ... [3,5] matches current outer
+ * ... [7,9] no match and no later matches for current outer
+ *
+ * Outer tuple [4,5] does not match [2,3], but it matches (overlaps with)
+ * the earlier tuple [1,9] and the later tuple [3,5]. But once we
+ * encounter [7,9], we know that no later inner tuple can possibly match
+ * the outer.
+ *
+ * When doing a range join, we lose two merge join optimizations:
+ *
+ * 1. Ordinary merge join only restores to the mark if it's equal to the
+ * new outer. For range join, we must always restore to the mark
+ * because there may be matches after the mark and before the current
+ * inner tuple.
+ * 2. After restoring to the mark, ordinary merge join immediately moves
+ * to JOINTUPLES. Range join must move to SKIP_TEST first.
+ *
+ * Range merge join is unable to implement RIGHT/FULL joins. It's also
+ * unable to cope with reverse sort order, because there could always be
+ * some later inner range that matches the outer tuple.
*/
#include "postgres.h"
#include "access/nbtree.h"
+ #include "catalog/pg_operator.h"
#include "executor/execdebug.h"
#include "executor/nodeMergejoin.h"
+ #include "nodes/nodeFuncs.h"
#include "utils/lsyscache.h"
#include "utils/memutils.h"
+ #include "utils/rangetypes.h"
+ #include "utils/typcache.h"
/*
***************
*** 137,142 **** typedef struct MergeJoinClauseData
--- 190,199 ----
* stored here.
*/
SortSupportData ssup;
+
+ /* needed for Range Join */
+ bool isrange;
+ TypeCacheEntry *range_typcache;
} MergeJoinClauseData;
/* Result type for MJEvalOuterValues and MJEvalInnerValues */
***************
*** 147,153 **** typedef enum
MJEVAL_ENDOFJOIN /* end of input (physical or effective) */
} MJEvalResult;
-
#define MarkInnerTuple(innerTupleSlot, mergestate) \
ExecCopySlot((mergestate)->mj_MarkedTupleSlot, (innerTupleSlot))
--- 204,209 ----
diff --git a/src/backend/optimizer/path/joiindex 5aedcd1..108d30c 100644
*** a/src/backend/optimizer/path/joinpath.c
--- b/src/backend/optimizer/path/joinpath.c
***************
*** 466,471 **** try_mergejoin_path(PlannerInfo *root,
--- 466,484 ----
Relids required_outer;
JoinCostWorkspace workspace;
+ /* RIGHT/FULL joins don't support range join */
+ if (jointype == JOIN_RIGHT || jointype == JOIN_FULL)
+ {
+ ListCell *lc;
+
+ foreach(lc, mergeclauses)
+ {
+ RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(lc);
+ if (restrictinfo->rangejoin)
+ return;
+ }
+ }
+
if (is_partial)
{
try_partial_mergejoin_path(root,
diff --git a/src/backend/optimizer/path/pathindex 2c26906..2ed2d64 100644
*** a/src/backend/optimizer/path/pathkeys.c
--- b/src/backend/optimizer/path/pathkeys.c
***************
*** 1125,1130 **** select_outer_pathkeys_for_merge(PlannerInfo *root,
--- 1125,1131 ----
int nClauses = list_length(mergeclauses);
EquivalenceClass **ecs;
int *scores;
+ bool *range_ecs;
int necs;
ListCell *lc;
int j;
***************
*** 1139,1144 **** select_outer_pathkeys_for_merge(PlannerInfo *root,
--- 1140,1146 ----
*/
ecs = (EquivalenceClass **) palloc(nClauses * sizeof(EquivalenceClass *));
scores = (int *) palloc(nClauses * sizeof(int));
+ range_ecs = palloc(nClauses * sizeof(bool));
necs = 0;
foreach(lc, mergeclauses)
***************
*** 1179,1184 **** select_outer_pathkeys_for_merge(PlannerInfo *root,
--- 1181,1187 ----
ecs[necs] = oeclass;
scores[necs] = score;
+ range_ecs[necs] = rinfo->rangejoin;
necs++;
}
***************
*** 1196,1201 **** select_outer_pathkeys_for_merge(PlannerInfo *root,
--- 1199,1209 ----
for (j = 0; j < necs; j++)
{
+ /* for range join, the input order must be ascending */
+ if (range_ecs[j] &&
+ query_pathkey->pk_strategy != BTLessStrategyNumber)
+ continue;
+
if (ecs[j] == query_ec)
break; /* found match */
}
diff --git a/src/backend/optimizer/plan/initindex ebd442a..86021c0 100644
*** a/src/backend/optimizer/plan/initsplan.c
--- b/src/backend/optimizer/plan/initsplan.c
***************
*** 14,19 ****
--- 14,20 ----
*/
#include "postgres.h"
+ #include "catalog/pg_operator.h"
#include "catalog/pg_type.h"
#include "nodes/nodeFuncs.h"
#include "optimizer/clauses.h"
***************
*** 1940,1946 **** distribute_qual_to_rels(PlannerInfo *root, Node *clause,
*/
if (restrictinfo->mergeopfamilies)
{
! if (maybe_equivalence)
{
if (check_equivalence_delay(root, restrictinfo) &&
process_equivalence(root, restrictinfo, below_outer_join))
--- 1941,1947 ----
*/
if (restrictinfo->mergeopfamilies)
{
! if (maybe_equivalence && !restrictinfo->rangejoin)
{
if (check_equivalence_delay(root, restrictinfo) &&
process_equivalence(root, restrictinfo, below_outer_join))
***************
*** 2594,2599 **** check_mergejoinable(RestrictInfo *restrictinfo)
--- 2595,2606 ----
opno = ((OpExpr *) clause)->opno;
leftarg = linitial(((OpExpr *) clause)->args);
+ if (opno == OID_RANGE_OVERLAP_OP)
+ {
+ restrictinfo->rangejoin = true;
+ opno = OID_RANGE_EQ_OP;
+ }
+
if (op_mergejoinable(opno, exprType(leftarg)) &&
!contain_volatile_functions((Node *) clause))
restrictinfo->mergeopfamilies = get_mergejoin_opfamilies(opno);
diff --git a/src/backend/optimizer/util/restrindex e946290..c2d1a23 100644
*** a/src/backend/optimizer/util/restrictinfo.c
--- b/src/backend/optimizer/util/restrictinfo.c
***************
*** 186,191 **** make_restrictinfo_internal(Expr *clause,
--- 186,192 ----
restrictinfo->outer_selec = -1;
restrictinfo->mergeopfamilies = NIL;
+ restrictinfo->rangejoin = false;
restrictinfo->left_ec = NULL;
restrictinfo->right_ec = NULL;
diff --git a/src/backend/utils/adt/selfuncs.c b/index a35b93b..5c8c69f 100644
*** a/src/backend/utils/adt/selfuncs.c
--- b/src/backend/utils/adt/selfuncs.c
***************
*** 2860,2866 **** mergejoinscansel(PlannerInfo *root, Node *clause,
*right;
VariableStatData leftvar,
rightvar;
- int op_strategy;
Oid op_lefttype;
Oid op_righttype;
Oid opno,
--- 2860,2865 ----
diff --git a/src/include/catalog/pg_opeindex fe8795a..1f1ffb4 100644
*** a/src/include/catalog/pg_operator.h
--- b/src/include/catalog/pg_operator.h
***************
*** 1748,1753 **** DESCR("greater than or equal");
--- 1748,1754 ----
/* generic range type operators */
DATA(insert OID = 3882 ( "=" PGNSP PGUID b t t 3831 3831 16 3882 3883 range_eq eqsel eqjoinsel ));
DESCR("equal");
+ #define OID_RANGE_EQ_OP 3882
DATA(insert OID = 3883 ( "<>" PGNSP PGUID b f f 3831 3831 16 3883 3882 range_ne neqsel neqjoinsel ));
DESCR("not equal");
DATA(insert OID = 3884 ( "<" PGNSP PGUID b f f 3831 3831 16 3887 3886 range_lt rangesel scalarltjoinsel ));
diff --git a/src/include/nodes/plannodesindex 12f9f61..e2b05e9 100644
*** a/src/include/nodes/plannodes.h
--- b/src/include/nodes/plannodes.h
***************
*** 703,708 **** typedef struct MergeJoin
--- 703,709 ----
Oid *mergeCollations; /* per-clause OIDs of collations */
int *mergeStrategies; /* per-clause ordering (ASC or DESC) */
bool *mergeNullsFirst; /* per-clause nulls ordering */
+ bool mergeRangeJoin; /* is this a range merge join? */
} MergeJoin;
/* ----------------
diff --git a/src/include/nodes/relatindex 7a8e2fd..aa16f9a 100644
*** a/src/include/nodes/relation.h
--- b/src/include/nodes/relation.h
***************
*** 1790,1795 **** typedef struct RestrictInfo
--- 1790,1798 ----
/* valid if clause is mergejoinable, else NIL */
List *mergeopfamilies; /* opfamilies containing clause operator */
+ /* is a rangejoin clause? */
+ bool rangejoin;
+
/* cache space for mergeclause processing; NULL if not yet set */
EquivalenceClass *left_ec; /* EquivalenceClass containing lefthand */
EquivalenceClass *right_ec; /* EquivalenceClass containing righthand */
diff --git a/src/test/regress/expecnew file mode 100644
index 0000000..e8fb835
*** /dev/null
--- b/src/test/regress/expected/rangejoin.out
***************
*** 0 ****
--- 1,526 ----
+ create table rangejoin_left(i1 int, ir1 int4range);
+ create table rangejoin_right(i2 int, ir2 int4range);
+ insert into rangejoin_left values
+ (1001, int4range(10, 80)),
+ (1002, int4range(20, 30)),
+ (1003, int4range(21, 25)),
+ (1004, int4range(22, 35)),
+ (1005, int4range(40, 60)),
+ (1006, int4range(50, 60));
+ insert into rangejoin_right values
+ (1000, 'empty'::int4range),
+ (1001, int4range(NULL, 4)),
+ (1002, int4range(10, 12)),
+ (1003, int4range(11, 14)),
+ (1004, int4range(20, 45)),
+ (1005, int4range(24, 28)),
+ (1006, int4range(85, 90));
+ -- simple inner join
+ explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left, rangejoin_right
+ where ir1 && ir2;
+ QUERY PLAN
+ -----------------------------------------------------------
+ Range Merge Join
+ Merge Cond: (rangejoin_left.ir1 && rangejoin_right.ir2)
+ -> Sort
+ Sort Key: rangejoin_left.ir1
+ -> Seq Scan on rangejoin_left
+ -> Sort
+ Sort Key: rangejoin_right.ir2
+ -> Seq Scan on rangejoin_right
+ (8 rows)
+
+ select i1, ir1, i2, ir2
+ from rangejoin_left, rangejoin_right
+ where ir1 && ir2;
+ i1 | ir1 | i2 | ir2
+ ------+---------+------+---------
+ 1001 | [10,80) | 1002 | [10,12)
+ 1001 | [10,80) | 1003 | [11,14)
+ 1001 | [10,80) | 1004 | [20,45)
+ 1001 | [10,80) | 1005 | [24,28)
+ 1002 | [20,30) | 1004 | [20,45)
+ 1002 | [20,30) | 1005 | [24,28)
+ 1003 | [21,25) | 1004 | [20,45)
+ 1003 | [21,25) | 1005 | [24,28)
+ 1004 | [22,35) | 1004 | [20,45)
+ 1004 | [22,35) | 1005 | [24,28)
+ 1005 | [40,60) | 1004 | [20,45)
+ (11 rows)
+
+ -- two predicates
+ explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left inner join rangejoin_right
+ on (i1 = i2 and ir1 && ir2);
+ QUERY PLAN
+ ----------------------------------------------------------------------------------------------------------
+ Range Merge Join
+ Merge Cond: ((rangejoin_left.ir1 && rangejoin_right.ir2) AND (rangejoin_left.i1 = rangejoin_right.i2))
+ -> Sort
+ Sort Key: rangejoin_left.ir1, rangejoin_left.i1
+ -> Seq Scan on rangejoin_left
+ -> Sort
+ Sort Key: rangejoin_right.ir2, rangejoin_right.i2
+ -> Seq Scan on rangejoin_right
+ (8 rows)
+
+ select i1, ir1, i2, ir2
+ from rangejoin_left inner join rangejoin_right
+ on (i1 = i2 and ir1 && ir2);
+ i1 | ir1 | i2 | ir2
+ ------+---------+------+---------
+ 1004 | [22,35) | 1004 | [20,45)
+ (1 row)
+
+ -- left join
+ explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left left join rangejoin_right
+ on (ir1 && ir2);
+ QUERY PLAN
+ -----------------------------------------------------------
+ Range Merge Left Join
+ Merge Cond: (rangejoin_left.ir1 && rangejoin_right.ir2)
+ -> Sort
+ Sort Key: rangejoin_left.ir1
+ -> Seq Scan on rangejoin_left
+ -> Sort
+ Sort Key: rangejoin_right.ir2
+ -> Seq Scan on rangejoin_right
+ (8 rows)
+
+ select i1, ir1, i2, ir2
+ from rangejoin_left left join rangejoin_right
+ on (ir1 && ir2);
+ i1 | ir1 | i2 | ir2
+ ------+---------+------+---------
+ 1001 | [10,80) | 1002 | [10,12)
+ 1001 | [10,80) | 1003 | [11,14)
+ 1001 | [10,80) | 1004 | [20,45)
+ 1001 | [10,80) | 1005 | [24,28)
+ 1002 | [20,30) | 1004 | [20,45)
+ 1002 | [20,30) | 1005 | [24,28)
+ 1003 | [21,25) | 1004 | [20,45)
+ 1003 | [21,25) | 1005 | [24,28)
+ 1004 | [22,35) | 1004 | [20,45)
+ 1004 | [22,35) | 1005 | [24,28)
+ 1005 | [40,60) | 1004 | [20,45)
+ 1006 | [50,60) | |
+ (12 rows)
+
+ -- right join should be implemented as left join
+ explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left right join rangejoin_right
+ on (ir1 && ir2);
+ QUERY PLAN
+ -----------------------------------------------------------
+ Range Merge Left Join
+ Merge Cond: (rangejoin_right.ir2 && rangejoin_left.ir1)
+ -> Sort
+ Sort Key: rangejoin_right.ir2
+ -> Seq Scan on rangejoin_right
+ -> Sort
+ Sort Key: rangejoin_left.ir1
+ -> Seq Scan on rangejoin_left
+ (8 rows)
+
+ -- full join doesn't support range join
+ explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left full join rangejoin_right
+ on (ir1 && ir2);
+ ERROR: FULL JOIN is only supported with merge-joinable or hash-joinable join conditions
+ -- range input to range join must be ascending
+ explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left inner join rangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 desc, i1;
+ QUERY PLAN
+ ----------------------------------------------------------------------------------------------------------------
+ Sort
+ Sort Key: rangejoin_left.ir1 DESC, rangejoin_left.i1
+ -> Range Merge Join
+ Merge Cond: ((rangejoin_left.ir1 && rangejoin_right.ir2) AND (rangejoin_left.i1 = rangejoin_right.i2))
+ -> Sort
+ Sort Key: rangejoin_left.ir1, rangejoin_left.i1
+ -> Seq Scan on rangejoin_left
+ -> Sort
+ Sort Key: rangejoin_right.ir2, rangejoin_right.i2
+ -> Seq Scan on rangejoin_right
+ (10 rows)
+
+ -- but it's OK for non-range inputs to be descending
+ explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left inner join rangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 nulls first, i1 desc;
+ QUERY PLAN
+ ----------------------------------------------------------------------------------------------------------
+ Range Merge Join
+ Merge Cond: ((rangejoin_left.ir1 && rangejoin_right.ir2) AND (rangejoin_left.i1 = rangejoin_right.i2))
+ -> Sort
+ Sort Key: rangejoin_left.ir1 NULLS FIRST, rangejoin_left.i1 DESC
+ -> Seq Scan on rangejoin_left
+ -> Sort
+ Sort Key: rangejoin_right.ir2 NULLS FIRST, rangejoin_right.i2 DESC
+ -> Seq Scan on rangejoin_right
+ (8 rows)
+
+ select i1, ir1, i2, ir2
+ from rangejoin_left inner join rangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 nulls first, i1 desc;
+ i1 | ir1 | i2 | ir2
+ ------+---------+------+---------
+ 1004 | [22,35) | 1004 | [20,45)
+ (1 row)
+
+ drop table rangejoin_left;
+ drop table rangejoin_right;
+ create table multirangejoin_left (ir1 int4range, ir2 int4range);
+ create table multirangejoin_right (ir3 int4range, ir4 int4range);
+ insert into multirangejoin_left values
+ (int4range(30,99), int4range(20,30)),
+ (int4range(2,40), int4range(15,27)),
+ (int4range(61,99), int4range(20,45)),
+ (int4range(22,32), int4range(21,66)),
+ (int4range(36,71), int4range(45,49)),
+ (int4range(9,80), int4range(2,4));
+ insert into multirangejoin_right values
+ (int4range(9,70), int4range(10,78)),
+ (int4range(21,37), int4range(89,99)),
+ (int4range(5,98), int4range(35,97)),
+ (int4range(12,17), int4range(81,92)),
+ (int4range(15,19), int4range(5,55)),
+ (int4range(57,58), int4range(42,80));
+ explain (costs off) select *
+ from multirangejoin_left inner join multirangejoin_right
+ on (ir1 && ir3 and ir2 && ir4) order by ir1, ir2, ir3, ir4;
+ QUERY PLAN
+ ---------------------------------------------------------------------------------------------------------------------------------------
+ Sort
+ Sort Key: multirangejoin_left.ir1, multirangejoin_left.ir2, multirangejoin_right.ir3, multirangejoin_right.ir4
+ -> Range Merge Join
+ Merge Cond: ((multirangejoin_left.ir1 && multirangejoin_right.ir3) AND (multirangejoin_left.ir2 && multirangejoin_right.ir4))
+ -> Sort
+ Sort Key: multirangejoin_left.ir1, multirangejoin_left.ir2
+ -> Seq Scan on multirangejoin_left
+ -> Sort
+ Sort Key: multirangejoin_right.ir3, multirangejoin_right.ir4
+ -> Seq Scan on multirangejoin_right
+ (10 rows)
+
+ select *
+ from multirangejoin_left inner join multirangejoin_right
+ on (ir1 && ir3 and ir2 && ir4) order by ir1, ir2, ir3, ir4;
+ ir1 | ir2 | ir3 | ir4
+ ---------+---------+---------+---------
+ [2,40) | [15,27) | [9,70) | [10,78)
+ [2,40) | [15,27) | [15,19) | [5,55)
+ [22,32) | [21,66) | [5,98) | [35,97)
+ [22,32) | [21,66) | [9,70) | [10,78)
+ [30,99) | [20,30) | [9,70) | [10,78)
+ [36,71) | [45,49) | [5,98) | [35,97)
+ [36,71) | [45,49) | [9,70) | [10,78)
+ [36,71) | [45,49) | [57,58) | [42,80)
+ [61,99) | [20,45) | [5,98) | [35,97)
+ [61,99) | [20,45) | [9,70) | [10,78)
+ (10 rows)
+
+ set enable_mergejoin=false;
+ explain (costs off) select *
+ from multirangejoin_left inner join multirangejoin_right
+ on (ir1 && ir3 and ir2 && ir4) order by ir1, ir2, ir3, ir4;
+ QUERY PLAN
+ ----------------------------------------------------------------------------------------------------------------------------------------
+ Sort
+ Sort Key: multirangejoin_left.ir1, multirangejoin_left.ir2, multirangejoin_right.ir3, multirangejoin_right.ir4
+ -> Nested Loop
+ Join Filter: ((multirangejoin_left.ir1 && multirangejoin_right.ir3) AND (multirangejoin_left.ir2 && multirangejoin_right.ir4))
+ -> Seq Scan on multirangejoin_left
+ -> Materialize
+ -> Seq Scan on multirangejoin_right
+ (7 rows)
+
+ select *
+ from multirangejoin_left inner join multirangejoin_right
+ on (ir1 && ir3 and ir2 && ir4) order by ir1, ir2, ir3, ir4;
+ ir1 | ir2 | ir3 | ir4
+ ---------+---------+---------+---------
+ [2,40) | [15,27) | [9,70) | [10,78)
+ [2,40) | [15,27) | [15,19) | [5,55)
+ [22,32) | [21,66) | [5,98) | [35,97)
+ [22,32) | [21,66) | [9,70) | [10,78)
+ [30,99) | [20,30) | [9,70) | [10,78)
+ [36,71) | [45,49) | [5,98) | [35,97)
+ [36,71) | [45,49) | [9,70) | [10,78)
+ [36,71) | [45,49) | [57,58) | [42,80)
+ [61,99) | [20,45) | [5,98) | [35,97)
+ [61,99) | [20,45) | [9,70) | [10,78)
+ (10 rows)
+
+ set enable_mergejoin=true;
+ explain (costs off) select *
+ from multirangejoin_left left join multirangejoin_right
+ on (ir1 && ir4 and ir2 && ir3) order by ir4, ir3, ir2, ir1;
+ QUERY PLAN
+ ---------------------------------------------------------------------------------------------------------------------------------------
+ Sort
+ Sort Key: multirangejoin_right.ir4, multirangejoin_right.ir3, multirangejoin_left.ir2, multirangejoin_left.ir1
+ -> Range Merge Left Join
+ Merge Cond: ((multirangejoin_left.ir1 && multirangejoin_right.ir4) AND (multirangejoin_left.ir2 && multirangejoin_right.ir3))
+ -> Sort
+ Sort Key: multirangejoin_left.ir1, multirangejoin_left.ir2
+ -> Seq Scan on multirangejoin_left
+ -> Sort
+ Sort Key: multirangejoin_right.ir4, multirangejoin_right.ir3
+ -> Seq Scan on multirangejoin_right
+ (10 rows)
+
+ select *
+ from multirangejoin_left left join multirangejoin_right
+ on (ir1 && ir4 and ir2 && ir3) order by ir4, ir3, ir2, ir1;
+ ir1 | ir2 | ir3 | ir4
+ ---------+---------+---------+---------
+ [2,40) | [15,27) | [15,19) | [5,55)
+ [2,40) | [15,27) | [9,70) | [10,78)
+ [30,99) | [20,30) | [9,70) | [10,78)
+ [61,99) | [20,45) | [9,70) | [10,78)
+ [22,32) | [21,66) | [9,70) | [10,78)
+ [36,71) | [45,49) | [9,70) | [10,78)
+ [2,40) | [15,27) | [5,98) | [35,97)
+ [30,99) | [20,30) | [5,98) | [35,97)
+ [61,99) | [20,45) | [5,98) | [35,97)
+ [36,71) | [45,49) | [5,98) | [35,97)
+ [30,99) | [20,30) | [21,37) | [89,99)
+ [61,99) | [20,45) | [21,37) | [89,99)
+ [9,80) | [2,4) | |
+ (13 rows)
+
+ set enable_mergejoin=false;
+ explain (costs off) select *
+ from multirangejoin_left left join multirangejoin_right
+ on (ir1 && ir4 and ir2 && ir3) order by ir4, ir3, ir2, ir1;
+ QUERY PLAN
+ ----------------------------------------------------------------------------------------------------------------------------------------
+ Sort
+ Sort Key: multirangejoin_right.ir4, multirangejoin_right.ir3, multirangejoin_left.ir2, multirangejoin_left.ir1
+ -> Nested Loop Left Join
+ Join Filter: ((multirangejoin_left.ir1 && multirangejoin_right.ir4) AND (multirangejoin_left.ir2 && multirangejoin_right.ir3))
+ -> Seq Scan on multirangejoin_left
+ -> Materialize
+ -> Seq Scan on multirangejoin_right
+ (7 rows)
+
+ select *
+ from multirangejoin_left left join multirangejoin_right
+ on (ir1 && ir4 and ir2 && ir3) order by ir4, ir3, ir2, ir1;
+ ir1 | ir2 | ir3 | ir4
+ ---------+---------+---------+---------
+ [2,40) | [15,27) | [15,19) | [5,55)
+ [2,40) | [15,27) | [9,70) | [10,78)
+ [30,99) | [20,30) | [9,70) | [10,78)
+ [61,99) | [20,45) | [9,70) | [10,78)
+ [22,32) | [21,66) | [9,70) | [10,78)
+ [36,71) | [45,49) | [9,70) | [10,78)
+ [2,40) | [15,27) | [5,98) | [35,97)
+ [30,99) | [20,30) | [5,98) | [35,97)
+ [61,99) | [20,45) | [5,98) | [35,97)
+ [36,71) | [45,49) | [5,98) | [35,97)
+ [30,99) | [20,30) | [21,37) | [89,99)
+ [61,99) | [20,45) | [21,37) | [89,99)
+ [9,80) | [2,4) | |
+ (13 rows)
+
+ set enable_mergejoin=true;
+ drop table multirangejoin_left;
+ drop table multirangejoin_right;
+ create table bigrangejoin_left (i1 int, ir1 int4range);
+ create table bigrangejoin_right (i2 int, ir2 int4range);
+ -- 100 small ranges
+ insert into bigrangejoin_left
+ select g/4,
+ int4range(g,
+ g + case when (g%2=0) then g%7 else 12-(g%11) end)
+ from generate_series(1,100) g;
+ insert into bigrangejoin_right
+ select g/4,
+ int4range(g-7+(g%19),
+ g-7+(g%19) + case when (g%3=0) then g%11 else 17-(g%15) end)
+ from generate_series(1,100) g;
+ -- 10 medium ranges
+ insert into bigrangejoin_left
+ select g/4*10,
+ int4range(g*10,
+ g*10 + case when (g%2=0) then g%7 else 12-(g%11) end)
+ from generate_series(1,10) g;
+ insert into bigrangejoin_right
+ select g/4*10,
+ int4range(g*10-57+(g%173),
+ g*10-57+(g%173) + case when (g%3=0) then g%123 else 97-(g%83) end)
+ from generate_series(1,10) g;
+ insert into bigrangejoin_left select g*11-21, 'empty'::int4range
+ from generate_series(1,9) g;
+ insert into bigrangejoin_right select g*13-29, 'empty'::int4range
+ from generate_series(1,8) g;
+ insert into bigrangejoin_left values
+ (4, int4range(NULL,5)),
+ (93, int4range(95, NULL));
+ insert into bigrangejoin_right values
+ (7, int4range(NULL,3)),
+ (92, int4range(99, NULL));
+ create temp table rangejoin_result1
+ (i1 int, ir1 int4range, i2 int, ir2 int4range);
+ create temp table rangejoin_result2
+ (i1 int, ir1 int4range, i2 int, ir2 int4range);
+ set enable_hashjoin=false;
+ explain (costs off) insert into rangejoin_result1
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left left join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 nulls first, i1 desc;
+ QUERY PLAN
+ ----------------------------------------------------------------------------------------------------------------------------
+ Insert on rangejoin_result1
+ -> Range Merge Left Join
+ Merge Cond: ((bigrangejoin_left.ir1 && bigrangejoin_right.ir2) AND (bigrangejoin_left.i1 = bigrangejoin_right.i2))
+ -> Sort
+ Sort Key: bigrangejoin_left.ir1 NULLS FIRST, bigrangejoin_left.i1 DESC
+ -> Seq Scan on bigrangejoin_left
+ -> Sort
+ Sort Key: bigrangejoin_right.ir2 NULLS FIRST, bigrangejoin_right.i2 DESC
+ -> Seq Scan on bigrangejoin_right
+ (9 rows)
+
+ insert into rangejoin_result1
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left left join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 nulls first, i1 desc;
+ set enable_hashjoin=true;
+ set enable_mergejoin=false;
+ explain (costs off) insert into rangejoin_result2
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left left join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 nulls first, i1 desc;
+ QUERY PLAN
+ --------------------------------------------------------------------------------
+ Insert on rangejoin_result2
+ -> Sort
+ Sort Key: bigrangejoin_left.ir1 NULLS FIRST, bigrangejoin_left.i1 DESC
+ -> Hash Left Join
+ Hash Cond: (bigrangejoin_left.i1 = bigrangejoin_right.i2)
+ Join Filter: (bigrangejoin_left.ir1 && bigrangejoin_right.ir2)
+ -> Seq Scan on bigrangejoin_left
+ -> Hash
+ -> Seq Scan on bigrangejoin_right
+ (9 rows)
+
+ insert into rangejoin_result2
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left left join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 nulls first, i1 desc;
+ set enable_mergejoin=true;
+ select count(*) from rangejoin_result1;
+ count
+ -------
+ 292
+ (1 row)
+
+ select count(*) from rangejoin_result2;
+ count
+ -------
+ 292
+ (1 row)
+
+ select * from rangejoin_result1 except select * from rangejoin_result2;
+ i1 | ir1 | i2 | ir2
+ ----+-----+----+-----
+ (0 rows)
+
+ select * from rangejoin_result2 except select * from rangejoin_result1;
+ i1 | ir1 | i2 | ir2
+ ----+-----+----+-----
+ (0 rows)
+
+ drop table rangejoin_result1;
+ drop table rangejoin_result2;
+ create temp table rangejoin_result3
+ (i1 int, ir1 int4range, i2 int, ir2 int4range);
+ create temp table rangejoin_result4
+ (i1 int, ir1 int4range, i2 int, ir2 int4range);
+ explain (costs off) insert into rangejoin_result3
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left inner join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by i1, ir1;
+ QUERY PLAN
+ ----------------------------------------------------------------------------------------------------------------------------
+ Insert on rangejoin_result3
+ -> Range Merge Join
+ Merge Cond: ((bigrangejoin_left.i1 = bigrangejoin_right.i2) AND (bigrangejoin_left.ir1 && bigrangejoin_right.ir2))
+ -> Sort
+ Sort Key: bigrangejoin_left.i1, bigrangejoin_left.ir1
+ -> Seq Scan on bigrangejoin_left
+ -> Sort
+ Sort Key: bigrangejoin_right.i2, bigrangejoin_right.ir2
+ -> Seq Scan on bigrangejoin_right
+ (9 rows)
+
+ insert into rangejoin_result3
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left inner join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by i1, ir1;
+ set enable_mergejoin=false;
+ explain (costs off) insert into rangejoin_result4
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left inner join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by i1, ir1;
+ QUERY PLAN
+ ------------------------------------------------------------------------------
+ Insert on rangejoin_result4
+ -> Sort
+ Sort Key: bigrangejoin_left.i1, bigrangejoin_left.ir1
+ -> Hash Join
+ Hash Cond: (bigrangejoin_left.i1 = bigrangejoin_right.i2)
+ Join Filter: (bigrangejoin_left.ir1 && bigrangejoin_right.ir2)
+ -> Seq Scan on bigrangejoin_left
+ -> Hash
+ -> Seq Scan on bigrangejoin_right
+ (9 rows)
+
+ insert into rangejoin_result4
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left inner join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by i1, ir1;
+ set enable_mergejoin=true;
+ select count(*) from rangejoin_result3;
+ count
+ -------
+ 259
+ (1 row)
+
+ select count(*) from rangejoin_result4;
+ count
+ -------
+ 259
+ (1 row)
+
+ select * from rangejoin_result3 except select * from rangejoin_result4;
+ i1 | ir1 | i2 | ir2
+ ----+-----+----+-----
+ (0 rows)
+
+ select * from rangejoin_result4 except select * from rangejoin_result3;
+ i1 | ir1 | i2 | ir2
+ ----+-----+----+-----
+ (0 rows)
+
+ drop table rangejoin_result3;
+ drop table rangejoin_result4;
+ drop table bigrangejoin_left;
+ drop table bigrangejoin_right;
diff --git a/src/test/regress/parallel_schedulindex 1f8f098..4f70bb0 100644
*** a/src/test/regress/parallel_schedule
--- b/src/test/regress/parallel_schedule
***************
*** 109,115 **** test: select_views portals_p2 foreign_key cluster dependency guc bitmapops combo
# NB: temp.sql does a reconnect which transiently uses 2 connections,
# so keep this parallel group to at most 19 tests
# ----------
! test: plancache limit plpgsql copy2 temp domain rangefuncs prepare without_oid conversion truncate alter_table sequence polymorphism rowtypes returning largeobject with xml
# ----------
# Another group of parallel tests
--- 109,115 ----
# NB: temp.sql does a reconnect which transiently uses 2 connections,
# so keep this parallel group to at most 19 tests
# ----------
! test: plancache limit plpgsql copy2 temp domain rangefuncs rangejoin prepare without_oid conversion truncate alter_table sequence polymorphism rowtypes returning largeobject with xml
# ----------
# Another group of parallel tests
diff --git a/src/test/regress/serial_scheindex 04206c3..659dc4a 100644
*** a/src/test/regress/serial_schedule
--- b/src/test/regress/serial_schedule
***************
*** 164,169 **** test: copy2
--- 164,170 ----
test: temp
test: domain
test: rangefuncs
+ test: rangejoin
test: prepare
test: without_oid
test: conversion
diff --git a/src/test/regress/sql/rangenew file mode 100644
index 0000000..e1849aa
*** /dev/null
--- b/src/test/regress/sql/rangejoin.sql
***************
*** 0 ****
--- 1,265 ----
+
+ create table rangejoin_left(i1 int, ir1 int4range);
+ create table rangejoin_right(i2 int, ir2 int4range);
+
+ insert into rangejoin_left values
+ (1001, int4range(10, 80)),
+ (1002, int4range(20, 30)),
+ (1003, int4range(21, 25)),
+ (1004, int4range(22, 35)),
+ (1005, int4range(40, 60)),
+ (1006, int4range(50, 60));
+
+ insert into rangejoin_right values
+ (1000, 'empty'::int4range),
+ (1001, int4range(NULL, 4)),
+ (1002, int4range(10, 12)),
+ (1003, int4range(11, 14)),
+ (1004, int4range(20, 45)),
+ (1005, int4range(24, 28)),
+ (1006, int4range(85, 90));
+
+ -- simple inner join
+ explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left, rangejoin_right
+ where ir1 && ir2;
+
+ select i1, ir1, i2, ir2
+ from rangejoin_left, rangejoin_right
+ where ir1 && ir2;
+
+ -- two predicates
+ explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left inner join rangejoin_right
+ on (i1 = i2 and ir1 && ir2);
+
+ select i1, ir1, i2, ir2
+ from rangejoin_left inner join rangejoin_right
+ on (i1 = i2 and ir1 && ir2);
+
+ -- left join
+ explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left left join rangejoin_right
+ on (ir1 && ir2);
+
+ select i1, ir1, i2, ir2
+ from rangejoin_left left join rangejoin_right
+ on (ir1 && ir2);
+
+ -- right join should be implemented as left join
+ explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left right join rangejoin_right
+ on (ir1 && ir2);
+
+ -- full join doesn't support range join
+ explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left full join rangejoin_right
+ on (ir1 && ir2);
+
+ -- range input to range join must be ascending
+ explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left inner join rangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 desc, i1;
+
+ -- but it's OK for non-range inputs to be descending
+ explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left inner join rangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 nulls first, i1 desc;
+
+ select i1, ir1, i2, ir2
+ from rangejoin_left inner join rangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 nulls first, i1 desc;
+
+ drop table rangejoin_left;
+ drop table rangejoin_right;
+
+ create table multirangejoin_left (ir1 int4range, ir2 int4range);
+ create table multirangejoin_right (ir3 int4range, ir4 int4range);
+
+ insert into multirangejoin_left values
+ (int4range(30,99), int4range(20,30)),
+ (int4range(2,40), int4range(15,27)),
+ (int4range(61,99), int4range(20,45)),
+ (int4range(22,32), int4range(21,66)),
+ (int4range(36,71), int4range(45,49)),
+ (int4range(9,80), int4range(2,4));
+
+
+ insert into multirangejoin_right values
+ (int4range(9,70), int4range(10,78)),
+ (int4range(21,37), int4range(89,99)),
+ (int4range(5,98), int4range(35,97)),
+ (int4range(12,17), int4range(81,92)),
+ (int4range(15,19), int4range(5,55)),
+ (int4range(57,58), int4range(42,80));
+
+ explain (costs off) select *
+ from multirangejoin_left inner join multirangejoin_right
+ on (ir1 && ir3 and ir2 && ir4) order by ir1, ir2, ir3, ir4;
+
+ select *
+ from multirangejoin_left inner join multirangejoin_right
+ on (ir1 && ir3 and ir2 && ir4) order by ir1, ir2, ir3, ir4;
+
+ set enable_mergejoin=false;
+ explain (costs off) select *
+ from multirangejoin_left inner join multirangejoin_right
+ on (ir1 && ir3 and ir2 && ir4) order by ir1, ir2, ir3, ir4;
+
+ select *
+ from multirangejoin_left inner join multirangejoin_right
+ on (ir1 && ir3 and ir2 && ir4) order by ir1, ir2, ir3, ir4;
+ set enable_mergejoin=true;
+
+ explain (costs off) select *
+ from multirangejoin_left left join multirangejoin_right
+ on (ir1 && ir4 and ir2 && ir3) order by ir4, ir3, ir2, ir1;
+
+ select *
+ from multirangejoin_left left join multirangejoin_right
+ on (ir1 && ir4 and ir2 && ir3) order by ir4, ir3, ir2, ir1;
+
+ set enable_mergejoin=false;
+ explain (costs off) select *
+ from multirangejoin_left left join multirangejoin_right
+ on (ir1 && ir4 and ir2 && ir3) order by ir4, ir3, ir2, ir1;
+
+ select *
+ from multirangejoin_left left join multirangejoin_right
+ on (ir1 && ir4 and ir2 && ir3) order by ir4, ir3, ir2, ir1;
+ set enable_mergejoin=true;
+
+ drop table multirangejoin_left;
+ drop table multirangejoin_right;
+
+ create table bigrangejoin_left (i1 int, ir1 int4range);
+ create table bigrangejoin_right (i2 int, ir2 int4range);
+
+ -- 100 small ranges
+ insert into bigrangejoin_left
+ select g/4,
+ int4range(g,
+ g + case when (g%2=0) then g%7 else 12-(g%11) end)
+ from generate_series(1,100) g;
+ insert into bigrangejoin_right
+ select g/4,
+ int4range(g-7+(g%19),
+ g-7+(g%19) + case when (g%3=0) then g%11 else 17-(g%15) end)
+ from generate_series(1,100) g;
+
+ -- 10 medium ranges
+ insert into bigrangejoin_left
+ select g/4*10,
+ int4range(g*10,
+ g*10 + case when (g%2=0) then g%7 else 12-(g%11) end)
+ from generate_series(1,10) g;
+ insert into bigrangejoin_right
+ select g/4*10,
+ int4range(g*10-57+(g%173),
+ g*10-57+(g%173) + case when (g%3=0) then g%123 else 97-(g%83) end)
+ from generate_series(1,10) g;
+
+ insert into bigrangejoin_left select g*11-21, 'empty'::int4range
+ from generate_series(1,9) g;
+
+ insert into bigrangejoin_right select g*13-29, 'empty'::int4range
+ from generate_series(1,8) g;
+
+ insert into bigrangejoin_left values
+ (4, int4range(NULL,5)),
+ (93, int4range(95, NULL));
+
+ insert into bigrangejoin_right values
+ (7, int4range(NULL,3)),
+ (92, int4range(99, NULL));
+
+ create temp table rangejoin_result1
+ (i1 int, ir1 int4range, i2 int, ir2 int4range);
+ create temp table rangejoin_result2
+ (i1 int, ir1 int4range, i2 int, ir2 int4range);
+
+ set enable_hashjoin=false;
+ explain (costs off) insert into rangejoin_result1
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left left join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 nulls first, i1 desc;
+
+ insert into rangejoin_result1
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left left join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 nulls first, i1 desc;
+ set enable_hashjoin=true;
+
+ set enable_mergejoin=false;
+ explain (costs off) insert into rangejoin_result2
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left left join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 nulls first, i1 desc;
+
+ insert into rangejoin_result2
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left left join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 nulls first, i1 desc;
+ set enable_mergejoin=true;
+
+ select count(*) from rangejoin_result1;
+ select count(*) from rangejoin_result2;
+
+ select * from rangejoin_result1 except select * from rangejoin_result2;
+
+ select * from rangejoin_result2 except select * from rangejoin_result1;
+
+ drop table rangejoin_result1;
+ drop table rangejoin_result2;
+
+ create temp table rangejoin_result3
+ (i1 int, ir1 int4range, i2 int, ir2 int4range);
+ create temp table rangejoin_result4
+ (i1 int, ir1 int4range, i2 int, ir2 int4range);
+
+
+ explain (costs off) insert into rangejoin_result3
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left inner join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by i1, ir1;
+
+ insert into rangejoin_result3
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left inner join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by i1, ir1;
+
+ set enable_mergejoin=false;
+ explain (costs off) insert into rangejoin_result4
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left inner join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by i1, ir1;
+
+ insert into rangejoin_result4
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left inner join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by i1, ir1;
+ set enable_mergejoin=true;
+
+ select count(*) from rangejoin_result3;
+ select count(*) from rangejoin_result4;
+
+ select * from rangejoin_result3 except select * from rangejoin_result4;
+
+ select * from rangejoin_result4 except select * from rangejoin_result3;
+
+ drop table rangejoin_result3;
+ drop table rangejoin_result4;
+
+ drop table bigrangejoin_left;
+ drop table bigrangejoin_right;
Re: Range Merge Join v1
On Tue, Apr 11, 2017 at 12:17 AM, Jeff Davis <pgsql@j-davis.com> wrote:
Version 2 attached. Fixed a few issues, expanded tests, added docs.
It looks like the CF app only listed my perf test script. Re-attaching
rangejoin-v2.patch so that it appears in the CF app. Identical to
other rangejoin-v2.patch.
Regards,
Jeff Davis
Attachments:
rangejoin-v2.patchtext/x-patch; charset=US-ASCII; name=rangejoin-v2.patchDownload
diff --git a/doc/src/sgml/rangetypes.sgml b/doc/src/sgml/rangetypes.sgml
index 9557c16..84578a7 100644
*** a/doc/src/sgml/rangetypes.sgml
--- b/doc/src/sgml/rangetypes.sgml
***************
*** 522,525 **** INSERT 0 1
--- 522,595 ----
</programlisting>
</para>
</sect2>
+ <sect2 id="rangetypes-join">
+ <title>Range Join</title>
+
+ <indexterm>
+ <primary>range type</primary>
+ <secondary>join</secondary>
+ </indexterm>
+
+ <para>
+ A Range Join is a join where one of the join conditions is the range
+ overlaps operator (see <xref linkend="range-operators-table">). In other
+ words, rather than returning rows where corresponding fields are equal, it
+ returns rows where the corresponding fields overlap.
+ </para>
+ <para>
+ For instance, to find users who were active on a website at the same time
+ as they were using a mobile app, you might issue a query like:
+ <programlisting>
+ CREATE TABLE web_session(
+ web_session_id text primary key,
+ username text,
+ during tstzrange);
+ CREATE TABLE app_session(
+ app_session_id text primary key,
+ username text,
+ during tstzrange);
+ INSERT INTO web_session VALUES
+ ('0cc175b9c0f1b6a8', 'user1', '[2017-02-01 09:30, 2017-02-01 10:45)'),
+ ('92eb5ffee6ae2fec', 'user2', '[2017-02-01 09:30, 2017-02-01 10:45)'),
+ ('4a8a08f09d37b737', 'user3', '[2017-02-01 09:30, 2017-02-01 10:45)');
+ INSERT INTO app_session VALUES
+ ('8277e0910d750195', 'user1', '[2017-02-01 10:30, 2017-02-01 11:45)'),
+ ('b448797616e091ad', 'user3', '[2017-02-01 09:00, 2017-02-01 11:00)'),
+ ('95649038408b5f33', 'user4', '[2017-02-01 09:30, 2017-02-01 10:45)');
+
+ SELECT w.username,
+ w.during * a.during AS both_during
+ FROM web_session w, app_session a
+ WHERE w.username = a.username
+ AND w.during && a.during;
+ username | both_during
+ ----------+-----------------------------------------------------
+ user1 | ["2017-02-01 10:30:00-08","2017-02-01 10:45:00-08")
+ user3 | ["2017-02-01 09:30:00-08","2017-02-01 10:45:00-08")
+ (2 rows)
+ </programlisting>
+ </para>
+ <para>
+ In addition to the general execution strategies available, Postgres also
+ has special support for a variant of Merge Join called Range Merge Join:
+ <programlisting>
+ EXPLAIN (costs off) SELECT w.username,
+ w.during * a.during AS both_during
+ FROM web_session w, app_session a
+ WHERE w.username = a.username
+ AND w.during && a.during;
+ QUERY PLAN
+ ----------------------------------------------------------------------
+ Range Merge Join
+ Merge Cond: ((w.during && a.during) AND (w.username = a.username))
+ -> Sort
+ Sort Key: w.during, w.username
+ -> Seq Scan on web_session w
+ -> Sort
+ Sort Key: a.during, a.username
+ -> Seq Scan on app_session a
+ (8 rows)
+ </programlisting>
+ </para>
+ </sect2>
</sect1>
diff --git a/src/backend/commands/eindex 9359d0a..1010668 100644
*** a/src/backend/commands/explain.c
--- b/src/backend/commands/explain.c
***************
*** 909,915 **** ExplainNode(PlanState *planstate, List *ancestors,
pname = sname = "Nested Loop";
break;
case T_MergeJoin:
! pname = "Merge"; /* "Join" gets added by jointype switch */
sname = "Merge Join";
break;
case T_HashJoin:
--- 909,919 ----
pname = sname = "Nested Loop";
break;
case T_MergeJoin:
! if (((MergeJoin*)plan)->mergeRangeJoin)
! pname = "Range Merge"; /* "Join" gets added by jointype switch */
! else
! pname = "Merge"; /* "Join" gets added by jointype switch */
!
sname = "Merge Join";
break;
case T_HashJoin:
diff --git a/src/backend/executor/nodindex 8c483bf..bd312e6 100644
*** a/src/backend/executor/nodeMergejoin.c
--- b/src/backend/executor/nodeMergejoin.c
***************
*** 89,102 ****
--- 89,155 ----
* proceed to another state. This state is stored in the node's
* execution state information and is preserved across calls to
* ExecMergeJoin. -cim 10/31/89
+ *
+ * RANGE MERGE JOIN
+ *
+ * Range Merge Join is a generalization of merge join. When a join
+ * predicate involves the range overlaps operator (&&), a merge join
+ * becomes a range join.
+ *
+ * The input ranges must be ordered by (lower-bound, upper-bound), which
+ * is the ordinary range_ops operator class. MJCompare must not simply
+ * use the operator class's comparison semantics though; instead it
+ * follows these rules:
+ *
+ * - return 0 if the outer range overlaps the inner range
+ * - return <0 if the outer range is strictly left-of the inner range
+ * - return >0 if the outer range is strictly right-of the inner range
+ *
+ * NB: the above is a simplification considering only a single merge
+ * clause. When there are multiple merge clauses, it's possible that one
+ * tuple is neither right-of, nor left-of, nor matching. For instance, if
+ * an earlier range merge clause matches (overlaps), but a later clause
+ * fails. In that case, MJCompare returns 0 but sets "noMatch=true". See
+ * MJCompare.
+ *
+ * If MJCompare returns >0, later or earlier tuples on the inner side may
+ * match. For example:
+ *
+ * OUTER INNER
+ * ... [1,9] matches current outer
+ * [4,5] [2,3] no match
+ * ... [3,5] matches current outer
+ * ... [7,9] no match and no later matches for current outer
+ *
+ * Outer tuple [4,5] does not match [2,3], but it matches (overlaps with)
+ * the earlier tuple [1,9] and the later tuple [3,5]. But once we
+ * encounter [7,9], we know that no later inner tuple can possibly match
+ * the outer.
+ *
+ * When doing a range join, we lose two merge join optimizations:
+ *
+ * 1. Ordinary merge join only restores to the mark if it's equal to the
+ * new outer. For range join, we must always restore to the mark
+ * because there may be matches after the mark and before the current
+ * inner tuple.
+ * 2. After restoring to the mark, ordinary merge join immediately moves
+ * to JOINTUPLES. Range join must move to SKIP_TEST first.
+ *
+ * Range merge join is unable to implement RIGHT/FULL joins. It's also
+ * unable to cope with reverse sort order, because there could always be
+ * some later inner range that matches the outer tuple.
*/
#include "postgres.h"
#include "access/nbtree.h"
+ #include "catalog/pg_operator.h"
#include "executor/execdebug.h"
#include "executor/nodeMergejoin.h"
+ #include "nodes/nodeFuncs.h"
#include "utils/lsyscache.h"
#include "utils/memutils.h"
+ #include "utils/rangetypes.h"
+ #include "utils/typcache.h"
/*
***************
*** 137,142 **** typedef struct MergeJoinClauseData
--- 190,199 ----
* stored here.
*/
SortSupportData ssup;
+
+ /* needed for Range Join */
+ bool isrange;
+ TypeCacheEntry *range_typcache;
} MergeJoinClauseData;
/* Result type for MJEvalOuterValues and MJEvalInnerValues */
***************
*** 147,153 **** typedef enum
MJEVAL_ENDOFJOIN /* end of input (physical or effective) */
} MJEvalResult;
-
#define MarkInnerTuple(innerTupleSlot, mergestate) \
ExecCopySlot((mergestate)->mj_MarkedTupleSlot, (innerTupleSlot))
--- 204,209 ----
diff --git a/src/backend/optimizer/path/joiindex 5aedcd1..108d30c 100644
*** a/src/backend/optimizer/path/joinpath.c
--- b/src/backend/optimizer/path/joinpath.c
***************
*** 466,471 **** try_mergejoin_path(PlannerInfo *root,
--- 466,484 ----
Relids required_outer;
JoinCostWorkspace workspace;
+ /* RIGHT/FULL joins don't support range join */
+ if (jointype == JOIN_RIGHT || jointype == JOIN_FULL)
+ {
+ ListCell *lc;
+
+ foreach(lc, mergeclauses)
+ {
+ RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(lc);
+ if (restrictinfo->rangejoin)
+ return;
+ }
+ }
+
if (is_partial)
{
try_partial_mergejoin_path(root,
diff --git a/src/backend/optimizer/path/pathindex 2c26906..2ed2d64 100644
*** a/src/backend/optimizer/path/pathkeys.c
--- b/src/backend/optimizer/path/pathkeys.c
***************
*** 1125,1130 **** select_outer_pathkeys_for_merge(PlannerInfo *root,
--- 1125,1131 ----
int nClauses = list_length(mergeclauses);
EquivalenceClass **ecs;
int *scores;
+ bool *range_ecs;
int necs;
ListCell *lc;
int j;
***************
*** 1139,1144 **** select_outer_pathkeys_for_merge(PlannerInfo *root,
--- 1140,1146 ----
*/
ecs = (EquivalenceClass **) palloc(nClauses * sizeof(EquivalenceClass *));
scores = (int *) palloc(nClauses * sizeof(int));
+ range_ecs = palloc(nClauses * sizeof(bool));
necs = 0;
foreach(lc, mergeclauses)
***************
*** 1179,1184 **** select_outer_pathkeys_for_merge(PlannerInfo *root,
--- 1181,1187 ----
ecs[necs] = oeclass;
scores[necs] = score;
+ range_ecs[necs] = rinfo->rangejoin;
necs++;
}
***************
*** 1196,1201 **** select_outer_pathkeys_for_merge(PlannerInfo *root,
--- 1199,1209 ----
for (j = 0; j < necs; j++)
{
+ /* for range join, the input order must be ascending */
+ if (range_ecs[j] &&
+ query_pathkey->pk_strategy != BTLessStrategyNumber)
+ continue;
+
if (ecs[j] == query_ec)
break; /* found match */
}
diff --git a/src/backend/optimizer/plan/initindex ebd442a..86021c0 100644
*** a/src/backend/optimizer/plan/initsplan.c
--- b/src/backend/optimizer/plan/initsplan.c
***************
*** 14,19 ****
--- 14,20 ----
*/
#include "postgres.h"
+ #include "catalog/pg_operator.h"
#include "catalog/pg_type.h"
#include "nodes/nodeFuncs.h"
#include "optimizer/clauses.h"
***************
*** 1940,1946 **** distribute_qual_to_rels(PlannerInfo *root, Node *clause,
*/
if (restrictinfo->mergeopfamilies)
{
! if (maybe_equivalence)
{
if (check_equivalence_delay(root, restrictinfo) &&
process_equivalence(root, restrictinfo, below_outer_join))
--- 1941,1947 ----
*/
if (restrictinfo->mergeopfamilies)
{
! if (maybe_equivalence && !restrictinfo->rangejoin)
{
if (check_equivalence_delay(root, restrictinfo) &&
process_equivalence(root, restrictinfo, below_outer_join))
***************
*** 2594,2599 **** check_mergejoinable(RestrictInfo *restrictinfo)
--- 2595,2606 ----
opno = ((OpExpr *) clause)->opno;
leftarg = linitial(((OpExpr *) clause)->args);
+ if (opno == OID_RANGE_OVERLAP_OP)
+ {
+ restrictinfo->rangejoin = true;
+ opno = OID_RANGE_EQ_OP;
+ }
+
if (op_mergejoinable(opno, exprType(leftarg)) &&
!contain_volatile_functions((Node *) clause))
restrictinfo->mergeopfamilies = get_mergejoin_opfamilies(opno);
diff --git a/src/backend/optimizer/util/restrindex e946290..c2d1a23 100644
*** a/src/backend/optimizer/util/restrictinfo.c
--- b/src/backend/optimizer/util/restrictinfo.c
***************
*** 186,191 **** make_restrictinfo_internal(Expr *clause,
--- 186,192 ----
restrictinfo->outer_selec = -1;
restrictinfo->mergeopfamilies = NIL;
+ restrictinfo->rangejoin = false;
restrictinfo->left_ec = NULL;
restrictinfo->right_ec = NULL;
diff --git a/src/backend/utils/adt/selfuncs.c b/index a35b93b..5c8c69f 100644
*** a/src/backend/utils/adt/selfuncs.c
--- b/src/backend/utils/adt/selfuncs.c
***************
*** 2860,2866 **** mergejoinscansel(PlannerInfo *root, Node *clause,
*right;
VariableStatData leftvar,
rightvar;
- int op_strategy;
Oid op_lefttype;
Oid op_righttype;
Oid opno,
--- 2860,2865 ----
diff --git a/src/include/catalog/pg_opeindex fe8795a..1f1ffb4 100644
*** a/src/include/catalog/pg_operator.h
--- b/src/include/catalog/pg_operator.h
***************
*** 1748,1753 **** DESCR("greater than or equal");
--- 1748,1754 ----
/* generic range type operators */
DATA(insert OID = 3882 ( "=" PGNSP PGUID b t t 3831 3831 16 3882 3883 range_eq eqsel eqjoinsel ));
DESCR("equal");
+ #define OID_RANGE_EQ_OP 3882
DATA(insert OID = 3883 ( "<>" PGNSP PGUID b f f 3831 3831 16 3883 3882 range_ne neqsel neqjoinsel ));
DESCR("not equal");
DATA(insert OID = 3884 ( "<" PGNSP PGUID b f f 3831 3831 16 3887 3886 range_lt rangesel scalarltjoinsel ));
diff --git a/src/include/nodes/plannodesindex 12f9f61..e2b05e9 100644
*** a/src/include/nodes/plannodes.h
--- b/src/include/nodes/plannodes.h
***************
*** 703,708 **** typedef struct MergeJoin
--- 703,709 ----
Oid *mergeCollations; /* per-clause OIDs of collations */
int *mergeStrategies; /* per-clause ordering (ASC or DESC) */
bool *mergeNullsFirst; /* per-clause nulls ordering */
+ bool mergeRangeJoin; /* is this a range merge join? */
} MergeJoin;
/* ----------------
diff --git a/src/include/nodes/relatindex 7a8e2fd..aa16f9a 100644
*** a/src/include/nodes/relation.h
--- b/src/include/nodes/relation.h
***************
*** 1790,1795 **** typedef struct RestrictInfo
--- 1790,1798 ----
/* valid if clause is mergejoinable, else NIL */
List *mergeopfamilies; /* opfamilies containing clause operator */
+ /* is a rangejoin clause? */
+ bool rangejoin;
+
/* cache space for mergeclause processing; NULL if not yet set */
EquivalenceClass *left_ec; /* EquivalenceClass containing lefthand */
EquivalenceClass *right_ec; /* EquivalenceClass containing righthand */
diff --git a/src/test/regress/expecnew file mode 100644
index 0000000..e8fb835
*** /dev/null
--- b/src/test/regress/expected/rangejoin.out
***************
*** 0 ****
--- 1,526 ----
+ create table rangejoin_left(i1 int, ir1 int4range);
+ create table rangejoin_right(i2 int, ir2 int4range);
+ insert into rangejoin_left values
+ (1001, int4range(10, 80)),
+ (1002, int4range(20, 30)),
+ (1003, int4range(21, 25)),
+ (1004, int4range(22, 35)),
+ (1005, int4range(40, 60)),
+ (1006, int4range(50, 60));
+ insert into rangejoin_right values
+ (1000, 'empty'::int4range),
+ (1001, int4range(NULL, 4)),
+ (1002, int4range(10, 12)),
+ (1003, int4range(11, 14)),
+ (1004, int4range(20, 45)),
+ (1005, int4range(24, 28)),
+ (1006, int4range(85, 90));
+ -- simple inner join
+ explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left, rangejoin_right
+ where ir1 && ir2;
+ QUERY PLAN
+ -----------------------------------------------------------
+ Range Merge Join
+ Merge Cond: (rangejoin_left.ir1 && rangejoin_right.ir2)
+ -> Sort
+ Sort Key: rangejoin_left.ir1
+ -> Seq Scan on rangejoin_left
+ -> Sort
+ Sort Key: rangejoin_right.ir2
+ -> Seq Scan on rangejoin_right
+ (8 rows)
+
+ select i1, ir1, i2, ir2
+ from rangejoin_left, rangejoin_right
+ where ir1 && ir2;
+ i1 | ir1 | i2 | ir2
+ ------+---------+------+---------
+ 1001 | [10,80) | 1002 | [10,12)
+ 1001 | [10,80) | 1003 | [11,14)
+ 1001 | [10,80) | 1004 | [20,45)
+ 1001 | [10,80) | 1005 | [24,28)
+ 1002 | [20,30) | 1004 | [20,45)
+ 1002 | [20,30) | 1005 | [24,28)
+ 1003 | [21,25) | 1004 | [20,45)
+ 1003 | [21,25) | 1005 | [24,28)
+ 1004 | [22,35) | 1004 | [20,45)
+ 1004 | [22,35) | 1005 | [24,28)
+ 1005 | [40,60) | 1004 | [20,45)
+ (11 rows)
+
+ -- two predicates
+ explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left inner join rangejoin_right
+ on (i1 = i2 and ir1 && ir2);
+ QUERY PLAN
+ ----------------------------------------------------------------------------------------------------------
+ Range Merge Join
+ Merge Cond: ((rangejoin_left.ir1 && rangejoin_right.ir2) AND (rangejoin_left.i1 = rangejoin_right.i2))
+ -> Sort
+ Sort Key: rangejoin_left.ir1, rangejoin_left.i1
+ -> Seq Scan on rangejoin_left
+ -> Sort
+ Sort Key: rangejoin_right.ir2, rangejoin_right.i2
+ -> Seq Scan on rangejoin_right
+ (8 rows)
+
+ select i1, ir1, i2, ir2
+ from rangejoin_left inner join rangejoin_right
+ on (i1 = i2 and ir1 && ir2);
+ i1 | ir1 | i2 | ir2
+ ------+---------+------+---------
+ 1004 | [22,35) | 1004 | [20,45)
+ (1 row)
+
+ -- left join
+ explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left left join rangejoin_right
+ on (ir1 && ir2);
+ QUERY PLAN
+ -----------------------------------------------------------
+ Range Merge Left Join
+ Merge Cond: (rangejoin_left.ir1 && rangejoin_right.ir2)
+ -> Sort
+ Sort Key: rangejoin_left.ir1
+ -> Seq Scan on rangejoin_left
+ -> Sort
+ Sort Key: rangejoin_right.ir2
+ -> Seq Scan on rangejoin_right
+ (8 rows)
+
+ select i1, ir1, i2, ir2
+ from rangejoin_left left join rangejoin_right
+ on (ir1 && ir2);
+ i1 | ir1 | i2 | ir2
+ ------+---------+------+---------
+ 1001 | [10,80) | 1002 | [10,12)
+ 1001 | [10,80) | 1003 | [11,14)
+ 1001 | [10,80) | 1004 | [20,45)
+ 1001 | [10,80) | 1005 | [24,28)
+ 1002 | [20,30) | 1004 | [20,45)
+ 1002 | [20,30) | 1005 | [24,28)
+ 1003 | [21,25) | 1004 | [20,45)
+ 1003 | [21,25) | 1005 | [24,28)
+ 1004 | [22,35) | 1004 | [20,45)
+ 1004 | [22,35) | 1005 | [24,28)
+ 1005 | [40,60) | 1004 | [20,45)
+ 1006 | [50,60) | |
+ (12 rows)
+
+ -- right join should be implemented as left join
+ explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left right join rangejoin_right
+ on (ir1 && ir2);
+ QUERY PLAN
+ -----------------------------------------------------------
+ Range Merge Left Join
+ Merge Cond: (rangejoin_right.ir2 && rangejoin_left.ir1)
+ -> Sort
+ Sort Key: rangejoin_right.ir2
+ -> Seq Scan on rangejoin_right
+ -> Sort
+ Sort Key: rangejoin_left.ir1
+ -> Seq Scan on rangejoin_left
+ (8 rows)
+
+ -- full join doesn't support range join
+ explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left full join rangejoin_right
+ on (ir1 && ir2);
+ ERROR: FULL JOIN is only supported with merge-joinable or hash-joinable join conditions
+ -- range input to range join must be ascending
+ explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left inner join rangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 desc, i1;
+ QUERY PLAN
+ ----------------------------------------------------------------------------------------------------------------
+ Sort
+ Sort Key: rangejoin_left.ir1 DESC, rangejoin_left.i1
+ -> Range Merge Join
+ Merge Cond: ((rangejoin_left.ir1 && rangejoin_right.ir2) AND (rangejoin_left.i1 = rangejoin_right.i2))
+ -> Sort
+ Sort Key: rangejoin_left.ir1, rangejoin_left.i1
+ -> Seq Scan on rangejoin_left
+ -> Sort
+ Sort Key: rangejoin_right.ir2, rangejoin_right.i2
+ -> Seq Scan on rangejoin_right
+ (10 rows)
+
+ -- but it's OK for non-range inputs to be descending
+ explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left inner join rangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 nulls first, i1 desc;
+ QUERY PLAN
+ ----------------------------------------------------------------------------------------------------------
+ Range Merge Join
+ Merge Cond: ((rangejoin_left.ir1 && rangejoin_right.ir2) AND (rangejoin_left.i1 = rangejoin_right.i2))
+ -> Sort
+ Sort Key: rangejoin_left.ir1 NULLS FIRST, rangejoin_left.i1 DESC
+ -> Seq Scan on rangejoin_left
+ -> Sort
+ Sort Key: rangejoin_right.ir2 NULLS FIRST, rangejoin_right.i2 DESC
+ -> Seq Scan on rangejoin_right
+ (8 rows)
+
+ select i1, ir1, i2, ir2
+ from rangejoin_left inner join rangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 nulls first, i1 desc;
+ i1 | ir1 | i2 | ir2
+ ------+---------+------+---------
+ 1004 | [22,35) | 1004 | [20,45)
+ (1 row)
+
+ drop table rangejoin_left;
+ drop table rangejoin_right;
+ create table multirangejoin_left (ir1 int4range, ir2 int4range);
+ create table multirangejoin_right (ir3 int4range, ir4 int4range);
+ insert into multirangejoin_left values
+ (int4range(30,99), int4range(20,30)),
+ (int4range(2,40), int4range(15,27)),
+ (int4range(61,99), int4range(20,45)),
+ (int4range(22,32), int4range(21,66)),
+ (int4range(36,71), int4range(45,49)),
+ (int4range(9,80), int4range(2,4));
+ insert into multirangejoin_right values
+ (int4range(9,70), int4range(10,78)),
+ (int4range(21,37), int4range(89,99)),
+ (int4range(5,98), int4range(35,97)),
+ (int4range(12,17), int4range(81,92)),
+ (int4range(15,19), int4range(5,55)),
+ (int4range(57,58), int4range(42,80));
+ explain (costs off) select *
+ from multirangejoin_left inner join multirangejoin_right
+ on (ir1 && ir3 and ir2 && ir4) order by ir1, ir2, ir3, ir4;
+ QUERY PLAN
+ ---------------------------------------------------------------------------------------------------------------------------------------
+ Sort
+ Sort Key: multirangejoin_left.ir1, multirangejoin_left.ir2, multirangejoin_right.ir3, multirangejoin_right.ir4
+ -> Range Merge Join
+ Merge Cond: ((multirangejoin_left.ir1 && multirangejoin_right.ir3) AND (multirangejoin_left.ir2 && multirangejoin_right.ir4))
+ -> Sort
+ Sort Key: multirangejoin_left.ir1, multirangejoin_left.ir2
+ -> Seq Scan on multirangejoin_left
+ -> Sort
+ Sort Key: multirangejoin_right.ir3, multirangejoin_right.ir4
+ -> Seq Scan on multirangejoin_right
+ (10 rows)
+
+ select *
+ from multirangejoin_left inner join multirangejoin_right
+ on (ir1 && ir3 and ir2 && ir4) order by ir1, ir2, ir3, ir4;
+ ir1 | ir2 | ir3 | ir4
+ ---------+---------+---------+---------
+ [2,40) | [15,27) | [9,70) | [10,78)
+ [2,40) | [15,27) | [15,19) | [5,55)
+ [22,32) | [21,66) | [5,98) | [35,97)
+ [22,32) | [21,66) | [9,70) | [10,78)
+ [30,99) | [20,30) | [9,70) | [10,78)
+ [36,71) | [45,49) | [5,98) | [35,97)
+ [36,71) | [45,49) | [9,70) | [10,78)
+ [36,71) | [45,49) | [57,58) | [42,80)
+ [61,99) | [20,45) | [5,98) | [35,97)
+ [61,99) | [20,45) | [9,70) | [10,78)
+ (10 rows)
+
+ set enable_mergejoin=false;
+ explain (costs off) select *
+ from multirangejoin_left inner join multirangejoin_right
+ on (ir1 && ir3 and ir2 && ir4) order by ir1, ir2, ir3, ir4;
+ QUERY PLAN
+ ----------------------------------------------------------------------------------------------------------------------------------------
+ Sort
+ Sort Key: multirangejoin_left.ir1, multirangejoin_left.ir2, multirangejoin_right.ir3, multirangejoin_right.ir4
+ -> Nested Loop
+ Join Filter: ((multirangejoin_left.ir1 && multirangejoin_right.ir3) AND (multirangejoin_left.ir2 && multirangejoin_right.ir4))
+ -> Seq Scan on multirangejoin_left
+ -> Materialize
+ -> Seq Scan on multirangejoin_right
+ (7 rows)
+
+ select *
+ from multirangejoin_left inner join multirangejoin_right
+ on (ir1 && ir3 and ir2 && ir4) order by ir1, ir2, ir3, ir4;
+ ir1 | ir2 | ir3 | ir4
+ ---------+---------+---------+---------
+ [2,40) | [15,27) | [9,70) | [10,78)
+ [2,40) | [15,27) | [15,19) | [5,55)
+ [22,32) | [21,66) | [5,98) | [35,97)
+ [22,32) | [21,66) | [9,70) | [10,78)
+ [30,99) | [20,30) | [9,70) | [10,78)
+ [36,71) | [45,49) | [5,98) | [35,97)
+ [36,71) | [45,49) | [9,70) | [10,78)
+ [36,71) | [45,49) | [57,58) | [42,80)
+ [61,99) | [20,45) | [5,98) | [35,97)
+ [61,99) | [20,45) | [9,70) | [10,78)
+ (10 rows)
+
+ set enable_mergejoin=true;
+ explain (costs off) select *
+ from multirangejoin_left left join multirangejoin_right
+ on (ir1 && ir4 and ir2 && ir3) order by ir4, ir3, ir2, ir1;
+ QUERY PLAN
+ ---------------------------------------------------------------------------------------------------------------------------------------
+ Sort
+ Sort Key: multirangejoin_right.ir4, multirangejoin_right.ir3, multirangejoin_left.ir2, multirangejoin_left.ir1
+ -> Range Merge Left Join
+ Merge Cond: ((multirangejoin_left.ir1 && multirangejoin_right.ir4) AND (multirangejoin_left.ir2 && multirangejoin_right.ir3))
+ -> Sort
+ Sort Key: multirangejoin_left.ir1, multirangejoin_left.ir2
+ -> Seq Scan on multirangejoin_left
+ -> Sort
+ Sort Key: multirangejoin_right.ir4, multirangejoin_right.ir3
+ -> Seq Scan on multirangejoin_right
+ (10 rows)
+
+ select *
+ from multirangejoin_left left join multirangejoin_right
+ on (ir1 && ir4 and ir2 && ir3) order by ir4, ir3, ir2, ir1;
+ ir1 | ir2 | ir3 | ir4
+ ---------+---------+---------+---------
+ [2,40) | [15,27) | [15,19) | [5,55)
+ [2,40) | [15,27) | [9,70) | [10,78)
+ [30,99) | [20,30) | [9,70) | [10,78)
+ [61,99) | [20,45) | [9,70) | [10,78)
+ [22,32) | [21,66) | [9,70) | [10,78)
+ [36,71) | [45,49) | [9,70) | [10,78)
+ [2,40) | [15,27) | [5,98) | [35,97)
+ [30,99) | [20,30) | [5,98) | [35,97)
+ [61,99) | [20,45) | [5,98) | [35,97)
+ [36,71) | [45,49) | [5,98) | [35,97)
+ [30,99) | [20,30) | [21,37) | [89,99)
+ [61,99) | [20,45) | [21,37) | [89,99)
+ [9,80) | [2,4) | |
+ (13 rows)
+
+ set enable_mergejoin=false;
+ explain (costs off) select *
+ from multirangejoin_left left join multirangejoin_right
+ on (ir1 && ir4 and ir2 && ir3) order by ir4, ir3, ir2, ir1;
+ QUERY PLAN
+ ----------------------------------------------------------------------------------------------------------------------------------------
+ Sort
+ Sort Key: multirangejoin_right.ir4, multirangejoin_right.ir3, multirangejoin_left.ir2, multirangejoin_left.ir1
+ -> Nested Loop Left Join
+ Join Filter: ((multirangejoin_left.ir1 && multirangejoin_right.ir4) AND (multirangejoin_left.ir2 && multirangejoin_right.ir3))
+ -> Seq Scan on multirangejoin_left
+ -> Materialize
+ -> Seq Scan on multirangejoin_right
+ (7 rows)
+
+ select *
+ from multirangejoin_left left join multirangejoin_right
+ on (ir1 && ir4 and ir2 && ir3) order by ir4, ir3, ir2, ir1;
+ ir1 | ir2 | ir3 | ir4
+ ---------+---------+---------+---------
+ [2,40) | [15,27) | [15,19) | [5,55)
+ [2,40) | [15,27) | [9,70) | [10,78)
+ [30,99) | [20,30) | [9,70) | [10,78)
+ [61,99) | [20,45) | [9,70) | [10,78)
+ [22,32) | [21,66) | [9,70) | [10,78)
+ [36,71) | [45,49) | [9,70) | [10,78)
+ [2,40) | [15,27) | [5,98) | [35,97)
+ [30,99) | [20,30) | [5,98) | [35,97)
+ [61,99) | [20,45) | [5,98) | [35,97)
+ [36,71) | [45,49) | [5,98) | [35,97)
+ [30,99) | [20,30) | [21,37) | [89,99)
+ [61,99) | [20,45) | [21,37) | [89,99)
+ [9,80) | [2,4) | |
+ (13 rows)
+
+ set enable_mergejoin=true;
+ drop table multirangejoin_left;
+ drop table multirangejoin_right;
+ create table bigrangejoin_left (i1 int, ir1 int4range);
+ create table bigrangejoin_right (i2 int, ir2 int4range);
+ -- 100 small ranges
+ insert into bigrangejoin_left
+ select g/4,
+ int4range(g,
+ g + case when (g%2=0) then g%7 else 12-(g%11) end)
+ from generate_series(1,100) g;
+ insert into bigrangejoin_right
+ select g/4,
+ int4range(g-7+(g%19),
+ g-7+(g%19) + case when (g%3=0) then g%11 else 17-(g%15) end)
+ from generate_series(1,100) g;
+ -- 10 medium ranges
+ insert into bigrangejoin_left
+ select g/4*10,
+ int4range(g*10,
+ g*10 + case when (g%2=0) then g%7 else 12-(g%11) end)
+ from generate_series(1,10) g;
+ insert into bigrangejoin_right
+ select g/4*10,
+ int4range(g*10-57+(g%173),
+ g*10-57+(g%173) + case when (g%3=0) then g%123 else 97-(g%83) end)
+ from generate_series(1,10) g;
+ insert into bigrangejoin_left select g*11-21, 'empty'::int4range
+ from generate_series(1,9) g;
+ insert into bigrangejoin_right select g*13-29, 'empty'::int4range
+ from generate_series(1,8) g;
+ insert into bigrangejoin_left values
+ (4, int4range(NULL,5)),
+ (93, int4range(95, NULL));
+ insert into bigrangejoin_right values
+ (7, int4range(NULL,3)),
+ (92, int4range(99, NULL));
+ create temp table rangejoin_result1
+ (i1 int, ir1 int4range, i2 int, ir2 int4range);
+ create temp table rangejoin_result2
+ (i1 int, ir1 int4range, i2 int, ir2 int4range);
+ set enable_hashjoin=false;
+ explain (costs off) insert into rangejoin_result1
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left left join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 nulls first, i1 desc;
+ QUERY PLAN
+ ----------------------------------------------------------------------------------------------------------------------------
+ Insert on rangejoin_result1
+ -> Range Merge Left Join
+ Merge Cond: ((bigrangejoin_left.ir1 && bigrangejoin_right.ir2) AND (bigrangejoin_left.i1 = bigrangejoin_right.i2))
+ -> Sort
+ Sort Key: bigrangejoin_left.ir1 NULLS FIRST, bigrangejoin_left.i1 DESC
+ -> Seq Scan on bigrangejoin_left
+ -> Sort
+ Sort Key: bigrangejoin_right.ir2 NULLS FIRST, bigrangejoin_right.i2 DESC
+ -> Seq Scan on bigrangejoin_right
+ (9 rows)
+
+ insert into rangejoin_result1
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left left join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 nulls first, i1 desc;
+ set enable_hashjoin=true;
+ set enable_mergejoin=false;
+ explain (costs off) insert into rangejoin_result2
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left left join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 nulls first, i1 desc;
+ QUERY PLAN
+ --------------------------------------------------------------------------------
+ Insert on rangejoin_result2
+ -> Sort
+ Sort Key: bigrangejoin_left.ir1 NULLS FIRST, bigrangejoin_left.i1 DESC
+ -> Hash Left Join
+ Hash Cond: (bigrangejoin_left.i1 = bigrangejoin_right.i2)
+ Join Filter: (bigrangejoin_left.ir1 && bigrangejoin_right.ir2)
+ -> Seq Scan on bigrangejoin_left
+ -> Hash
+ -> Seq Scan on bigrangejoin_right
+ (9 rows)
+
+ insert into rangejoin_result2
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left left join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 nulls first, i1 desc;
+ set enable_mergejoin=true;
+ select count(*) from rangejoin_result1;
+ count
+ -------
+ 292
+ (1 row)
+
+ select count(*) from rangejoin_result2;
+ count
+ -------
+ 292
+ (1 row)
+
+ select * from rangejoin_result1 except select * from rangejoin_result2;
+ i1 | ir1 | i2 | ir2
+ ----+-----+----+-----
+ (0 rows)
+
+ select * from rangejoin_result2 except select * from rangejoin_result1;
+ i1 | ir1 | i2 | ir2
+ ----+-----+----+-----
+ (0 rows)
+
+ drop table rangejoin_result1;
+ drop table rangejoin_result2;
+ create temp table rangejoin_result3
+ (i1 int, ir1 int4range, i2 int, ir2 int4range);
+ create temp table rangejoin_result4
+ (i1 int, ir1 int4range, i2 int, ir2 int4range);
+ explain (costs off) insert into rangejoin_result3
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left inner join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by i1, ir1;
+ QUERY PLAN
+ ----------------------------------------------------------------------------------------------------------------------------
+ Insert on rangejoin_result3
+ -> Range Merge Join
+ Merge Cond: ((bigrangejoin_left.i1 = bigrangejoin_right.i2) AND (bigrangejoin_left.ir1 && bigrangejoin_right.ir2))
+ -> Sort
+ Sort Key: bigrangejoin_left.i1, bigrangejoin_left.ir1
+ -> Seq Scan on bigrangejoin_left
+ -> Sort
+ Sort Key: bigrangejoin_right.i2, bigrangejoin_right.ir2
+ -> Seq Scan on bigrangejoin_right
+ (9 rows)
+
+ insert into rangejoin_result3
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left inner join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by i1, ir1;
+ set enable_mergejoin=false;
+ explain (costs off) insert into rangejoin_result4
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left inner join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by i1, ir1;
+ QUERY PLAN
+ ------------------------------------------------------------------------------
+ Insert on rangejoin_result4
+ -> Sort
+ Sort Key: bigrangejoin_left.i1, bigrangejoin_left.ir1
+ -> Hash Join
+ Hash Cond: (bigrangejoin_left.i1 = bigrangejoin_right.i2)
+ Join Filter: (bigrangejoin_left.ir1 && bigrangejoin_right.ir2)
+ -> Seq Scan on bigrangejoin_left
+ -> Hash
+ -> Seq Scan on bigrangejoin_right
+ (9 rows)
+
+ insert into rangejoin_result4
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left inner join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by i1, ir1;
+ set enable_mergejoin=true;
+ select count(*) from rangejoin_result3;
+ count
+ -------
+ 259
+ (1 row)
+
+ select count(*) from rangejoin_result4;
+ count
+ -------
+ 259
+ (1 row)
+
+ select * from rangejoin_result3 except select * from rangejoin_result4;
+ i1 | ir1 | i2 | ir2
+ ----+-----+----+-----
+ (0 rows)
+
+ select * from rangejoin_result4 except select * from rangejoin_result3;
+ i1 | ir1 | i2 | ir2
+ ----+-----+----+-----
+ (0 rows)
+
+ drop table rangejoin_result3;
+ drop table rangejoin_result4;
+ drop table bigrangejoin_left;
+ drop table bigrangejoin_right;
diff --git a/src/test/regress/parallel_schedulindex 1f8f098..4f70bb0 100644
*** a/src/test/regress/parallel_schedule
--- b/src/test/regress/parallel_schedule
***************
*** 109,115 **** test: select_views portals_p2 foreign_key cluster dependency guc bitmapops combo
# NB: temp.sql does a reconnect which transiently uses 2 connections,
# so keep this parallel group to at most 19 tests
# ----------
! test: plancache limit plpgsql copy2 temp domain rangefuncs prepare without_oid conversion truncate alter_table sequence polymorphism rowtypes returning largeobject with xml
# ----------
# Another group of parallel tests
--- 109,115 ----
# NB: temp.sql does a reconnect which transiently uses 2 connections,
# so keep this parallel group to at most 19 tests
# ----------
! test: plancache limit plpgsql copy2 temp domain rangefuncs rangejoin prepare without_oid conversion truncate alter_table sequence polymorphism rowtypes returning largeobject with xml
# ----------
# Another group of parallel tests
diff --git a/src/test/regress/serial_scheindex 04206c3..659dc4a 100644
*** a/src/test/regress/serial_schedule
--- b/src/test/regress/serial_schedule
***************
*** 164,169 **** test: copy2
--- 164,170 ----
test: temp
test: domain
test: rangefuncs
+ test: rangejoin
test: prepare
test: without_oid
test: conversion
diff --git a/src/test/regress/sql/rangenew file mode 100644
index 0000000..e1849aa
*** /dev/null
--- b/src/test/regress/sql/rangejoin.sql
***************
*** 0 ****
--- 1,265 ----
+
+ create table rangejoin_left(i1 int, ir1 int4range);
+ create table rangejoin_right(i2 int, ir2 int4range);
+
+ insert into rangejoin_left values
+ (1001, int4range(10, 80)),
+ (1002, int4range(20, 30)),
+ (1003, int4range(21, 25)),
+ (1004, int4range(22, 35)),
+ (1005, int4range(40, 60)),
+ (1006, int4range(50, 60));
+
+ insert into rangejoin_right values
+ (1000, 'empty'::int4range),
+ (1001, int4range(NULL, 4)),
+ (1002, int4range(10, 12)),
+ (1003, int4range(11, 14)),
+ (1004, int4range(20, 45)),
+ (1005, int4range(24, 28)),
+ (1006, int4range(85, 90));
+
+ -- simple inner join
+ explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left, rangejoin_right
+ where ir1 && ir2;
+
+ select i1, ir1, i2, ir2
+ from rangejoin_left, rangejoin_right
+ where ir1 && ir2;
+
+ -- two predicates
+ explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left inner join rangejoin_right
+ on (i1 = i2 and ir1 && ir2);
+
+ select i1, ir1, i2, ir2
+ from rangejoin_left inner join rangejoin_right
+ on (i1 = i2 and ir1 && ir2);
+
+ -- left join
+ explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left left join rangejoin_right
+ on (ir1 && ir2);
+
+ select i1, ir1, i2, ir2
+ from rangejoin_left left join rangejoin_right
+ on (ir1 && ir2);
+
+ -- right join should be implemented as left join
+ explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left right join rangejoin_right
+ on (ir1 && ir2);
+
+ -- full join doesn't support range join
+ explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left full join rangejoin_right
+ on (ir1 && ir2);
+
+ -- range input to range join must be ascending
+ explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left inner join rangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 desc, i1;
+
+ -- but it's OK for non-range inputs to be descending
+ explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left inner join rangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 nulls first, i1 desc;
+
+ select i1, ir1, i2, ir2
+ from rangejoin_left inner join rangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 nulls first, i1 desc;
+
+ drop table rangejoin_left;
+ drop table rangejoin_right;
+
+ create table multirangejoin_left (ir1 int4range, ir2 int4range);
+ create table multirangejoin_right (ir3 int4range, ir4 int4range);
+
+ insert into multirangejoin_left values
+ (int4range(30,99), int4range(20,30)),
+ (int4range(2,40), int4range(15,27)),
+ (int4range(61,99), int4range(20,45)),
+ (int4range(22,32), int4range(21,66)),
+ (int4range(36,71), int4range(45,49)),
+ (int4range(9,80), int4range(2,4));
+
+
+ insert into multirangejoin_right values
+ (int4range(9,70), int4range(10,78)),
+ (int4range(21,37), int4range(89,99)),
+ (int4range(5,98), int4range(35,97)),
+ (int4range(12,17), int4range(81,92)),
+ (int4range(15,19), int4range(5,55)),
+ (int4range(57,58), int4range(42,80));
+
+ explain (costs off) select *
+ from multirangejoin_left inner join multirangejoin_right
+ on (ir1 && ir3 and ir2 && ir4) order by ir1, ir2, ir3, ir4;
+
+ select *
+ from multirangejoin_left inner join multirangejoin_right
+ on (ir1 && ir3 and ir2 && ir4) order by ir1, ir2, ir3, ir4;
+
+ set enable_mergejoin=false;
+ explain (costs off) select *
+ from multirangejoin_left inner join multirangejoin_right
+ on (ir1 && ir3 and ir2 && ir4) order by ir1, ir2, ir3, ir4;
+
+ select *
+ from multirangejoin_left inner join multirangejoin_right
+ on (ir1 && ir3 and ir2 && ir4) order by ir1, ir2, ir3, ir4;
+ set enable_mergejoin=true;
+
+ explain (costs off) select *
+ from multirangejoin_left left join multirangejoin_right
+ on (ir1 && ir4 and ir2 && ir3) order by ir4, ir3, ir2, ir1;
+
+ select *
+ from multirangejoin_left left join multirangejoin_right
+ on (ir1 && ir4 and ir2 && ir3) order by ir4, ir3, ir2, ir1;
+
+ set enable_mergejoin=false;
+ explain (costs off) select *
+ from multirangejoin_left left join multirangejoin_right
+ on (ir1 && ir4 and ir2 && ir3) order by ir4, ir3, ir2, ir1;
+
+ select *
+ from multirangejoin_left left join multirangejoin_right
+ on (ir1 && ir4 and ir2 && ir3) order by ir4, ir3, ir2, ir1;
+ set enable_mergejoin=true;
+
+ drop table multirangejoin_left;
+ drop table multirangejoin_right;
+
+ create table bigrangejoin_left (i1 int, ir1 int4range);
+ create table bigrangejoin_right (i2 int, ir2 int4range);
+
+ -- 100 small ranges
+ insert into bigrangejoin_left
+ select g/4,
+ int4range(g,
+ g + case when (g%2=0) then g%7 else 12-(g%11) end)
+ from generate_series(1,100) g;
+ insert into bigrangejoin_right
+ select g/4,
+ int4range(g-7+(g%19),
+ g-7+(g%19) + case when (g%3=0) then g%11 else 17-(g%15) end)
+ from generate_series(1,100) g;
+
+ -- 10 medium ranges
+ insert into bigrangejoin_left
+ select g/4*10,
+ int4range(g*10,
+ g*10 + case when (g%2=0) then g%7 else 12-(g%11) end)
+ from generate_series(1,10) g;
+ insert into bigrangejoin_right
+ select g/4*10,
+ int4range(g*10-57+(g%173),
+ g*10-57+(g%173) + case when (g%3=0) then g%123 else 97-(g%83) end)
+ from generate_series(1,10) g;
+
+ insert into bigrangejoin_left select g*11-21, 'empty'::int4range
+ from generate_series(1,9) g;
+
+ insert into bigrangejoin_right select g*13-29, 'empty'::int4range
+ from generate_series(1,8) g;
+
+ insert into bigrangejoin_left values
+ (4, int4range(NULL,5)),
+ (93, int4range(95, NULL));
+
+ insert into bigrangejoin_right values
+ (7, int4range(NULL,3)),
+ (92, int4range(99, NULL));
+
+ create temp table rangejoin_result1
+ (i1 int, ir1 int4range, i2 int, ir2 int4range);
+ create temp table rangejoin_result2
+ (i1 int, ir1 int4range, i2 int, ir2 int4range);
+
+ set enable_hashjoin=false;
+ explain (costs off) insert into rangejoin_result1
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left left join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 nulls first, i1 desc;
+
+ insert into rangejoin_result1
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left left join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 nulls first, i1 desc;
+ set enable_hashjoin=true;
+
+ set enable_mergejoin=false;
+ explain (costs off) insert into rangejoin_result2
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left left join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 nulls first, i1 desc;
+
+ insert into rangejoin_result2
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left left join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 nulls first, i1 desc;
+ set enable_mergejoin=true;
+
+ select count(*) from rangejoin_result1;
+ select count(*) from rangejoin_result2;
+
+ select * from rangejoin_result1 except select * from rangejoin_result2;
+
+ select * from rangejoin_result2 except select * from rangejoin_result1;
+
+ drop table rangejoin_result1;
+ drop table rangejoin_result2;
+
+ create temp table rangejoin_result3
+ (i1 int, ir1 int4range, i2 int, ir2 int4range);
+ create temp table rangejoin_result4
+ (i1 int, ir1 int4range, i2 int, ir2 int4range);
+
+
+ explain (costs off) insert into rangejoin_result3
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left inner join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by i1, ir1;
+
+ insert into rangejoin_result3
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left inner join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by i1, ir1;
+
+ set enable_mergejoin=false;
+ explain (costs off) insert into rangejoin_result4
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left inner join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by i1, ir1;
+
+ insert into rangejoin_result4
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left inner join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by i1, ir1;
+ set enable_mergejoin=true;
+
+ select count(*) from rangejoin_result3;
+ select count(*) from rangejoin_result4;
+
+ select * from rangejoin_result3 except select * from rangejoin_result4;
+
+ select * from rangejoin_result4 except select * from rangejoin_result3;
+
+ drop table rangejoin_result3;
+ drop table rangejoin_result4;
+
+ drop table bigrangejoin_left;
+ drop table bigrangejoin_right;
Re: Range Merge Join v1
On Thu, Apr 6, 2017 at 2:13 PM, Jeff Davis <pgsql@j-davis.com> wrote:
========
Example:
========Find different people using the same website at the same time:
create table session(sessionid text, username text, during tstzrange);
SELECT s1.username, s2.username, s1.during * s2.during
FROM session s1, session s2
WHERE s1.during && s2.during AND s1.username < s2.username=====================================
Brief summary of previous discussion:
=====================================/messages/by-id/1334554850.10878.52.camel@jdavis
- can indexes solve it already (parameterized paths, etc.)?
- planner complexity (track path keys, mergejoinable equality, etc.)
- spatial join algorithm choice
- compare range merge join against existing indexes to see if any
indexing approach is viable==========
Externals:
==========No new syntax or other externals. Just improved execution strategy for
joining ranges using the overlaps operator (&&).New syntax is possible, but I don't see a strong reason to support
special range join syntax at this time.=============
Optimizer Design
=============I took the path of least resistance, so if I am doing something wrong
please let me know. I hardwired it to look for the range overlaps
operator when checking if it could do a merge join, and then add
range_ops to restrictinfo->mergeopfamilies.Then, I have to suppress adding it as an equivalence class, because
overlaps is not equality. It still adds single-member ECs to
restrictinfo->right_ec and left_ec, but (I think) that's OK.Also, I have to prevent generating paths for right/full join, because
the range join algorithm can't (currently) handle those.=============
Costing
=============Needs more consideration. Seems to do reasonable things in the few
examples I tried.=============
Executor Design
=============See detailed comments in nodeMergejoin.c
=============
Performance
=============Seems much better than index nest loop join when the join is not
selective. I will post detailed numbers soon.If no index is available, range merge join is the only reasonable way
to execute a range join. For instance, if the inner is not a leaf in
the plan.=============
Alternatives:
=============It was suggested that I approach it as a general spatial-join
problem. That has merit, but I rejected it for now because the
algorithm that I think has the most promise is range-oriented
anyway. By that I mean we would need to extract all of the dimensions
into ranges first, and then perform the join. With that in mind, it
makes sense to implement range joins first; and then later provide the
APIs to get at the spatial dimensions so that we can implement other
spatial joins as range joins.Another suggestion was to base it on hash join, but I never understood
that proposal and it didn't seem to map very well to a spatial join.Yet another suggestion was to use some kind of temporary index. Some
brief experiments I did indicated that it would be fairly slow (though
more investigation might be useful here). Also, it doesn't provide any
alternative to the nestloop-with-inner-index we already offer at the
leaf level today.Regards,
Jeff Davis
Looks like an interesting idea, however, in an attempt to test this patch I
found following error when compiling,
selfuncs.c: In function ‘mergejoinscansel’:
selfuncs.c:2901:12: error: ‘op_strategy’ undeclared (first use in this
function)
&op_strategy,
--
Regards,
Rafia Sabih
EnterpriseDB: http://www.enterprisedb.com/
Re: Range Merge Join v1
On Thu, Apr 20, 2017 at 2:05 AM, Rafia Sabih
<rafia.sabih@enterprisedb.com> wrote:
Looks like an interesting idea, however, in an attempt to test this patch I
found following error when compiling,
selfuncs.c: In function ‘mergejoinscansel’:
selfuncs.c:2901:12: error: ‘op_strategy’ undeclared (first use in this
function)
&op_strategy,
Looks like filterdiff destroyed my patch from git. Attaching unified
version against master 3820c63d.
Thanks!
Jeff Davis
Attachments:
rangejoin-v2.unified.patchtext/x-patch; charset=US-ASCII; name=rangejoin-v2.unified.patchDownload
diff --git a/doc/src/sgml/rangetypes.sgml b/doc/src/sgml/rangetypes.sgml
index 9557c16..84578a7 100644
--- a/doc/src/sgml/rangetypes.sgml
+++ b/doc/src/sgml/rangetypes.sgml
@@ -522,4 +522,74 @@ INSERT 0 1
</programlisting>
</para>
</sect2>
+ <sect2 id="rangetypes-join">
+ <title>Range Join</title>
+
+ <indexterm>
+ <primary>range type</primary>
+ <secondary>join</secondary>
+ </indexterm>
+
+ <para>
+ A Range Join is a join where one of the join conditions is the range
+ overlaps operator (see <xref linkend="range-operators-table">). In other
+ words, rather than returning rows where corresponding fields are equal, it
+ returns rows where the corresponding fields overlap.
+ </para>
+ <para>
+ For instance, to find users who were active on a website at the same time
+ as they were using a mobile app, you might issue a query like:
+<programlisting>
+CREATE TABLE web_session(
+ web_session_id text primary key,
+ username text,
+ during tstzrange);
+CREATE TABLE app_session(
+ app_session_id text primary key,
+ username text,
+ during tstzrange);
+INSERT INTO web_session VALUES
+ ('0cc175b9c0f1b6a8', 'user1', '[2017-02-01 09:30, 2017-02-01 10:45)'),
+ ('92eb5ffee6ae2fec', 'user2', '[2017-02-01 09:30, 2017-02-01 10:45)'),
+ ('4a8a08f09d37b737', 'user3', '[2017-02-01 09:30, 2017-02-01 10:45)');
+INSERT INTO app_session VALUES
+ ('8277e0910d750195', 'user1', '[2017-02-01 10:30, 2017-02-01 11:45)'),
+ ('b448797616e091ad', 'user3', '[2017-02-01 09:00, 2017-02-01 11:00)'),
+ ('95649038408b5f33', 'user4', '[2017-02-01 09:30, 2017-02-01 10:45)');
+
+SELECT w.username,
+ w.during * a.during AS both_during
+ FROM web_session w, app_session a
+ WHERE w.username = a.username
+ AND w.during && a.during;
+ username | both_during
+----------+-----------------------------------------------------
+ user1 | ["2017-02-01 10:30:00-08","2017-02-01 10:45:00-08")
+ user3 | ["2017-02-01 09:30:00-08","2017-02-01 10:45:00-08")
+(2 rows)
+</programlisting>
+ </para>
+ <para>
+ In addition to the general execution strategies available, Postgres also
+ has special support for a variant of Merge Join called Range Merge Join:
+<programlisting>
+ EXPLAIN (costs off) SELECT w.username,
+ w.during * a.during AS both_during
+ FROM web_session w, app_session a
+ WHERE w.username = a.username
+ AND w.during && a.during;
+ QUERY PLAN
+----------------------------------------------------------------------
+ Range Merge Join
+ Merge Cond: ((w.during && a.during) AND (w.username = a.username))
+ -> Sort
+ Sort Key: w.during, w.username
+ -> Seq Scan on web_session w
+ -> Sort
+ Sort Key: a.during, a.username
+ -> Seq Scan on app_session a
+(8 rows)
+</programlisting>
+ </para>
+ </sect2>
</sect1>
diff --git a/src/backend/commands/explain.c b/src/backend/commands/explain.c
index 9359d0a..1010668 100644
--- a/src/backend/commands/explain.c
+++ b/src/backend/commands/explain.c
@@ -909,7 +909,11 @@ ExplainNode(PlanState *planstate, List *ancestors,
pname = sname = "Nested Loop";
break;
case T_MergeJoin:
- pname = "Merge"; /* "Join" gets added by jointype switch */
+ if (((MergeJoin*)plan)->mergeRangeJoin)
+ pname = "Range Merge"; /* "Join" gets added by jointype switch */
+ else
+ pname = "Merge"; /* "Join" gets added by jointype switch */
+
sname = "Merge Join";
break;
case T_HashJoin:
diff --git a/src/backend/executor/nodeMergejoin.c b/src/backend/executor/nodeMergejoin.c
index 8c483bf..bd312e6 100644
--- a/src/backend/executor/nodeMergejoin.c
+++ b/src/backend/executor/nodeMergejoin.c
@@ -89,14 +89,67 @@
* proceed to another state. This state is stored in the node's
* execution state information and is preserved across calls to
* ExecMergeJoin. -cim 10/31/89
+ *
+ * RANGE MERGE JOIN
+ *
+ * Range Merge Join is a generalization of merge join. When a join
+ * predicate involves the range overlaps operator (&&), a merge join
+ * becomes a range join.
+ *
+ * The input ranges must be ordered by (lower-bound, upper-bound), which
+ * is the ordinary range_ops operator class. MJCompare must not simply
+ * use the operator class's comparison semantics though; instead it
+ * follows these rules:
+ *
+ * - return 0 if the outer range overlaps the inner range
+ * - return <0 if the outer range is strictly left-of the inner range
+ * - return >0 if the outer range is strictly right-of the inner range
+ *
+ * NB: the above is a simplification considering only a single merge
+ * clause. When there are multiple merge clauses, it's possible that one
+ * tuple is neither right-of, nor left-of, nor matching. For instance, if
+ * an earlier range merge clause matches (overlaps), but a later clause
+ * fails. In that case, MJCompare returns 0 but sets "noMatch=true". See
+ * MJCompare.
+ *
+ * If MJCompare returns >0, later or earlier tuples on the inner side may
+ * match. For example:
+ *
+ * OUTER INNER
+ * ... [1,9] matches current outer
+ * [4,5] [2,3] no match
+ * ... [3,5] matches current outer
+ * ... [7,9] no match and no later matches for current outer
+ *
+ * Outer tuple [4,5] does not match [2,3], but it matches (overlaps with)
+ * the earlier tuple [1,9] and the later tuple [3,5]. But once we
+ * encounter [7,9], we know that no later inner tuple can possibly match
+ * the outer.
+ *
+ * When doing a range join, we lose two merge join optimizations:
+ *
+ * 1. Ordinary merge join only restores to the mark if it's equal to the
+ * new outer. For range join, we must always restore to the mark
+ * because there may be matches after the mark and before the current
+ * inner tuple.
+ * 2. After restoring to the mark, ordinary merge join immediately moves
+ * to JOINTUPLES. Range join must move to SKIP_TEST first.
+ *
+ * Range merge join is unable to implement RIGHT/FULL joins. It's also
+ * unable to cope with reverse sort order, because there could always be
+ * some later inner range that matches the outer tuple.
*/
#include "postgres.h"
#include "access/nbtree.h"
+#include "catalog/pg_operator.h"
#include "executor/execdebug.h"
#include "executor/nodeMergejoin.h"
+#include "nodes/nodeFuncs.h"
#include "utils/lsyscache.h"
#include "utils/memutils.h"
+#include "utils/rangetypes.h"
+#include "utils/typcache.h"
/*
@@ -137,6 +190,10 @@ typedef struct MergeJoinClauseData
* stored here.
*/
SortSupportData ssup;
+
+ /* needed for Range Join */
+ bool isrange;
+ TypeCacheEntry *range_typcache;
} MergeJoinClauseData;
/* Result type for MJEvalOuterValues and MJEvalInnerValues */
@@ -147,7 +204,6 @@ typedef enum
MJEVAL_ENDOFJOIN /* end of input (physical or effective) */
} MJEvalResult;
-
#define MarkInnerTuple(innerTupleSlot, mergestate) \
ExecCopySlot((mergestate)->mj_MarkedTupleSlot, (innerTupleSlot))
@@ -177,6 +233,7 @@ MJExamineQuals(List *mergeclauses,
Oid *mergecollations,
int *mergestrategies,
bool *mergenullsfirst,
+ bool *israngejoin,
PlanState *parent)
{
MergeJoinClause clauses;
@@ -184,6 +241,8 @@ MJExamineQuals(List *mergeclauses,
int iClause;
ListCell *cl;
+ *israngejoin = false;
+
clauses = (MergeJoinClause) palloc0(nClauses * sizeof(MergeJoinClauseData));
iClause = 0;
@@ -195,6 +254,7 @@ MJExamineQuals(List *mergeclauses,
Oid collation = mergecollations[iClause];
StrategyNumber opstrategy = mergestrategies[iClause];
bool nulls_first = mergenullsfirst[iClause];
+ Oid eq_opno;
int op_strategy;
Oid op_lefttype;
Oid op_righttype;
@@ -220,8 +280,32 @@ MJExamineQuals(List *mergeclauses,
elog(ERROR, "unsupported mergejoin strategy %d", opstrategy);
clause->ssup.ssup_nulls_first = nulls_first;
+ /*
+ * If a range join, the original operator must be "&&" rather than
+ * "=". Set eq_opno to the range equality operator for the purposes of
+ * setting up the merge clause, but mark it as a range.
+ */
+ if (qual->opno == OID_RANGE_OVERLAP_OP)
+ {
+ Oid rngtypid = exprType((Node*)clause->lexpr->expr);
+ Assert(exprType((Node*)clause->lexpr->expr) ==
+ exprType((Node*)clause->rexpr->expr));
+ eq_opno = OID_RANGE_EQ_OP;
+ clause->isrange = true;
+ clause->range_typcache = lookup_type_cache(rngtypid,
+ TYPECACHE_RANGE_INFO);
+ *israngejoin = true;
+ }
+ else
+ {
+ eq_opno = qual->opno;
+ clause->isrange = false;
+ clause->range_typcache = NULL;
+ }
+
+
/* Extract the operator's declared left/right datatypes */
- get_op_opfamily_properties(qual->opno, opfamily, false,
+ get_op_opfamily_properties(eq_opno, opfamily, false,
&op_strategy,
&op_lefttype,
&op_righttype);
@@ -323,6 +407,11 @@ MJEvalOuterValues(MergeJoinState *mergestate)
else if (result == MJEVAL_MATCHABLE)
result = MJEVAL_NONMATCHABLE;
}
+ else if (clause->isrange)
+ {
+ if (RangeIsEmpty(DatumGetRangeType(clause->ldatum)))
+ result = MJEVAL_NONMATCHABLE;
+ }
}
MemoryContextSwitchTo(oldContext);
@@ -370,6 +459,11 @@ MJEvalInnerValues(MergeJoinState *mergestate, TupleTableSlot *innerslot)
else if (result == MJEVAL_MATCHABLE)
result = MJEVAL_NONMATCHABLE;
}
+ else if (clause->isrange)
+ {
+ if (RangeIsEmpty(DatumGetRangeType(clause->rdatum)))
+ result = MJEVAL_NONMATCHABLE;
+ }
}
MemoryContextSwitchTo(oldContext);
@@ -378,6 +472,34 @@ MJEvalInnerValues(MergeJoinState *mergestate, TupleTableSlot *innerslot)
}
/*
+ * Return 0 if ranges overlap, <0 if the first range is left-of the second, or
+ * >0 if the first range is right-of the second. See comment at the top of the
+ * file for explanation.
+ */
+static int
+ApplyRangeMatch(Datum ldatum, bool lisnull, Datum rdatum, bool risnull,
+ SortSupport ssup, TypeCacheEntry *typcache)
+{
+ /* can't handle reverse sort order; should be prevented by optimizer */
+ Assert(!ssup->ssup_reverse);
+ Assert(!lisnull || !risnull);
+
+ if (lisnull)
+ return ssup->ssup_nulls_first ? -1 : 1;
+ if (risnull)
+ return ssup->ssup_nulls_first ? 1 : -1;
+
+ if (range_before_internal(typcache, DatumGetRangeType(ldatum),
+ DatumGetRangeType(rdatum)))
+ return -1;
+ else if (range_overlaps_internal(typcache, DatumGetRangeType(ldatum),
+ DatumGetRangeType(rdatum)))
+ return 0;
+ else
+ return 1;
+}
+
+/*
* MJCompare
*
* Compare the mergejoinable values of the current two input tuples
@@ -388,14 +510,17 @@ MJEvalInnerValues(MergeJoinState *mergestate, TupleTableSlot *innerslot)
* for the current outer and inner tuples, respectively.
*/
static int
-MJCompare(MergeJoinState *mergestate)
+MJCompare(MergeJoinState *mergestate, bool *noMatch)
{
int result = 0;
bool nulleqnull = false;
+ bool range_overlaps = false;
ExprContext *econtext = mergestate->js.ps.ps_ExprContext;
int i;
MemoryContext oldContext;
+ *noMatch = false;
+
/*
* Call the comparison functions in short-lived context, in case they leak
* memory.
@@ -417,9 +542,18 @@ MJCompare(MergeJoinState *mergestate)
continue;
}
- result = ApplySortComparator(clause->ldatum, clause->lisnull,
+ if (clause->isrange)
+ {
+ result = ApplyRangeMatch(clause->ldatum, clause->lisnull,
clause->rdatum, clause->risnull,
- &clause->ssup);
+ &clause->ssup, clause->range_typcache);
+ if (result == 0)
+ range_overlaps = true;
+ }
+ else
+ result = ApplySortComparator(clause->ldatum, clause->lisnull,
+ clause->rdatum, clause->risnull,
+ &clause->ssup);
if (result != 0)
break;
@@ -438,6 +572,17 @@ MJCompare(MergeJoinState *mergestate)
(nulleqnull || mergestate->mj_ConstFalseJoin))
result = 1;
+ /*
+ * If a range predicate succeeds (overlaps) but a later predicate fails,
+ * it's neither strictly right-of, nor strictly left-of, nor matching. So
+ * we return 0, but mark it *noMatch.
+ */
+ if (result != 0 && range_overlaps)
+ {
+ result = 0;
+ *noMatch = true;
+ }
+
MemoryContextSwitchTo(oldContext);
return result;
@@ -532,7 +677,6 @@ check_constant_qual(List *qual, bool *is_const_false)
return true;
}
-
/* ----------------------------------------------------------------
* ExecMergeTupleDump
*
@@ -602,6 +746,7 @@ ExecMergeJoin(MergeJoinState *node)
ExprState *otherqual;
bool qualResult;
int compareResult;
+ bool compareNoMatch = false;
PlanState *innerPlan;
TupleTableSlot *innerTupleSlot;
PlanState *outerPlan;
@@ -884,15 +1029,25 @@ ExecMergeJoin(MergeJoinState *node)
* If they do not match then advance to next outer
* tuple.
*/
- compareResult = MJCompare(node);
+ compareResult = MJCompare(node, &compareNoMatch);
MJ_DEBUG_COMPARE(compareResult);
- if (compareResult == 0)
+ if (compareResult == 0 && !compareNoMatch)
node->mj_JoinState = EXEC_MJ_JOINTUPLES;
+ else if (compareResult < 0)
+ node->mj_JoinState = EXEC_MJ_NEXTOUTER;
else
{
- Assert(compareResult < 0);
- node->mj_JoinState = EXEC_MJ_NEXTOUTER;
+ /*
+ * This state is only reached during a range join,
+ * where earlier tuples may match, the current
+ * tuple may not match ( compareResult>0 ||
+ * compareNoMatch==true ), but a later tuple in the
+ * inner may still match. See comment at the top
+ * of the file.
+ */
+ Assert(((MergeJoin*)node->js.ps.plan)->mergeRangeJoin);
+ node->mj_JoinState = EXEC_MJ_NEXTINNER;
}
break;
case MJEVAL_NONMATCHABLE:
@@ -1034,14 +1189,30 @@ ExecMergeJoin(MergeJoinState *node)
MJ_printf("ExecMergeJoin: EXEC_MJ_TESTOUTER\n");
/*
- * Here we must compare the outer tuple with the marked inner
- * tuple. (We can ignore the result of MJEvalInnerValues,
- * since the marked inner tuple is certainly matchable.)
+ * We can ignore the result of MJEvalInnerValues, since the
+ * marked inner tuple is certainly matchable.
*/
innerTupleSlot = node->mj_MarkedTupleSlot;
(void) MJEvalInnerValues(node, innerTupleSlot);
- compareResult = MJCompare(node);
+ if (((MergeJoin*)node->js.ps.plan)->mergeRangeJoin)
+ {
+ /*
+ * For range join, we must always restore to the mark, and
+ * then move to SKIP_TEST.
+ */
+ ExecRestrPos(innerPlan);
+ node->mj_InnerTupleSlot = node->mj_MarkedTupleSlot;
+ node->mj_JoinState = EXEC_MJ_SKIP_TEST;
+ break;
+ }
+
+ /*
+ * Here we must compare the outer tuple with the marked inner
+ * tuple.
+ */
+ compareResult = MJCompare(node, &compareNoMatch);
+ Assert(!compareNoMatch);
MJ_DEBUG_COMPARE(compareResult);
if (compareResult == 0)
@@ -1139,7 +1310,7 @@ ExecMergeJoin(MergeJoinState *node)
break;
/*----------------------------------------------------------
- * EXEC_MJ_SKIP means compare tuples and if they do not
+ * EXEC_MJ_SKIP_TEST means compare tuples and if they do not
* match, skip whichever is lesser.
*
* For example:
@@ -1175,7 +1346,7 @@ ExecMergeJoin(MergeJoinState *node)
* satisfy the mergeclauses. If they do, then we update the
* marked tuple position and go join them.
*/
- compareResult = MJCompare(node);
+ compareResult = MJCompare(node, &compareNoMatch);
MJ_DEBUG_COMPARE(compareResult);
if (compareResult == 0)
@@ -1185,7 +1356,10 @@ ExecMergeJoin(MergeJoinState *node)
MarkInnerTuple(node->mj_InnerTupleSlot, node);
- node->mj_JoinState = EXEC_MJ_JOINTUPLES;
+ if (compareNoMatch)
+ node->mj_JoinState = EXEC_MJ_NEXTINNER;
+ else
+ node->mj_JoinState = EXEC_MJ_JOINTUPLES;
}
else if (compareResult < 0)
node->mj_JoinState = EXEC_MJ_SKIPOUTER_ADVANCE;
@@ -1593,6 +1767,7 @@ ExecInitMergeJoin(MergeJoin *node, EState *estate, int eflags)
node->mergeCollations,
node->mergeStrategies,
node->mergeNullsFirst,
+ &node->mergeRangeJoin,
(PlanState *) mergestate);
/*
diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c
index 5aedcd1..108d30c 100644
--- a/src/backend/optimizer/path/joinpath.c
+++ b/src/backend/optimizer/path/joinpath.c
@@ -466,6 +466,19 @@ try_mergejoin_path(PlannerInfo *root,
Relids required_outer;
JoinCostWorkspace workspace;
+ /* RIGHT/FULL joins don't support range join */
+ if (jointype == JOIN_RIGHT || jointype == JOIN_FULL)
+ {
+ ListCell *lc;
+
+ foreach(lc, mergeclauses)
+ {
+ RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(lc);
+ if (restrictinfo->rangejoin)
+ return;
+ }
+ }
+
if (is_partial)
{
try_partial_mergejoin_path(root,
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index 2c26906..2ed2d64 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -1125,6 +1125,7 @@ select_outer_pathkeys_for_merge(PlannerInfo *root,
int nClauses = list_length(mergeclauses);
EquivalenceClass **ecs;
int *scores;
+ bool *range_ecs;
int necs;
ListCell *lc;
int j;
@@ -1139,6 +1140,7 @@ select_outer_pathkeys_for_merge(PlannerInfo *root,
*/
ecs = (EquivalenceClass **) palloc(nClauses * sizeof(EquivalenceClass *));
scores = (int *) palloc(nClauses * sizeof(int));
+ range_ecs = palloc(nClauses * sizeof(bool));
necs = 0;
foreach(lc, mergeclauses)
@@ -1179,6 +1181,7 @@ select_outer_pathkeys_for_merge(PlannerInfo *root,
ecs[necs] = oeclass;
scores[necs] = score;
+ range_ecs[necs] = rinfo->rangejoin;
necs++;
}
@@ -1196,6 +1199,11 @@ select_outer_pathkeys_for_merge(PlannerInfo *root,
for (j = 0; j < necs; j++)
{
+ /* for range join, the input order must be ascending */
+ if (range_ecs[j] &&
+ query_pathkey->pk_strategy != BTLessStrategyNumber)
+ continue;
+
if (ecs[j] == query_ec)
break; /* found match */
}
diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.c
index ebd442a..86021c0 100644
--- a/src/backend/optimizer/plan/initsplan.c
+++ b/src/backend/optimizer/plan/initsplan.c
@@ -14,6 +14,7 @@
*/
#include "postgres.h"
+#include "catalog/pg_operator.h"
#include "catalog/pg_type.h"
#include "nodes/nodeFuncs.h"
#include "optimizer/clauses.h"
@@ -1940,7 +1941,7 @@ distribute_qual_to_rels(PlannerInfo *root, Node *clause,
*/
if (restrictinfo->mergeopfamilies)
{
- if (maybe_equivalence)
+ if (maybe_equivalence && !restrictinfo->rangejoin)
{
if (check_equivalence_delay(root, restrictinfo) &&
process_equivalence(root, restrictinfo, below_outer_join))
@@ -2594,6 +2595,12 @@ check_mergejoinable(RestrictInfo *restrictinfo)
opno = ((OpExpr *) clause)->opno;
leftarg = linitial(((OpExpr *) clause)->args);
+ if (opno == OID_RANGE_OVERLAP_OP)
+ {
+ restrictinfo->rangejoin = true;
+ opno = OID_RANGE_EQ_OP;
+ }
+
if (op_mergejoinable(opno, exprType(leftarg)) &&
!contain_volatile_functions((Node *) clause))
restrictinfo->mergeopfamilies = get_mergejoin_opfamilies(opno);
diff --git a/src/backend/optimizer/util/restrictinfo.c b/src/backend/optimizer/util/restrictinfo.c
index e946290..c2d1a23 100644
--- a/src/backend/optimizer/util/restrictinfo.c
+++ b/src/backend/optimizer/util/restrictinfo.c
@@ -186,6 +186,7 @@ make_restrictinfo_internal(Expr *clause,
restrictinfo->outer_selec = -1;
restrictinfo->mergeopfamilies = NIL;
+ restrictinfo->rangejoin = false;
restrictinfo->left_ec = NULL;
restrictinfo->right_ec = NULL;
diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
index a35b93b..5c8c69f 100644
--- a/src/backend/utils/adt/selfuncs.c
+++ b/src/backend/utils/adt/selfuncs.c
@@ -2860,7 +2860,6 @@ mergejoinscansel(PlannerInfo *root, Node *clause,
*right;
VariableStatData leftvar,
rightvar;
- int op_strategy;
Oid op_lefttype;
Oid op_righttype;
Oid opno,
@@ -2897,12 +2896,20 @@ mergejoinscansel(PlannerInfo *root, Node *clause,
examine_variable(root, left, 0, &leftvar);
examine_variable(root, right, 0, &rightvar);
- /* Extract the operator's declared left/right datatypes */
- get_op_opfamily_properties(opno, opfamily, false,
- &op_strategy,
- &op_lefttype,
- &op_righttype);
- Assert(op_strategy == BTEqualStrategyNumber);
+ if (opno == OID_RANGE_OVERLAP_OP)
+ {
+ op_lefttype = op_righttype = ANYRANGEOID;
+ }
+ else
+ {
+ int op_strategy;
+ /* Extract the operator's declared left/right datatypes */
+ get_op_opfamily_properties(opno, opfamily, false,
+ &op_strategy,
+ &op_lefttype,
+ &op_righttype);
+ Assert(op_strategy == BTEqualStrategyNumber);
+ }
/*
* Look up the various operators we need. If we don't find them all, it
diff --git a/src/include/catalog/pg_operator.h b/src/include/catalog/pg_operator.h
index fe8795a..1f1ffb4 100644
--- a/src/include/catalog/pg_operator.h
+++ b/src/include/catalog/pg_operator.h
@@ -1748,6 +1748,7 @@ DESCR("greater than or equal");
/* generic range type operators */
DATA(insert OID = 3882 ( "=" PGNSP PGUID b t t 3831 3831 16 3882 3883 range_eq eqsel eqjoinsel ));
DESCR("equal");
+#define OID_RANGE_EQ_OP 3882
DATA(insert OID = 3883 ( "<>" PGNSP PGUID b f f 3831 3831 16 3883 3882 range_ne neqsel neqjoinsel ));
DESCR("not equal");
DATA(insert OID = 3884 ( "<" PGNSP PGUID b f f 3831 3831 16 3887 3886 range_lt rangesel scalarltjoinsel ));
diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h
index 12f9f61..e2b05e9 100644
--- a/src/include/nodes/plannodes.h
+++ b/src/include/nodes/plannodes.h
@@ -703,6 +703,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 */
+ bool mergeRangeJoin; /* is this a range merge join? */
} MergeJoin;
/* ----------------
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index 7a8e2fd..aa16f9a 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -1790,6 +1790,9 @@ typedef struct RestrictInfo
/* valid if clause is mergejoinable, else NIL */
List *mergeopfamilies; /* opfamilies containing clause operator */
+ /* is a rangejoin clause? */
+ bool rangejoin;
+
/* cache space for mergeclause processing; NULL if not yet set */
EquivalenceClass *left_ec; /* EquivalenceClass containing lefthand */
EquivalenceClass *right_ec; /* EquivalenceClass containing righthand */
diff --git a/src/test/regress/expected/rangejoin.out b/src/test/regress/expected/rangejoin.out
new file mode 100644
index 0000000..e8fb835
--- /dev/null
+++ b/src/test/regress/expected/rangejoin.out
@@ -0,0 +1,526 @@
+create table rangejoin_left(i1 int, ir1 int4range);
+create table rangejoin_right(i2 int, ir2 int4range);
+insert into rangejoin_left values
+ (1001, int4range(10, 80)),
+ (1002, int4range(20, 30)),
+ (1003, int4range(21, 25)),
+ (1004, int4range(22, 35)),
+ (1005, int4range(40, 60)),
+ (1006, int4range(50, 60));
+insert into rangejoin_right values
+ (1000, 'empty'::int4range),
+ (1001, int4range(NULL, 4)),
+ (1002, int4range(10, 12)),
+ (1003, int4range(11, 14)),
+ (1004, int4range(20, 45)),
+ (1005, int4range(24, 28)),
+ (1006, int4range(85, 90));
+-- simple inner join
+explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left, rangejoin_right
+ where ir1 && ir2;
+ QUERY PLAN
+-----------------------------------------------------------
+ Range Merge Join
+ Merge Cond: (rangejoin_left.ir1 && rangejoin_right.ir2)
+ -> Sort
+ Sort Key: rangejoin_left.ir1
+ -> Seq Scan on rangejoin_left
+ -> Sort
+ Sort Key: rangejoin_right.ir2
+ -> Seq Scan on rangejoin_right
+(8 rows)
+
+select i1, ir1, i2, ir2
+ from rangejoin_left, rangejoin_right
+ where ir1 && ir2;
+ i1 | ir1 | i2 | ir2
+------+---------+------+---------
+ 1001 | [10,80) | 1002 | [10,12)
+ 1001 | [10,80) | 1003 | [11,14)
+ 1001 | [10,80) | 1004 | [20,45)
+ 1001 | [10,80) | 1005 | [24,28)
+ 1002 | [20,30) | 1004 | [20,45)
+ 1002 | [20,30) | 1005 | [24,28)
+ 1003 | [21,25) | 1004 | [20,45)
+ 1003 | [21,25) | 1005 | [24,28)
+ 1004 | [22,35) | 1004 | [20,45)
+ 1004 | [22,35) | 1005 | [24,28)
+ 1005 | [40,60) | 1004 | [20,45)
+(11 rows)
+
+-- two predicates
+explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left inner join rangejoin_right
+ on (i1 = i2 and ir1 && ir2);
+ QUERY PLAN
+----------------------------------------------------------------------------------------------------------
+ Range Merge Join
+ Merge Cond: ((rangejoin_left.ir1 && rangejoin_right.ir2) AND (rangejoin_left.i1 = rangejoin_right.i2))
+ -> Sort
+ Sort Key: rangejoin_left.ir1, rangejoin_left.i1
+ -> Seq Scan on rangejoin_left
+ -> Sort
+ Sort Key: rangejoin_right.ir2, rangejoin_right.i2
+ -> Seq Scan on rangejoin_right
+(8 rows)
+
+select i1, ir1, i2, ir2
+ from rangejoin_left inner join rangejoin_right
+ on (i1 = i2 and ir1 && ir2);
+ i1 | ir1 | i2 | ir2
+------+---------+------+---------
+ 1004 | [22,35) | 1004 | [20,45)
+(1 row)
+
+-- left join
+explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left left join rangejoin_right
+ on (ir1 && ir2);
+ QUERY PLAN
+-----------------------------------------------------------
+ Range Merge Left Join
+ Merge Cond: (rangejoin_left.ir1 && rangejoin_right.ir2)
+ -> Sort
+ Sort Key: rangejoin_left.ir1
+ -> Seq Scan on rangejoin_left
+ -> Sort
+ Sort Key: rangejoin_right.ir2
+ -> Seq Scan on rangejoin_right
+(8 rows)
+
+select i1, ir1, i2, ir2
+ from rangejoin_left left join rangejoin_right
+ on (ir1 && ir2);
+ i1 | ir1 | i2 | ir2
+------+---------+------+---------
+ 1001 | [10,80) | 1002 | [10,12)
+ 1001 | [10,80) | 1003 | [11,14)
+ 1001 | [10,80) | 1004 | [20,45)
+ 1001 | [10,80) | 1005 | [24,28)
+ 1002 | [20,30) | 1004 | [20,45)
+ 1002 | [20,30) | 1005 | [24,28)
+ 1003 | [21,25) | 1004 | [20,45)
+ 1003 | [21,25) | 1005 | [24,28)
+ 1004 | [22,35) | 1004 | [20,45)
+ 1004 | [22,35) | 1005 | [24,28)
+ 1005 | [40,60) | 1004 | [20,45)
+ 1006 | [50,60) | |
+(12 rows)
+
+-- right join should be implemented as left join
+explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left right join rangejoin_right
+ on (ir1 && ir2);
+ QUERY PLAN
+-----------------------------------------------------------
+ Range Merge Left Join
+ Merge Cond: (rangejoin_right.ir2 && rangejoin_left.ir1)
+ -> Sort
+ Sort Key: rangejoin_right.ir2
+ -> Seq Scan on rangejoin_right
+ -> Sort
+ Sort Key: rangejoin_left.ir1
+ -> Seq Scan on rangejoin_left
+(8 rows)
+
+-- full join doesn't support range join
+explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left full join rangejoin_right
+ on (ir1 && ir2);
+ERROR: FULL JOIN is only supported with merge-joinable or hash-joinable join conditions
+-- range input to range join must be ascending
+explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left inner join rangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 desc, i1;
+ QUERY PLAN
+----------------------------------------------------------------------------------------------------------------
+ Sort
+ Sort Key: rangejoin_left.ir1 DESC, rangejoin_left.i1
+ -> Range Merge Join
+ Merge Cond: ((rangejoin_left.ir1 && rangejoin_right.ir2) AND (rangejoin_left.i1 = rangejoin_right.i2))
+ -> Sort
+ Sort Key: rangejoin_left.ir1, rangejoin_left.i1
+ -> Seq Scan on rangejoin_left
+ -> Sort
+ Sort Key: rangejoin_right.ir2, rangejoin_right.i2
+ -> Seq Scan on rangejoin_right
+(10 rows)
+
+-- but it's OK for non-range inputs to be descending
+explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left inner join rangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 nulls first, i1 desc;
+ QUERY PLAN
+----------------------------------------------------------------------------------------------------------
+ Range Merge Join
+ Merge Cond: ((rangejoin_left.ir1 && rangejoin_right.ir2) AND (rangejoin_left.i1 = rangejoin_right.i2))
+ -> Sort
+ Sort Key: rangejoin_left.ir1 NULLS FIRST, rangejoin_left.i1 DESC
+ -> Seq Scan on rangejoin_left
+ -> Sort
+ Sort Key: rangejoin_right.ir2 NULLS FIRST, rangejoin_right.i2 DESC
+ -> Seq Scan on rangejoin_right
+(8 rows)
+
+select i1, ir1, i2, ir2
+ from rangejoin_left inner join rangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 nulls first, i1 desc;
+ i1 | ir1 | i2 | ir2
+------+---------+------+---------
+ 1004 | [22,35) | 1004 | [20,45)
+(1 row)
+
+drop table rangejoin_left;
+drop table rangejoin_right;
+create table multirangejoin_left (ir1 int4range, ir2 int4range);
+create table multirangejoin_right (ir3 int4range, ir4 int4range);
+insert into multirangejoin_left values
+ (int4range(30,99), int4range(20,30)),
+ (int4range(2,40), int4range(15,27)),
+ (int4range(61,99), int4range(20,45)),
+ (int4range(22,32), int4range(21,66)),
+ (int4range(36,71), int4range(45,49)),
+ (int4range(9,80), int4range(2,4));
+insert into multirangejoin_right values
+ (int4range(9,70), int4range(10,78)),
+ (int4range(21,37), int4range(89,99)),
+ (int4range(5,98), int4range(35,97)),
+ (int4range(12,17), int4range(81,92)),
+ (int4range(15,19), int4range(5,55)),
+ (int4range(57,58), int4range(42,80));
+explain (costs off) select *
+ from multirangejoin_left inner join multirangejoin_right
+ on (ir1 && ir3 and ir2 && ir4) order by ir1, ir2, ir3, ir4;
+ QUERY PLAN
+---------------------------------------------------------------------------------------------------------------------------------------
+ Sort
+ Sort Key: multirangejoin_left.ir1, multirangejoin_left.ir2, multirangejoin_right.ir3, multirangejoin_right.ir4
+ -> Range Merge Join
+ Merge Cond: ((multirangejoin_left.ir1 && multirangejoin_right.ir3) AND (multirangejoin_left.ir2 && multirangejoin_right.ir4))
+ -> Sort
+ Sort Key: multirangejoin_left.ir1, multirangejoin_left.ir2
+ -> Seq Scan on multirangejoin_left
+ -> Sort
+ Sort Key: multirangejoin_right.ir3, multirangejoin_right.ir4
+ -> Seq Scan on multirangejoin_right
+(10 rows)
+
+select *
+ from multirangejoin_left inner join multirangejoin_right
+ on (ir1 && ir3 and ir2 && ir4) order by ir1, ir2, ir3, ir4;
+ ir1 | ir2 | ir3 | ir4
+---------+---------+---------+---------
+ [2,40) | [15,27) | [9,70) | [10,78)
+ [2,40) | [15,27) | [15,19) | [5,55)
+ [22,32) | [21,66) | [5,98) | [35,97)
+ [22,32) | [21,66) | [9,70) | [10,78)
+ [30,99) | [20,30) | [9,70) | [10,78)
+ [36,71) | [45,49) | [5,98) | [35,97)
+ [36,71) | [45,49) | [9,70) | [10,78)
+ [36,71) | [45,49) | [57,58) | [42,80)
+ [61,99) | [20,45) | [5,98) | [35,97)
+ [61,99) | [20,45) | [9,70) | [10,78)
+(10 rows)
+
+set enable_mergejoin=false;
+explain (costs off) select *
+ from multirangejoin_left inner join multirangejoin_right
+ on (ir1 && ir3 and ir2 && ir4) order by ir1, ir2, ir3, ir4;
+ QUERY PLAN
+----------------------------------------------------------------------------------------------------------------------------------------
+ Sort
+ Sort Key: multirangejoin_left.ir1, multirangejoin_left.ir2, multirangejoin_right.ir3, multirangejoin_right.ir4
+ -> Nested Loop
+ Join Filter: ((multirangejoin_left.ir1 && multirangejoin_right.ir3) AND (multirangejoin_left.ir2 && multirangejoin_right.ir4))
+ -> Seq Scan on multirangejoin_left
+ -> Materialize
+ -> Seq Scan on multirangejoin_right
+(7 rows)
+
+select *
+ from multirangejoin_left inner join multirangejoin_right
+ on (ir1 && ir3 and ir2 && ir4) order by ir1, ir2, ir3, ir4;
+ ir1 | ir2 | ir3 | ir4
+---------+---------+---------+---------
+ [2,40) | [15,27) | [9,70) | [10,78)
+ [2,40) | [15,27) | [15,19) | [5,55)
+ [22,32) | [21,66) | [5,98) | [35,97)
+ [22,32) | [21,66) | [9,70) | [10,78)
+ [30,99) | [20,30) | [9,70) | [10,78)
+ [36,71) | [45,49) | [5,98) | [35,97)
+ [36,71) | [45,49) | [9,70) | [10,78)
+ [36,71) | [45,49) | [57,58) | [42,80)
+ [61,99) | [20,45) | [5,98) | [35,97)
+ [61,99) | [20,45) | [9,70) | [10,78)
+(10 rows)
+
+set enable_mergejoin=true;
+explain (costs off) select *
+ from multirangejoin_left left join multirangejoin_right
+ on (ir1 && ir4 and ir2 && ir3) order by ir4, ir3, ir2, ir1;
+ QUERY PLAN
+---------------------------------------------------------------------------------------------------------------------------------------
+ Sort
+ Sort Key: multirangejoin_right.ir4, multirangejoin_right.ir3, multirangejoin_left.ir2, multirangejoin_left.ir1
+ -> Range Merge Left Join
+ Merge Cond: ((multirangejoin_left.ir1 && multirangejoin_right.ir4) AND (multirangejoin_left.ir2 && multirangejoin_right.ir3))
+ -> Sort
+ Sort Key: multirangejoin_left.ir1, multirangejoin_left.ir2
+ -> Seq Scan on multirangejoin_left
+ -> Sort
+ Sort Key: multirangejoin_right.ir4, multirangejoin_right.ir3
+ -> Seq Scan on multirangejoin_right
+(10 rows)
+
+select *
+ from multirangejoin_left left join multirangejoin_right
+ on (ir1 && ir4 and ir2 && ir3) order by ir4, ir3, ir2, ir1;
+ ir1 | ir2 | ir3 | ir4
+---------+---------+---------+---------
+ [2,40) | [15,27) | [15,19) | [5,55)
+ [2,40) | [15,27) | [9,70) | [10,78)
+ [30,99) | [20,30) | [9,70) | [10,78)
+ [61,99) | [20,45) | [9,70) | [10,78)
+ [22,32) | [21,66) | [9,70) | [10,78)
+ [36,71) | [45,49) | [9,70) | [10,78)
+ [2,40) | [15,27) | [5,98) | [35,97)
+ [30,99) | [20,30) | [5,98) | [35,97)
+ [61,99) | [20,45) | [5,98) | [35,97)
+ [36,71) | [45,49) | [5,98) | [35,97)
+ [30,99) | [20,30) | [21,37) | [89,99)
+ [61,99) | [20,45) | [21,37) | [89,99)
+ [9,80) | [2,4) | |
+(13 rows)
+
+set enable_mergejoin=false;
+explain (costs off) select *
+ from multirangejoin_left left join multirangejoin_right
+ on (ir1 && ir4 and ir2 && ir3) order by ir4, ir3, ir2, ir1;
+ QUERY PLAN
+----------------------------------------------------------------------------------------------------------------------------------------
+ Sort
+ Sort Key: multirangejoin_right.ir4, multirangejoin_right.ir3, multirangejoin_left.ir2, multirangejoin_left.ir1
+ -> Nested Loop Left Join
+ Join Filter: ((multirangejoin_left.ir1 && multirangejoin_right.ir4) AND (multirangejoin_left.ir2 && multirangejoin_right.ir3))
+ -> Seq Scan on multirangejoin_left
+ -> Materialize
+ -> Seq Scan on multirangejoin_right
+(7 rows)
+
+select *
+ from multirangejoin_left left join multirangejoin_right
+ on (ir1 && ir4 and ir2 && ir3) order by ir4, ir3, ir2, ir1;
+ ir1 | ir2 | ir3 | ir4
+---------+---------+---------+---------
+ [2,40) | [15,27) | [15,19) | [5,55)
+ [2,40) | [15,27) | [9,70) | [10,78)
+ [30,99) | [20,30) | [9,70) | [10,78)
+ [61,99) | [20,45) | [9,70) | [10,78)
+ [22,32) | [21,66) | [9,70) | [10,78)
+ [36,71) | [45,49) | [9,70) | [10,78)
+ [2,40) | [15,27) | [5,98) | [35,97)
+ [30,99) | [20,30) | [5,98) | [35,97)
+ [61,99) | [20,45) | [5,98) | [35,97)
+ [36,71) | [45,49) | [5,98) | [35,97)
+ [30,99) | [20,30) | [21,37) | [89,99)
+ [61,99) | [20,45) | [21,37) | [89,99)
+ [9,80) | [2,4) | |
+(13 rows)
+
+set enable_mergejoin=true;
+drop table multirangejoin_left;
+drop table multirangejoin_right;
+create table bigrangejoin_left (i1 int, ir1 int4range);
+create table bigrangejoin_right (i2 int, ir2 int4range);
+-- 100 small ranges
+insert into bigrangejoin_left
+ select g/4,
+ int4range(g,
+ g + case when (g%2=0) then g%7 else 12-(g%11) end)
+ from generate_series(1,100) g;
+insert into bigrangejoin_right
+ select g/4,
+ int4range(g-7+(g%19),
+ g-7+(g%19) + case when (g%3=0) then g%11 else 17-(g%15) end)
+ from generate_series(1,100) g;
+-- 10 medium ranges
+insert into bigrangejoin_left
+ select g/4*10,
+ int4range(g*10,
+ g*10 + case when (g%2=0) then g%7 else 12-(g%11) end)
+ from generate_series(1,10) g;
+insert into bigrangejoin_right
+ select g/4*10,
+ int4range(g*10-57+(g%173),
+ g*10-57+(g%173) + case when (g%3=0) then g%123 else 97-(g%83) end)
+ from generate_series(1,10) g;
+insert into bigrangejoin_left select g*11-21, 'empty'::int4range
+ from generate_series(1,9) g;
+insert into bigrangejoin_right select g*13-29, 'empty'::int4range
+ from generate_series(1,8) g;
+insert into bigrangejoin_left values
+ (4, int4range(NULL,5)),
+ (93, int4range(95, NULL));
+insert into bigrangejoin_right values
+ (7, int4range(NULL,3)),
+ (92, int4range(99, NULL));
+create temp table rangejoin_result1
+ (i1 int, ir1 int4range, i2 int, ir2 int4range);
+create temp table rangejoin_result2
+ (i1 int, ir1 int4range, i2 int, ir2 int4range);
+set enable_hashjoin=false;
+explain (costs off) insert into rangejoin_result1
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left left join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 nulls first, i1 desc;
+ QUERY PLAN
+----------------------------------------------------------------------------------------------------------------------------
+ Insert on rangejoin_result1
+ -> Range Merge Left Join
+ Merge Cond: ((bigrangejoin_left.ir1 && bigrangejoin_right.ir2) AND (bigrangejoin_left.i1 = bigrangejoin_right.i2))
+ -> Sort
+ Sort Key: bigrangejoin_left.ir1 NULLS FIRST, bigrangejoin_left.i1 DESC
+ -> Seq Scan on bigrangejoin_left
+ -> Sort
+ Sort Key: bigrangejoin_right.ir2 NULLS FIRST, bigrangejoin_right.i2 DESC
+ -> Seq Scan on bigrangejoin_right
+(9 rows)
+
+insert into rangejoin_result1
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left left join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 nulls first, i1 desc;
+set enable_hashjoin=true;
+set enable_mergejoin=false;
+explain (costs off) insert into rangejoin_result2
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left left join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 nulls first, i1 desc;
+ QUERY PLAN
+--------------------------------------------------------------------------------
+ Insert on rangejoin_result2
+ -> Sort
+ Sort Key: bigrangejoin_left.ir1 NULLS FIRST, bigrangejoin_left.i1 DESC
+ -> Hash Left Join
+ Hash Cond: (bigrangejoin_left.i1 = bigrangejoin_right.i2)
+ Join Filter: (bigrangejoin_left.ir1 && bigrangejoin_right.ir2)
+ -> Seq Scan on bigrangejoin_left
+ -> Hash
+ -> Seq Scan on bigrangejoin_right
+(9 rows)
+
+insert into rangejoin_result2
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left left join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 nulls first, i1 desc;
+set enable_mergejoin=true;
+select count(*) from rangejoin_result1;
+ count
+-------
+ 292
+(1 row)
+
+select count(*) from rangejoin_result2;
+ count
+-------
+ 292
+(1 row)
+
+select * from rangejoin_result1 except select * from rangejoin_result2;
+ i1 | ir1 | i2 | ir2
+----+-----+----+-----
+(0 rows)
+
+select * from rangejoin_result2 except select * from rangejoin_result1;
+ i1 | ir1 | i2 | ir2
+----+-----+----+-----
+(0 rows)
+
+drop table rangejoin_result1;
+drop table rangejoin_result2;
+create temp table rangejoin_result3
+ (i1 int, ir1 int4range, i2 int, ir2 int4range);
+create temp table rangejoin_result4
+ (i1 int, ir1 int4range, i2 int, ir2 int4range);
+explain (costs off) insert into rangejoin_result3
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left inner join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by i1, ir1;
+ QUERY PLAN
+----------------------------------------------------------------------------------------------------------------------------
+ Insert on rangejoin_result3
+ -> Range Merge Join
+ Merge Cond: ((bigrangejoin_left.i1 = bigrangejoin_right.i2) AND (bigrangejoin_left.ir1 && bigrangejoin_right.ir2))
+ -> Sort
+ Sort Key: bigrangejoin_left.i1, bigrangejoin_left.ir1
+ -> Seq Scan on bigrangejoin_left
+ -> Sort
+ Sort Key: bigrangejoin_right.i2, bigrangejoin_right.ir2
+ -> Seq Scan on bigrangejoin_right
+(9 rows)
+
+insert into rangejoin_result3
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left inner join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by i1, ir1;
+set enable_mergejoin=false;
+explain (costs off) insert into rangejoin_result4
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left inner join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by i1, ir1;
+ QUERY PLAN
+------------------------------------------------------------------------------
+ Insert on rangejoin_result4
+ -> Sort
+ Sort Key: bigrangejoin_left.i1, bigrangejoin_left.ir1
+ -> Hash Join
+ Hash Cond: (bigrangejoin_left.i1 = bigrangejoin_right.i2)
+ Join Filter: (bigrangejoin_left.ir1 && bigrangejoin_right.ir2)
+ -> Seq Scan on bigrangejoin_left
+ -> Hash
+ -> Seq Scan on bigrangejoin_right
+(9 rows)
+
+insert into rangejoin_result4
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left inner join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by i1, ir1;
+set enable_mergejoin=true;
+select count(*) from rangejoin_result3;
+ count
+-------
+ 259
+(1 row)
+
+select count(*) from rangejoin_result4;
+ count
+-------
+ 259
+(1 row)
+
+select * from rangejoin_result3 except select * from rangejoin_result4;
+ i1 | ir1 | i2 | ir2
+----+-----+----+-----
+(0 rows)
+
+select * from rangejoin_result4 except select * from rangejoin_result3;
+ i1 | ir1 | i2 | ir2
+----+-----+----+-----
+(0 rows)
+
+drop table rangejoin_result3;
+drop table rangejoin_result4;
+drop table bigrangejoin_left;
+drop table bigrangejoin_right;
diff --git a/src/test/regress/parallel_schedule b/src/test/regress/parallel_schedule
index 1f8f098..4f70bb0 100644
--- a/src/test/regress/parallel_schedule
+++ b/src/test/regress/parallel_schedule
@@ -109,7 +109,7 @@ test: select_views portals_p2 foreign_key cluster dependency guc bitmapops combo
# NB: temp.sql does a reconnect which transiently uses 2 connections,
# so keep this parallel group to at most 19 tests
# ----------
-test: plancache limit plpgsql copy2 temp domain rangefuncs prepare without_oid conversion truncate alter_table sequence polymorphism rowtypes returning largeobject with xml
+test: plancache limit plpgsql copy2 temp domain rangefuncs rangejoin prepare without_oid conversion truncate alter_table sequence polymorphism rowtypes returning largeobject with xml
# ----------
# Another group of parallel tests
diff --git a/src/test/regress/serial_schedule b/src/test/regress/serial_schedule
index 04206c3..659dc4a 100644
--- a/src/test/regress/serial_schedule
+++ b/src/test/regress/serial_schedule
@@ -164,6 +164,7 @@ test: copy2
test: temp
test: domain
test: rangefuncs
+test: rangejoin
test: prepare
test: without_oid
test: conversion
diff --git a/src/test/regress/sql/rangejoin.sql b/src/test/regress/sql/rangejoin.sql
new file mode 100644
index 0000000..e1849aa
--- /dev/null
+++ b/src/test/regress/sql/rangejoin.sql
@@ -0,0 +1,265 @@
+
+create table rangejoin_left(i1 int, ir1 int4range);
+create table rangejoin_right(i2 int, ir2 int4range);
+
+insert into rangejoin_left values
+ (1001, int4range(10, 80)),
+ (1002, int4range(20, 30)),
+ (1003, int4range(21, 25)),
+ (1004, int4range(22, 35)),
+ (1005, int4range(40, 60)),
+ (1006, int4range(50, 60));
+
+insert into rangejoin_right values
+ (1000, 'empty'::int4range),
+ (1001, int4range(NULL, 4)),
+ (1002, int4range(10, 12)),
+ (1003, int4range(11, 14)),
+ (1004, int4range(20, 45)),
+ (1005, int4range(24, 28)),
+ (1006, int4range(85, 90));
+
+-- simple inner join
+explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left, rangejoin_right
+ where ir1 && ir2;
+
+select i1, ir1, i2, ir2
+ from rangejoin_left, rangejoin_right
+ where ir1 && ir2;
+
+-- two predicates
+explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left inner join rangejoin_right
+ on (i1 = i2 and ir1 && ir2);
+
+select i1, ir1, i2, ir2
+ from rangejoin_left inner join rangejoin_right
+ on (i1 = i2 and ir1 && ir2);
+
+-- left join
+explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left left join rangejoin_right
+ on (ir1 && ir2);
+
+select i1, ir1, i2, ir2
+ from rangejoin_left left join rangejoin_right
+ on (ir1 && ir2);
+
+-- right join should be implemented as left join
+explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left right join rangejoin_right
+ on (ir1 && ir2);
+
+-- full join doesn't support range join
+explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left full join rangejoin_right
+ on (ir1 && ir2);
+
+-- range input to range join must be ascending
+explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left inner join rangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 desc, i1;
+
+-- but it's OK for non-range inputs to be descending
+explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left inner join rangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 nulls first, i1 desc;
+
+select i1, ir1, i2, ir2
+ from rangejoin_left inner join rangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 nulls first, i1 desc;
+
+drop table rangejoin_left;
+drop table rangejoin_right;
+
+create table multirangejoin_left (ir1 int4range, ir2 int4range);
+create table multirangejoin_right (ir3 int4range, ir4 int4range);
+
+insert into multirangejoin_left values
+ (int4range(30,99), int4range(20,30)),
+ (int4range(2,40), int4range(15,27)),
+ (int4range(61,99), int4range(20,45)),
+ (int4range(22,32), int4range(21,66)),
+ (int4range(36,71), int4range(45,49)),
+ (int4range(9,80), int4range(2,4));
+
+
+insert into multirangejoin_right values
+ (int4range(9,70), int4range(10,78)),
+ (int4range(21,37), int4range(89,99)),
+ (int4range(5,98), int4range(35,97)),
+ (int4range(12,17), int4range(81,92)),
+ (int4range(15,19), int4range(5,55)),
+ (int4range(57,58), int4range(42,80));
+
+explain (costs off) select *
+ from multirangejoin_left inner join multirangejoin_right
+ on (ir1 && ir3 and ir2 && ir4) order by ir1, ir2, ir3, ir4;
+
+select *
+ from multirangejoin_left inner join multirangejoin_right
+ on (ir1 && ir3 and ir2 && ir4) order by ir1, ir2, ir3, ir4;
+
+set enable_mergejoin=false;
+explain (costs off) select *
+ from multirangejoin_left inner join multirangejoin_right
+ on (ir1 && ir3 and ir2 && ir4) order by ir1, ir2, ir3, ir4;
+
+select *
+ from multirangejoin_left inner join multirangejoin_right
+ on (ir1 && ir3 and ir2 && ir4) order by ir1, ir2, ir3, ir4;
+set enable_mergejoin=true;
+
+explain (costs off) select *
+ from multirangejoin_left left join multirangejoin_right
+ on (ir1 && ir4 and ir2 && ir3) order by ir4, ir3, ir2, ir1;
+
+select *
+ from multirangejoin_left left join multirangejoin_right
+ on (ir1 && ir4 and ir2 && ir3) order by ir4, ir3, ir2, ir1;
+
+set enable_mergejoin=false;
+explain (costs off) select *
+ from multirangejoin_left left join multirangejoin_right
+ on (ir1 && ir4 and ir2 && ir3) order by ir4, ir3, ir2, ir1;
+
+select *
+ from multirangejoin_left left join multirangejoin_right
+ on (ir1 && ir4 and ir2 && ir3) order by ir4, ir3, ir2, ir1;
+set enable_mergejoin=true;
+
+drop table multirangejoin_left;
+drop table multirangejoin_right;
+
+create table bigrangejoin_left (i1 int, ir1 int4range);
+create table bigrangejoin_right (i2 int, ir2 int4range);
+
+-- 100 small ranges
+insert into bigrangejoin_left
+ select g/4,
+ int4range(g,
+ g + case when (g%2=0) then g%7 else 12-(g%11) end)
+ from generate_series(1,100) g;
+insert into bigrangejoin_right
+ select g/4,
+ int4range(g-7+(g%19),
+ g-7+(g%19) + case when (g%3=0) then g%11 else 17-(g%15) end)
+ from generate_series(1,100) g;
+
+-- 10 medium ranges
+insert into bigrangejoin_left
+ select g/4*10,
+ int4range(g*10,
+ g*10 + case when (g%2=0) then g%7 else 12-(g%11) end)
+ from generate_series(1,10) g;
+insert into bigrangejoin_right
+ select g/4*10,
+ int4range(g*10-57+(g%173),
+ g*10-57+(g%173) + case when (g%3=0) then g%123 else 97-(g%83) end)
+ from generate_series(1,10) g;
+
+insert into bigrangejoin_left select g*11-21, 'empty'::int4range
+ from generate_series(1,9) g;
+
+insert into bigrangejoin_right select g*13-29, 'empty'::int4range
+ from generate_series(1,8) g;
+
+insert into bigrangejoin_left values
+ (4, int4range(NULL,5)),
+ (93, int4range(95, NULL));
+
+insert into bigrangejoin_right values
+ (7, int4range(NULL,3)),
+ (92, int4range(99, NULL));
+
+create temp table rangejoin_result1
+ (i1 int, ir1 int4range, i2 int, ir2 int4range);
+create temp table rangejoin_result2
+ (i1 int, ir1 int4range, i2 int, ir2 int4range);
+
+set enable_hashjoin=false;
+explain (costs off) insert into rangejoin_result1
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left left join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 nulls first, i1 desc;
+
+insert into rangejoin_result1
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left left join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 nulls first, i1 desc;
+set enable_hashjoin=true;
+
+set enable_mergejoin=false;
+explain (costs off) insert into rangejoin_result2
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left left join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 nulls first, i1 desc;
+
+insert into rangejoin_result2
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left left join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 nulls first, i1 desc;
+set enable_mergejoin=true;
+
+select count(*) from rangejoin_result1;
+select count(*) from rangejoin_result2;
+
+select * from rangejoin_result1 except select * from rangejoin_result2;
+
+select * from rangejoin_result2 except select * from rangejoin_result1;
+
+drop table rangejoin_result1;
+drop table rangejoin_result2;
+
+create temp table rangejoin_result3
+ (i1 int, ir1 int4range, i2 int, ir2 int4range);
+create temp table rangejoin_result4
+ (i1 int, ir1 int4range, i2 int, ir2 int4range);
+
+
+explain (costs off) insert into rangejoin_result3
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left inner join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by i1, ir1;
+
+insert into rangejoin_result3
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left inner join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by i1, ir1;
+
+set enable_mergejoin=false;
+explain (costs off) insert into rangejoin_result4
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left inner join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by i1, ir1;
+
+insert into rangejoin_result4
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left inner join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by i1, ir1;
+set enable_mergejoin=true;
+
+select count(*) from rangejoin_result3;
+select count(*) from rangejoin_result4;
+
+select * from rangejoin_result3 except select * from rangejoin_result4;
+
+select * from rangejoin_result4 except select * from rangejoin_result3;
+
+drop table rangejoin_result3;
+drop table rangejoin_result4;
+
+drop table bigrangejoin_left;
+drop table bigrangejoin_right;
Re: Range Merge Join v1
Hi, Jeff!
I'm planning to provide the review for this patch in future. I've done
some performance tesing (see attachment).
All in all, nothing important, everything works fine.
Tests were executed under current HEAD on Ubuntu 16 over MacBook Air.
I observe that:
1. Patch brings performance improvement for specified query
2. Performance improvement of Range Merge Join vs GiST Nested Loop
Join (on Index Only Scan) is between 4x and 6x
3. Performance improvement of RMJ with B-tree index vs GiST is between
4x and 10x
(due to lack of actually competing cases, here I omit T-tests, they
are not that important when speaking about 4x difference)
4. Range Merge Join is capable to consume expressional index with
exactly same effect as direct index
5. Other attributes residing in joined tables do not affect
performance improvement
I'll make code review some time later, probably next week. (I hope
there is no urge in this, since commitfest is in July, or is it
urgent?) BTW fixe typo in index specification of original performance
test (both indexes were for same table)
Best regards, Andrey Borodin.
Attachments:
Re: Range Merge Join v1
Hi, Jeff!
Sorry for being late. Actually, I had several unsuccessful attempts to
find something wrong with the patch.
Here's my review.
in pathkey.c
ecs = (EquivalenceClass **) palloc(nClauses * sizeof(EquivalenceClass *));
scores = (int *) palloc(nClauses * sizeof(int));
range_ecs = palloc(nClauses * sizeof(bool));
Third assignment has no cast.
And I have few questions:
1. Are there any types, which could benefit from Range Merge and are
not covered by this patch?
2. Can Range Merge handle merge of different ranges? Like int4range()
&& int8range() ?
My perf test script from the previous message was broken, here's fixed
one in the attachment.
This patch implements feature, contains new tests and passes old
tests, is documented and spec compliant. I do not see any reason why
not mark it "Ready for committer".
Best regards, Andrey Borodin.
Attachments:
Re: Range Merge Join v1
On Tue, May 30, 2017 at 11:44 PM, Andrew Borodin <borodin@octonica.com> wrote:
Hi, Jeff!
Hi!
Sorry for being late. Actually, I had several unsuccessful attempts to
find something wrong with the patch.
Here's my review.in pathkey.c
ecs = (EquivalenceClass **) palloc(nClauses * sizeof(EquivalenceClass *));
scores = (int *) palloc(nClauses * sizeof(int));
range_ecs = palloc(nClauses * sizeof(bool));Third assignment has no cast.
Will fix.
And I have few questions:
1. Are there any types, which could benefit from Range Merge and are
not covered by this patch?
I thought about this for a while, and the only thing I can think of
are range joins that don't explicitly use range types.
2. Can Range Merge handle merge of different ranges? Like int4range()
&& int8range() ?
Right now, there aren't even casts between range types. I think the
best way to handle that at this point would be to add casts among the
numeric ranges. There may be advantages to supporting any two ranges
where the contained types are part of the same opfamily, but it seems
a little early to add that complication.
My perf test script from the previous message was broken, here's fixed
one in the attachment.This patch implements feature, contains new tests and passes old
tests, is documented and spec compliant. I do not see any reason why
not mark it "Ready for committer".
Great!
I think there are a couple more things that could be done if we want
to. Let me know if you think these things should be done now, or if
they should be a separate patch later when the need arises:
* Support for r1 @> r2 joins (join on "contains" rather than "overlaps").
* Better integration with the catalog so that users could add their
own types that support range merge join.
Thank you for the review.
Regards,
Jeff Davis
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Re: Range Merge Join v1
2017-06-02 19:42 GMT+05:00 Jeff Davis <pgsql@j-davis.com>:
On Tue, May 30, 2017 at 11:44 PM, Andrew Borodin <borodin@octonica.com> wrote:
1. Are there any types, which could benefit from Range Merge and are
not covered by this patch?I thought about this for a while, and the only thing I can think of
are range joins that don't explicitly use range types.
Let me try to write && in SQL
select * from a join b where (a.min<=b.max and a.min>=b.min) or
(a.max<=b.max and a.max>=b.min);
Quite complicated. Here user knows that min <= max, but DB don't. If
we write it precisely we get hell lot of permutations.
Here's what I think:
1. For me, this feature seems hard to implement.
2. This feature also will be hard to commit solely, since it's use
case will be rare.
3. If this could yield unexpected performance for queries like
select * from t where x<y and b>c or a!=z or [other conditions]
and optimizer could think: "Aha! I'll sort it and do it fast" it'd be cool.
I do not think range joins that don't explicitly use range types are
possible right now...
2. Can Range Merge handle merge of different ranges? Like int4range()
&& int8range() ?Right now, there aren't even casts between range types. I think the
best way to handle that at this point would be to add casts among the
numeric ranges. There may be advantages to supporting any two ranges
where the contained types are part of the same opfamily, but it seems
a little early to add that complication.
Agree.
I think there are a couple more things that could be done if we want
to. Let me know if you think these things should be done now, or if
they should be a separate patch later when the need arises:* Support for r1 @> r2 joins (join on "contains" rather than "overlaps").
* Better integration with the catalog so that users could add their
own types that support range merge join.
1. I believe this changes can be incremental. They constitute value
for the end user, then they are committable. This patch is not overly
complicated, but it's easier to do this stuff in small pieces.
2. The commitfest is 3 months away. If you will have new versions of
the patch, I'll review again. Maybe will spot some new things :)
Best regards, Andrey Borodin, Octonica.
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Re: Range Merge Join v1
Hi Jeff,
Fast range joins are very nice to have, thank you for working on this.
I've been doing a somewhat related thing recently, trying to teach the
merge join executor to perform full joins on comparison clauses [1]/messages/by-id/1d23ad41-a9d9-1d1e-1d79-83b002d6f776@postgrespro.ru. I
have some comments after reading your patch:
* At the moment, "mergejoinable clause" and "equality clause" mean the
same thing to the planner, and those clauses are used both to create
equivalence classes and to perform merge joins. If we start performing
merge joins for different kinds of clauses, such as comparison or range
intersection, it makes sense to separate these two meanings. I tried
this in my patch and it didn't require many changes. I use
RestrictInfo.equivopfamilies to build equivalence classes, and
RestrictInfo.mergeopfamilies for mergejoinable clauses.
* Semantically, MJCompare() is a function that determines whether you
should emit a join result or advance one of the pointers. This meaning
is not explicit in the code and is not well encapsulated: the function
returns and int and 'compareNoMatch' flag, and the calling code combines
them in various ways to derive the final result. This meaning can be
made explicit by making MJCompare return enum values {Join, NextInner,
NextOuter}, and putting inside it all the logic that decides whether we
join or advance. ExecMergeJoin looks intimidating already, and I think
this change would help readability. Again, you can find an illustration
in my patch.
I hope you find these points helpful.
[1]: /messages/by-id/1d23ad41-a9d9-1d1e-1d79-83b002d6f776@postgrespro.ru
/messages/by-id/1d23ad41-a9d9-1d1e-1d79-83b002d6f776@postgrespro.ru
--
Alexander Kuzmenkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Re: Range Merge Join v1
On Fri, Aug 25, 2017 at 10:19 AM, Alexander Kuzmenkov
<a.kuzmenkov@postgrespro.ru> wrote:
Hi Jeff,
Hi,
Thank you for the review and suggestions!
* At the moment, "mergejoinable clause" and "equality clause" mean the same
thing to the planner, and those clauses are used both to create equivalence
classes and to perform merge joins. If we start performing merge joins for
different kinds of clauses, such as comparison or range intersection, it
makes sense to separate these two meanings. I tried this in my patch and it
didn't require many changes. I use RestrictInfo.equivopfamilies to build
equivalence classes, and RestrictInfo.mergeopfamilies for mergejoinable
clauses.
I like the idea. I will look in more detail and I can either change my
patch or piggyback on yours.
* Semantically, MJCompare() is a function that determines whether you should
emit a join result or advance one of the pointers. This meaning is not
explicit in the code and is not well encapsulated: the function returns and
int and 'compareNoMatch' flag, and the calling code combines them in various
ways to derive the final result. This meaning can be made explicit by making
MJCompare return enum values {Join, NextInner, NextOuter}, and putting
inside it all the logic that decides whether we join or advance.
ExecMergeJoin looks intimidating already, and I think this change would help
readability. Again, you can find an illustration in my patch.
I actually tried doing something similar in my patch, but there are
four cases to consider in EXEC_MJ_SKIP_TEST:
1. Overlaps: mark and then join the tuples
2. left-of: SKIPOUTER_ADVANCE
3. right-of: SKIPINNER_ADVANCE
4. None of the above: mark and NEXTINNER
However, you are right that the current code is ugly, and I should
refactor into 4 explicit cases. I don't think I will call them by the
same names as the join states, though, because there's not a direct
mapping.
Updated patch attached. Changelog:
* Rebased
* Changed MJCompare to return an enum as suggested, but it has 4
possible values rather than 3.
* Added support for joining on contains or contained by (@> or <@) and
updated tests.
Regards,
Jeff Davis
Attachments:
rangejoin-v3.difftext/plain; charset=US-ASCII; name=rangejoin-v3.diffDownload
diff --git a/doc/src/sgml/rangetypes.sgml b/doc/src/sgml/rangetypes.sgml
index 9557c16..84578a7 100644
*** a/doc/src/sgml/rangetypes.sgml
--- b/doc/src/sgml/rangetypes.sgml
***************
*** 522,525 **** INSERT 0 1
--- 522,595 ----
</programlisting>
</para>
</sect2>
+ <sect2 id="rangetypes-join">
+ <title>Range Join</title>
+
+ <indexterm>
+ <primary>range type</primary>
+ <secondary>join</secondary>
+ </indexterm>
+
+ <para>
+ A Range Join is a join where one of the join conditions is the range
+ overlaps operator (see <xref linkend="range-operators-table">). In other
+ words, rather than returning rows where corresponding fields are equal, it
+ returns rows where the corresponding fields overlap.
+ </para>
+ <para>
+ For instance, to find users who were active on a website at the same time
+ as they were using a mobile app, you might issue a query like:
+ <programlisting>
+ CREATE TABLE web_session(
+ web_session_id text primary key,
+ username text,
+ during tstzrange);
+ CREATE TABLE app_session(
+ app_session_id text primary key,
+ username text,
+ during tstzrange);
+ INSERT INTO web_session VALUES
+ ('0cc175b9c0f1b6a8', 'user1', '[2017-02-01 09:30, 2017-02-01 10:45)'),
+ ('92eb5ffee6ae2fec', 'user2', '[2017-02-01 09:30, 2017-02-01 10:45)'),
+ ('4a8a08f09d37b737', 'user3', '[2017-02-01 09:30, 2017-02-01 10:45)');
+ INSERT INTO app_session VALUES
+ ('8277e0910d750195', 'user1', '[2017-02-01 10:30, 2017-02-01 11:45)'),
+ ('b448797616e091ad', 'user3', '[2017-02-01 09:00, 2017-02-01 11:00)'),
+ ('95649038408b5f33', 'user4', '[2017-02-01 09:30, 2017-02-01 10:45)');
+
+ SELECT w.username,
+ w.during * a.during AS both_during
+ FROM web_session w, app_session a
+ WHERE w.username = a.username
+ AND w.during && a.during;
+ username | both_during
+ ----------+-----------------------------------------------------
+ user1 | ["2017-02-01 10:30:00-08","2017-02-01 10:45:00-08")
+ user3 | ["2017-02-01 09:30:00-08","2017-02-01 10:45:00-08")
+ (2 rows)
+ </programlisting>
+ </para>
+ <para>
+ In addition to the general execution strategies available, Postgres also
+ has special support for a variant of Merge Join called Range Merge Join:
+ <programlisting>
+ EXPLAIN (costs off) SELECT w.username,
+ w.during * a.during AS both_during
+ FROM web_session w, app_session a
+ WHERE w.username = a.username
+ AND w.during && a.during;
+ QUERY PLAN
+ ----------------------------------------------------------------------
+ Range Merge Join
+ Merge Cond: ((w.during && a.during) AND (w.username = a.username))
+ -> Sort
+ Sort Key: w.during, w.username
+ -> Seq Scan on web_session w
+ -> Sort
+ Sort Key: a.during, a.username
+ -> Seq Scan on app_session a
+ (8 rows)
+ </programlisting>
+ </para>
+ </sect2>
</sect1>
diff --git a/src/backend/commands/eindex 4cee357..620c8bd 100644
*** a/src/backend/commands/explain.c
--- b/src/backend/commands/explain.c
***************
*** 922,928 **** ExplainNode(PlanState *planstate, List *ancestors,
pname = sname = "Nested Loop";
break;
case T_MergeJoin:
! pname = "Merge"; /* "Join" gets added by jointype switch */
sname = "Merge Join";
break;
case T_HashJoin:
--- 922,932 ----
pname = sname = "Nested Loop";
break;
case T_MergeJoin:
! if (((MergeJoin*)plan)->mergeRangeJoin)
! pname = "Range Merge"; /* "Join" gets added by jointype switch */
! else
! pname = "Merge"; /* "Join" gets added by jointype switch */
!
sname = "Merge Join";
break;
case T_HashJoin:
diff --git a/src/backend/executor/nodindex 925b4cf..ebb3505 100644
*** a/src/backend/executor/nodeMergejoin.c
--- b/src/backend/executor/nodeMergejoin.c
***************
*** 89,103 ****
--- 89,155 ----
* proceed to another state. This state is stored in the node's
* execution state information and is preserved across calls to
* ExecMergeJoin. -cim 10/31/89
+ *
+ * RANGE MERGE JOIN
+ *
+ * Range Merge Join is a generalization of merge join. When a join
+ * predicate involves the range overlaps operator (&&), a merge join
+ * becomes a range join.
+ *
+ * The input ranges must be ordered by (lower-bound, upper-bound), which
+ * is the ordinary range_ops operator class. MJCompare must not simply
+ * use the operator class's comparison semantics though; instead it
+ * returns:
+ *
+ * - MJCMP_MATCHES if outer range overlaps inner range
+ * - MJCMP_LEFTOF if outer range is strictly left-of inner range
+ * - MJCMP_RIGHTOF if outer range is strictly right-of inner range
+ *
+ * NB: the above is a simplification considering only a single merge
+ * clause. When there are multiple merge clauses, it's possible that one
+ * tuple is neither right-of, nor left-of, nor matching. For instance, if
+ * an earlier range merge clause matches (overlaps), but a later clause
+ * fails. In that case, MJCompare returns MJCMP_NOSKIP.
+ *
+ * If MJCompare returns MJCMP_RIGHTOF, later or earlier tuples on the
+ * inner side may match. For example:
+ *
+ * OUTER INNER
+ * ... [1,9] matches current outer
+ * [4,5] [2,3] no match
+ * ... [3,5] matches current outer
+ * ... [7,9] no match and no later matches for current outer
+ *
+ * Outer tuple [4,5] does not match [2,3], but it matches (overlaps with)
+ * the earlier tuple [1,9] and the later tuple [3,5]. But once we
+ * encounter [7,9], we know that no later inner tuple can possibly match
+ * the outer.
+ *
+ * When doing a range join, we lose two merge join optimizations:
+ *
+ * 1. Ordinary merge join only restores to the mark if it's equal to the
+ * new outer. For range join, we must always restore to the mark
+ * because there may be matches after the mark and before the current
+ * inner tuple.
+ * 2. After restoring to the mark, ordinary merge join immediately moves
+ * to JOINTUPLES. Range join must move to SKIP_TEST first.
+ *
+ * Range merge join is unable to implement RIGHT/FULL joins. It's also
+ * unable to cope with reverse sort order, because there could always be
+ * some later inner range that matches the outer tuple.
*/
#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/lsyscache.h"
#include "utils/memutils.h"
+ #include "utils/rangetypes.h"
+ #include "utils/typcache.h"
/*
***************
*** 138,143 **** typedef struct MergeJoinClauseData
--- 190,203 ----
* stored here.
*/
SortSupportData ssup;
+
+ /* needed for Range Join */
+ bool isrange;
+ TypeCacheEntry *range_typcache;
+ bool (*range_matches_fn)(TypeCacheEntry *typcache,
+ RangeType *r1, RangeType *r2);
+ bool range_left_empty_ok;
+ bool range_right_empty_ok;
} MergeJoinClauseData;
/* Result type for MJEvalOuterValues and MJEvalInnerValues */
***************
*** 148,153 **** typedef enum
--- 208,220 ----
MJEVAL_ENDOFJOIN /* end of input (physical or effective) */
} MJEvalResult;
+ typedef enum
+ {
+ MJCMP_LEFTOF,
+ MJCMP_RIGHTOF,
+ MJCMP_MATCHES,
+ MJCMP_NOSKIP
+ } MJCompareResult;
#define MarkInnerTuple(innerTupleSlot, mergestate) \
ExecCopySlot((mergestate)->mj_MarkedTupleSlot, (innerTupleSlot))
***************
*** 178,183 **** MJExamineQuals(List *mergeclauses,
--- 245,251 ----
Oid *mergecollations,
int *mergestrategies,
bool *mergenullsfirst,
+ bool *israngejoin,
PlanState *parent)
{
MergeJoinClause clauses;
***************
*** 185,190 **** MJExamineQuals(List *mergeclauses,
--- 253,260 ----
int iClause;
ListCell *cl;
+ *israngejoin = false;
+
clauses = (MergeJoinClause) palloc0(nClauses * sizeof(MergeJoinClauseData));
iClause = 0;
***************
*** 196,201 **** MJExamineQuals(List *mergeclauses,
--- 266,272 ----
Oid collation = mergecollations[iClause];
StrategyNumber opstrategy = mergestrategies[iClause];
bool nulls_first = mergenullsfirst[iClause];
+ Oid eq_opno;
int op_strategy;
Oid op_lefttype;
Oid op_righttype;
***************
*** 221,228 **** MJExamineQuals(List *mergeclauses,
elog(ERROR, "unsupported mergejoin strategy %d", opstrategy);
clause->ssup.ssup_nulls_first = nulls_first;
/* Extract the operator's declared left/right datatypes */
! get_op_opfamily_properties(qual->opno, opfamily, false,
&op_strategy,
&op_lefttype,
&op_righttype);
--- 292,347 ----
elog(ERROR, "unsupported mergejoin strategy %d", opstrategy);
clause->ssup.ssup_nulls_first = nulls_first;
+ /*
+ * If a range join, the original operator must be "&&" rather than
+ * "=". Set eq_opno to the range equality operator for the purposes of
+ * setting up the merge clause, but mark it as a range.
+ */
+ if (qual->opno == OID_RANGE_OVERLAP_OP ||
+ qual->opno == OID_RANGE_CONTAINS_OP ||
+ qual->opno == OID_RANGE_CONTAINED_OP)
+ {
+ Oid rngtypid = exprType((Node*)clause->lexpr->expr);
+
+ Assert(exprType((Node*)clause->lexpr->expr) ==
+ exprType((Node*)clause->rexpr->expr));
+
+ eq_opno = OID_RANGE_EQ_OP;
+ clause->isrange = true;
+
+ switch (qual->opno)
+ {
+ case OID_RANGE_OVERLAP_OP:
+ clause->range_matches_fn = range_overlaps_internal;
+ clause->range_left_empty_ok = false;
+ clause->range_right_empty_ok = false;
+ break;
+ case OID_RANGE_CONTAINS_OP:
+ clause->range_matches_fn = range_contains_internal;
+ clause->range_left_empty_ok = false;
+ clause->range_right_empty_ok = true;
+ break;
+ case OID_RANGE_CONTAINED_OP:
+ clause->range_matches_fn = range_contained_by_internal;
+ clause->range_left_empty_ok = true;
+ clause->range_right_empty_ok = false;
+ break;
+ }
+
+ clause->range_typcache = lookup_type_cache(rngtypid,
+ TYPECACHE_RANGE_INFO);
+ *israngejoin = true;
+ }
+ else
+ {
+ eq_opno = qual->opno;
+ clause->isrange = false;
+ clause->range_typcache = NULL;
+ }
+
+
/* Extract the operator's declared left/right datatypes */
! get_op_opfamily_properties(eq_opno, opfamily, false,
&op_strategy,
&op_lefttype,
&op_righttype);
***************
*** 324,329 **** MJEvalOuterValues(MergeJoinState *mergestate)
--- 443,454 ----
else if (result == MJEVAL_MATCHABLE)
result = MJEVAL_NONMATCHABLE;
}
+ else if (clause->isrange)
+ {
+ if (!clause->range_left_empty_ok &&
+ RangeIsEmpty(DatumGetRangeType(clause->ldatum)))
+ result = MJEVAL_NONMATCHABLE;
+ }
}
MemoryContextSwitchTo(oldContext);
***************
*** 371,376 **** MJEvalInnerValues(MergeJoinState *mergestate, TupleTableSlot *innerslot)
--- 496,507 ----
else if (result == MJEVAL_MATCHABLE)
result = MJEVAL_NONMATCHABLE;
}
+ else if (clause->isrange)
+ {
+ if (!clause->range_right_empty_ok &&
+ RangeIsEmpty(DatumGetRangeType(clause->rdatum)))
+ result = MJEVAL_NONMATCHABLE;
+ }
}
MemoryContextSwitchTo(oldContext);
***************
*** 379,384 **** MJEvalInnerValues(MergeJoinState *mergestate, TupleTableSlot *innerslot)
--- 510,543 ----
}
/*
+ * Return 0 if ranges overlap, <0 if the first range is left-of the second, or
+ * >0 if the first range is right-of the second. See comment at the top of the
+ * file for explanation.
+ */
+ static int
+ ApplyRangeMatch(Datum ldatum, bool lisnull, Datum rdatum, bool risnull,
+ SortSupport ssup, TypeCacheEntry *typcache)
+ {
+ /* can't handle reverse sort order; should be prevented by optimizer */
+ Assert(!ssup->ssup_reverse);
+ Assert(!lisnull || !risnull);
+
+ if (lisnull)
+ return ssup->ssup_nulls_first ? -1 : 1;
+ if (risnull)
+ return ssup->ssup_nulls_first ? 1 : -1;
+
+ if (range_before_internal(typcache, DatumGetRangeType(ldatum),
+ DatumGetRangeType(rdatum)))
+ return -1;
+ else if (range_after_internal(typcache, DatumGetRangeType(ldatum),
+ DatumGetRangeType(rdatum)))
+ return 1;
+ else
+ return 0;
+ }
+
+ /*
* MJCompare
*
* Compare the mergejoinable values of the current two input tuples
***************
*** 388,398 **** MJEvalInnerValues(MergeJoinState *mergestate, TupleTableSlot *innerslot)
* MJEvalOuterValues and MJEvalInnerValues must already have been called
* for the current outer and inner tuples, respectively.
*/
! static int
MJCompare(MergeJoinState *mergestate)
{
int result = 0;
bool nulleqnull = false;
ExprContext *econtext = mergestate->js.ps.ps_ExprContext;
int i;
MemoryContext oldContext;
--- 547,559 ----
* MJEvalOuterValues and MJEvalInnerValues must already have been called
* for the current outer and inner tuples, respectively.
*/
! static MJCompareResult
MJCompare(MergeJoinState *mergestate)
{
int result = 0;
bool nulleqnull = false;
+ bool noskip = false;
+ bool nomatch = false;
ExprContext *econtext = mergestate->js.ps.ps_ExprContext;
int i;
MemoryContext oldContext;
***************
*** 418,431 **** MJCompare(MergeJoinState *mergestate)
continue;
}
! result = ApplySortComparator(clause->ldatum, clause->lisnull,
! clause->rdatum, clause->risnull,
! &clause->ssup);
! if (result != 0)
break;
}
/*
* If we had any NULL-vs-NULL inputs, we do not want to report that the
* tuples are equal. Instead, if result is still 0, change it to +1. This
--- 579,618 ----
continue;
}
! if (clause->isrange)
! {
! result = ApplyRangeMatch(clause->ldatum, clause->lisnull,
! clause->rdatum, clause->risnull,
! &clause->ssup, clause->range_typcache);
! if (result == 0)
! {
! /*
! * If the first clause overlaps, we can't skip this tuple
! * because a later tuple may still match it.
! */
! noskip = true;
! /*
! * Check that this clause matches the join condition.
! */
! if (!clause->range_matches_fn(
! clause->range_typcache,
! DatumGetRangeType(clause->ldatum),
! DatumGetRangeType(clause->rdatum)))
! nomatch = true;
! }
! }
! else
! result = ApplySortComparator(clause->ldatum, clause->lisnull,
! clause->rdatum, clause->risnull,
! &clause->ssup);
!
! if (result != 0 || nomatch)
break;
}
+ MemoryContextSwitchTo(oldContext);
+
/*
* If we had any NULL-vs-NULL inputs, we do not want to report that the
* tuples are equal. Instead, if result is still 0, change it to +1. This
***************
*** 437,447 **** MJCompare(MergeJoinState *mergestate)
*/
if (result == 0 &&
(nulleqnull || mergestate->mj_ConstFalseJoin))
! result = 1;
! MemoryContextSwitchTo(oldContext);
!
! return result;
}
--- 624,650 ----
*/
if (result == 0 &&
(nulleqnull || mergestate->mj_ConstFalseJoin))
! return MJCMP_RIGHTOF;
! /*
! * Range Join: if the first clause overlaps (regardless of the range
! * operator), we must never skip the tuple because a later tuple may still
! * match it. But the tuples may still not match (i.e. should not produce a
! * join result) if later clauses do not overlap or if the operator fails
! * to match for some overlapping ranges (e.g. "contains" will fail if the
! * right operand is a larger range than the left).
! */
! if (result != 0 && noskip)
! return MJCMP_NOSKIP;
! if (result == 0 && nomatch)
! return MJCMP_NOSKIP;
!
! if (result == 0)
! return MJCMP_MATCHES;
! else if (result < 0)
! return MJCMP_LEFTOF;
! else
! return MJCMP_RIGHTOF;
}
***************
*** 533,539 **** check_constant_qual(List *qual, bool *is_const_false)
return true;
}
-
/* ----------------------------------------------------------------
* ExecMergeTupleDump
*
--- 736,741 ----
diff --git a/src/backend/optimizer/path/joiindex 43833ea..99eff87 100644
*** a/src/backend/optimizer/path/joinpath.c
--- b/src/backend/optimizer/path/joinpath.c
***************
*** 481,486 **** try_mergejoin_path(PlannerInfo *root,
--- 481,499 ----
Relids required_outer;
JoinCostWorkspace workspace;
+ /* RIGHT/FULL joins don't support range join */
+ if (jointype == JOIN_RIGHT || jointype == JOIN_FULL)
+ {
+ ListCell *lc;
+
+ foreach(lc, mergeclauses)
+ {
+ RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(lc);
+ if (restrictinfo->rangejoin)
+ return;
+ }
+ }
+
if (is_partial)
{
try_partial_mergejoin_path(root,
diff --git a/src/backend/optimizer/path/pathindex 9d83a5c..ba58129 100644
*** a/src/backend/optimizer/path/pathkeys.c
--- b/src/backend/optimizer/path/pathkeys.c
***************
*** 1125,1130 **** select_outer_pathkeys_for_merge(PlannerInfo *root,
--- 1125,1131 ----
int nClauses = list_length(mergeclauses);
EquivalenceClass **ecs;
int *scores;
+ bool *range_ecs;
int necs;
ListCell *lc;
int j;
***************
*** 1139,1144 **** select_outer_pathkeys_for_merge(PlannerInfo *root,
--- 1140,1146 ----
*/
ecs = (EquivalenceClass **) palloc(nClauses * sizeof(EquivalenceClass *));
scores = (int *) palloc(nClauses * sizeof(int));
+ range_ecs = palloc(nClauses * sizeof(bool));
necs = 0;
foreach(lc, mergeclauses)
***************
*** 1179,1184 **** select_outer_pathkeys_for_merge(PlannerInfo *root,
--- 1181,1187 ----
ecs[necs] = oeclass;
scores[necs] = score;
+ range_ecs[necs] = rinfo->rangejoin;
necs++;
}
***************
*** 1196,1201 **** select_outer_pathkeys_for_merge(PlannerInfo *root,
--- 1199,1209 ----
for (j = 0; j < necs; j++)
{
+ /* for range join, the input order must be ascending */
+ if (range_ecs[j] &&
+ query_pathkey->pk_strategy != BTLessStrategyNumber)
+ continue;
+
if (ecs[j] == query_ec)
break; /* found match */
}
diff --git a/src/backend/optimizer/plan/initindex 987c20a..9c7bc92 100644
*** a/src/backend/optimizer/plan/initsplan.c
--- b/src/backend/optimizer/plan/initsplan.c
***************
*** 14,19 ****
--- 14,20 ----
*/
#include "postgres.h"
+ #include "catalog/pg_operator.h"
#include "catalog/pg_type.h"
#include "nodes/nodeFuncs.h"
#include "optimizer/clauses.h"
***************
*** 1940,1946 **** distribute_qual_to_rels(PlannerInfo *root, Node *clause,
*/
if (restrictinfo->mergeopfamilies)
{
! if (maybe_equivalence)
{
if (check_equivalence_delay(root, restrictinfo) &&
process_equivalence(root, restrictinfo, below_outer_join))
--- 1941,1947 ----
*/
if (restrictinfo->mergeopfamilies)
{
! if (maybe_equivalence && !restrictinfo->rangejoin)
{
if (check_equivalence_delay(root, restrictinfo) &&
process_equivalence(root, restrictinfo, below_outer_join))
***************
*** 2594,2599 **** check_mergejoinable(RestrictInfo *restrictinfo)
--- 2595,2608 ----
opno = ((OpExpr *) clause)->opno;
leftarg = linitial(((OpExpr *) clause)->args);
+ if (opno == OID_RANGE_OVERLAP_OP ||
+ opno == OID_RANGE_CONTAINS_OP ||
+ opno == OID_RANGE_CONTAINED_OP)
+ {
+ restrictinfo->rangejoin = true;
+ opno = OID_RANGE_EQ_OP;
+ }
+
if (op_mergejoinable(opno, exprType(leftarg)) &&
!contain_volatile_functions((Node *) clause))
restrictinfo->mergeopfamilies = get_mergejoin_opfamilies(opno);
diff --git a/src/backend/optimizer/util/restrindex 39b52ae..ba0dd7b 100644
*** a/src/backend/optimizer/util/restrictinfo.c
--- b/src/backend/optimizer/util/restrictinfo.c
***************
*** 186,191 **** make_restrictinfo_internal(Expr *clause,
--- 186,192 ----
restrictinfo->outer_selec = -1;
restrictinfo->mergeopfamilies = NIL;
+ restrictinfo->rangejoin = false;
restrictinfo->left_ec = NULL;
restrictinfo->right_ec = NULL;
diff --git a/src/backend/utils/adt/selfuncs.c b/index 23e5526..555d510 100644
*** a/src/backend/utils/adt/selfuncs.c
--- b/src/backend/utils/adt/selfuncs.c
***************
*** 2851,2857 **** mergejoinscansel(PlannerInfo *root, Node *clause,
*right;
VariableStatData leftvar,
rightvar;
- int op_strategy;
Oid op_lefttype;
Oid op_righttype;
Oid opno,
--- 2851,2856 ----
diff --git a/src/include/catalog/pg_opeindex ffabc20..7e32c5f 100644
*** a/src/include/catalog/pg_operator.h
--- b/src/include/catalog/pg_operator.h
***************
*** 1748,1753 **** DESCR("greater than or equal");
--- 1748,1754 ----
/* generic range type operators */
DATA(insert OID = 3882 ( "=" PGNSP PGUID b t t 3831 3831 16 3882 3883 range_eq eqsel eqjoinsel ));
DESCR("equal");
+ #define OID_RANGE_EQ_OP 3882
DATA(insert OID = 3883 ( "<>" PGNSP PGUID b f f 3831 3831 16 3883 3882 range_ne neqsel neqjoinsel ));
DESCR("not equal");
DATA(insert OID = 3884 ( "<" PGNSP PGUID b f f 3831 3831 16 3887 3886 range_lt rangesel scalarltjoinsel ));
diff --git a/src/include/nodes/plannodesindex 7c51e7f..4dc0d8d 100644
*** a/src/include/nodes/plannodes.h
--- b/src/include/nodes/plannodes.h
***************
*** 714,719 **** typedef struct MergeJoin
--- 714,720 ----
Oid *mergeCollations; /* per-clause OIDs of collations */
int *mergeStrategies; /* per-clause ordering (ASC or DESC) */
bool *mergeNullsFirst; /* per-clause nulls ordering */
+ bool mergeRangeJoin; /* is this a range merge join? */
} MergeJoin;
/* ----------------
diff --git a/src/include/nodes/relatindex 3ccc9d1..5bca967 100644
*** a/src/include/nodes/relation.h
--- b/src/include/nodes/relation.h
***************
*** 1791,1796 **** typedef struct RestrictInfo
--- 1791,1799 ----
/* valid if clause is mergejoinable, else NIL */
List *mergeopfamilies; /* opfamilies containing clause operator */
+ /* is a rangejoin clause? */
+ bool rangejoin;
+
/* cache space for mergeclause processing; NULL if not yet set */
EquivalenceClass *left_ec; /* EquivalenceClass containing lefthand */
EquivalenceClass *right_ec; /* EquivalenceClass containing righthand */
diff --git a/src/test/regress/expecnew file mode 100644
index 0000000..d21ecbc
*** /dev/null
--- b/src/test/regress/expected/rangejoin.out
***************
*** 0 ****
--- 1,661 ----
+ create table rangejoin_left(i1 int, ir1 int4range);
+ create table rangejoin_right(i2 int, ir2 int4range);
+ insert into rangejoin_left values
+ (1001, int4range(10, 80)),
+ (1002, int4range(20, 30)),
+ (1003, int4range(21, 25)),
+ (1004, int4range(22, 35)),
+ (1005, int4range(40, 60)),
+ (1006, int4range(50, 60));
+ insert into rangejoin_right values
+ (1000, 'empty'::int4range),
+ (1001, int4range(NULL, 4)),
+ (1002, int4range(10, 12)),
+ (1003, int4range(11, 14)),
+ (1004, int4range(20, 45)),
+ (1005, int4range(24, 28)),
+ (1006, int4range(85, 90));
+ -- simple inner join with =
+ explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left, rangejoin_right
+ where ir1 = ir2;
+ QUERY PLAN
+ ----------------------------------------------------------
+ Merge Join
+ Merge Cond: (rangejoin_left.ir1 = rangejoin_right.ir2)
+ -> Sort
+ Sort Key: rangejoin_left.ir1
+ -> Seq Scan on rangejoin_left
+ -> Sort
+ Sort Key: rangejoin_right.ir2
+ -> Seq Scan on rangejoin_right
+ (8 rows)
+
+ select i1, ir1, i2, ir2
+ from rangejoin_left, rangejoin_right
+ where ir1 = ir2;
+ i1 | ir1 | i2 | ir2
+ ----+-----+----+-----
+ (0 rows)
+
+ -- inner join with &&
+ explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left, rangejoin_right
+ where ir1 && ir2;
+ QUERY PLAN
+ -----------------------------------------------------------
+ Range Merge Join
+ Merge Cond: (rangejoin_left.ir1 && rangejoin_right.ir2)
+ -> Sort
+ Sort Key: rangejoin_left.ir1
+ -> Seq Scan on rangejoin_left
+ -> Sort
+ Sort Key: rangejoin_right.ir2
+ -> Seq Scan on rangejoin_right
+ (8 rows)
+
+ select i1, ir1, i2, ir2
+ from rangejoin_left, rangejoin_right
+ where ir1 && ir2;
+ i1 | ir1 | i2 | ir2
+ ------+---------+------+---------
+ 1001 | [10,80) | 1002 | [10,12)
+ 1001 | [10,80) | 1003 | [11,14)
+ 1001 | [10,80) | 1004 | [20,45)
+ 1001 | [10,80) | 1005 | [24,28)
+ 1002 | [20,30) | 1004 | [20,45)
+ 1002 | [20,30) | 1005 | [24,28)
+ 1003 | [21,25) | 1004 | [20,45)
+ 1003 | [21,25) | 1005 | [24,28)
+ 1004 | [22,35) | 1004 | [20,45)
+ 1004 | [22,35) | 1005 | [24,28)
+ 1005 | [40,60) | 1004 | [20,45)
+ (11 rows)
+
+ -- inner join with @>
+ explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left, rangejoin_right
+ where ir1 @> ir2;
+ QUERY PLAN
+ -----------------------------------------------------------
+ Range Merge Join
+ Merge Cond: (rangejoin_left.ir1 @> rangejoin_right.ir2)
+ -> Sort
+ Sort Key: rangejoin_left.ir1
+ -> Seq Scan on rangejoin_left
+ -> Sort
+ Sort Key: rangejoin_right.ir2
+ -> Seq Scan on rangejoin_right
+ (8 rows)
+
+ select i1, ir1, i2, ir2
+ from rangejoin_left, rangejoin_right
+ where ir1 @> ir2;
+ i1 | ir1 | i2 | ir2
+ ------+---------+------+---------
+ 1001 | [10,80) | 1000 | empty
+ 1001 | [10,80) | 1002 | [10,12)
+ 1001 | [10,80) | 1003 | [11,14)
+ 1001 | [10,80) | 1004 | [20,45)
+ 1001 | [10,80) | 1005 | [24,28)
+ 1002 | [20,30) | 1000 | empty
+ 1002 | [20,30) | 1005 | [24,28)
+ 1003 | [21,25) | 1000 | empty
+ 1004 | [22,35) | 1000 | empty
+ 1004 | [22,35) | 1005 | [24,28)
+ 1005 | [40,60) | 1000 | empty
+ 1006 | [50,60) | 1000 | empty
+ (12 rows)
+
+ -- inner join with <@
+ explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left, rangejoin_right
+ where ir1 <@ ir2;
+ QUERY PLAN
+ -----------------------------------------------------------
+ Range Merge Join
+ Merge Cond: (rangejoin_left.ir1 <@ rangejoin_right.ir2)
+ -> Sort
+ Sort Key: rangejoin_left.ir1
+ -> Seq Scan on rangejoin_left
+ -> Sort
+ Sort Key: rangejoin_right.ir2
+ -> Seq Scan on rangejoin_right
+ (8 rows)
+
+ select i1, ir1, i2, ir2
+ from rangejoin_left, rangejoin_right
+ where ir1 <@ ir2;
+ i1 | ir1 | i2 | ir2
+ ------+---------+------+---------
+ 1002 | [20,30) | 1004 | [20,45)
+ 1003 | [21,25) | 1004 | [20,45)
+ 1004 | [22,35) | 1004 | [20,45)
+ (3 rows)
+
+ -- two predicates
+ explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left inner join rangejoin_right
+ on (i1 = i2 and ir1 && ir2);
+ QUERY PLAN
+ ----------------------------------------------------------------------------------------------------------
+ Range Merge Join
+ Merge Cond: ((rangejoin_left.ir1 && rangejoin_right.ir2) AND (rangejoin_left.i1 = rangejoin_right.i2))
+ -> Sort
+ Sort Key: rangejoin_left.ir1, rangejoin_left.i1
+ -> Seq Scan on rangejoin_left
+ -> Sort
+ Sort Key: rangejoin_right.ir2, rangejoin_right.i2
+ -> Seq Scan on rangejoin_right
+ (8 rows)
+
+ select i1, ir1, i2, ir2
+ from rangejoin_left inner join rangejoin_right
+ on (i1 = i2 and ir1 && ir2);
+ i1 | ir1 | i2 | ir2
+ ------+---------+------+---------
+ 1004 | [22,35) | 1004 | [20,45)
+ (1 row)
+
+ -- left join
+ explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left left join rangejoin_right
+ on (ir1 && ir2);
+ QUERY PLAN
+ -----------------------------------------------------------
+ Range Merge Left Join
+ Merge Cond: (rangejoin_left.ir1 && rangejoin_right.ir2)
+ -> Sort
+ Sort Key: rangejoin_left.ir1
+ -> Seq Scan on rangejoin_left
+ -> Sort
+ Sort Key: rangejoin_right.ir2
+ -> Seq Scan on rangejoin_right
+ (8 rows)
+
+ select i1, ir1, i2, ir2
+ from rangejoin_left left join rangejoin_right
+ on (ir1 && ir2);
+ i1 | ir1 | i2 | ir2
+ ------+---------+------+---------
+ 1001 | [10,80) | 1002 | [10,12)
+ 1001 | [10,80) | 1003 | [11,14)
+ 1001 | [10,80) | 1004 | [20,45)
+ 1001 | [10,80) | 1005 | [24,28)
+ 1002 | [20,30) | 1004 | [20,45)
+ 1002 | [20,30) | 1005 | [24,28)
+ 1003 | [21,25) | 1004 | [20,45)
+ 1003 | [21,25) | 1005 | [24,28)
+ 1004 | [22,35) | 1004 | [20,45)
+ 1004 | [22,35) | 1005 | [24,28)
+ 1005 | [40,60) | 1004 | [20,45)
+ 1006 | [50,60) | |
+ (12 rows)
+
+ -- right join should be implemented as left join
+ explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left right join rangejoin_right
+ on (ir1 && ir2);
+ QUERY PLAN
+ -----------------------------------------------------------
+ Range Merge Left Join
+ Merge Cond: (rangejoin_right.ir2 && rangejoin_left.ir1)
+ -> Sort
+ Sort Key: rangejoin_right.ir2
+ -> Seq Scan on rangejoin_right
+ -> Sort
+ Sort Key: rangejoin_left.ir1
+ -> Seq Scan on rangejoin_left
+ (8 rows)
+
+ -- full join doesn't support range join
+ explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left full join rangejoin_right
+ on (ir1 && ir2);
+ ERROR: FULL JOIN is only supported with merge-joinable or hash-joinable join conditions
+ -- range input to range join must be ascending
+ explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left inner join rangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 desc, i1;
+ QUERY PLAN
+ ----------------------------------------------------------------------------------------------------------------
+ Sort
+ Sort Key: rangejoin_left.ir1 DESC, rangejoin_left.i1
+ -> Range Merge Join
+ Merge Cond: ((rangejoin_left.ir1 && rangejoin_right.ir2) AND (rangejoin_left.i1 = rangejoin_right.i2))
+ -> Sort
+ Sort Key: rangejoin_left.ir1, rangejoin_left.i1
+ -> Seq Scan on rangejoin_left
+ -> Sort
+ Sort Key: rangejoin_right.ir2, rangejoin_right.i2
+ -> Seq Scan on rangejoin_right
+ (10 rows)
+
+ -- but it's OK for non-range inputs to be descending
+ explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left inner join rangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 nulls first, i1 desc;
+ QUERY PLAN
+ ----------------------------------------------------------------------------------------------------------
+ Range Merge Join
+ Merge Cond: ((rangejoin_left.ir1 && rangejoin_right.ir2) AND (rangejoin_left.i1 = rangejoin_right.i2))
+ -> Sort
+ Sort Key: rangejoin_left.ir1 NULLS FIRST, rangejoin_left.i1 DESC
+ -> Seq Scan on rangejoin_left
+ -> Sort
+ Sort Key: rangejoin_right.ir2 NULLS FIRST, rangejoin_right.i2 DESC
+ -> Seq Scan on rangejoin_right
+ (8 rows)
+
+ select i1, ir1, i2, ir2
+ from rangejoin_left inner join rangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 nulls first, i1 desc;
+ i1 | ir1 | i2 | ir2
+ ------+---------+------+---------
+ 1004 | [22,35) | 1004 | [20,45)
+ (1 row)
+
+ drop table rangejoin_left;
+ drop table rangejoin_right;
+ create table multirangejoin_left (ir1 int4range, ir2 int4range);
+ create table multirangejoin_right (ir3 int4range, ir4 int4range);
+ insert into multirangejoin_left values
+ (int4range(30,99), int4range(20,30)),
+ (int4range(2,40), int4range(15,27)),
+ (int4range(61,99), int4range(20,45)),
+ (int4range(22,32), int4range(21,66)),
+ (int4range(36,71), int4range(45,49)),
+ (int4range(9,80), int4range(2,4));
+ insert into multirangejoin_right values
+ (int4range(9,70), int4range(10,78)),
+ (int4range(21,37), int4range(89,99)),
+ (int4range(5,98), int4range(35,97)),
+ (int4range(12,17), int4range(81,92)),
+ (int4range(15,19), int4range(5,55)),
+ (int4range(57,58), int4range(42,80));
+ explain (costs off) select *
+ from multirangejoin_left inner join multirangejoin_right
+ on (ir1 && ir3 and ir2 && ir4) order by ir1, ir2, ir3, ir4;
+ QUERY PLAN
+ ---------------------------------------------------------------------------------------------------------------------------------------
+ Sort
+ Sort Key: multirangejoin_left.ir1, multirangejoin_left.ir2, multirangejoin_right.ir3, multirangejoin_right.ir4
+ -> Range Merge Join
+ Merge Cond: ((multirangejoin_left.ir1 && multirangejoin_right.ir3) AND (multirangejoin_left.ir2 && multirangejoin_right.ir4))
+ -> Sort
+ Sort Key: multirangejoin_left.ir1, multirangejoin_left.ir2
+ -> Seq Scan on multirangejoin_left
+ -> Sort
+ Sort Key: multirangejoin_right.ir3, multirangejoin_right.ir4
+ -> Seq Scan on multirangejoin_right
+ (10 rows)
+
+ select *
+ from multirangejoin_left inner join multirangejoin_right
+ on (ir1 && ir3 and ir2 && ir4) order by ir1, ir2, ir3, ir4;
+ ir1 | ir2 | ir3 | ir4
+ ---------+---------+---------+---------
+ [2,40) | [15,27) | [9,70) | [10,78)
+ [2,40) | [15,27) | [15,19) | [5,55)
+ [22,32) | [21,66) | [5,98) | [35,97)
+ [22,32) | [21,66) | [9,70) | [10,78)
+ [30,99) | [20,30) | [9,70) | [10,78)
+ [36,71) | [45,49) | [5,98) | [35,97)
+ [36,71) | [45,49) | [9,70) | [10,78)
+ [36,71) | [45,49) | [57,58) | [42,80)
+ [61,99) | [20,45) | [5,98) | [35,97)
+ [61,99) | [20,45) | [9,70) | [10,78)
+ (10 rows)
+
+ set enable_mergejoin=false;
+ explain (costs off) select *
+ from multirangejoin_left inner join multirangejoin_right
+ on (ir1 && ir3 and ir2 && ir4) order by ir1, ir2, ir3, ir4;
+ QUERY PLAN
+ ----------------------------------------------------------------------------------------------------------------------------------------
+ Sort
+ Sort Key: multirangejoin_left.ir1, multirangejoin_left.ir2, multirangejoin_right.ir3, multirangejoin_right.ir4
+ -> Nested Loop
+ Join Filter: ((multirangejoin_left.ir1 && multirangejoin_right.ir3) AND (multirangejoin_left.ir2 && multirangejoin_right.ir4))
+ -> Seq Scan on multirangejoin_left
+ -> Materialize
+ -> Seq Scan on multirangejoin_right
+ (7 rows)
+
+ select *
+ from multirangejoin_left inner join multirangejoin_right
+ on (ir1 && ir3 and ir2 && ir4) order by ir1, ir2, ir3, ir4;
+ ir1 | ir2 | ir3 | ir4
+ ---------+---------+---------+---------
+ [2,40) | [15,27) | [9,70) | [10,78)
+ [2,40) | [15,27) | [15,19) | [5,55)
+ [22,32) | [21,66) | [5,98) | [35,97)
+ [22,32) | [21,66) | [9,70) | [10,78)
+ [30,99) | [20,30) | [9,70) | [10,78)
+ [36,71) | [45,49) | [5,98) | [35,97)
+ [36,71) | [45,49) | [9,70) | [10,78)
+ [36,71) | [45,49) | [57,58) | [42,80)
+ [61,99) | [20,45) | [5,98) | [35,97)
+ [61,99) | [20,45) | [9,70) | [10,78)
+ (10 rows)
+
+ set enable_mergejoin=true;
+ explain (costs off) select *
+ from multirangejoin_left inner join multirangejoin_right
+ on (ir1 @> ir3 and ir2 && ir4) order by ir1, ir2, ir3, ir4;
+ QUERY PLAN
+ ---------------------------------------------------------------------------------------------------------------------------------------
+ Sort
+ Sort Key: multirangejoin_left.ir1, multirangejoin_left.ir2, multirangejoin_right.ir3, multirangejoin_right.ir4
+ -> Range Merge Join
+ Merge Cond: ((multirangejoin_left.ir1 @> multirangejoin_right.ir3) AND (multirangejoin_left.ir2 && multirangejoin_right.ir4))
+ -> Sort
+ Sort Key: multirangejoin_left.ir1, multirangejoin_left.ir2
+ -> Seq Scan on multirangejoin_left
+ -> Sort
+ Sort Key: multirangejoin_right.ir3, multirangejoin_right.ir4
+ -> Seq Scan on multirangejoin_right
+ (10 rows)
+
+ select *
+ from multirangejoin_left inner join multirangejoin_right
+ on (ir1 @> ir3 and ir2 && ir4) order by ir1, ir2, ir3, ir4;
+ ir1 | ir2 | ir3 | ir4
+ ---------+---------+---------+---------
+ [2,40) | [15,27) | [15,19) | [5,55)
+ [36,71) | [45,49) | [57,58) | [42,80)
+ (2 rows)
+
+ set enable_mergejoin=false;
+ explain (costs off) select *
+ from multirangejoin_left inner join multirangejoin_right
+ on (ir1 @> ir3 and ir2 && ir4) order by ir1, ir2, ir3, ir4;
+ QUERY PLAN
+ ----------------------------------------------------------------------------------------------------------------------------------------
+ Sort
+ Sort Key: multirangejoin_left.ir1, multirangejoin_left.ir2, multirangejoin_right.ir3, multirangejoin_right.ir4
+ -> Nested Loop
+ Join Filter: ((multirangejoin_left.ir1 @> multirangejoin_right.ir3) AND (multirangejoin_left.ir2 && multirangejoin_right.ir4))
+ -> Seq Scan on multirangejoin_left
+ -> Materialize
+ -> Seq Scan on multirangejoin_right
+ (7 rows)
+
+ select *
+ from multirangejoin_left inner join multirangejoin_right
+ on (ir1 @> ir3 and ir2 && ir4) order by ir1, ir2, ir3, ir4;
+ ir1 | ir2 | ir3 | ir4
+ ---------+---------+---------+---------
+ [2,40) | [15,27) | [15,19) | [5,55)
+ [36,71) | [45,49) | [57,58) | [42,80)
+ (2 rows)
+
+ set enable_mergejoin=true;
+ explain (costs off) select *
+ from multirangejoin_left left join multirangejoin_right
+ on (ir1 && ir4 and ir2 && ir3) order by ir4, ir3, ir2, ir1;
+ QUERY PLAN
+ ---------------------------------------------------------------------------------------------------------------------------------------
+ Sort
+ Sort Key: multirangejoin_right.ir4, multirangejoin_right.ir3, multirangejoin_left.ir2, multirangejoin_left.ir1
+ -> Range Merge Left Join
+ Merge Cond: ((multirangejoin_left.ir1 && multirangejoin_right.ir4) AND (multirangejoin_left.ir2 && multirangejoin_right.ir3))
+ -> Sort
+ Sort Key: multirangejoin_left.ir1, multirangejoin_left.ir2
+ -> Seq Scan on multirangejoin_left
+ -> Sort
+ Sort Key: multirangejoin_right.ir4, multirangejoin_right.ir3
+ -> Seq Scan on multirangejoin_right
+ (10 rows)
+
+ select *
+ from multirangejoin_left left join multirangejoin_right
+ on (ir1 && ir4 and ir2 && ir3) order by ir4, ir3, ir2, ir1;
+ ir1 | ir2 | ir3 | ir4
+ ---------+---------+---------+---------
+ [2,40) | [15,27) | [15,19) | [5,55)
+ [2,40) | [15,27) | [9,70) | [10,78)
+ [30,99) | [20,30) | [9,70) | [10,78)
+ [61,99) | [20,45) | [9,70) | [10,78)
+ [22,32) | [21,66) | [9,70) | [10,78)
+ [36,71) | [45,49) | [9,70) | [10,78)
+ [2,40) | [15,27) | [5,98) | [35,97)
+ [30,99) | [20,30) | [5,98) | [35,97)
+ [61,99) | [20,45) | [5,98) | [35,97)
+ [36,71) | [45,49) | [5,98) | [35,97)
+ [30,99) | [20,30) | [21,37) | [89,99)
+ [61,99) | [20,45) | [21,37) | [89,99)
+ [9,80) | [2,4) | |
+ (13 rows)
+
+ set enable_mergejoin=false;
+ explain (costs off) select *
+ from multirangejoin_left left join multirangejoin_right
+ on (ir1 && ir4 and ir2 && ir3) order by ir4, ir3, ir2, ir1;
+ QUERY PLAN
+ ----------------------------------------------------------------------------------------------------------------------------------------
+ Sort
+ Sort Key: multirangejoin_right.ir4, multirangejoin_right.ir3, multirangejoin_left.ir2, multirangejoin_left.ir1
+ -> Nested Loop Left Join
+ Join Filter: ((multirangejoin_left.ir1 && multirangejoin_right.ir4) AND (multirangejoin_left.ir2 && multirangejoin_right.ir3))
+ -> Seq Scan on multirangejoin_left
+ -> Materialize
+ -> Seq Scan on multirangejoin_right
+ (7 rows)
+
+ select *
+ from multirangejoin_left left join multirangejoin_right
+ on (ir1 && ir4 and ir2 && ir3) order by ir4, ir3, ir2, ir1;
+ ir1 | ir2 | ir3 | ir4
+ ---------+---------+---------+---------
+ [2,40) | [15,27) | [15,19) | [5,55)
+ [2,40) | [15,27) | [9,70) | [10,78)
+ [30,99) | [20,30) | [9,70) | [10,78)
+ [61,99) | [20,45) | [9,70) | [10,78)
+ [22,32) | [21,66) | [9,70) | [10,78)
+ [36,71) | [45,49) | [9,70) | [10,78)
+ [2,40) | [15,27) | [5,98) | [35,97)
+ [30,99) | [20,30) | [5,98) | [35,97)
+ [61,99) | [20,45) | [5,98) | [35,97)
+ [36,71) | [45,49) | [5,98) | [35,97)
+ [30,99) | [20,30) | [21,37) | [89,99)
+ [61,99) | [20,45) | [21,37) | [89,99)
+ [9,80) | [2,4) | |
+ (13 rows)
+
+ set enable_mergejoin=true;
+ drop table multirangejoin_left;
+ drop table multirangejoin_right;
+ create table bigrangejoin_left (i1 int, ir1 int4range);
+ create table bigrangejoin_right (i2 int, ir2 int4range);
+ -- 100 small ranges
+ insert into bigrangejoin_left
+ select g/4,
+ int4range(g,
+ g + case when (g%2=0) then g%7 else 12-(g%11) end)
+ from generate_series(1,100) g;
+ insert into bigrangejoin_right
+ select g/4,
+ int4range(g-7+(g%19),
+ g-7+(g%19) + case when (g%3=0) then g%11 else 17-(g%15) end)
+ from generate_series(1,100) g;
+ -- 10 medium ranges
+ insert into bigrangejoin_left
+ select g/4*10,
+ int4range(g*10,
+ g*10 + case when (g%2=0) then g%7 else 12-(g%11) end)
+ from generate_series(1,10) g;
+ insert into bigrangejoin_right
+ select g/4*10,
+ int4range(g*10-57+(g%173),
+ g*10-57+(g%173) + case when (g%3=0) then g%123 else 97-(g%83) end)
+ from generate_series(1,10) g;
+ insert into bigrangejoin_left select g*11-21, 'empty'::int4range
+ from generate_series(1,9) g;
+ insert into bigrangejoin_right select g*13-29, 'empty'::int4range
+ from generate_series(1,8) g;
+ insert into bigrangejoin_left values
+ (4, int4range(NULL,5)),
+ (93, int4range(95, NULL));
+ insert into bigrangejoin_right values
+ (7, int4range(NULL,3)),
+ (92, int4range(99, NULL));
+ create temp table rangejoin_result1
+ (i1 int, ir1 int4range, i2 int, ir2 int4range);
+ create temp table rangejoin_result2
+ (i1 int, ir1 int4range, i2 int, ir2 int4range);
+ set enable_hashjoin=false;
+ explain (costs off) insert into rangejoin_result1
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left left join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 nulls first, i1 desc;
+ QUERY PLAN
+ ----------------------------------------------------------------------------------------------------------------------------
+ Insert on rangejoin_result1
+ -> Range Merge Left Join
+ Merge Cond: ((bigrangejoin_left.ir1 && bigrangejoin_right.ir2) AND (bigrangejoin_left.i1 = bigrangejoin_right.i2))
+ -> Sort
+ Sort Key: bigrangejoin_left.ir1 NULLS FIRST, bigrangejoin_left.i1 DESC
+ -> Seq Scan on bigrangejoin_left
+ -> Sort
+ Sort Key: bigrangejoin_right.ir2 NULLS FIRST, bigrangejoin_right.i2 DESC
+ -> Seq Scan on bigrangejoin_right
+ (9 rows)
+
+ insert into rangejoin_result1
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left left join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 nulls first, i1 desc;
+ set enable_hashjoin=true;
+ set enable_mergejoin=false;
+ explain (costs off) insert into rangejoin_result2
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left left join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 nulls first, i1 desc;
+ QUERY PLAN
+ --------------------------------------------------------------------------------
+ Insert on rangejoin_result2
+ -> Sort
+ Sort Key: bigrangejoin_left.ir1 NULLS FIRST, bigrangejoin_left.i1 DESC
+ -> Hash Left Join
+ Hash Cond: (bigrangejoin_left.i1 = bigrangejoin_right.i2)
+ Join Filter: (bigrangejoin_left.ir1 && bigrangejoin_right.ir2)
+ -> Seq Scan on bigrangejoin_left
+ -> Hash
+ -> Seq Scan on bigrangejoin_right
+ (9 rows)
+
+ insert into rangejoin_result2
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left left join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 nulls first, i1 desc;
+ set enable_mergejoin=true;
+ select count(*) from rangejoin_result1;
+ count
+ -------
+ 292
+ (1 row)
+
+ select count(*) from rangejoin_result2;
+ count
+ -------
+ 292
+ (1 row)
+
+ select * from rangejoin_result1 except select * from rangejoin_result2;
+ i1 | ir1 | i2 | ir2
+ ----+-----+----+-----
+ (0 rows)
+
+ select * from rangejoin_result2 except select * from rangejoin_result1;
+ i1 | ir1 | i2 | ir2
+ ----+-----+----+-----
+ (0 rows)
+
+ drop table rangejoin_result1;
+ drop table rangejoin_result2;
+ create temp table rangejoin_result3
+ (i1 int, ir1 int4range, i2 int, ir2 int4range);
+ create temp table rangejoin_result4
+ (i1 int, ir1 int4range, i2 int, ir2 int4range);
+ explain (costs off) insert into rangejoin_result3
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left inner join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by i1, ir1;
+ QUERY PLAN
+ ----------------------------------------------------------------------------------------------------------------------------
+ Insert on rangejoin_result3
+ -> Range Merge Join
+ Merge Cond: ((bigrangejoin_left.i1 = bigrangejoin_right.i2) AND (bigrangejoin_left.ir1 && bigrangejoin_right.ir2))
+ -> Sort
+ Sort Key: bigrangejoin_left.i1, bigrangejoin_left.ir1
+ -> Seq Scan on bigrangejoin_left
+ -> Sort
+ Sort Key: bigrangejoin_right.i2, bigrangejoin_right.ir2
+ -> Seq Scan on bigrangejoin_right
+ (9 rows)
+
+ insert into rangejoin_result3
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left inner join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by i1, ir1;
+ set enable_mergejoin=false;
+ explain (costs off) insert into rangejoin_result4
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left inner join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by i1, ir1;
+ QUERY PLAN
+ ------------------------------------------------------------------------------
+ Insert on rangejoin_result4
+ -> Sort
+ Sort Key: bigrangejoin_left.i1, bigrangejoin_left.ir1
+ -> Hash Join
+ Hash Cond: (bigrangejoin_left.i1 = bigrangejoin_right.i2)
+ Join Filter: (bigrangejoin_left.ir1 && bigrangejoin_right.ir2)
+ -> Seq Scan on bigrangejoin_left
+ -> Hash
+ -> Seq Scan on bigrangejoin_right
+ (9 rows)
+
+ insert into rangejoin_result4
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left inner join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by i1, ir1;
+ set enable_mergejoin=true;
+ select count(*) from rangejoin_result3;
+ count
+ -------
+ 259
+ (1 row)
+
+ select count(*) from rangejoin_result4;
+ count
+ -------
+ 259
+ (1 row)
+
+ select * from rangejoin_result3 except select * from rangejoin_result4;
+ i1 | ir1 | i2 | ir2
+ ----+-----+----+-----
+ (0 rows)
+
+ select * from rangejoin_result4 except select * from rangejoin_result3;
+ i1 | ir1 | i2 | ir2
+ ----+-----+----+-----
+ (0 rows)
+
+ drop table rangejoin_result3;
+ drop table rangejoin_result4;
+ drop table bigrangejoin_left;
+ drop table bigrangejoin_right;
diff --git a/src/test/regress/parallel_schedulindex eefdeea..05b6f25 100644
*** a/src/test/regress/parallel_schedule
--- b/src/test/regress/parallel_schedule
***************
*** 109,115 **** test: select_views portals_p2 foreign_key cluster dependency guc bitmapops combo
# NB: temp.sql does a reconnect which transiently uses 2 connections,
# so keep this parallel group to at most 19 tests
# ----------
! test: plancache limit plpgsql copy2 temp domain rangefuncs prepare without_oid conversion truncate alter_table sequence polymorphism rowtypes returning largeobject with xml
# ----------
# Another group of parallel tests
--- 109,115 ----
# NB: temp.sql does a reconnect which transiently uses 2 connections,
# so keep this parallel group to at most 19 tests
# ----------
! test: plancache limit plpgsql copy2 temp domain rangefuncs rangejoin prepare without_oid conversion truncate alter_table sequence polymorphism rowtypes returning largeobject with xml
# ----------
# Another group of parallel tests
diff --git a/src/test/regress/serial_scheindex 76b0de3..82d9e5d 100644
*** a/src/test/regress/serial_schedule
--- b/src/test/regress/serial_schedule
***************
*** 164,169 **** test: copy2
--- 164,170 ----
test: temp
test: domain
test: rangefuncs
+ test: rangejoin
test: prepare
test: without_oid
test: conversion
diff --git a/src/test/regress/sql/rangenew file mode 100644
index 0000000..72a7d53
*** /dev/null
--- b/src/test/regress/sql/rangejoin.sql
***************
*** 0 ****
--- 1,310 ----
+
+ create table rangejoin_left(i1 int, ir1 int4range);
+ create table rangejoin_right(i2 int, ir2 int4range);
+
+ insert into rangejoin_left values
+ (1001, int4range(10, 80)),
+ (1002, int4range(20, 30)),
+ (1003, int4range(21, 25)),
+ (1004, int4range(22, 35)),
+ (1005, int4range(40, 60)),
+ (1006, int4range(50, 60));
+
+ insert into rangejoin_right values
+ (1000, 'empty'::int4range),
+ (1001, int4range(NULL, 4)),
+ (1002, int4range(10, 12)),
+ (1003, int4range(11, 14)),
+ (1004, int4range(20, 45)),
+ (1005, int4range(24, 28)),
+ (1006, int4range(85, 90));
+
+ -- simple inner join with =
+ explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left, rangejoin_right
+ where ir1 = ir2;
+
+ select i1, ir1, i2, ir2
+ from rangejoin_left, rangejoin_right
+ where ir1 = ir2;
+
+ -- inner join with &&
+ explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left, rangejoin_right
+ where ir1 && ir2;
+
+ select i1, ir1, i2, ir2
+ from rangejoin_left, rangejoin_right
+ where ir1 && ir2;
+
+ -- inner join with @>
+ explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left, rangejoin_right
+ where ir1 @> ir2;
+
+ select i1, ir1, i2, ir2
+ from rangejoin_left, rangejoin_right
+ where ir1 @> ir2;
+
+ -- inner join with <@
+ explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left, rangejoin_right
+ where ir1 <@ ir2;
+
+ select i1, ir1, i2, ir2
+ from rangejoin_left, rangejoin_right
+ where ir1 <@ ir2;
+
+ -- two predicates
+ explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left inner join rangejoin_right
+ on (i1 = i2 and ir1 && ir2);
+
+ select i1, ir1, i2, ir2
+ from rangejoin_left inner join rangejoin_right
+ on (i1 = i2 and ir1 && ir2);
+
+ -- left join
+ explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left left join rangejoin_right
+ on (ir1 && ir2);
+
+ select i1, ir1, i2, ir2
+ from rangejoin_left left join rangejoin_right
+ on (ir1 && ir2);
+
+ -- right join should be implemented as left join
+ explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left right join rangejoin_right
+ on (ir1 && ir2);
+
+ -- full join doesn't support range join
+ explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left full join rangejoin_right
+ on (ir1 && ir2);
+
+ -- range input to range join must be ascending
+ explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left inner join rangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 desc, i1;
+
+ -- but it's OK for non-range inputs to be descending
+ explain (costs off) select i1, ir1, i2, ir2
+ from rangejoin_left inner join rangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 nulls first, i1 desc;
+
+ select i1, ir1, i2, ir2
+ from rangejoin_left inner join rangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 nulls first, i1 desc;
+
+ drop table rangejoin_left;
+ drop table rangejoin_right;
+
+ create table multirangejoin_left (ir1 int4range, ir2 int4range);
+ create table multirangejoin_right (ir3 int4range, ir4 int4range);
+
+ insert into multirangejoin_left values
+ (int4range(30,99), int4range(20,30)),
+ (int4range(2,40), int4range(15,27)),
+ (int4range(61,99), int4range(20,45)),
+ (int4range(22,32), int4range(21,66)),
+ (int4range(36,71), int4range(45,49)),
+ (int4range(9,80), int4range(2,4));
+
+
+ insert into multirangejoin_right values
+ (int4range(9,70), int4range(10,78)),
+ (int4range(21,37), int4range(89,99)),
+ (int4range(5,98), int4range(35,97)),
+ (int4range(12,17), int4range(81,92)),
+ (int4range(15,19), int4range(5,55)),
+ (int4range(57,58), int4range(42,80));
+
+ explain (costs off) select *
+ from multirangejoin_left inner join multirangejoin_right
+ on (ir1 && ir3 and ir2 && ir4) order by ir1, ir2, ir3, ir4;
+
+ select *
+ from multirangejoin_left inner join multirangejoin_right
+ on (ir1 && ir3 and ir2 && ir4) order by ir1, ir2, ir3, ir4;
+
+ set enable_mergejoin=false;
+ explain (costs off) select *
+ from multirangejoin_left inner join multirangejoin_right
+ on (ir1 && ir3 and ir2 && ir4) order by ir1, ir2, ir3, ir4;
+
+ select *
+ from multirangejoin_left inner join multirangejoin_right
+ on (ir1 && ir3 and ir2 && ir4) order by ir1, ir2, ir3, ir4;
+ set enable_mergejoin=true;
+
+ explain (costs off) select *
+ from multirangejoin_left inner join multirangejoin_right
+ on (ir1 @> ir3 and ir2 && ir4) order by ir1, ir2, ir3, ir4;
+
+ select *
+ from multirangejoin_left inner join multirangejoin_right
+ on (ir1 @> ir3 and ir2 && ir4) order by ir1, ir2, ir3, ir4;
+
+ set enable_mergejoin=false;
+ explain (costs off) select *
+ from multirangejoin_left inner join multirangejoin_right
+ on (ir1 @> ir3 and ir2 && ir4) order by ir1, ir2, ir3, ir4;
+
+ select *
+ from multirangejoin_left inner join multirangejoin_right
+ on (ir1 @> ir3 and ir2 && ir4) order by ir1, ir2, ir3, ir4;
+ set enable_mergejoin=true;
+
+ explain (costs off) select *
+ from multirangejoin_left left join multirangejoin_right
+ on (ir1 && ir4 and ir2 && ir3) order by ir4, ir3, ir2, ir1;
+
+ select *
+ from multirangejoin_left left join multirangejoin_right
+ on (ir1 && ir4 and ir2 && ir3) order by ir4, ir3, ir2, ir1;
+
+ set enable_mergejoin=false;
+ explain (costs off) select *
+ from multirangejoin_left left join multirangejoin_right
+ on (ir1 && ir4 and ir2 && ir3) order by ir4, ir3, ir2, ir1;
+
+ select *
+ from multirangejoin_left left join multirangejoin_right
+ on (ir1 && ir4 and ir2 && ir3) order by ir4, ir3, ir2, ir1;
+ set enable_mergejoin=true;
+
+ drop table multirangejoin_left;
+ drop table multirangejoin_right;
+
+ create table bigrangejoin_left (i1 int, ir1 int4range);
+ create table bigrangejoin_right (i2 int, ir2 int4range);
+
+ -- 100 small ranges
+ insert into bigrangejoin_left
+ select g/4,
+ int4range(g,
+ g + case when (g%2=0) then g%7 else 12-(g%11) end)
+ from generate_series(1,100) g;
+ insert into bigrangejoin_right
+ select g/4,
+ int4range(g-7+(g%19),
+ g-7+(g%19) + case when (g%3=0) then g%11 else 17-(g%15) end)
+ from generate_series(1,100) g;
+
+ -- 10 medium ranges
+ insert into bigrangejoin_left
+ select g/4*10,
+ int4range(g*10,
+ g*10 + case when (g%2=0) then g%7 else 12-(g%11) end)
+ from generate_series(1,10) g;
+ insert into bigrangejoin_right
+ select g/4*10,
+ int4range(g*10-57+(g%173),
+ g*10-57+(g%173) + case when (g%3=0) then g%123 else 97-(g%83) end)
+ from generate_series(1,10) g;
+
+ insert into bigrangejoin_left select g*11-21, 'empty'::int4range
+ from generate_series(1,9) g;
+
+ insert into bigrangejoin_right select g*13-29, 'empty'::int4range
+ from generate_series(1,8) g;
+
+ insert into bigrangejoin_left values
+ (4, int4range(NULL,5)),
+ (93, int4range(95, NULL));
+
+ insert into bigrangejoin_right values
+ (7, int4range(NULL,3)),
+ (92, int4range(99, NULL));
+
+ create temp table rangejoin_result1
+ (i1 int, ir1 int4range, i2 int, ir2 int4range);
+ create temp table rangejoin_result2
+ (i1 int, ir1 int4range, i2 int, ir2 int4range);
+
+ set enable_hashjoin=false;
+ explain (costs off) insert into rangejoin_result1
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left left join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 nulls first, i1 desc;
+
+ insert into rangejoin_result1
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left left join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 nulls first, i1 desc;
+ set enable_hashjoin=true;
+
+ set enable_mergejoin=false;
+ explain (costs off) insert into rangejoin_result2
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left left join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 nulls first, i1 desc;
+
+ insert into rangejoin_result2
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left left join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by ir1 nulls first, i1 desc;
+ set enable_mergejoin=true;
+
+ select count(*) from rangejoin_result1;
+ select count(*) from rangejoin_result2;
+
+ select * from rangejoin_result1 except select * from rangejoin_result2;
+
+ select * from rangejoin_result2 except select * from rangejoin_result1;
+
+ drop table rangejoin_result1;
+ drop table rangejoin_result2;
+
+ create temp table rangejoin_result3
+ (i1 int, ir1 int4range, i2 int, ir2 int4range);
+ create temp table rangejoin_result4
+ (i1 int, ir1 int4range, i2 int, ir2 int4range);
+
+
+ explain (costs off) insert into rangejoin_result3
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left inner join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by i1, ir1;
+
+ insert into rangejoin_result3
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left inner join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by i1, ir1;
+
+ set enable_mergejoin=false;
+ explain (costs off) insert into rangejoin_result4
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left inner join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by i1, ir1;
+
+ insert into rangejoin_result4
+ select i1, ir1, i2, ir2
+ from bigrangejoin_left inner join bigrangejoin_right
+ on (i1 = i2 and ir1 && ir2)
+ order by i1, ir1;
+ set enable_mergejoin=true;
+
+ select count(*) from rangejoin_result3;
+ select count(*) from rangejoin_result4;
+
+ select * from rangejoin_result3 except select * from rangejoin_result4;
+
+ select * from rangejoin_result4 except select * from rangejoin_result3;
+
+ drop table rangejoin_result3;
+ drop table rangejoin_result4;
+
+ drop table bigrangejoin_left;
+ drop table bigrangejoin_right;
Re: Range Merge Join v1
On Thu, Aug 31, 2017 at 1:52 AM, Jeff Davis <pgsql@j-davis.com> wrote:
Updated patch attached. Changelog:
* Rebased
* Changed MJCompare to return an enum as suggested, but it has 4
possible values rather than 3.
* Added support for joining on contains or contained by (@> or <@) and
updated tests.
The current patch does not work well with multiple keys, and I believe
it's important to solve because it will make it usable for
multi-dimension spatial joins.
The problem is this: the algorithm for a single key demands that the
input is sorted by (lower(r) NULLS FIRST, upper(r) NULLS LAST). That's
easy, because that's also the sort order for the range operator class,
so everything just works.
For multiple keys, the order of the input is:
lower(r1) NULLS FIRST, lower(r2) NULLS FIRST,
upper(r1) NULLS LAST, upper(r2) NULLS LAST
But that can't match up with any opclass, because an opclass can only
order one attribute at a time. In this case, the lower bound of r2 is
more significant than the upper bound of r1.
It's easy enough to adapt the execution to make this work as long as
the input is properly sorted. The challenge is making the optimizer
choose the sort keys properly.
I have tried a few approaches. The current approach that I'm using is:
* have a new, special range operator family with no operator classes
* in check_mergejoinable(), detect the && operator and set the
mergeopfamilies to contain only the special operator family
* in try_mergejoin_path(), it will convert the pathkeys using that
operator class into pathkeys over a "lower" expression over the same
EC; and then add on additional pathkeys for the "upper" expressions
onto the end of the pathkey list
Any comments or alternative suggestions welcome. This will probably
take a few days at least, so I put the patch in "waiting on author"
state.
Regards,
Jeff Davis
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Range Merge Join v1
On Mon, Sep 18, 2017 at 2:24 AM, Jeff Davis <pgsql@j-davis.com> wrote:
Any comments or alternative suggestions welcome. This will probably
take a few days at least, so I put the patch in "waiting on author"
state.
This did not receive an update for two months. I am marking it as
returned with feedback.
--
Michael