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
On Thu, Apr 6, 2017 at 1:43 AM, Jeff Davis <pg...@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:
> =====================================
>
> http://www.postgresql.org/message-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
perf.sql
Description: application/sql
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;
-- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
