A rather hackish POC for alternative implementation of WITH TIES
This patch is a rather hacky implementation of the basic idea for
implementing FETCH ... WITH TIES, and potentially also PERCENT, by using
a window function expression to compute a stopping point.
Large chunks of this (the parser/ruleutils changes, docs, tests) are
taken from Surafel Temesgen's patch. The difference is that the executor
change in my version is minimal: Limit allows a boolean column in the
input to signal the point at which to stop. The planner inserts a
WindowAgg node to compute the necessary condition using the rank()
function.
The way this is done in the planner isn't (IMO) the best and should
probably be improved; in particular it currently misses some possible
optimizations (most notably constant-folding of the offset+limit
subexpression). I also haven't tested it properly to see whether I broke
anything, though it does pass regression.
--
Andrew (irc:RhodiumToad)
Attachments:
with_ties_window.patchtext/x-patchDownload
diff --git a/doc/src/sgml/ref/select.sgml b/doc/src/sgml/ref/select.sgml
index 691e402803..2b11c38087 100644
--- a/doc/src/sgml/ref/select.sgml
+++ b/doc/src/sgml/ref/select.sgml
@@ -44,7 +44,7 @@ SELECT [ ALL | DISTINCT [ ON ( <replaceable class="parameter">expression</replac
[ ORDER BY <replaceable class="parameter">expression</replaceable> [ ASC | DESC | USING <replaceable class="parameter">operator</replaceable> ] [ NULLS { FIRST | LAST } ] [, ...] ]
[ LIMIT { <replaceable class="parameter">count</replaceable> | ALL } ]
[ OFFSET <replaceable class="parameter">start</replaceable> [ ROW | ROWS ] ]
- [ FETCH { FIRST | NEXT } [ <replaceable class="parameter">count</replaceable> ] { ROW | ROWS } ONLY ]
+ [ FETCH { FIRST | NEXT } [ <replaceable class="parameter">count</replaceable> ] { ROW | ROWS } { ONLY | WITH TIES } ]
[ FOR { UPDATE | NO KEY UPDATE | SHARE | KEY SHARE } [ OF <replaceable class="parameter">table_name</replaceable> [, ...] ] [ NOWAIT | SKIP LOCKED ] [...] ]
<phrase>where <replaceable class="parameter">from_item</replaceable> can be one of:</phrase>
@@ -1438,7 +1438,7 @@ OFFSET <replaceable class="parameter">start</replaceable>
which <productname>PostgreSQL</productname> also supports. It is:
<synopsis>
OFFSET <replaceable class="parameter">start</replaceable> { ROW | ROWS }
-FETCH { FIRST | NEXT } [ <replaceable class="parameter">count</replaceable> ] { ROW | ROWS } ONLY
+FETCH { FIRST | NEXT } [ <replaceable class="parameter">count</replaceable> ] { ROW | ROWS } { ONLY | WITH TIES }
</synopsis>
In this syntax, the <replaceable class="parameter">start</replaceable>
or <replaceable class="parameter">count</replaceable> value is required by
@@ -1448,10 +1448,13 @@ FETCH { FIRST | NEXT } [ <replaceable class="parameter">count</replaceable> ] {
ambiguity.
If <replaceable class="parameter">count</replaceable> is
omitted in a <literal>FETCH</literal> clause, it defaults to 1.
- <literal>ROW</literal>
- and <literal>ROWS</literal> as well as <literal>FIRST</literal>
- and <literal>NEXT</literal> are noise words that don't influence
- the effects of these clauses.
+ The <literal>WITH TIES</literal> option is used to return any additional
+ rows that tie for the last place in the result set according to
+ <literal>ORDER BY</literal> clause; <literal>ORDER BY</literal>
+ is mandatory in this case.
+ <literal>ROW</literal> and <literal>ROWS</literal> as well as
+ <literal>FIRST</literal> and <literal>NEXT</literal> are noise
+ words that don't influence the effects of these clauses.
According to the standard, the <literal>OFFSET</literal> clause must come
before the <literal>FETCH</literal> clause if both are present; but
<productname>PostgreSQL</productname> is laxer and allows either order.
diff --git a/src/backend/catalog/sql_features.txt b/src/backend/catalog/sql_features.txt
index ab3e381cff..cd720eb19a 100644
--- a/src/backend/catalog/sql_features.txt
+++ b/src/backend/catalog/sql_features.txt
@@ -345,7 +345,7 @@ F863 Nested <result offset clause> in <query expression> YES
F864 Top-level <result offset clause> in views YES
F865 <offset row count> in <result offset clause> YES
F866 FETCH FIRST clause: PERCENT option NO
-F867 FETCH FIRST clause: WITH TIES option NO
+F867 FETCH FIRST clause: WITH TIES option YES
R010 Row pattern recognition: FROM clause NO
R020 Row pattern recognition: WINDOW clause NO
R030 Row pattern recognition: full aggregate support NO
diff --git a/src/backend/executor/nodeLimit.c b/src/backend/executor/nodeLimit.c
index 5e4d02ce4a..a2a8864b28 100644
--- a/src/backend/executor/nodeLimit.c
+++ b/src/backend/executor/nodeLimit.c
@@ -108,8 +108,20 @@ ExecLimit(PlanState *pstate)
}
/*
- * Okay, we have the first tuple of the window.
+ * Okay, we have the first tuple of the window. However, if we're
+ * doing LIMIT WHEN, our stop condition might be true already; so
+ * check that.
*/
+ if (node->whenColno > 0)
+ {
+ bool isnull = false;
+ Datum res = slot_getattr(slot, node->whenColno, &isnull);
+ if (!isnull && DatumGetBool(res))
+ {
+ node->lstate = LIMIT_EMPTY;
+ return NULL;
+ }
+ }
node->lstate = LIMIT_INWINDOW;
break;
@@ -152,6 +164,23 @@ ExecLimit(PlanState *pstate)
node->lstate = LIMIT_SUBPLANEOF;
return NULL;
}
+ /*
+ * Check whether our termination condition is reached, and
+ * pretend the subplan ran out if so. The subplan remains
+ * pointing at the terminating row, we must be careful not
+ * to advance it further as that will mess up backward scan.
+ */
+ if (node->whenColno > 0)
+ {
+ bool isnull = false;
+ Datum res = slot_getattr(slot, node->whenColno, &isnull);
+ if (!isnull && DatumGetBool(res))
+ {
+ node->lstate = LIMIT_SUBPLANEOF;
+ return NULL;
+ }
+ }
+
node->subSlot = slot;
node->position++;
}
@@ -372,6 +401,7 @@ ExecInitLimit(Limit *node, EState *estate, int eflags)
(PlanState *) limitstate);
limitstate->limitCount = ExecInitExpr((Expr *) node->limitCount,
(PlanState *) limitstate);
+ limitstate->whenColno = node->whenColno;
/*
* Initialize result type.
diff --git a/src/backend/nodes/copyfuncs.c b/src/backend/nodes/copyfuncs.c
index 2f267e4bb6..c9db414d12 100644
--- a/src/backend/nodes/copyfuncs.c
+++ b/src/backend/nodes/copyfuncs.c
@@ -1147,6 +1147,7 @@ _copyLimit(const Limit *from)
*/
COPY_NODE_FIELD(limitOffset);
COPY_NODE_FIELD(limitCount);
+ COPY_SCALAR_FIELD(whenColno);
return newnode;
}
@@ -3035,6 +3036,7 @@ _copyQuery(const Query *from)
COPY_NODE_FIELD(sortClause);
COPY_NODE_FIELD(limitOffset);
COPY_NODE_FIELD(limitCount);
+ COPY_SCALAR_FIELD(limitOption);
COPY_NODE_FIELD(rowMarks);
COPY_NODE_FIELD(setOperations);
COPY_NODE_FIELD(constraintDeps);
@@ -3119,6 +3121,7 @@ _copySelectStmt(const SelectStmt *from)
COPY_NODE_FIELD(sortClause);
COPY_NODE_FIELD(limitOffset);
COPY_NODE_FIELD(limitCount);
+ COPY_SCALAR_FIELD(limitOption);
COPY_NODE_FIELD(lockingClause);
COPY_NODE_FIELD(withClause);
COPY_SCALAR_FIELD(op);
diff --git a/src/backend/nodes/equalfuncs.c b/src/backend/nodes/equalfuncs.c
index da0e1d139a..4c25f61472 100644
--- a/src/backend/nodes/equalfuncs.c
+++ b/src/backend/nodes/equalfuncs.c
@@ -975,6 +975,7 @@ _equalQuery(const Query *a, const Query *b)
COMPARE_NODE_FIELD(sortClause);
COMPARE_NODE_FIELD(limitOffset);
COMPARE_NODE_FIELD(limitCount);
+ COMPARE_SCALAR_FIELD(limitOption);
COMPARE_NODE_FIELD(rowMarks);
COMPARE_NODE_FIELD(setOperations);
COMPARE_NODE_FIELD(constraintDeps);
@@ -1049,6 +1050,7 @@ _equalSelectStmt(const SelectStmt *a, const SelectStmt *b)
COMPARE_NODE_FIELD(sortClause);
COMPARE_NODE_FIELD(limitOffset);
COMPARE_NODE_FIELD(limitCount);
+ COMPARE_SCALAR_FIELD(limitOption);
COMPARE_NODE_FIELD(lockingClause);
COMPARE_NODE_FIELD(withClause);
COMPARE_SCALAR_FIELD(op);
diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index b0dcd02ff6..10aedab666 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -911,6 +911,7 @@ _outLimit(StringInfo str, const Limit *node)
WRITE_NODE_FIELD(limitOffset);
WRITE_NODE_FIELD(limitCount);
+ WRITE_INT_FIELD(whenColno);
}
static void
@@ -2714,6 +2715,7 @@ _outSelectStmt(StringInfo str, const SelectStmt *node)
WRITE_NODE_FIELD(sortClause);
WRITE_NODE_FIELD(limitOffset);
WRITE_NODE_FIELD(limitCount);
+ WRITE_ENUM_FIELD(limitOption, LimitOption);
WRITE_NODE_FIELD(lockingClause);
WRITE_NODE_FIELD(withClause);
WRITE_ENUM_FIELD(op, SetOperation);
@@ -2924,6 +2926,7 @@ _outQuery(StringInfo str, const Query *node)
WRITE_NODE_FIELD(sortClause);
WRITE_NODE_FIELD(limitOffset);
WRITE_NODE_FIELD(limitCount);
+ WRITE_ENUM_FIELD(limitOption, LimitOption);
WRITE_NODE_FIELD(rowMarks);
WRITE_NODE_FIELD(setOperations);
WRITE_NODE_FIELD(constraintDeps);
diff --git a/src/backend/nodes/readfuncs.c b/src/backend/nodes/readfuncs.c
index 764e3bb90c..d4e94a0f44 100644
--- a/src/backend/nodes/readfuncs.c
+++ b/src/backend/nodes/readfuncs.c
@@ -278,6 +278,7 @@ _readQuery(void)
READ_NODE_FIELD(sortClause);
READ_NODE_FIELD(limitOffset);
READ_NODE_FIELD(limitCount);
+ READ_ENUM_FIELD(limitOption, LimitOption);
READ_NODE_FIELD(rowMarks);
READ_NODE_FIELD(setOperations);
READ_NODE_FIELD(constraintDeps);
@@ -2337,6 +2338,7 @@ _readLimit(void)
READ_NODE_FIELD(limitOffset);
READ_NODE_FIELD(limitCount);
+ READ_INT_FIELD(whenColno);
READ_DONE();
}
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index aee81bd755..3500ae1565 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -2333,7 +2333,8 @@ create_minmaxagg_plan(PlannerInfo *root, MinMaxAggPath *best_path)
plan = (Plan *) make_limit(plan,
subparse->limitOffset,
- subparse->limitCount);
+ subparse->limitCount,
+ 0);
/* Must apply correct cost/width data to Limit node */
plan->startup_cost = mminfo->path->startup_cost;
@@ -2649,7 +2650,8 @@ create_limit_plan(PlannerInfo *root, LimitPath *best_path, int flags)
plan = make_limit(subplan,
best_path->limitOffset,
- best_path->limitCount);
+ best_path->limitCount,
+ best_path->whenColno);
copy_generic_path_info(&plan->plan, (Path *) best_path);
@@ -6552,7 +6554,7 @@ make_lockrows(Plan *lefttree, List *rowMarks, int epqParam)
* Build a Limit plan node
*/
Limit *
-make_limit(Plan *lefttree, Node *limitOffset, Node *limitCount)
+make_limit(Plan *lefttree, Node *limitOffset, Node *limitCount, AttrNumber whenColno)
{
Limit *node = makeNode(Limit);
Plan *plan = &node->plan;
@@ -6564,6 +6566,7 @@ make_limit(Plan *lefttree, Node *limitOffset, Node *limitCount)
node->limitOffset = limitOffset;
node->limitCount = limitCount;
+ node->whenColno = whenColno;
return node;
}
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 7fe11b59a0..49e0e8b4a2 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -190,6 +190,13 @@ static void create_one_window_path(PlannerInfo *root,
PathTarget *output_target,
WindowFuncLists *wflists,
List *activeWindows);
+static Path *generate_windowed_limit(PlannerInfo *root,
+ RelOptInfo *rel,
+ Path *input_path,
+ Node *limitOffset,
+ Node *limitCount,
+ LimitOption limitOption,
+ int64 offset_est, int64 count_est);
static RelOptInfo *create_distinct_paths(PlannerInfo *root,
RelOptInfo *input_rel);
static RelOptInfo *create_ordered_paths(PlannerInfo *root,
@@ -2311,10 +2318,19 @@ grouping_planner(PlannerInfo *root, bool inheritance_update,
*/
if (limit_needed(parse))
{
- path = (Path *) create_limit_path(root, final_rel, path,
- parse->limitOffset,
- parse->limitCount,
- offset_est, count_est);
+ if (parse->limitOption == LIMIT_OPTION_COUNT)
+ path = (Path *) create_limit_path(root, final_rel, path,
+ parse->limitOffset,
+ parse->limitCount,
+ 0, offset_est, count_est);
+ else
+ {
+ path = (Path *) generate_windowed_limit(root, final_rel, path,
+ parse->limitOffset,
+ parse->limitCount,
+ parse->limitOption,
+ offset_est, count_est);
+ }
}
/*
@@ -4709,6 +4725,105 @@ create_one_window_path(PlannerInfo *root,
add_path(window_rel, path);
}
+/*
+ * generate_windowed_limit
+ *
+ * Given a path which is ordered by the query ORDER BY, generate a window
+ * function expression over that same ordering, and a limit node on top.
+ * This is used to implement WITH TIES and (in future) PERCENT
+ */
+static Path *
+generate_windowed_limit(PlannerInfo *root,
+ RelOptInfo *rel,
+ Path *input_path,
+ Node *limitOffset,
+ Node *limitCount,
+ LimitOption limitOption,
+ int64 offset_est, int64 count_est)
+{
+ WindowFunc *arg1;
+ Node *arg2;
+ FuncExpr *newexpr;
+ PathTarget *target = copy_pathtarget(input_path->pathtarget);
+ WindowClause *wc = makeNode(WindowClause);
+ Path *path;
+ AttrNumber attno;
+
+ /*
+ * Cons up an expression of the form
+ *
+ * pg_catalog.rank() OVER (order by ...) > offset+limit
+ *
+ */
+ arg1 = makeNode(WindowFunc);
+ arg1->winfnoid = WINDOW_RANK_OID;
+ arg1->wintype = INT8OID;
+ arg1->wincollid = InvalidOid;
+ arg1->inputcollid = InvalidOid;
+ arg1->args = NIL;
+ arg1->aggfilter = NULL;
+ arg1->winref = ~0;
+ arg1->winstar = false;
+ arg1->winagg = false;
+ arg1->location = -1;
+
+ if (limitOffset)
+ {
+ FuncExpr *arg = makeNode(FuncExpr);
+ arg->funcid = INT8PL_OID;
+ arg->funcresulttype = INT8OID;
+ arg->funcretset = false;
+ arg->funcvariadic = false;
+ arg->funcformat = COERCE_EXPLICIT_CALL;
+ arg->funccollid = InvalidOid;
+ arg->inputcollid = InvalidOid;
+ arg->args = list_make2(limitOffset,limitCount);
+ arg->location = -1;
+ arg2 = (Node *) arg;
+ }
+ else
+ arg2 = limitCount;
+
+ newexpr = makeNode(FuncExpr);
+ newexpr->funcid = INT8GT_OID;
+ newexpr->funcresulttype = INT8OID;
+ newexpr->funcretset = false;
+ newexpr->funcvariadic = false;
+ newexpr->funcformat = COERCE_EXPLICIT_CALL;
+ newexpr->funccollid = InvalidOid;
+ newexpr->inputcollid = InvalidOid;
+ newexpr->args = list_make2(arg1,arg2);
+ newexpr->location = exprLocation(limitCount);
+
+ attno = list_length(root->processed_tlist) + 1;
+ root->processed_tlist = lappend(root->processed_tlist,
+ makeTargetEntry((Expr *) newexpr,
+ attno,
+ "limit_flag",
+ true));
+
+ add_column_to_pathtarget(target, (Expr *) newexpr, 0);
+
+ wc->name = NULL;
+ wc->refname = NULL;
+ wc->partitionClause = NIL;
+ wc->orderClause = root->parse->sortClause;
+ wc->frameOptions = 0;
+ wc->startOffset = NULL;
+ wc->endOffset = NULL;
+ wc->winref = ~0;
+ wc->copiedOrder = false;
+
+ path = (Path *)
+ create_windowagg_path(root, rel, input_path, target,
+ list_make1(arg1),
+ wc);
+ return (Path *) create_limit_path(root, rel, path,
+ limitOffset, NULL, attno,
+ offset_est, count_est);
+}
+
+
/*
* create_distinct_paths
*
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index 60c93ee7c5..6c6efb5746 100644
--- a/src/backend/optimizer/util/pathnode.c
+++ b/src/backend/optimizer/util/pathnode.c
@@ -3538,6 +3538,7 @@ create_modifytable_path(PlannerInfo *root, RelOptInfo *rel,
* 'subpath' is the path representing the source of data
* 'limitOffset' is the actual OFFSET expression, or NULL
* 'limitCount' is the actual LIMIT expression, or NULL
+ * 'limitOption' is how the LIMIT is to be interpreted
* 'offset_est' is the estimated value of the OFFSET expression
* 'count_est' is the estimated value of the LIMIT expression
*/
@@ -3545,6 +3546,7 @@ LimitPath *
create_limit_path(PlannerInfo *root, RelOptInfo *rel,
Path *subpath,
Node *limitOffset, Node *limitCount,
+ AttrNumber whenColno,
int64 offset_est, int64 count_est)
{
LimitPath *pathnode = makeNode(LimitPath);
@@ -3566,6 +3568,7 @@ create_limit_path(PlannerInfo *root, RelOptInfo *rel,
pathnode->subpath = subpath;
pathnode->limitOffset = limitOffset;
pathnode->limitCount = limitCount;
+ pathnode->whenColno = whenColno;
/*
* Adjust the output rows count and costs according to the offset/limit.
diff --git a/src/backend/parser/analyze.c b/src/backend/parser/analyze.c
index 85d7a96406..f0b863f41a 100644
--- a/src/backend/parser/analyze.c
+++ b/src/backend/parser/analyze.c
@@ -1292,6 +1292,7 @@ transformSelectStmt(ParseState *pstate, SelectStmt *stmt)
EXPR_KIND_OFFSET, "OFFSET");
qry->limitCount = transformLimitClause(pstate, stmt->limitCount,
EXPR_KIND_LIMIT, "LIMIT");
+ qry->limitOption = stmt->limitOption;
/* transform window clauses after we have seen all window functions */
qry->windowClause = transformWindowDefinitions(pstate,
@@ -1540,6 +1541,7 @@ transformValuesClause(ParseState *pstate, SelectStmt *stmt)
EXPR_KIND_OFFSET, "OFFSET");
qry->limitCount = transformLimitClause(pstate, stmt->limitCount,
EXPR_KIND_LIMIT, "LIMIT");
+ qry->limitOption = stmt->limitOption;
if (stmt->lockingClause)
ereport(ERROR,
@@ -1774,6 +1776,7 @@ transformSetOperationStmt(ParseState *pstate, SelectStmt *stmt)
EXPR_KIND_OFFSET, "OFFSET");
qry->limitCount = transformLimitClause(pstate, limitCount,
EXPR_KIND_LIMIT, "LIMIT");
+ qry->limitOption = stmt->limitOption;
qry->rtable = pstate->p_rtable;
qry->jointree = makeFromExpr(pstate->p_joinlist, NULL);
diff --git a/src/backend/parser/gram.y b/src/backend/parser/gram.y
index c5086846de..1dc45eec62 100644
--- a/src/backend/parser/gram.y
+++ b/src/backend/parser/gram.y
@@ -127,6 +127,14 @@ typedef struct ImportQual
List *table_names;
} ImportQual;
+/* Private struct for the result of opt_select_limit production */
+typedef struct SelectLimit
+{
+ Node *limitOffset;
+ Node *limitCount;
+ LimitOption limitOption;
+} SelectLimit;
+
/* ConstraintAttributeSpec yields an integer bitmask of these flags: */
#define CAS_NOT_DEFERRABLE 0x01
#define CAS_DEFERRABLE 0x02
@@ -164,7 +172,7 @@ static List *makeOrderedSetArgs(List *directargs, List *orderedargs,
core_yyscan_t yyscanner);
static void insertSelectOptions(SelectStmt *stmt,
List *sortClause, List *lockingClause,
- Node *limitOffset, Node *limitCount,
+ SelectLimit *limitClause,
WithClause *withClause,
core_yyscan_t yyscanner);
static Node *makeSetOp(SetOperation op, bool all, Node *larg, Node *rarg);
@@ -242,6 +250,7 @@ static Node *makeRecursiveViewSelect(char *relname, List *aliases, Node *query);
PartitionSpec *partspec;
PartitionBoundSpec *partboundspec;
RoleSpec *rolespec;
+ struct SelectLimit *selectlimit;
}
%type <node> stmt schema_stmt
@@ -374,6 +383,7 @@ static Node *makeRecursiveViewSelect(char *relname, List *aliases, Node *query);
%type <ival> import_qualification_type
%type <importqual> import_qualification
%type <node> vacuum_relation
+%type <selectlimit> opt_select_limit select_limit limit_clause
%type <list> stmtblock stmtmulti
OptTableElementList TableElementList OptInherit definition
@@ -394,8 +404,7 @@ static Node *makeRecursiveViewSelect(char *relname, List *aliases, Node *query);
target_list opt_target_list insert_column_list set_target_list
set_clause_list set_clause
def_list operator_def_list indirection opt_indirection
- reloption_list group_clause TriggerFuncArgs select_limit
- opt_select_limit opclass_item_list opclass_drop_list
+ reloption_list group_clause TriggerFuncArgs opclass_item_list opclass_drop_list
opclass_purpose opt_opfamily transaction_mode_list_or_empty
OptTableFuncElementList TableFuncElementList opt_type_modifiers
prep_type_clause
@@ -457,7 +466,7 @@ static Node *makeRecursiveViewSelect(char *relname, List *aliases, Node *query);
comment_type_any_name comment_type_name
security_label_type_any_name security_label_type_name
-%type <node> fetch_args limit_clause select_limit_value
+%type <node> fetch_args select_limit_value
offset_clause select_offset_value
select_fetch_first_value I_or_F_const
%type <ival> row_or_rows first_or_next
@@ -11317,14 +11326,14 @@ select_no_parens:
| select_clause sort_clause
{
insertSelectOptions((SelectStmt *) $1, $2, NIL,
- NULL, NULL, NULL,
+ NULL, NULL,
yyscanner);
$$ = $1;
}
| select_clause opt_sort_clause for_locking_clause opt_select_limit
{
insertSelectOptions((SelectStmt *) $1, $2, $3,
- list_nth($4, 0), list_nth($4, 1),
+ $4,
NULL,
yyscanner);
$$ = $1;
@@ -11332,7 +11341,7 @@ select_no_parens:
| select_clause opt_sort_clause select_limit opt_for_locking_clause
{
insertSelectOptions((SelectStmt *) $1, $2, $4,
- list_nth($3, 0), list_nth($3, 1),
+ $3,
NULL,
yyscanner);
$$ = $1;
@@ -11340,7 +11349,7 @@ select_no_parens:
| with_clause select_clause
{
insertSelectOptions((SelectStmt *) $2, NULL, NIL,
- NULL, NULL,
+ NULL,
$1,
yyscanner);
$$ = $2;
@@ -11348,7 +11357,7 @@ select_no_parens:
| with_clause select_clause sort_clause
{
insertSelectOptions((SelectStmt *) $2, $3, NIL,
- NULL, NULL,
+ NULL,
$1,
yyscanner);
$$ = $2;
@@ -11356,7 +11365,7 @@ select_no_parens:
| with_clause select_clause opt_sort_clause for_locking_clause opt_select_limit
{
insertSelectOptions((SelectStmt *) $2, $3, $4,
- list_nth($5, 0), list_nth($5, 1),
+ $5,
$1,
yyscanner);
$$ = $2;
@@ -11364,7 +11373,7 @@ select_no_parens:
| with_clause select_clause opt_sort_clause select_limit opt_for_locking_clause
{
insertSelectOptions((SelectStmt *) $2, $3, $5,
- list_nth($4, 0), list_nth($4, 1),
+ $4,
$1,
yyscanner);
$$ = $2;
@@ -11658,20 +11667,44 @@ sortby: a_expr USING qual_all_Op opt_nulls_order
select_limit:
- limit_clause offset_clause { $$ = list_make2($2, $1); }
- | offset_clause limit_clause { $$ = list_make2($1, $2); }
- | limit_clause { $$ = list_make2(NULL, $1); }
- | offset_clause { $$ = list_make2($1, NULL); }
+ limit_clause offset_clause
+ {
+ $$ = $1;
+ ($$)->limitOffset = $2;
+ }
+ | offset_clause limit_clause
+ {
+ $$ = $2;
+ ($$)->limitOffset = $1;
+ }
+ | limit_clause
+ {
+ $$ = $1;
+ }
+ | offset_clause
+ {
+ SelectLimit *n = (SelectLimit *) palloc(sizeof(SelectLimit));
+ n->limitOffset = $1;
+ n->limitCount = NULL;
+ n->limitOption = LIMIT_OPTION_COUNT;
+ $$ = n;
+ }
;
opt_select_limit:
select_limit { $$ = $1; }
- | /* EMPTY */ { $$ = list_make2(NULL,NULL); }
+ | /* EMPTY */ { $$ = NULL; }
;
limit_clause:
LIMIT select_limit_value
- { $$ = $2; }
+ {
+ SelectLimit *n = (SelectLimit *) palloc(sizeof(SelectLimit));
+ n->limitOffset = NULL;
+ n->limitCount = $2;
+ n->limitOption = LIMIT_OPTION_COUNT;
+ $$ = n;
+ }
| LIMIT select_limit_value ',' select_offset_value
{
/* Disabled because it was too confusing, bjm 2002-02-18 */
@@ -11689,9 +11722,29 @@ limit_clause:
* we can see the ONLY token in the lookahead slot.
*/
| FETCH first_or_next select_fetch_first_value row_or_rows ONLY
- { $$ = $3; }
+ {
+ SelectLimit *n = (SelectLimit *) palloc(sizeof(SelectLimit));
+ n->limitOffset = NULL;
+ n->limitCount = $3;
+ n->limitOption = LIMIT_OPTION_COUNT;
+ $$ = n;
+ }
+ | FETCH first_or_next select_fetch_first_value row_or_rows WITH TIES
+ {
+ SelectLimit *n = (SelectLimit *) palloc(sizeof(SelectLimit));
+ n->limitOffset = NULL;
+ n->limitCount = $3;
+ n->limitOption = LIMIT_OPTION_WITH_TIES;
+ $$ = n;
+ }
| FETCH first_or_next row_or_rows ONLY
- { $$ = makeIntConst(1, -1); }
+ {
+ SelectLimit *n = (SelectLimit *) palloc(sizeof(SelectLimit));
+ n->limitOffset = NULL;
+ n->limitCount = makeIntConst(1, -1);
+ n->limitOption = LIMIT_OPTION_COUNT;
+ $$ = n;
+ }
;
offset_clause:
@@ -15947,7 +16000,7 @@ makeOrderedSetArgs(List *directargs, List *orderedargs,
static void
insertSelectOptions(SelectStmt *stmt,
List *sortClause, List *lockingClause,
- Node *limitOffset, Node *limitCount,
+ SelectLimit *limitClause,
WithClause *withClause,
core_yyscan_t yyscanner)
{
@@ -15968,23 +16021,35 @@ insertSelectOptions(SelectStmt *stmt,
}
/* We can handle multiple locking clauses, though */
stmt->lockingClause = list_concat(stmt->lockingClause, lockingClause);
- if (limitOffset)
+ if (limitClause && limitClause->limitOffset)
{
if (stmt->limitOffset)
ereport(ERROR,
(errcode(ERRCODE_SYNTAX_ERROR),
errmsg("multiple OFFSET clauses not allowed"),
- parser_errposition(exprLocation(limitOffset))));
- stmt->limitOffset = limitOffset;
+ parser_errposition(exprLocation(limitClause->limitOffset))));
+ stmt->limitOffset = limitClause->limitOffset;
}
- if (limitCount)
+ if (limitClause && limitClause->limitCount)
{
if (stmt->limitCount)
ereport(ERROR,
(errcode(ERRCODE_SYNTAX_ERROR),
errmsg("multiple LIMIT clauses not allowed"),
- parser_errposition(exprLocation(limitCount))));
- stmt->limitCount = limitCount;
+ parser_errposition(exprLocation(limitClause->limitCount))));
+ stmt->limitCount = limitClause->limitCount;
+ }
+ if (limitClause && limitClause->limitOption != LIMIT_OPTION_DEFAULT)
+ {
+ if (stmt->limitOption)
+ ereport(ERROR,
+ (errcode(ERRCODE_SYNTAX_ERROR),
+ errmsg("multiple limit options not allowed")));
+ if (!stmt->sortClause && limitClause->limitOption == LIMIT_OPTION_WITH_TIES)
+ ereport(ERROR,
+ (errcode(ERRCODE_SYNTAX_ERROR),
+ errmsg("WITH TIES options can not be specified without ORDER BY clause")));
+ stmt->limitOption = limitClause->limitOption;
}
if (withClause)
{
diff --git a/src/backend/utils/adt/ruleutils.c b/src/backend/utils/adt/ruleutils.c
index 13685a0a0e..82ef187b06 100644
--- a/src/backend/utils/adt/ruleutils.c
+++ b/src/backend/utils/adt/ruleutils.c
@@ -5308,7 +5308,15 @@ get_select_query_def(Query *query, deparse_context *context,
-PRETTYINDENT_STD, PRETTYINDENT_STD, 0);
get_rule_expr(query->limitOffset, context, false);
}
- if (query->limitCount != NULL)
+ if (query->limitOption == LIMIT_OPTION_WITH_TIES)
+ {
+ appendContextKeyword(context, " FETCH FIRST ",
+ -PRETTYINDENT_STD, PRETTYINDENT_STD, 0);
+ get_rule_expr(query->limitCount, context, false);
+ appendContextKeyword(context, " ROWS WITH TIES ",
+ -PRETTYINDENT_STD, PRETTYINDENT_STD, 0);
+ }
+ if (query->limitCount != NULL && query->limitOption != LIMIT_OPTION_WITH_TIES)
{
appendContextKeyword(context, " LIMIT ",
-PRETTYINDENT_STD, PRETTYINDENT_STD, 0);
diff --git a/src/include/catalog/pg_proc.dat b/src/include/catalog/pg_proc.dat
index ac8f64b219..e6f299e3dd 100644
--- a/src/include/catalog/pg_proc.dat
+++ b/src/include/catalog/pg_proc.dat
@@ -1245,7 +1245,7 @@
{ oid => '462',
proname => 'int8um', prorettype => 'int8', proargtypes => 'int8',
prosrc => 'int8um' },
-{ oid => '463',
+{ oid => '463', oid_symbol => 'INT8PL_OID',
proname => 'int8pl', prorettype => 'int8', proargtypes => 'int8 int8',
prosrc => 'int8pl' },
{ oid => '464',
@@ -1266,7 +1266,7 @@
{ oid => '469',
proname => 'int8lt', proleakproof => 't', prorettype => 'bool',
proargtypes => 'int8 int8', prosrc => 'int8lt' },
-{ oid => '470',
+{ oid => '470', oid_symbol => 'INT8GT_OID',
proname => 'int8gt', proleakproof => 't', prorettype => 'bool',
proargtypes => 'int8 int8', prosrc => 'int8gt' },
{ oid => '471',
@@ -9477,7 +9477,8 @@
{ oid => '3100', descr => 'row number within partition',
proname => 'row_number', prokind => 'w', proisstrict => 'f',
prorettype => 'int8', proargtypes => '', prosrc => 'window_row_number' },
-{ oid => '3101', descr => 'integer rank with gaps',
+{ oid => '3101', oid_symbol => 'WINDOW_RANK_OID',
+ descr => 'integer rank with gaps',
proname => 'rank', prokind => 'w', proisstrict => 'f', prorettype => 'int8',
proargtypes => '', prosrc => 'window_rank' },
{ oid => '3102', descr => 'integer rank without gaps',
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index 6eb647290b..03b92013f4 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -2351,6 +2351,7 @@ typedef struct LimitState
ExprState *limitCount; /* COUNT parameter, or NULL if none */
int64 offset; /* current OFFSET value */
int64 count; /* current COUNT, if any */
+ AttrNumber whenColno; /* input column number of WHEN expr */
bool noCount; /* if true, ignore count */
LimitStateCond lstate; /* state machine status, as above */
int64 position; /* 1-based index of last tuple returned */
diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.h
index bce2d59b0d..1aa2d88994 100644
--- a/src/include/nodes/nodes.h
+++ b/src/include/nodes/nodes.h
@@ -822,4 +822,17 @@ typedef enum OnConflictAction
ONCONFLICT_UPDATE /* ON CONFLICT ... DO UPDATE */
} OnConflictAction;
+/*
+ * LimitOption -
+ * LIMIT option of query
+ *
+ * This is needed in both parsenodes.h and plannodes.h, so put it here...
+ */
+typedef enum LimitOption
+{
+ LIMIT_OPTION_DEFAULT, /* No limit present */
+ LIMIT_OPTION_COUNT, /* FETCH FIRST... ONLY */
+ LIMIT_OPTION_WITH_TIES /* FETCH FIRST... WITH TIES */
+} LimitOption;
+
#endif /* NODES_H */
diff --git a/src/include/nodes/parsenodes.h b/src/include/nodes/parsenodes.h
index ff626cbe61..18cd221d20 100644
--- a/src/include/nodes/parsenodes.h
+++ b/src/include/nodes/parsenodes.h
@@ -158,7 +158,8 @@ typedef struct Query
List *sortClause; /* a list of SortGroupClause's */
Node *limitOffset; /* # of result tuples to skip (int8 expr) */
- Node *limitCount; /* # of result tuples to return (int8 expr) */
+ Node *limitCount; /* # of result tuples to return (int8 or bool expr) */
+ LimitOption limitOption; /* limit type { WITH TIES | ONLY | WHEN } */
List *rowMarks; /* a list of RowMarkClause's */
@@ -1595,6 +1596,7 @@ typedef struct SelectStmt
List *sortClause; /* sort clause (a list of SortBy's) */
Node *limitOffset; /* # of result tuples to skip */
Node *limitCount; /* # of result tuples to return */
+ LimitOption limitOption; /* limit type */
List *lockingClause; /* FOR UPDATE (list of LockingClause's) */
WithClause *withClause; /* WITH clause */
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index 23a06d718e..655b2b99dd 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -1793,6 +1793,7 @@ typedef struct LimitPath
Path *subpath; /* path representing input source */
Node *limitOffset; /* OFFSET parameter, or NULL if none */
Node *limitCount; /* COUNT parameter, or NULL if none */
+ AttrNumber whenColno;
} LimitPath;
diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h
index 8e6594e355..9420dd2998 100644
--- a/src/include/nodes/plannodes.h
+++ b/src/include/nodes/plannodes.h
@@ -967,6 +967,7 @@ typedef struct Limit
Plan plan;
Node *limitOffset; /* OFFSET parameter, or NULL if none */
Node *limitCount; /* COUNT parameter, or NULL if none */
+ AttrNumber whenColno; /* input column number of WHEN expr */
} Limit;
diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h
index a12af54971..8e275bdcad 100644
--- a/src/include/optimizer/pathnode.h
+++ b/src/include/optimizer/pathnode.h
@@ -262,6 +262,7 @@ extern ModifyTablePath *create_modifytable_path(PlannerInfo *root,
extern LimitPath *create_limit_path(PlannerInfo *root, RelOptInfo *rel,
Path *subpath,
Node *limitOffset, Node *limitCount,
+ AttrNumber whenColno,
int64 offset_est, int64 count_est);
extern void adjust_limit_rows_costs(double *rows,
Cost *startup_cost, Cost *total_cost,
diff --git a/src/include/optimizer/planmain.h b/src/include/optimizer/planmain.h
index e7aaddd50d..5efcba318c 100644
--- a/src/include/optimizer/planmain.h
+++ b/src/include/optimizer/planmain.h
@@ -56,7 +56,7 @@ extern Agg *make_agg(List *tlist, List *qual,
int numGroupCols, AttrNumber *grpColIdx, Oid *grpOperators, Oid *grpCollations,
List *groupingSets, List *chain,
double dNumGroups, Plan *lefttree);
-extern Limit *make_limit(Plan *lefttree, Node *limitOffset, Node *limitCount);
+extern Limit *make_limit(Plan *lefttree, Node *limitOffset, Node *limitCount, AttrNumber whenColno);
/*
* prototypes for plan/initsplan.c
diff --git a/src/test/regress/expected/limit.out b/src/test/regress/expected/limit.out
index c18f547cbd..d59b9cb376 100644
--- a/src/test/regress/expected/limit.out
+++ b/src/test/regress/expected/limit.out
@@ -503,3 +503,55 @@ select sum(tenthous) as s1, sum(tenthous) + random()*0 as s2
45020 | 45020
(3 rows)
+--
+-- FETCH FIRST
+-- Check the WITH TIES clause
+--
+SELECT thousand
+ FROM onek WHERE thousand < 5
+ ORDER BY thousand FETCH FIRST 2 ROW WITH TIES;
+ thousand
+----------
+ 0
+ 0
+ 0
+ 0
+ 0
+ 0
+ 0
+ 0
+ 0
+ 0
+(10 rows)
+
+SELECT thousand
+ FROM onek WHERE thousand < 5
+ ORDER BY thousand FETCH FIRST 1 ROW WITH TIES;
+ thousand
+----------
+ 0
+ 0
+ 0
+ 0
+ 0
+ 0
+ 0
+ 0
+ 0
+ 0
+(10 rows)
+
+SELECT thousand
+ FROM onek WHERE thousand < 5
+ ORDER BY thousand FETCH FIRST 2 ROW ONLY;
+ thousand
+----------
+ 0
+ 0
+(2 rows)
+
+-- should fail
+SELECT ''::text AS two, unique1, unique2, stringu1
+ FROM onek WHERE unique1 > 50
+ FETCH FIRST 2 ROW WITH TIES;
+ERROR: WITH TIES options can not be specified without ORDER BY clause
diff --git a/src/test/regress/sql/limit.sql b/src/test/regress/sql/limit.sql
index 2a313d80ca..ecd4ae6aee 100644
--- a/src/test/regress/sql/limit.sql
+++ b/src/test/regress/sql/limit.sql
@@ -141,3 +141,24 @@ select sum(tenthous) as s1, sum(tenthous) + random()*0 as s2
select sum(tenthous) as s1, sum(tenthous) + random()*0 as s2
from tenk1 group by thousand order by thousand limit 3;
+
+--
+-- FETCH FIRST
+-- Check the WITH TIES clause
+--
+
+SELECT thousand
+ FROM onek WHERE thousand < 5
+ ORDER BY thousand FETCH FIRST 2 ROW WITH TIES;
+
+SELECT thousand
+ FROM onek WHERE thousand < 5
+ ORDER BY thousand FETCH FIRST 1 ROW WITH TIES;
+
+SELECT thousand
+ FROM onek WHERE thousand < 5
+ ORDER BY thousand FETCH FIRST 2 ROW ONLY;
+-- should fail
+SELECT ''::text AS two, unique1, unique2, stringu1
+ FROM onek WHERE unique1 > 50
+ FETCH FIRST 2 ROW WITH TIES;
On Fri, Nov 29, 2019 at 8:40 AM Andrew Gierth <andrew@tao11.riddles.org.uk>
wrote:
This patch is a rather hacky implementation of the basic idea for
implementing FETCH ... WITH TIES, and potentially also PERCENT, by using
a window function expression to compute a stopping point.Large chunks of this (the parser/ruleutils changes, docs, tests) are
taken from Surafel Temesgen's patch. The difference is that the executor
change in my version is minimal: Limit allows a boolean column in the
input to signal the point at which to stop. The planner inserts a
WindowAgg node to compute the necessary condition using the rank()
function.The way this is done in the planner isn't (IMO) the best and should
probably be improved; in particular it currently misses some possible
optimizations (most notably constant-folding of the offset+limit
subexpression). I also haven't tested it properly to see whether I broke
anything, though it does pass regression.
Unlike most other executor node limit node has implementation for handling
backward scan that support cursor operation but your approach didn't do
this inherently because it outsource limitNode functionality to window
function and window function didn't do this
eg.
postgres=# begin;
BEGIN
postgres=# declare c cursor for select i from generate_series(1,1000000)
s(i) order by i fetch first 2 rows with ties;
DECLARE CURSOR
postgres=# fetch all in c;
i
---
1
2
(2 rows)
postgres=# fetch backward all in c;
ERROR: cursor can only scan forward
HINT: Declare it with SCROLL option to enable backward scan.
Even with SCROLL option it is not working as limitNode does. It store the
result and return in backward scan that use more space than current limit
and limit with ties implementation.
If am not mistaken the patch also reevaluate limit every time returning row
beside its not good for performance its will return incorrect result with
limit involving volatile function
regards
Surafel
"Surafel" == Surafel Temesgen <surafel3000@gmail.com> writes:
Surafel> Unlike most other executor node limit node has implementation
Surafel> for handling backward scan that support cursor operation but
Surafel> your approach didn't do this inherently because it outsource
Surafel> limitNode functionality to window function and window function
Surafel> didn't do this
Correct. But this is a non-issue: if you want to be able to do backward
scan you are supposed to declare the cursor as SCROLL; if it happens to
work without it, that is pure coincidence. (Cursors declared with neither
SCROLL nor NO SCROLL support backwards scan only if the underlying plan
supports backward scan with no additional overhead, which is something
you can't predict from the query.)
The Limit node declares that it supports backwards scan if, and only if,
its immediate child node supports it. It happens that WindowAgg does
not, so in this implementation, LIMIT ... WITH TIES will not support
backward scan without a tuplestore. I don't consider this an especially
big deal; backward scans are extremely rare (as shown by the fact that
bugs in backward scan have tended to go unnoticed for decades, e.g. bug
#15336), and therefore we should not optimize for them.
Surafel> If am not mistaken the patch also reevaluate limit every time
The (offset+limit) expression is, yes. I noted in the original post that
this needs work - probably it should be pushed out to an InitPlan if it
doesn't fold to a constant. i.e. using the expression
rank() over (...) > (select offset+limit)
where it currently has
rank() over (...) > (offset+limit)
(Generating the limit expression so late in planning is the main thing
that needs changing to get this from a hack POC to usable code)
The main point here is that the same rather minimal executor changes
allow support for not only WITH TIES but also PERCENT and possibly
arbitrary stop conditions as well. (I know I've often wanted LIMIT WHEN
to stop a query at a data-dependent point without having to resort to
recursion - this patch doesn't quite get there, because of the scope
issues involved in analyzing the WHEN condition, but it at least sets up
the concept.)
--
Andrew (irc:RhodiumToad)
Hello
As this is a valuable feature, it would be good to have something happen
here. I wouldn't like to have pg13 ship with no implementation of WITH
TIES at all.
My own inclination is that Andrew's implementation, being more general
in nature, would be the better one to have in the codebase; but we don't
have a complete patch yet. Can we reach some compromise such as if
Andrew's patch is not completed then we push Surafel's?
Thanks
--
�lvaro Herrera https://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
"Alvaro" == Alvaro Herrera <alvherre@2ndquadrant.com> writes:
Alvaro> My own inclination is that Andrew's implementation, being more
Alvaro> general in nature, would be the better one to have in the
Alvaro> codebase; but we don't have a complete patch yet. Can we reach
Alvaro> some compromise such as if Andrew's patch is not completed then
Alvaro> we push Surafel's?
Mine needs some attention to where exactly in planning the necessary
transformation work should be done; right now the planner part is a
hack, intended to demonstrate the idea (and to let the executor changes
work) rather than actually be the final version. As I mentioned before,
some stuff does need to be pushed out to an InitPlan to make it work
without multiple-evaluation problems.
(A second opinion from another planner expert would be welcome on that
part)
I was largely holding off on doing further work hoping for some
discussion of which way we should go. If you think my approach is worth
pursuing (I haven't seriously tested the performance, but I'd expect it
to be slower than Surafel's - the price you pay for flexibility) then I
can look at it further, but figuring out the planner stuff will take
some time.
--
Andrew.
On Wed, Jan 22, 2020 at 3:06 PM Alvaro Herrera <alvherre@2ndquadrant.com>
wrote:
My own inclination is that Andrew's implementation, being more general
in nature, would be the better one to have in the codebase; but we don't
have a complete patch yet. Can we reach some compromise such as if
Andrew's patch is not completed then we push Surafel's?
+1
On Wed, Jan 22, 2020 at 4:35 PM Andrew Gierth <andrew@tao11.riddles.org.uk>
wrote:
I was largely holding off on doing further work hoping for some
discussion of which way we should go. If you think my approach is worth
pursuing (I haven't seriously tested the performance, but I'd expect it
to be slower than Surafel's - the price you pay for flexibility) then I
can look at it further, but figuring out the planner stuff will take
some time.
Flexibility with more generalized code is good, though if performance is
significantly slower I would be concerned. I quickly reviewed the patch
but haven't tested it yet.
Is it realistic to add PERCENT into this patch or would that be a future
enhancement?
Thanks,
*Ryan Lambert*
On Wed, Jan 22, 2020 at 3:35 PM Andrew Gierth <andrew@tao11.riddles.org.uk>
wrote:
"Alvaro" == Alvaro Herrera <alvherre@2ndquadrant.com> writes:
I was largely holding off on doing further work hoping for some
discussion of which way we should go. If you think my approach is worth
pursuing (I haven't seriously tested the performance, but I'd expect it
to be slower than Surafel's - the price you pay for flexibility) then I
can look at it further, but figuring out the planner stuff will take
some time.
Other alternative can be pushing the existing implementation
which will be open to change in case of better-finished
implementation.
regards
Surafel
On 2020-Mar-26, Surafel Temesgen wrote:
On Wed, Jan 22, 2020 at 3:35 PM Andrew Gierth <andrew@tao11.riddles.org.uk>
wrote:"Alvaro" == Alvaro Herrera <alvherre@2ndquadrant.com> writes:
I was largely holding off on doing further work hoping for some
discussion of which way we should go. If you think my approach is worth
pursuing (I haven't seriously tested the performance, but I'd expect it
to be slower than Surafel's - the price you pay for flexibility) then I
can look at it further, but figuring out the planner stuff will take
some time.Other alternative can be pushing the existing implementation
which will be open to change in case of better-finished
implementation.
At this point, I think that's what we should do.
--
�lvaro Herrera https://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services