Subject: Patch: Range Merge Join

From: Thomas <[email-masked]>
Date: Wed, 9 Jun 2021 17:05:35 +0200

Hi Hackers,

More than a year ago we submitted a patch that offered two primitives
(ALIGN and NORMALIZE) to support the processing of temporal data with range
types. During the ensuing discussion we decided to withdraw the original
patch
and to split it into smaller parts.

In the context of my BSc thesis, we started working and implementing a
Range Merge Join (RMJ), which is key for most temporal operations. The RMJ
is a useful operator in its own right and it greatly benefits any possible
temporal extension.

We have implemented the Range Merge Join algorithm by extending the
existing Merge Join to also support range conditions, i.e., BETWEEN-AND
or @> (containment for range types). Range joins contain a containment
condition and may have (optional) equality conditions. For example the
following query joins employees with a department and work period with
events on a specific day for that department:

SELECT emps.name, emps.dept, events.event, events.day
FROM emps JOIN events ON emps.dept = events.dept
AND events.day <@ emps.eperiod;

The resulting query plan is as follows:

                                          QUERY PLAN

----------------------------------------------------------------------------------------------
 Range Merge Join  (cost=106.73..118.01 rows=3 width=100) (actual rows=6
loops=1)
   Merge Cond: (emps.dept = events.dept)
   Range Cond: (events.day <@ emps.eperiod)
   ->  Sort  (cost=46.87..48.49 rows=650 width=96) (actual rows=5 loops=1)
         Sort Key: emps.dept, emps.eperiod
         Sort Method: quicksort  Memory: 25kB
         ->  Seq Scan on emps  (cost=0.00..16.50 rows=650 width=96) (actual
rows=5 loops=1)
   ->  Sort  (cost=59.86..61.98 rows=850 width=68) (actual rows=6 loops=1)
         Sort Key: events.dept, events.day
         Sort Method: quicksort  Memory: 25kB
         ->  Seq Scan on events  (cost=0.00..18.50 rows=850 width=68)
(actual rows=5 loops=1)
 Planning Time: 0.077 ms
 Execution Time: 0.092 ms
(13 rows)

Example queries and instances of tables can be found at the end of the mail.

The range merge join works with range types using <@ and also scalar data
types
using "a.ts BETWEEN b.ts AND b.te" or "b.ts <= a.ts AND a.ts <= b.te".
Currently, PostgreSQL does not provide specialized join algorithms for range
conditions (besides index nested loops), or Hash Join and Merge Joins that
evaluate an equality condition only.

Our idea is to have a separate range_cond besides the merge_cond for the
Merge Join that stores the potential range conditions of a query. The state
diagram of the Merge Join is then extended to also take into consideration
the range_cond. See the simplified state diagram of the Range Merge Join as
an extension of the Merge Join in the attachment. These additions besides a
boolean check have no effect on the Marge Join when no range condition is
present.

We provide extensive testing results and further information, including the
full BSc Thesis (technical report), describing the implementation and tests
in detail on http://tpg.inf.unibz.it/project-rmj and
http://tpg.inf.unibz.it/downloads/rmj-report.pdf.

We performed several experiments and show that depending on the selectivity
of
the range condition the range merge join outperforms existing execution
algorithms up to an order of magnitude. We found that the range merge join
that
needs to find range_cond from inequalities, incurs only a very small
overhead
in planning time in some TPCH queries (see Table 5.3 in the technical
report)
and in general only a very small overhead for a large number of joins or
many
inequality conditions (see Figure 5.1). To check the overhead of our
extension
for the traditional merge join execution time, we executed the TPCH queries
using the merge join (hash join disabled) and found no statistically
significant difference (see Table 5.4).

We are looking forward to your feedback and any suggestions to improve the
patch.

Best Regards,

Thomas Mannhart

Attachments: State Diagram and Patch

OPEN POINTS AND TODOs:

- Currently we do not consider parallelization
- Not all cases for input sort orders are considered yet

EXAMPLE QUERIES:

The first query uses a range condition using BETWEEN AND only and no
equality condition.

----------------------------------------------------------------------------------------------

DROP TABLE IF EXISTS marks;
DROP TABLE IF EXISTS grades;

CREATE TABLE marks (name text, snumber numeric, mark numeric);
CREATE TABLE grades (mmin numeric, mmax numeric, grade numeric);

INSERT INTO marks (name, snumber, mark) VALUES
('Anton', 1232, 23.5),
('Thomas', 4356, 95),
('Michael', 1125, 72),
('Hans', 3425, 90);

INSERT INTO grades (mmin, mmax, grade) VALUES
(0.0, 18, 1),
(18.5, 36, 2),
(36.5, 54, 3),
(54.5, 72, 4),
(72.5, 90, 5),
(90.5, 100, 6);

EXPLAIN(ANALYZE, TIMING FALSE)
SELECT marks.name, marks.snumber, grades.grade
FROM marks JOIN grades ON marks.mark BETWEEN grades.mmin AND grades.mmax;

                                          QUERY PLAN

-----------------------------------------------------------------------------------------------
 Range Merge Join  (cost=93.74..920.13 rows=46944 width=96) (actual rows=16
loops=1)
   Range Cond: ((marks.mark >= grades.mmin) AND (marks.mark <= grades.mmax))
   ->  Sort  (cost=46.87..48.49 rows=650 width=96) (actual rows=12 loops=1)
         Sort Key: grades.mmin
         Sort Method: quicksort  Memory: 25kB
         ->  Seq Scan on grades  (cost=0.00..16.50 rows=650 width=96)
(actual rows=12 loops=1)
   ->  Sort  (cost=46.87..48.49 rows=650 width=96) (actual rows=21 loops=1)
         Sort Key: marks.mark
         Sort Method: quicksort  Memory: 25kB
         ->  Seq Scan on marks  (cost=0.00..16.50 rows=650 width=96)
(actual rows=8 loops=1)
 Planning Time: 0.078 ms
 Execution Time: 0.068 ms
(12 rows)

----------------------------------------------------------------------------------------------

The second query uses a range and an equality condition and joins the
relations using contained in (<@).

----------------------------------------------------------------------------------------------

DROP TABLE IF EXISTS emps;
DROP TABLE IF EXISTS events;

CREATE TABLE emps (name text, dept text, eperiod daterange);
CREATE TABLE events (event text, dept text, day date);

INSERT INTO emps (name, dept, eperiod) VALUES
('Anton', 'Sales', '(2020-01-01, 2020-03-31)'),
('Thomas', 'Marketing', '(2020-01-01, 2020-06-30)'),
('Michael', 'Marketing', '(2020-03-01, 2020-12-31)'),
('Hans', 'Sales', '(2020-01-01, 2020-12-31)'),
('Thomas', 'Accounting', '(2020-07-01, 2020-12-31)');

INSERT INTO events (event, dept, day) VALUES
('Fair CH', 'Marketing', '2020-03-05'),
('Presentation', 'Sales', '2020-06-15'),
('Fair IT', 'Marketing', '2020-08-03'),
('Balance Report', 'Accounting', '2020-08-03'),
('Product launch', 'Marketing', '2020-10-15');

EXPLAIN(ANALYZE, TIMING FALSE)
SELECT emps.name, emps.dept, events.event, events.day
FROM emps JOIN events ON emps.dept = events.dept
AND events.day <@ emps.eperiod;

                                          QUERY PLAN

----------------------------------------------------------------------------------------------
 Range Merge Join  (cost=106.73..118.01 rows=3 width=100) (actual rows=6
loops=1)
   Merge Cond: (emps.dept = events.dept)
   Range Cond: (events.day <@ emps.eperiod)
   ->  Sort  (cost=46.87..48.49 rows=650 width=96) (actual rows=5 loops=1)
         Sort Key: emps.dept, emps.eperiod
         Sort Method: quicksort  Memory: 25kB
         ->  Seq Scan on emps  (cost=0.00..16.50 rows=650 width=96) (actual
rows=5 loops=1)
   ->  Sort  (cost=59.86..61.98 rows=850 width=68) (actual rows=6 loops=1)
         Sort Key: events.dept, events.day
         Sort Method: quicksort  Memory: 25kB
         ->  Seq Scan on events  (cost=0.00..18.50 rows=850 width=68)
(actual rows=5 loops=1)
 Planning Time: 0.077 ms
 Execution Time: 0.092 ms
(13 rows)

----------------------------------------------------------------------------------------------

---

From: David Rowley <[email-masked]>
Date: Thu, 10 Jun 2021 15:09:54 +1200

On Thu, 10 Jun 2021 at 03:05, Thomas <[email-masked]> wrote:
> or @> (containment for range types).

It shouldn't be a blocker for you, but just so you're aware, there was
a previous proposal for this in [1] and a patch in [2].  I've include
Jeff here just so he's aware of this. Jeff may wish to state his
intentions with his own patch. It's been a few years now.

I only just glanced over the patch. I'd suggest getting rid of the /*
Thomas */ comments.  We use git, so if you need an audit trail about
changes then you'll find it in git blame.  If you have those for an
internal audit trail then you should consider using git. No committer
would commit those to PostgreSQL, so they might as well disappear.

For further review, please add the patch to the July commitfest [3].
We should be branching for pg15 sometime before the start of July.
There will be more focus on new patches around that time. Further
details in [4].

Also, I see this if your first post to this list, so welcome, and
thank you for the contribution.  Also, just to set expectations;
patches like this almost always take a while to get into shape for
PostgreSQL. Please expect a lot of requests to change things. That's
fairly standard procedure.  The process often drags on for months and
in some less common cases, years.

David

[1] https://www.postgresql.org/message-id/flat/6227.1334559170%40sss.pgh.pa.us#82c771950ba486dec911923a5e910000
[2] https://www.postgresql.org/message-id/flat/CAMp0ubfwAFFW3O_NgKqpRPmm56M4weTEXjprb2gP_NrDaEC4Eg%40mail.gmail.com
[3] https://commitfest.postgresql.org/33/
[4] https://wiki.postgresql.org/wiki/CommitFest

---

From: Thomas <[email-masked]>
Date: Thu, 10 Jun 2021 11:04:08 +0200

Thank you for the feedback.
I removed the redundant comments from the patch and added this thread to
the July CF [1].

Best Regards,
Thomas Mannhart

[1] https://commitfest.postgresql.org/33/3160/

Am Do., 10. Juni 2021 um 05:10 Uhr schrieb David Rowley <
[email-masked]>:

> [1]
> https://www.postgresql.org/message-id/flat/6227.1334559170%40sss.pgh.pa.us#82c771950ba486dec911923a5e910000
> [2]
> https://www.postgresql.org/message-id/flat/CAMp0ubfwAFFW3O_NgKqpRPmm56M4weTEXjprb2gP_NrDaEC4Eg%40mail.gmail.com

---

From: Jeff Davis <[email-masked]>
Date: Thu, 10 Jun 2021 19:14:32 -0700

> intentions with his own patch. It's been a few years now.

Great, thank you for working on this!

I'll start with the reason I set the work down before: it did not work
well with multiple join keys. That might be fine, but I also started
thinking it was specialized enough that I wanted to look into doing it
as an extension using the CustomScan mechanism.

Do you have any solution to working better with multiple join keys? And
do you have thoughts on whether it would be a good candidate for the
CustomScan extension mechanism, which would make it easier to
experiment with?

Regards,
	Jeff Davis

---

From: Jaime Casanova <[email-masked]>
Date: Mon, 4 Oct 2021 16:27:54 -0500

> CustomScan extension mechanism, which would make it easier to

Hi,

It seems this has been stalled since jun-2021. I intend mark this as
RwF unless someone speaks in the next hour or so.

-- 
Jaime Casanova
Director de Servicios Profesionales
SystemGuards - Consultores de PostgreSQL

---

From: Jaime Casanova <[email-masked]>
Date: Mon, 4 Oct 2021 19:30:34 -0500

> On Mon, Oct 04, 2021 at 04:27:54PM -0500, Jaime Casanova wrote:

Thomas <[email-masked]> wrote me:

> Hi,
> 
> I registered this patch for the commitfest in july. It had not been reviewed and moved to the next CF. I still like to submit it.
> 
> Regards,
> Thomas
>

Just for clarification RwF doesn't imply reject of the patch.
Nevertheless, given that there has been no real review I will mark this
patch as "Waiting on Author" and move it to the next CF.

Meanwhile, cfbot (aka http://commitfest.cputube.org) says this doesn't
compile. Here is a little patch to fix the compilation errors, after
that it passes all tests in make check-world.

Also attached a rebased version of your patch with the fixes so we turn
cfbot entry green again

-- 
Jaime Casanova
Director de Servicios Profesionales
SystemGuards - Consultores de PostgreSQL
diff --git a/src/backend/executor/nodeMergejoin.c b/src/backend/executor/nodeMergejoin.c
index 2dccba24b3..d18b4a4605 100644
--- a/src/backend/executor/nodeMergejoin.c
+++ b/src/backend/executor/nodeMergejoin.c
@@ -294,7 +294,7 @@ MJCreateRangeData(List *rangeclause,
 {
 	RangeData data;
 
-	Assert(list_legth(node->rangeclause) < 3);
+	Assert(list_length(rangeclause) < 3);
 
 	data = (RangeData) palloc0(sizeof(RangeJoinData));
 
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index 8a2778485c..24ee41b9ed 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -3440,8 +3440,8 @@ final_cost_mergejoin(PlannerInfo *root, MergePath *path,

     /* Protect some assumptions below that rowcounts aren't zero */
-    if (inner_path_rows <= 0)
-        inner_path_rows = 1;
+	if (inner_path_rows <= 0)
+		inner_path_rows = 1;
 
 	/* Mark the path with the correct row estimate */
 	if (path->jpath.path.param_info)
diff --git a/src/backend/commands/explain.c b/src/backend/commands/explain.c
index 10644dfac4..9b7503630c 100644
--- a/src/backend/commands/explain.c
+++ b/src/backend/commands/explain.c
@@ -1206,8 +1206,16 @@ ExplainNode(PlanState *planstate, List *ancestors,
 			pname = sname = "Nested Loop";
 			break;
 		case T_MergeJoin:
-			pname = "Merge";	/* "Join" gets added by jointype switch */
-			sname = "Merge Join";
+			if(((MergeJoin *) plan)->rangeclause)
+			{
+				pname = "Range Merge";	/* "Join" gets added by jointype switch */
+				sname = "Range Merge Join";
+			}
+			else
+			{
+				pname = "Merge";	/* "Join" gets added by jointype switch */
+				sname = "Merge Join";
+			}
 			break;
 		case T_HashJoin:
 			pname = "Hash";		/* "Join" gets added by jointype switch */
@@ -1948,6 +1956,8 @@ ExplainNode(PlanState *planstate, List *ancestors,
 		case T_MergeJoin:
 			show_upper_qual(((MergeJoin *) plan)->mergeclauses,
 							"Merge Cond", planstate, ancestors, es);
+			show_upper_qual(((MergeJoin *) plan)->rangeclause,
+							"Range Cond", planstate, ancestors, es);
 			show_upper_qual(((MergeJoin *) plan)->join.joinqual,
 							"Join Filter", planstate, ancestors, es);
 			if (((MergeJoin *) plan)->join.joinqual)
diff --git a/src/backend/executor/nodeMergejoin.c b/src/backend/executor/nodeMergejoin.c
index b41454ab6d..d18b4a4605 100644
--- a/src/backend/executor/nodeMergejoin.c
+++ b/src/backend/executor/nodeMergejoin.c
@@ -93,11 +93,15 @@
 #include "postgres.h"
 
 #include "access/nbtree.h"
+#include "catalog/pg_operator.h"
 #include "executor/execdebug.h"
 #include "executor/nodeMergejoin.h"
 #include "miscadmin.h"
+#include "nodes/nodeFuncs.h"
+#include "utils/rangetypes.h"
 #include "utils/lsyscache.h"
 #include "utils/memutils.h"
+#include "utils/typcache.h"

 /*
@@ -140,6 +144,18 @@ typedef struct MergeJoinClauseData
 	SortSupportData ssup;
 }			MergeJoinClauseData;
 
+/*
+ * Runtime data for the range clause
+ */
+typedef struct RangeJoinData
+{
+	ExprState *startClause;
+	ExprState *endClause;
+	ExprState *rangeExpr;
+	ExprState *elemExpr;
+
+}			RangeJoinData;
+
 /* Result type for MJEvalOuterValues and MJEvalInnerValues */
 typedef enum
 {
@@ -269,6 +285,57 @@ MJExamineQuals(List *mergeclauses,
 	return clauses;
 }
 
+/*
+ * MJCreateRangeData
+ */
+static RangeData
+MJCreateRangeData(List *rangeclause,
+				   PlanState *parent)
+{
+	RangeData data;
+
+	Assert(list_length(rangeclause) < 3);
+
+	data = (RangeData) palloc0(sizeof(RangeJoinData));
+
+	data->startClause = NULL;
+	data->endClause = NULL;
+	data->rangeExpr = NULL;
+	data->elemExpr = NULL;
+
+	if(list_length(rangeclause) == 2)
+	{
+		data->startClause = ExecInitExpr(linitial(rangeclause), parent);
+		data->endClause = ExecInitExpr(lsecond(rangeclause), parent);
+	}
+	else
+	{
+		OpExpr		*qual = (OpExpr *) linitial(rangeclause);
+		ExprState	*lexpr;
+		ExprState	*rexpr;
+
+		/*
+		 * Prepare the input expressions for execution.
+		 */
+		lexpr = ExecInitExpr((Expr *) get_leftop(qual), parent);
+		rexpr = ExecInitExpr((Expr *) get_rightop(qual), parent);
+
+		if(qual->opno == OID_RANGE_CONTAINS_ELEM_OP)
+		{
+			data->rangeExpr = lexpr;
+			data->elemExpr = rexpr;
+		}
+		else
+		{
+			Assert(qual->opno == OID_RANGE_ELEM_CONTAINED_OP);
+			data->rangeExpr = rexpr;
+			data->elemExpr = lexpr;
+		}
+	}
+
+	return data;
+}
+
 /*
  * MJEvalOuterValues
  *
@@ -445,6 +512,73 @@ MJCompare(MergeJoinState *mergestate)
 }

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

---

From: Thomas <[email-masked]>
Date: Wed, 10 Nov 2021 15:03:55 +0100

Dear all,
thanks for the feedback!

We had a closer look at the previous patches and the CustomScan
infrastructure.

Compared to the previous patch, we do not (directly) focus on joins
with the overlap (&&) condition in this patch.  Instead we consider
joins with containment (@>) between a range and an element, and joins
with conditions over scalars of the form "right.element BETWEEN
left.start AND left.end", and more generally left.start >(=)
right.element AND right.element <(=) left.end. We call such conditions
range conditions and these conditions can be combined with equality
conditions in the Range Merge Join.

The Range Merge Join can use (optional) equality conditions and one
range condition of the form shown above. In this case the inputs are
sorted first by the attributes used for equality and then one input by
the range (or start in the case of scalars) and the other input by the
element. The Range Merge Join is then a simple extension of the Merge
Join that in addition to the (optional) equality attributes also uses
the range condition in the merge join states. This is similar to an
index-nested loop with scalars for cases when the relation containing
the element has an index on the equality attributes followed by the
element. The Range Merge Join uses sorting and thus does not require
the index for this purpose and performs better.

The patch uses the optimizer estimates to evaluate if the Range Merge
Join is beneficial as compared to other execution strategies, but when
no equality attributes are present, it becomes the only efficient
option for the above range conditions. If a join contains multiple
range conditions, then based on the estimates the most effective
strategy is chosen for the Range Merge Join.

Although we do not directly focus on joins with the overlap (&&)
condition between two ranges, we show in [1] that these joins can be
evaluated using the union (UNION ALL) of two joins with a range
condition, where intuitively, one tests that the start of one input
falls within the range of the other and vice versa. We evaluated this
using regular (B-tree) indices and compare it to joins with the
overlap (&&) condition using GiST, SP-GiST and others, and found that
it performs better. The Range Merge Join would improve this further
and would not require the creation of an index.

We did not consider an implementation as a CustomScan, as we feel the
join is rather general, can be implemented using a small extension of
the existing Merge Join, and would require a substantial duplication
of the Merge Join code.

Kind regards,
Thomas, Anton, Johann, Michael, Peter

[1] https://doi.org/10.1007/s00778-021-00692-3 (open access)

Am Di., 5. Okt. 2021 um 02:30 Uhr schrieb Jaime Casanova <
[email-masked]>:

> > I registered this patch for the commitfest in july. It had not been
> reviewed and moved to the next CF. I still like to submit it.
> >
> > Regards,
> > Thomas
> >
>

---

From: Daniel Gustafsson <[email-masked]>
Date: Wed, 17 Nov 2021 15:03:32 +0100

This patch fails to compile due to an incorrect function name in an assertion:

  nodeMergejoin.c:297:9: warning: implicit declaration of function 'list_legth' is invalid in C99 [-Wimplicit-function-declaration]
  Assert(list_legth(node->rangeclause) < 3);
         ^

--
Daniel Gustafsson		https://vmware.com/

---

From: Thomas <[email-masked]>
Date: Wed, 17 Nov 2021 15:45:26 +0100

Thank you for the feedback and sorry for the oversight. I fixed the bug and
attached a new version of the patch.

Kind Regards, Thomas

Am Mi., 17. Nov. 2021 um 15:03 Uhr schrieb Daniel Gustafsson <
[email-masked]>:

>   nodeMergejoin.c:297:9: warning: implicit declaration of function
> 'list_legth' is invalid in C99 [-Wimplicit-function-declaration]

---

From: Tomas Vondra <[email-masked]>
Date: Wed, 17 Nov 2021 23:28:43 +0100

On 11/17/21 15:45, Thomas wrote:
> Thank you for the feedback and sorry for the oversight. I fixed the bug 
> and attached a new version of the patch.
> 
> Kind Regards, Thomas
> 
> Am Mi., 17. Nov. 2021 um 15:03 Uhr schrieb Daniel Gustafsson 
> <[email-masked] <mailto:[email-masked]>>:
> 

That still doesn't compile with asserts, because MJCreateRangeData has

     Assert(list_length(node->rangeclause) < 3);

but there's no 'node' variable :-/

I took a brief look at the patch, and I think there are two main issues 
preventing it from moving forward.

1) no tests

There's not a *single* regression test exercising the new code, so even 
after adding Assert(false) to MJCreateRangeData() tests pass just fine. 
Clearly, that needs to change.

2) lack of comments

The patch adds a bunch of functions, but it does not really explain what 
the functions do (unlike the various surrounding functions). Even if I 
can work out what the functions do, it's much harder to determine what 
the "contract" is (i.e. what assumptions the function do and what is 
guaranteed).

Similarly, the patch modifies/reworks large blocks of executor code, 
without updating the comments describing what the block does.

See 0002 for various places that I think are missing comments.

Aside from that, I have a couple minor comments:

3) I'm not quite sure I like "Range Merge Join" to be honest. It's still 
a "Merge Join" pretty much. What about ditching the "Range"? There'll 
still be "Range Cond" key, which should be good enough I think.

4) Some minor whitespace issues (tabs vs. spaces). See 0002.

regards

-- 
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

From 1bc7921b4ad51cf23723c2ad7c7f618cde6fcba3 Mon Sep 17 00:00:00 2001
From: Tomas Vondra <[email-masked]>
Date: Wed, 17 Nov 2021 22:52:31 +0100
Subject: [PATCH 2/2] review

---
 .gitignore                            |  1 +
 src/backend/commands/explain.c        |  5 +++++
 src/backend/executor/nodeMergejoin.c  | 24 +++++++++++++++++++++---
 src/backend/optimizer/path/costsize.c |  8 ++++----
 src/backend/optimizer/path/joinpath.c |  9 +++++++++
 src/backend/optimizer/path/pathkeys.c |  8 ++++++++
 src/backend/utils/adt/rangetypes.c    |  4 ++++
 src/backend/utils/cache/lsyscache.c   |  2 ++
 src/include/nodes/pathnodes.h         |  4 ++--
 9 files changed, 56 insertions(+), 9 deletions(-)

diff --git a/.gitignore b/.gitignore
index 5dca1a39ec..23a555185c 100644
--- a/.gitignore
+++ b/.gitignore
@@ -44,6 +44,7 @@ lib*.pc
 /tmp_install/
 
 # Thomas
+# XXX Shouldn't be in the patch.
 /data/
 /server/
 .idea/
diff --git a/src/backend/commands/explain.c b/src/backend/commands/explain.c
index 9b7503630c..3610048c90 100644
--- a/src/backend/commands/explain.c
+++ b/src/backend/commands/explain.c
@@ -1206,6 +1206,11 @@ ExplainNode(PlanState *planstate, List *ancestors,
 			pname = sname = "Nested Loop";
 			break;
 		case T_MergeJoin:
+			/*
+			 * XXX Not sure we want to add another top-level node (Merge vs. Range Merge).
+			 *
+			 * I'd use Merge for both and just differentiate them using Range Cond.
+			 */
 			if(((MergeJoin *) plan)->rangeclause)
 			{
 				pname = "Range Merge";	/* "Join" gets added by jointype switch */
diff --git a/src/backend/executor/nodeMergejoin.c b/src/backend/executor/nodeMergejoin.c
index 09131479b1..d7f9ba809e 100644
--- a/src/backend/executor/nodeMergejoin.c
+++ b/src/backend/executor/nodeMergejoin.c
@@ -145,7 +145,9 @@ typedef struct MergeJoinClauseData
 }			MergeJoinClauseData;
 
 /*
- * Runtime data for the range clause
+ * Runtime data for the range clause.
+ *
+ * XXX This really needs some comments, explaining what the fields are for.
  */
 typedef struct RangeJoinData
 {
@@ -153,7 +155,6 @@ typedef struct RangeJoinData
 	ExprState *endClause;
 	ExprState *rangeExpr;
 	ExprState *elemExpr;
-
 }			RangeJoinData;
 
 /* Result type for MJEvalOuterValues and MJEvalInnerValues */
@@ -294,10 +295,14 @@ MJCreateRangeData(List *rangeclause,
 {
 	RangeData data;
 
-	Assert(list_length(node->rangeclause) < 3);
+	/* XXX how come this does not crash anything? */
+	Assert(false);
+	// FIXME, there's no 'node' variable
+	// Assert(list_length(node->rangeclause) < 3);

+	/* XXX useless, thanks to the palloc0 */
 	data->startClause = NULL;
 	data->endClause = NULL;
 	data->rangeExpr = NULL;
@@ -518,6 +523,10 @@ MJCompare(MergeJoinState *mergestate)
  * Compare the rangejoinable values of the current two input tuples
  * and return 0 if they are equal (ie, the outer interval contains the inner),
  * >0 if outer > inner, <0 if outer < inner.
+ *
+ * XXX So this is essentially a simple comparator function, except that it
+ * also deals with ranges. That'd deserve explanation how clauses with ranges
+ * works, I guess.
  */
 static int
 MJCompareRange(MergeJoinState *mergestate)
@@ -1028,6 +1037,9 @@ ExecMergeJoin(PlanState *pstate)
 						compareResult = MJCompare(node);
 						MJ_DEBUG_COMPARE(compareResult);
 
+						/*
+						 * XXX Incomprehensible. Maybe add some comments?
+						 */
 						if(compareResult == 0)
 						{
 							if(isRangeJoin)
@@ -1237,6 +1249,9 @@ ExecMergeJoin(PlanState *pstate)
 						/* we need not do MJEvalInnerValues again */
 					}
 
+					/*
+					 * Comments?
+					 */
 					if(isRangeJoin)
 					{
 						compareRangeResult = MJCompareRange(node);
@@ -1348,6 +1363,9 @@ ExecMergeJoin(PlanState *pstate)
 
 				if (compareResult == 0)
 				{
+					/*
+					 * XXX Comments?
+					 */
 					if(isRangeJoin)
 					{
 						compareRangeResult = MJCompareRange(node);
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index 041331d6bf..835944661b 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -3436,12 +3436,12 @@ final_cost_mergejoin(PlannerInfo *root, MergePath *path,
 				rescannedtuples;
 	double		rescanratio;
 
+	/* XXX ??? */
 	allclauses = list_concat(list_copy(mergeclauses), path->path_rangeclause);
 
-
 
 	/* Mark the path with the correct row estimate */
 	if (path->jpath.path.param_info)
diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c
index 4777e0a850..3f93f994a2 100644
--- a/src/backend/optimizer/path/joinpath.c
+++ b/src/backend/optimizer/path/joinpath.c
@@ -222,6 +222,7 @@ add_paths_to_joinrel(PlannerInfo *root,
 														  jointype,
 														  &mergejoin_allowed);
 
+		/* XXX Why only for inner/left joins? */
 		if (jointype == JOIN_INNER || jointype == JOIN_LEFT)
 			extra.rangeclause_list = select_rangejoin_clauses(outerrel,
 															  innerrel,
@@ -1238,6 +1239,9 @@ sort_inner_and_outer(PlannerInfo *root,
 	 * The pathkey order returned by select_outer_pathkeys_for_merge() has
 	 * some heuristics behind it (see that function), so be sure to try it
 	 * exactly as-is as well as making variants.
+	 *
+	 * XXX This comment probably needs updating? The patch significantly
+	 * reworks the following code ...
 	 */
 
 	range_pathkeys = select_outer_pathkeys_for_range(root,
@@ -1368,6 +1372,7 @@ sort_inner_and_outer(PlannerInfo *root,
 									   jointype,
 									   extra);
 
+		/* XXX comments? */
 		foreach(l, range_pathkeys)
 		{
 			PathKey		*range_outer_pathkey = (PathKey *) lfirst(l);
@@ -2442,6 +2447,8 @@ select_mergejoin_clauses(PlannerInfo *root,
 
 /*
  * range_clause_order
+ *
+ * XXX And what does this do?
  */
 static int
 range_clause_order(RestrictInfo *first,
@@ -2514,6 +2521,8 @@ range_clause_order(RestrictInfo *first,
 
 /*
  * select_rangejoin_clauses
+ *
+ * XXX And what does this do?
  */
 static List *
 select_rangejoin_clauses(RelOptInfo *outerrel,
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index f82e760658..4d1c539cd1 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -1217,6 +1217,8 @@ initialize_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
 
 /*
  * initialize_rangeclause_eclasses
+ *
+ * XXX And what does this do?
  */
 void
 initialize_rangeclause_eclasses(PlannerInfo *root,
@@ -1404,6 +1406,8 @@ find_mergeclauses_for_outer_pathkeys(PlannerInfo *root,
 
 /*
  * find_rangeclauses_for_outer_pathkeys
+ *
+ * XXX And what does this do?
  */
 List *
 find_rangeclauses_for_outer_pathkeys(PlannerInfo *root,
@@ -1637,6 +1641,8 @@ select_outer_pathkeys_for_merge(PlannerInfo *root,
 
 /*
  * select_outer_pathkeys_for_range
+ *
+ * XXX And what does this do?
  */
 List *
 select_outer_pathkeys_for_range(PlannerInfo *root,
@@ -1767,6 +1773,8 @@ make_inner_pathkeys_for_merge(PlannerInfo *root,
 
 /*
  * make_inner_pathkey_for_range
+ *
+ * XXX And what does this do?
  */
 PathKey *
 make_inner_pathkey_for_range(PlannerInfo *root,
diff --git a/src/backend/utils/adt/rangetypes.c b/src/backend/utils/adt/rangetypes.c
index 3972480519..ad3e2933a7 100644
--- a/src/backend/utils/adt/rangetypes.c
+++ b/src/backend/utils/adt/rangetypes.c
@@ -2509,6 +2509,8 @@ range_contains_elem_internal(TypeCacheEntry *typcache, const RangeType *r, Datum
 
 /*
  * Test whether range r is right of a specific element value.
+ *
+ * XXX naming seems a bit strange, all other functions here start with range_
  */
 bool
 elem_before_range_internal(TypeCacheEntry *typcache, Datum val, const RangeType *r)
@@ -2539,6 +2541,8 @@ elem_before_range_internal(TypeCacheEntry *typcache, Datum val, const RangeType
 
 /*
  * Test whether range r is left of a specific element value.
+ *
+ * XXX naming seems a bit strange, all other functions here start with range_
  */
 bool
 elem_after_range_internal(TypeCacheEntry *typcache, Datum val, const RangeType *r)
diff --git a/src/backend/utils/cache/lsyscache.c b/src/backend/utils/cache/lsyscache.c
index f6cc0cdb8a..136a30ed77 100644
--- a/src/backend/utils/cache/lsyscache.c
+++ b/src/backend/utils/cache/lsyscache.c
@@ -391,6 +391,8 @@ get_mergejoin_opfamilies(Oid opno)
 
 /*
  * get_rangejoin_opfamilies
+ *
+ * XXX and what does this do?
  */
 List *
 get_rangejoin_opfamilies(Oid opno)
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index c7d4431f06..66840821fb 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -2103,8 +2103,8 @@ typedef struct RestrictInfo
 
 	/* valid if clause is mergejoinable, else NIL */
 	List	   *mergeopfamilies;	/* opfamilies containing clause operator */
-	List	   *rangeleftopfamilies;
-	List	   *rangerightopfamilies;
+	List	   *rangeleftopfamilies;	/* comment? */
+	List	   *rangerightopfamilies;	/* comment? */
 
2.31.1

From 94f4ea1ffe1551e4d58c2b578e3ae371e28e3883 Mon Sep 17 00:00:00 2001
From: Tomas Vondra <[email-masked]>
Date: Wed, 17 Nov 2021 20:24:50 +0100
Subject: [PATCH 1/2] 2021/11/17

---
 .gitignore                                |  11 +
 src/backend/commands/explain.c            |  14 +-
 src/backend/executor/nodeMergejoin.c      | 209 ++++++++++++++-
 src/backend/nodes/copyfuncs.c             |   2 +
 src/backend/nodes/outfuncs.c              |   4 +
 src/backend/nodes/readfuncs.c             |   1 +
 src/backend/optimizer/path/costsize.c     |  14 +-
 src/backend/optimizer/path/joinpath.c     | 313 +++++++++++++++++++++-
 src/backend/optimizer/path/pathkeys.c     | 173 ++++++++++++
 src/backend/optimizer/plan/createplan.c   |  10 +
 src/backend/optimizer/plan/initsplan.c    |  55 ++++
 src/backend/optimizer/plan/setrefs.c      |   8 +
 src/backend/optimizer/util/pathnode.c     |   3 +
 src/backend/optimizer/util/restrictinfo.c |   2 +
 src/backend/utils/adt/rangetypes.c        |  60 +++++
 src/backend/utils/cache/lsyscache.c       |  34 +++
 src/include/nodes/execnodes.h             |   3 +
 src/include/nodes/pathnodes.h             |   4 +
 src/include/nodes/plannodes.h             |   1 +
 src/include/optimizer/pathnode.h          |   1 +
 src/include/optimizer/paths.h             |  10 +
 src/include/utils/lsyscache.h             |   1 +
 src/include/utils/rangetypes.h            |   2 +
 23 files changed, 906 insertions(+), 29 deletions(-)

diff --git a/.gitignore b/.gitignore
index 794e35b73c..5dca1a39ec 100644
--- a/.gitignore
+++ b/.gitignore
@@ -42,3 +42,14 @@ lib*.pc
 /Debug/
 /Release/
 /tmp_install/
+
+# Thomas
+/data/
+/server/
+.idea/
+.settings/
+.cproject
+.project
+logfile
+src/backend/catalog/postgres.*
+*.patch
index b41454ab6d..09131479b1 100644

 /*
 
+/*
 
+/*
+ * MJCreateRangeData
+ */
+static RangeData
+	Assert(list_length(node->rangeclause) < 3);

+/*
+ * MJCompareRange
+ *
 
 	CHECK_FOR_INTERRUPTS();

 	/*

 
 				if (compareResult == 0)
 				{
 
+	/*
index ad1ea2ff2f..262676b1fd 100644
index 23f23f11dc..1361c86d08 100644

 

 
 
index 1e4d404f02..041331d6bf 100644
@@ -3435,9 +3436,12 @@ final_cost_mergejoin(PlannerInfo *root, MergePath *path,
 				rescannedtuples;
 	double		rescanratio;

 
 	/*
index 0f3ad8aa65..4777e0a850 100644
 
 #include <math.h>

 

+		if (jointype == JOIN_INNER || jointype == JOIN_LEFT)
+			extra.rangeclause_list = select_rangejoin_clauses(outerrel,
+															  innerrel,
+															  restrictlist);
+	}
+
 	/*
 	 * If it's SEMI, ANTI, or inner_unique join, compute correction factors
 	 * for cost estimation.  These will be the same for all paths.
@@ -792,6 +805,7 @@ try_mergejoin_path(PlannerInfo *root,
 				   Path *inner_path,
 				   List *pathkeys,
 				   List *mergeclauses,
+				   List *rangeclause,
 				   List *outersortkeys,
 				   List *innersortkeys,
 				   JoinType jointype,
@@ -865,6 +879,7 @@ try_mergejoin_path(PlannerInfo *root,
 									   pathkeys,
 									   required_outer,
 									   mergeclauses,
+									   rangeclause,
 									   outersortkeys,
 									   innersortkeys));
 	}
@@ -941,6 +956,7 @@ try_partial_mergejoin_path(PlannerInfo *root,
 										   pathkeys,
 										   NULL,
 										   mergeclauses,
+										   NIL,
 										   outersortkeys,
 										   innersortkeys));
 }
@@ -1122,7 +1138,8 @@ sort_inner_and_outer(PlannerInfo *root,
 	Path	   *inner_path;
 	Path	   *cheapest_partial_outer = NULL;
 	Path	   *cheapest_safe_inner = NULL;
-	List	   *all_pathkeys;
+	List	   *merge_pathkeys;
+	List	   *range_pathkeys;
 	ListCell   *l;
 
 	/*
@@ -1222,25 +1239,80 @@ sort_inner_and_outer(PlannerInfo *root,

 
 		/* Sort the mergeclauses into the corresponding ordering */
 		cur_mergeclauses =
@@ -1257,7 +1329,7 @@ sort_inner_and_outer(PlannerInfo *root,
 												  outerkeys);

 		/*
@@ -1271,8 +1343,9 @@ sort_inner_and_outer(PlannerInfo *root,
 						   joinrel,
 						   outer_path,
 						   inner_path,
-						   merge_pathkeys,
+						   mergejoin_pathkeys,
 						   cur_mergeclauses,
+						   NIL,
 						   outerkeys,
 						   innerkeys,
 						   jointype,
@@ -1288,12 +1361,88 @@ sort_inner_and_outer(PlannerInfo *root,
 									   joinrel,
 									   cheapest_partial_outer,
 									   cheapest_safe_inner,
-									   merge_pathkeys,
+									   mergejoin_pathkeys,
 									   cur_mergeclauses,
 									   outerkeys,
 									   innerkeys,
 									   jointype,
 									   extra);
+
 
@@ -1379,6 +1528,7 @@ generate_mergejoin_paths(PlannerInfo *root,
 					   merge_pathkeys,
 					   mergeclauses,
 					   NIL,
+					   NIL,
 					   innersortkeys,
 					   jointype,
 					   extra,
@@ -1477,6 +1627,7 @@ generate_mergejoin_paths(PlannerInfo *root,
 							   newclauses,
 							   NIL,
 							   NIL,
+							   NIL,
 							   jointype,
 							   extra,
 							   is_partial);
@@ -1521,6 +1672,7 @@ generate_mergejoin_paths(PlannerInfo *root,
 								   newclauses,
 								   NIL,
 								   NIL,
+								   NIL,
 								   jointype,
 								   extra,
 								   is_partial);
@@ -2287,3 +2439,138 @@ select_mergejoin_clauses(PlannerInfo *root,
 
 	return result_list;
 }
+
+/*
+ * range_clause_order
+ */
+static int

+/*
 
+/*
 
+/*
 
+/*

 	/*
 
 	return node;
 }
diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.c
index f6a202d900..10990394ec 100644
--- a/src/backend/optimizer/plan/initsplan.c
+++ b/src/backend/optimizer/plan/initsplan.c
@@ -16,6 +16,7 @@

 

+/*
+ * check_rangejoinable
+ */
+static void
index ebfcf91826..3051ad540b 100644

 
+/*
 
 /*
 
+/*
index 2e8cbee69f..a682694a21 100644
@@ -1949,6 +1949,7 @@ typedef struct NestLoopState
 
@@ -1970,6 +1971,8 @@ typedef struct MergeJoinState
 
 /* ----------------
index 186e89905b..c7d4431f06 100644

@@ -2529,6 +2532,7 @@ typedef struct JoinPathExtraData
 
 /* ----------------

 
2.31.1