01_tid_scan_ordering.patch

diff --git a/src/backend/commands/explain.c b/src/backend/commands/explain.c
index 16a80a0..d9deb72 100644
--- a/src/backend/commands/explain.c
+++ b/src/backend/commands/explain.c
@@ -111,6 +111,7 @@ static void show_foreignscan_info(ForeignScanState *fsstate, ExplainState *es);
 static void show_eval_params(Bitmapset *bms_params, ExplainState *es);
 static const char *explain_get_index_name(Oid indexId);
 static void show_buffer_usage(ExplainState *es, const BufferUsage *usage);
+static void show_scan_direction(ExplainState *es, ScanDirection direction);
 static void ExplainIndexScanDetails(Oid indexid, ScanDirection indexorderdir,
 						ExplainState *es);
 static void ExplainScanTarget(Scan *plan, ExplainState *es);
@@ -1194,7 +1195,6 @@ ExplainNode(PlanState *planstate, List *ancestors,
 		case T_SeqScan:
 		case T_SampleScan:
 		case T_BitmapHeapScan:
-		case T_TidScan:
 		case T_SubqueryScan:
 		case T_FunctionScan:
 		case T_TableFuncScan:
@@ -1203,6 +1203,10 @@ ExplainNode(PlanState *planstate, List *ancestors,
 		case T_WorkTableScan:
 			ExplainScanTarget((Scan *) plan, es);
 			break;
+		case T_TidScan:
+			show_scan_direction(es, ((TidScan *) plan)->direction);
+			ExplainScanTarget((Scan *) plan, es);
+			break;
 		case T_ForeignScan:
 		case T_CustomScan:
 			if (((Scan *) plan)->scanrelid > 0)
@@ -2797,25 +2801,21 @@ show_buffer_usage(ExplainState *es, const BufferUsage *usage)
 }
 
 /*
- * Add some additional details about an IndexScan or IndexOnlyScan
+ * Show the direction of a scan.
  */
 static void
-ExplainIndexScanDetails(Oid indexid, ScanDirection indexorderdir,
-						ExplainState *es)
+show_scan_direction(ExplainState *es, ScanDirection direction)
 {
-	const char *indexname = explain_get_index_name(indexid);
-
 	if (es->format == EXPLAIN_FORMAT_TEXT)
 	{
-		if (ScanDirectionIsBackward(indexorderdir))
+		if (ScanDirectionIsBackward(direction))
 			appendStringInfoString(es->str, " Backward");
-		appendStringInfo(es->str, " using %s", indexname);
 	}
 	else
 	{
 		const char *scandir;
 
-		switch (indexorderdir)
+		switch (direction)
 		{
 			case BackwardScanDirection:
 				scandir = "Backward";
@@ -2831,11 +2831,27 @@ ExplainIndexScanDetails(Oid indexid, ScanDirection indexorderdir,
 				break;
 		}
 		ExplainPropertyText("Scan Direction", scandir, es);
-		ExplainPropertyText("Index Name", indexname, es);
 	}
 }
 
 /*
+ * Add some additional details about an IndexScan or IndexOnlyScan
+ */
+static void
+ExplainIndexScanDetails(Oid indexid, ScanDirection indexorderdir,
+						ExplainState *es)
+{
+	const char *indexname = explain_get_index_name(indexid);
+
+	show_scan_direction(es, indexorderdir);
+
+	if (es->format == EXPLAIN_FORMAT_TEXT)
+		appendStringInfo(es->str, " using %s", indexname);
+	else
+		ExplainPropertyText("Index Name", indexname, es);
+}
+
+/*
  * Show the target of a Scan node
  */
 static void
diff --git a/src/backend/executor/nodeTidscan.c b/src/backend/executor/nodeTidscan.c
index e207b1f..df11d92 100644
--- a/src/backend/executor/nodeTidscan.c
+++ b/src/backend/executor/nodeTidscan.c
@@ -50,6 +50,7 @@ typedef struct TidExpr
 static void TidExprListCreate(TidScanState *tidstate);
 static void TidListEval(TidScanState *tidstate);
 static int	itemptr_comparator(const void *a, const void *b);
+static int	itemptr_comparator_reverse(const void *a, const void *b);
 static TupleTableSlot *TidNext(TidScanState *node);
 
 
@@ -225,13 +226,12 @@ TidListEval(TidScanState *tidstate)
 							  RelationGetRelid(tidstate->ss.ss_currentRelation),
 							  &cursor_tid))
 			{
-				if (numTids >= numAllocTids)
-				{
-					numAllocTids *= 2;
-					tidList = (ItemPointerData *)
-						repalloc(tidList,
-								 numAllocTids * sizeof(ItemPointerData));
-				}
+				/*
+				 * A current-of TidExpr only exists by itself, and we should
+				 * already have allocated a tidList entry for it.  We don't
+				 * need to check whether the tidList array needs to be resized.
+				 */
+				Assert(numTids < numAllocTids);
 				tidList[numTids++] = cursor_tid;
 			}
 		}
@@ -247,12 +247,16 @@ TidListEval(TidScanState *tidstate)
 	{
 		int			lastTid;
 		int			i;
+		int (* cmp) (const void *, const void *);
+
+		/* Choose the sort order based on the scan direction. */
+		cmp = ScanDirectionIsBackward(((TidScan *) tidstate->ss.ps.plan)->direction) ? itemptr_comparator_reverse : itemptr_comparator;
 
 		/* CurrentOfExpr could never appear OR'd with something else */
 		Assert(!tidstate->tss_isCurrentOf);
 
 		qsort((void *) tidList, numTids, sizeof(ItemPointerData),
-			  itemptr_comparator);
+			  cmp);
 		lastTid = 0;
 		for (i = 1; i < numTids; i++)
 		{
@@ -291,6 +295,15 @@ itemptr_comparator(const void *a, const void *b)
 	return 0;
 }
 
+/*
+ * qsort comparator for ItemPointerData items, in reverse order
+ */
+static int
+itemptr_comparator_reverse(const void *a, const void *b)
+{
+	return itemptr_comparator(b,a);
+}
+
 /* ----------------------------------------------------------------
  *		TidNext
  *
diff --git a/src/backend/nodes/copyfuncs.c b/src/backend/nodes/copyfuncs.c
index 7c8220c..5f84984 100644
--- a/src/backend/nodes/copyfuncs.c
+++ b/src/backend/nodes/copyfuncs.c
@@ -583,6 +583,7 @@ _copyTidScan(const TidScan *from)
 	 * copy remainder of node
 	 */
 	COPY_NODE_FIELD(tidquals);
+	COPY_SCALAR_FIELD(direction);
 
 	return newnode;
 }
diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index 6269f47..870dd2e 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -615,6 +615,7 @@ _outTidScan(StringInfo str, const TidScan *node)
 	_outScanInfo(str, (const Scan *) node);
 
 	WRITE_NODE_FIELD(tidquals);
+	WRITE_ENUM_FIELD(direction, ScanDirection);
 }
 
 static void
diff --git a/src/backend/nodes/readfuncs.c b/src/backend/nodes/readfuncs.c
index 3254524..2317f58 100644
--- a/src/backend/nodes/readfuncs.c
+++ b/src/backend/nodes/readfuncs.c
@@ -1828,6 +1828,7 @@ _readTidScan(void)
 	ReadCommonScan(&local_node->scan);
 
 	READ_NODE_FIELD(tidquals);
+	READ_ENUM_FIELD(direction, ScanDirection);
 
 	READ_DONE();
 }
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index ec66cb9..729b207 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -18,6 +18,9 @@
 #include "postgres.h"
 
 #include "access/stratnum.h"
+#include "access/sysattr.h"
+#include "catalog/pg_operator.h"
+#include "catalog/pg_type.h"
 #include "nodes/makefuncs.h"
 #include "nodes/nodeFuncs.h"
 #include "nodes/plannodes.h"
@@ -848,6 +851,22 @@ build_join_pathkeys(PlannerInfo *root,
 	return truncate_useless_pathkeys(root, joinrel, outer_pathkeys);
 }
 
+/*
+ * build_tidscan_pathkeys
+ *	  Build the path keys corresponding to ORDER BY ctid ASC|DESC.
+ */
+List *
+build_tidscan_pathkeys(PlannerInfo *root,
+					   RelOptInfo *rel,
+					   ScanDirection direction)
+{
+	int opno = (direction == ForwardScanDirection) ? TIDLessOperator : TIDGreaterOperator;
+	Var *varexpr = makeVar(rel->relid, SelfItemPointerAttributeNumber, TIDOID, -1, InvalidOid, 0);
+	List *pathkeys = build_expression_pathkey(root, (Expr *) varexpr, NULL, opno, rel->relids, true);
+
+	return pathkeys;
+}
+
 /****************************************************************************
  *		PATHKEYS AND SORT CLAUSES
  ****************************************************************************/
diff --git a/src/backend/optimizer/path/tidpath.c b/src/backend/optimizer/path/tidpath.c
index 3bb5b8d..7a40700 100644
--- a/src/backend/optimizer/path/tidpath.c
+++ b/src/backend/optimizer/path/tidpath.c
@@ -247,6 +247,8 @@ TidQualFromBaseRestrictinfo(RelOptInfo *rel)
  * create_tidscan_paths
  *	  Create paths corresponding to direct TID scans of the given rel.
  *
+ *	  Path keys and direction will be set on the scans if it looks useful.
+ *
  *	  Candidate paths are added to the rel's pathlist (using add_path).
  */
 void
@@ -265,6 +267,30 @@ create_tidscan_paths(PlannerInfo *root, RelOptInfo *rel)
 	tidquals = TidQualFromBaseRestrictinfo(rel);
 
 	if (tidquals)
-		add_path(rel, (Path *) create_tidscan_path(root, rel, tidquals,
+	{
+		List			*pathkeys = NULL;
+		ScanDirection	 direction = ForwardScanDirection;
+
+		if (has_useful_pathkeys(root, rel)) {
+			/*
+			 * Build path keys corresponding to ORDER BY ctid ASC, and check
+			 * whether they will be useful for this scan.  If not, build
+			 * path keys for DESC, and try that; set the direction to
+			 * BackwardScanDirection if so.  If neither of them will be
+			 * useful, no path keys will be set.
+			 */
+			pathkeys = build_tidscan_pathkeys(root, rel, ForwardScanDirection);
+			if (!pathkeys_contained_in(pathkeys, root->query_pathkeys))
+			{
+				pathkeys = build_tidscan_pathkeys(root, rel, BackwardScanDirection);
+				if (pathkeys_contained_in(pathkeys, root->query_pathkeys))
+					direction = BackwardScanDirection;
+				else
+					pathkeys = NULL;
+			}
+		}
+
+		add_path(rel, (Path *) create_tidscan_path(root, rel, tidquals, pathkeys, direction,
 												   required_outer));
+	}
 }
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index ae41c9e..4e1faa6 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -185,7 +185,7 @@ static BitmapHeapScan *make_bitmap_heapscan(List *qptlist,
 					 List *bitmapqualorig,
 					 Index scanrelid);
 static TidScan *make_tidscan(List *qptlist, List *qpqual, Index scanrelid,
-			 List *tidquals);
+			 List *tidquals, ScanDirection direction);
 static SubqueryScan *make_subqueryscan(List *qptlist,
 				  List *qpqual,
 				  Index scanrelid,
@@ -3097,7 +3097,9 @@ create_tidscan_plan(PlannerInfo *root, TidPath *best_path,
 	scan_plan = make_tidscan(tlist,
 							 scan_clauses,
 							 scan_relid,
-							 tidquals);
+							 tidquals,
+							 best_path->direction
+							);
 
 	copy_generic_path_info(&scan_plan->scan.plan, &best_path->path);
 
@@ -5179,7 +5181,8 @@ static TidScan *
 make_tidscan(List *qptlist,
 			 List *qpqual,
 			 Index scanrelid,
-			 List *tidquals)
+			 List *tidquals,
+			 ScanDirection direction)
 {
 	TidScan    *node = makeNode(TidScan);
 	Plan	   *plan = &node->scan.plan;
@@ -5190,6 +5193,7 @@ make_tidscan(List *qptlist,
 	plan->righttree = NULL;
 	node->scan.scanrelid = scanrelid;
 	node->tidquals = tidquals;
+	node->direction = direction;
 
 	return node;
 }
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index c5aaaf5..e2d51a9 100644
--- a/src/backend/optimizer/util/pathnode.c
+++ b/src/backend/optimizer/util/pathnode.c
@@ -1186,6 +1186,7 @@ create_bitmap_or_path(PlannerInfo *root,
  */
 TidPath *
 create_tidscan_path(PlannerInfo *root, RelOptInfo *rel, List *tidquals,
+					List *pathkeys, ScanDirection direction,
 					Relids required_outer)
 {
 	TidPath    *pathnode = makeNode(TidPath);
@@ -1198,9 +1199,10 @@ create_tidscan_path(PlannerInfo *root, RelOptInfo *rel, List *tidquals,
 	pathnode->path.parallel_aware = false;
 	pathnode->path.parallel_safe = rel->consider_parallel;
 	pathnode->path.parallel_workers = 0;
-	pathnode->path.pathkeys = NIL;	/* always unordered */
+	pathnode->path.pathkeys = pathkeys;
 
 	pathnode->tidquals = tidquals;
+	pathnode->direction = direction;
 
 	cost_tidscan(&pathnode->path, root, rel, tidquals,
 				 pathnode->path.param_info);
diff --git a/src/include/catalog/pg_operator.dat b/src/include/catalog/pg_operator.dat
index d9b6bad..31e7d61 100644
--- a/src/include/catalog/pg_operator.dat
+++ b/src/include/catalog/pg_operator.dat
@@ -156,7 +156,7 @@
   oprname => '<', oprleft => 'tid', oprright => 'tid', oprresult => 'bool',
   oprcom => '>(tid,tid)', oprnegate => '>=(tid,tid)', oprcode => 'tidlt',
   oprrest => 'scalarltsel', oprjoin => 'scalarltjoinsel' },
-{ oid => '2800', descr => 'greater than',
+{ oid => '2800', oid_symbol => 'TIDGreaterOperator', descr => 'greater than',
   oprname => '>', oprleft => 'tid', oprright => 'tid', oprresult => 'bool',
   oprcom => '<(tid,tid)', oprnegate => '<=(tid,tid)', oprcode => 'tidgt',
   oprrest => 'scalargtsel', oprjoin => 'scalargtjoinsel' },
diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h
index 7c2abbd..96d30aa 100644
--- a/src/include/nodes/plannodes.h
+++ b/src/include/nodes/plannodes.h
@@ -492,6 +492,7 @@ typedef struct TidScan
 {
 	Scan		scan;
 	List	   *tidquals;		/* qual(s) involving CTID = something */
+	ScanDirection direction;
 } TidScan;
 
 /* ----------------
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index 41caf87..cf4839d 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -1233,6 +1233,7 @@ typedef struct TidPath
 {
 	Path		path;
 	List	   *tidquals;		/* qual(s) involving CTID = something */
+	ScanDirection direction;
 } TidPath;
 
 /*
diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h
index 7c5ff22..a0a88a5 100644
--- a/src/include/optimizer/pathnode.h
+++ b/src/include/optimizer/pathnode.h
@@ -63,7 +63,8 @@ extern BitmapOrPath *create_bitmap_or_path(PlannerInfo *root,
 					  RelOptInfo *rel,
 					  List *bitmapquals);
 extern TidPath *create_tidscan_path(PlannerInfo *root, RelOptInfo *rel,
-					List *tidquals, Relids required_outer);
+					List *tidquals, List *pathkeys, ScanDirection direction,
+					Relids required_outer);
 extern AppendPath *create_append_path(PlannerInfo *root, RelOptInfo *rel,
 				   List *subpaths, List *partial_subpaths,
 				   Relids required_outer,
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index cafde30..3b915b5 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -211,6 +211,9 @@ extern List *build_join_pathkeys(PlannerInfo *root,
 					RelOptInfo *joinrel,
 					JoinType jointype,
 					List *outer_pathkeys);
+extern List *build_tidscan_pathkeys(PlannerInfo *root,
+									RelOptInfo *rel,
+									ScanDirection direction);
 extern List *make_pathkeys_for_sortclauses(PlannerInfo *root,
 							  List *sortclauses,
 							  List *tlist);
diff --git a/src/test/regress/expected/tidscan.out b/src/test/regress/expected/tidscan.out
index 521ed1b..7eebe77 100644
--- a/src/test/regress/expected/tidscan.out
+++ b/src/test/regress/expected/tidscan.out
@@ -116,6 +116,39 @@ FETCH FIRST FROM c;
 (1 row)
 
 ROLLBACK;
+-- check that ordering on a tidscan doesn't require a sort
+EXPLAIN (COSTS OFF)
+SELECT ctid, * FROM tidscan WHERE ctid = ANY(ARRAY['(0,2)', '(0,1)', '(0,3)']::tid[]) ORDER BY ctid;
+                          QUERY PLAN                           
+---------------------------------------------------------------
+ Tid Scan on tidscan
+   TID Cond: (ctid = ANY ('{"(0,2)","(0,1)","(0,3)"}'::tid[]))
+(2 rows)
+
+SELECT ctid, * FROM tidscan WHERE ctid = ANY(ARRAY['(0,2)', '(0,1)', '(0,3)']::tid[]) ORDER BY ctid;
+ ctid  | id 
+-------+----
+ (0,1) |  1
+ (0,2) |  2
+ (0,3) |  3
+(3 rows)
+
+EXPLAIN (COSTS OFF)
+SELECT ctid, * FROM tidscan WHERE ctid = ANY(ARRAY['(0,2)', '(0,1)', '(0,3)']::tid[]) ORDER BY ctid DESC;
+                          QUERY PLAN                           
+---------------------------------------------------------------
+ Tid Scan Backward on tidscan
+   TID Cond: (ctid = ANY ('{"(0,2)","(0,1)","(0,3)"}'::tid[]))
+(2 rows)
+
+SELECT ctid, * FROM tidscan WHERE ctid = ANY(ARRAY['(0,2)', '(0,1)', '(0,3)']::tid[]) ORDER BY ctid DESC;
+ ctid  | id 
+-------+----
+ (0,3) |  3
+ (0,2) |  2
+ (0,1) |  1
+(3 rows)
+
 -- tidscan via CURRENT OF
 BEGIN;
 DECLARE c CURSOR FOR SELECT ctid, * FROM tidscan;
diff --git a/src/test/regress/sql/tidscan.sql b/src/test/regress/sql/tidscan.sql
index a8472e0..5237f06 100644
--- a/src/test/regress/sql/tidscan.sql
+++ b/src/test/regress/sql/tidscan.sql
@@ -43,6 +43,15 @@ FETCH BACKWARD 1 FROM c;
 FETCH FIRST FROM c;
 ROLLBACK;
 
+-- check that ordering on a tidscan doesn't require a sort
+EXPLAIN (COSTS OFF)
+SELECT ctid, * FROM tidscan WHERE ctid = ANY(ARRAY['(0,2)', '(0,1)', '(0,3)']::tid[]) ORDER BY ctid;
+SELECT ctid, * FROM tidscan WHERE ctid = ANY(ARRAY['(0,2)', '(0,1)', '(0,3)']::tid[]) ORDER BY ctid;
+
+EXPLAIN (COSTS OFF)
+SELECT ctid, * FROM tidscan WHERE ctid = ANY(ARRAY['(0,2)', '(0,1)', '(0,3)']::tid[]) ORDER BY ctid DESC;
+SELECT ctid, * FROM tidscan WHERE ctid = ANY(ARRAY['(0,2)', '(0,1)', '(0,3)']::tid[]) ORDER BY ctid DESC;
+
 -- tidscan via CURRENT OF
 BEGIN;
 DECLARE c CURSOR FOR SELECT ctid, * FROM tidscan;