Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_CBC_SHA1:256) (Exim 4.89) (envelope-from ) id 1hAO81-0003Mf-61 for pgsql-hackers@arkaria.postgresql.org; Sun, 31 Mar 2019 00:15:13 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.89) (envelope-from ) id 1hAO7x-0003hD-Vd for pgsql-hackers@arkaria.postgresql.org; Sun, 31 Mar 2019 00:15:09 +0000 Received: from magus.postgresql.org ([2a02:c0:301:0:ffff::29]) by malur.postgresql.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_CBC_SHA1:256) (Exim 4.89) (envelope-from ) id 1hAO7x-0003h6-Hc for pgsql-hackers@lists.postgresql.org; Sun, 31 Mar 2019 00:15:09 +0000 Received: from mail-wr1-x444.google.com ([2a00:1450:4864:20::444]) by magus.postgresql.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_CBC_SHA1:256) (Exim 4.89) (envelope-from ) id 1hAO7o-0004Bn-KY for pgsql-hackers@postgresql.org; Sun, 31 Mar 2019 00:15:08 +0000 Received: by mail-wr1-x444.google.com with SMTP id g3so7130401wrx.9 for ; Sat, 30 Mar 2019 17:15:00 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=2ndquadrant-com.20150623.gappssmtp.com; s=20150623; h=date:from:to:cc:subject:message-id:references:mime-version :content-disposition:in-reply-to:user-agent; bh=u8gMfsquf4quYza3hVXkEGmJSFXof4pri/DVTsjAskE=; b=DbvtfSffRNb58up19rAdJ+W7oLA7asvs8QgHnE+B9654PtmkCL8uqZhB0zUYkrZ66L 5cC+mcc3WMKKFErJ2KfV6gbx4T6MWaUG0zM+jR/Blcp0xVd53vgqERZoFZUQHqZ2RgIx GoRrX9k1VG3DYkSmXKdmJyLVA9SkiTlvOAvCAH10ROJ3YnEvbse903g2/VpK7/5fIOHV nd5fSkajRxHF3D95Ozqw9Q0NRDffximRyqenjvInVYfB/dKF4jDzSCSgUPeagItKmCCh Hoxyy0cljOhWCNeMZ8dTXLTGYIp7JYpUIMk5Lr9EAnRe285wwfU3GtO/OO1+7cztyKmV vNQQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:cc:subject:message-id:references :mime-version:content-disposition:in-reply-to:user-agent; bh=u8gMfsquf4quYza3hVXkEGmJSFXof4pri/DVTsjAskE=; b=VfuPT0P+nwfQyjxlXSxNlDowQ6W2kKUHANhC34UiyQOrAmFvb0zd1dNvfT5zqtyC5G QoUzsGrg1JrI0ZPniWyL6Zx83ceajQ2jiaG+31WQ1nZwujbY57pKdRVFBaNQl7nhOdJy BLAX1LJzSNrl8ewGXNidPKpo86BBOXkUX3at/RGuOz89KAtEBSUP4SBUKljwQ/3byUZV hZH/od7/w0Oltn5CBxzAd2CLZfd0Zp3wJHAUKqWyT9xdAM96oUU+3I6S/Zp+X+dnGUVW fPqvlM9BlxB6pXyO+PhYAeq82N86or1OosSkvMpVXhH70NYPLx0Dp1GXf5/T9Tt18ybU OVAw== X-Gm-Message-State: APjAAAXRaKtV6hYKHIvwwy4JfzE6AElrsvjHt1H8F5hH2BQ3eZiLLArA 5Eo/fn8ZZ8BmCN7hbhC6kj1IXA== X-Google-Smtp-Source: APXvYqxriPxe0eQKjJvIHQqW4HHESAB1D42XFkvs3oA6v58YgCBy548G2OGVcQQxjY8ZFjomk9OmUA== X-Received: by 2002:a05:6000:12c7:: with SMTP id l7mr7331286wrx.4.1553991297936; Sat, 30 Mar 2019 17:14:57 -0700 (PDT) Received: from localhost (ip-86-49-243-43.net.upcbroadband.cz. [86.49.243.43]) by smtp.gmail.com with ESMTPSA id h2sm13370296wro.11.2019.03.30.17.14.47 (version=TLS1_3 cipher=AEAD-AES256-GCM-SHA384 bits=256/256); Sat, 30 Mar 2019 17:14:48 -0700 (PDT) Date: Sun, 31 Mar 2019 01:14:46 +0100 From: Tomas Vondra To: Surafel Temesgen Cc: David Steele , Michael Paquier , Robert Haas , andrew@tao11.riddles.org.uk, PostgreSQL Hackers Subject: Re: Re: FETCH FIRST clause WITH TIES option Message-ID: <20190331001446.GA10804@development> References: <20190204052857.GP29064@paquier.xyz> <20190329005648.GA1136@development> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="WIyZ46R2i8wDzkSu" Content-Disposition: inline In-Reply-To: <20190329005648.GA1136@development> User-Agent: Mutt/1.11.4+135 (aae3e555) (2019-03-21) List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Precedence: bulk --WIyZ46R2i8wDzkSu Content-Type: text/plain; charset=us-ascii; format=flowed Content-Disposition: inline On Fri, Mar 29, 2019 at 01:56:48AM +0100, Tomas Vondra wrote: >On Tue, Mar 26, 2019 at 10:46:00AM +0300, Surafel Temesgen wrote: >>On Mon, Mar 25, 2019 at 11:56 AM David Steele wrote: >> >>>This patch no longer passes testing so marked Waiting on Author. >>> >>> >>Thank you for informing. Fixed > >Thanks for the updated patch. I do have this on my list of patches that >I'd like to commit in this CF - likely tomorrow after one more round of >review, or so. > Hi, I got to look at the patch today, with the intent to commit, but sadly I ran into a couple of minor issues that I don't feel comfortable fixing on my own. Attached is a patch highlighling some of the places (0001 is your v7 patch, to keep the cfbot happy). 1) the docs documented this as ... [ ONLY | WITH TIES ] but that's wrong, because it implies those options are optional (i.e. the user may not specify anything). That's not the case, exactly one of those options needs to be specified, so it should have been ... { ONLY | WITH TIES } 2) The comment in ExecLimit() needs to be updated to explain that WITH TIES changes the behavior. 3) Minor code style issues (no space before * on comment lines, {} around single-line if statements, ...). 4) The ExecLimit() does this if (node->limitOption == WITH_TIES) ExecCopySlot(node->last_slot, slot); but I think we only really need to do that for the last tuple in the window, no? Would it be a useful optimization? 5) Two issues in _outLimit(). Firstly, when printing uniqCollations the code actually prints uniqOperators. Secondly, why does the code use these loops at all, instead of using WRITE_ATTRNUMBER_ARRAY and WRITE_OID_ARRAY, like other places? Perhaps there's an issue with empty arrays? I haven't tested this, but looking at the READ_ counterparts, I don't see why that would be the case. regards -- Tomas Vondra http://www.2ndQuadrant.com PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services --WIyZ46R2i8wDzkSu Content-Type: text/plain; charset=us-ascii Content-Disposition: attachment; filename="0001-fetch_first_with_ties_v7.patch" From af9b8b8edcad84f88fc846ab3ce3f77cfb94230e Mon Sep 17 00:00:00 2001 From: Tomas Vondra Date: Sun, 31 Mar 2019 00:04:31 +0100 Subject: [PATCH 1/2] fetch_first_with_ties_v7 --- doc/src/sgml/ref/select.sgml | 9 ++- src/backend/executor/nodeLimit.c | 91 ++++++++++++++++++++++--- src/backend/nodes/copyfuncs.c | 7 ++ src/backend/nodes/equalfuncs.c | 2 + src/backend/nodes/outfuncs.c | 31 +++++++++ src/backend/nodes/readfuncs.c | 6 ++ src/backend/optimizer/plan/createplan.c | 44 +++++++++++- src/backend/optimizer/plan/planner.c | 1 + src/backend/optimizer/util/pathnode.c | 16 +++++ src/backend/parser/analyze.c | 3 + src/backend/parser/gram.y | 49 +++++++++---- src/include/nodes/execnodes.h | 3 + src/include/nodes/nodes.h | 12 ++++ src/include/nodes/parsenodes.h | 2 + src/include/nodes/pathnodes.h | 1 + src/include/nodes/plannodes.h | 5 ++ src/include/optimizer/pathnode.h | 1 + src/include/optimizer/planmain.h | 3 +- src/test/regress/expected/limit.out | 35 ++++++++++ src/test/regress/sql/limit.sql | 17 +++++ 20 files changed, 307 insertions(+), 31 deletions(-) diff --git a/doc/src/sgml/ref/select.sgml b/doc/src/sgml/ref/select.sgml index 06d611b64c..b3b045ea87 100644 --- a/doc/src/sgml/ref/select.sgml +++ b/doc/src/sgml/ref/select.sgml @@ -44,7 +44,7 @@ SELECT [ ALL | DISTINCT [ ON ( expressionexpression [ ASC | DESC | USING operator ] [ NULLS { FIRST | LAST } ] [, ...] ] [ LIMIT { count | ALL } ] [ OFFSET start [ ROW | ROWS ] ] - [ FETCH { FIRST | NEXT } [ count ] { ROW | ROWS } ONLY ] + [ FETCH { FIRST | NEXT } [ count ] { ROW | ROWS } [ ONLY | WITH TIES ] ] [ FOR { UPDATE | NO KEY UPDATE | SHARE | KEY SHARE } [ OF table_name [, ...] ] [ NOWAIT | SKIP LOCKED ] [...] ] where from_item can be one of: @@ -1430,7 +1430,7 @@ OFFSET start which PostgreSQL also supports. It is: OFFSET start { ROW | ROWS } -FETCH { FIRST | NEXT } [ count ] { ROW | ROWS } ONLY +FETCH { FIRST | NEXT } [ count ] { ROW | ROWS } [ ONLY | WITH TIES ] In this syntax, the start or count value is required by @@ -1440,7 +1440,10 @@ FETCH { FIRST | NEXT } [ count ] { ambiguity. If count is omitted in a FETCH clause, it defaults to 1. - ROW + ROW . + WITH TIES option is used to return two or more rows + that tie for last place in the limit results set according to ORDER BY + clause (ORDER BY clause must be specified in this case). and ROWS as well as FIRST and NEXT are noise words that don't influence the effects of these clauses. diff --git a/src/backend/executor/nodeLimit.c b/src/backend/executor/nodeLimit.c index baa669abe8..e8aed10177 100644 --- a/src/backend/executor/nodeLimit.c +++ b/src/backend/executor/nodeLimit.c @@ -41,6 +41,7 @@ static TupleTableSlot * /* return: a tuple or NULL */ ExecLimit(PlanState *pstate) { LimitState *node = castNode(LimitState, pstate); + ExprContext *econtext = node->ps.ps_ExprContext; ScanDirection direction; TupleTableSlot *slot; PlanState *outerPlan; @@ -131,7 +132,8 @@ ExecLimit(PlanState *pstate) * the state machine state to record having done so. */ if (!node->noCount && - node->position - node->offset >= node->count) + node->position - node->offset >= node->count && + node->limitOption == WITH_ONLY) { node->lstate = LIMIT_WINDOWEND; @@ -144,18 +146,64 @@ ExecLimit(PlanState *pstate) return NULL; } + else if (!node->noCount && + node->position - node->offset >= node->count && + node->limitOption == WITH_TIES) + { + /* + * Get next tuple from subplan, if any. + */ + slot = ExecProcNode(outerPlan); + if (TupIsNull(slot)) + { + node->lstate = LIMIT_SUBPLANEOF; + return NULL; + } + /* + * Test if the new tuple and the last tuple match. + * If so we return the tuple. + */ + econtext->ecxt_innertuple = slot; + econtext->ecxt_outertuple = node->last_slot; + if (ExecQualAndReset(node->eqfunction, econtext)) + { + ExecCopySlot(node->last_slot, slot); + node->subSlot = slot; + node->position++; + } + else + { + node->lstate = LIMIT_WINDOWEND; + + /* + * If we know we won't need to back up, we can release + * resources at this point. + */ + if (!(node->ps.state->es_top_eflags & EXEC_FLAG_BACKWARD)) + (void) ExecShutdownNode(outerPlan); + + return NULL; + } - /* - * Get next tuple from subplan, if any. - */ - slot = ExecProcNode(outerPlan); - if (TupIsNull(slot)) + } + else { - node->lstate = LIMIT_SUBPLANEOF; - return NULL; + /* + * Get next tuple from subplan, if any. + */ + slot = ExecProcNode(outerPlan); + if (TupIsNull(slot)) + { + node->lstate = LIMIT_SUBPLANEOF; + return NULL; + } + if (node->limitOption == WITH_TIES) + { + ExecCopySlot(node->last_slot, slot); + } + node->subSlot = slot; + node->position++; } - node->subSlot = slot; - node->position++; } else { @@ -311,7 +359,8 @@ recompute_limits(LimitState *node) * must update the child node anyway, in case this is a rescan and the * previous time we got a different result. */ - ExecSetTupleBound(compute_tuples_needed(node), outerPlanState(node)); + if(node->limitOption == WITH_ONLY) + ExecSetTupleBound(compute_tuples_needed(node), outerPlanState(node)); } /* @@ -374,6 +423,7 @@ ExecInitLimit(Limit *node, EState *estate, int eflags) (PlanState *) limitstate); limitstate->limitCount = ExecInitExpr((Expr *) node->limitCount, (PlanState *) limitstate); + limitstate->limitOption = node->limitOption; /* * Initialize result type. @@ -390,6 +440,25 @@ ExecInitLimit(Limit *node, EState *estate, int eflags) */ limitstate->ps.ps_ProjInfo = NULL; + /* + * Initialize the equality evaluation, to detect ties. + */ + if (node->limitOption == WITH_TIES) + { + TupleDesc scanDesc; + const TupleTableSlotOps *ops; + scanDesc = limitstate->ps.ps_ResultTupleDesc; + ops = ExecGetResultSlotOps(outerPlanState(limitstate), NULL); + limitstate->last_slot = ExecInitExtraTupleSlot(estate, scanDesc, ops); + limitstate->eqfunction = + execTuplesMatchPrepare(ExecGetResultType(outerPlanState(limitstate)), + node->numCols, + node->uniqColIdx, + node->uniqOperators, + node->uniqCollations, + &limitstate->ps); + } + return limitstate; } diff --git a/src/backend/nodes/copyfuncs.c b/src/backend/nodes/copyfuncs.c index 8f51315bee..b14150ac5f 100644 --- a/src/backend/nodes/copyfuncs.c +++ b/src/backend/nodes/copyfuncs.c @@ -1143,6 +1143,11 @@ _copyLimit(const Limit *from) */ COPY_NODE_FIELD(limitOffset); COPY_NODE_FIELD(limitCount); + COPY_SCALAR_FIELD(limitOption); + COPY_SCALAR_FIELD(numCols); + COPY_POINTER_FIELD(uniqColIdx, from->numCols * sizeof(AttrNumber)); + COPY_POINTER_FIELD(uniqOperators, from->numCols * sizeof(Oid)); + COPY_POINTER_FIELD(uniqCollations, from->numCols * sizeof(Oid)); return newnode; } @@ -3033,6 +3038,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); @@ -3117,6 +3123,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 68b51f3de7..02b59aac83 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 3282be0e4b..2d2ea588d2 100644 --- a/src/backend/nodes/outfuncs.c +++ b/src/backend/nodes/outfuncs.c @@ -901,12 +901,41 @@ _outLockRows(StringInfo str, const LockRows *node) static void _outLimit(StringInfo str, const Limit *node) { + int i; WRITE_NODE_TYPE("LIMIT"); _outPlanInfo(str, (const Plan *) node); WRITE_NODE_FIELD(limitOffset); WRITE_NODE_FIELD(limitCount); + WRITE_ENUM_FIELD(limitOption, LimitOption); + WRITE_INT_FIELD(numCols); + if (node->numCols > 0) + { + appendStringInfoString(str, " :uniqColIdx"); + for (i = 0; i < node->numCols; i++) + appendStringInfo(str, " %d", node->uniqColIdx[i]); + + appendStringInfoString(str, " :uniqOperators"); + for (i = 0; i < node->numCols; i++) + appendStringInfo(str, " %u", node->uniqOperators[i]); + + appendStringInfoString(str, " :uniqCollations"); + for (i = 0; i < node->numCols; i++) + appendStringInfo(str, " %u", node->uniqOperators[i]); + } + else + { + appendStringInfoString(str, " :uniqColIdx"); + appendStringInfo(str, " NULL"); + + appendStringInfoString(str, " :uniqOperators"); + appendStringInfo(str, " NULL"); + + appendStringInfoString(str, " :uniqCollations"); + appendStringInfo(str, " NULL"); + } + } static void @@ -2699,6 +2728,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); @@ -2909,6 +2939,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 3b96492b36..6d65ba8d59 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); @@ -2333,6 +2334,11 @@ _readLimit(void) READ_NODE_FIELD(limitOffset); READ_NODE_FIELD(limitCount); + READ_ENUM_FIELD(limitOption, LimitOption); + READ_INT_FIELD(numCols); + READ_ATTRNUMBER_ARRAY(uniqColIdx, local_node->numCols); + READ_OID_ARRAY(uniqOperators, local_node->numCols); + READ_OID_ARRAY(uniqCollations, local_node->numCols); READ_DONE(); } diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c index cc222cb06c..7b087fd228 100644 --- a/src/backend/optimizer/plan/createplan.c +++ b/src/backend/optimizer/plan/createplan.c @@ -2201,7 +2201,9 @@ create_minmaxagg_plan(PlannerInfo *root, MinMaxAggPath *best_path) plan = (Plan *) make_limit(plan, subparse->limitOffset, - subparse->limitCount); + subparse->limitCount, + subparse->limitOption, + 0, NULL, NULL, NULL); /* Must apply correct cost/width data to Limit node */ plan->startup_cost = mminfo->path->startup_cost; @@ -2508,13 +2510,43 @@ create_limit_plan(PlannerInfo *root, LimitPath *best_path, int flags) { Limit *plan; Plan *subplan; + int numsortkeys = 0; + AttrNumber *sortColIdx = NULL; + Oid *sortOperators = NULL; + Oid *sortCollations = NULL; /* Limit doesn't project, so tlist requirements pass through */ subplan = create_plan_recurse(root, best_path->subpath, flags); + if (best_path->limitOption == WITH_TIES) + { + Query *parse = root->parse; + ListCell *l; + + numsortkeys = list_length(parse->sortClause); + sortColIdx = (AttrNumber *) palloc(numsortkeys * sizeof(AttrNumber)); + sortOperators = (Oid *) palloc(numsortkeys * sizeof(Oid)); + sortCollations = (Oid *) palloc(numsortkeys * sizeof(Oid)); + + numsortkeys = 0; + foreach(l, parse->sortClause) + { + SortGroupClause *sortcl = (SortGroupClause *) lfirst(l); + TargetEntry *tle = get_sortgroupclause_tle(sortcl, parse->targetList); + + sortColIdx[numsortkeys] = tle->resno; + sortOperators[numsortkeys] = sortcl->eqop; + sortCollations[numsortkeys] = exprCollation((Node *) tle->expr); + numsortkeys++; + } + + } + plan = make_limit(subplan, best_path->limitOffset, - best_path->limitCount); + best_path->limitCount, + best_path->limitOption, + numsortkeys, sortColIdx, sortOperators, sortCollations); copy_generic_path_info(&plan->plan, (Path *) best_path); @@ -6399,7 +6431,8 @@ 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, LimitOption limitOption, + int ordNumCols, AttrNumber *ordColIdx, Oid *ordOperators, Oid *ordCollations) { Limit *node = makeNode(Limit); Plan *plan = &node->plan; @@ -6411,6 +6444,11 @@ make_limit(Plan *lefttree, Node *limitOffset, Node *limitCount) node->limitOffset = limitOffset; node->limitCount = limitCount; + node->limitOption = limitOption; + node->numCols = ordNumCols; + node->uniqColIdx = ordColIdx; + node->uniqOperators = ordOperators; + node->uniqCollations = ordCollations; return node; } diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c index 031e709718..326f6e77d7 100644 --- a/src/backend/optimizer/plan/planner.c +++ b/src/backend/optimizer/plan/planner.c @@ -2173,6 +2173,7 @@ grouping_planner(PlannerInfo *root, bool inheritance_update, path = (Path *) create_limit_path(root, final_rel, path, parse->limitOffset, parse->limitCount, + parse->limitOption, offset_est, count_est); } diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c index 56de8fc370..5bc5924f7a 100644 --- a/src/backend/optimizer/util/pathnode.c +++ b/src/backend/optimizer/util/pathnode.c @@ -3554,6 +3554,7 @@ LimitPath * create_limit_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, Node *limitOffset, Node *limitCount, + LimitOption limitOption, int64 offset_est, int64 count_est) { LimitPath *pathnode = makeNode(LimitPath); @@ -3575,6 +3576,7 @@ create_limit_path(PlannerInfo *root, RelOptInfo *rel, pathnode->subpath = subpath; pathnode->limitOffset = limitOffset; pathnode->limitCount = limitCount; + pathnode->limitOption = limitOption; /* * Adjust the output rows count and costs according to the offset/limit. @@ -3616,6 +3618,20 @@ create_limit_path(PlannerInfo *root, RelOptInfo *rel, count_rows = (double) count_est; else count_rows = clamp_row_est(subpath->rows * 0.10); + if (limitOption == WITH_TIES) + { + double numGroups; + double avgGroupSize; + List *groupExprs; + + groupExprs = get_sortgrouplist_exprs(root->parse->sortClause, + root->parse->targetList); + + numGroups = estimate_num_groups(root, groupExprs, subpath->rows, + NULL); + avgGroupSize = subpath->rows / numGroups; + count_rows = Max(avgGroupSize, count_est + (avgGroupSize/2)); + } if (count_rows > pathnode->path.rows) count_rows = pathnode->path.rows; if (subpath->rows > 0) diff --git a/src/backend/parser/analyze.c b/src/backend/parser/analyze.c index 400558b552..1d9bf30e20 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 01521789e8..de6d2c3267 100644 --- a/src/backend/parser/gram.y +++ b/src/backend/parser/gram.y @@ -165,6 +165,7 @@ static List *makeOrderedSetArgs(List *directargs, List *orderedargs, static void insertSelectOptions(SelectStmt *stmt, List *sortClause, List *lockingClause, Node *limitOffset, Node *limitCount, + void *limitOption, WithClause *withClause, core_yyscan_t yyscanner); static Node *makeSetOp(SetOperation op, bool all, Node *larg, Node *rarg); @@ -393,7 +394,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 + reloption_list group_clause TriggerFuncArgs select_limit limit_clause opt_select_limit opclass_item_list opclass_drop_list opclass_purpose opt_opfamily transaction_mode_list_or_empty OptTableFuncElementList TableFuncElementList opt_type_modifiers @@ -455,7 +456,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 fetch_args limit_clause select_limit_value +%type fetch_args select_limit_value offset_clause select_offset_value select_fetch_first_value I_or_F_const %type row_or_rows first_or_next @@ -11209,7 +11210,7 @@ select_no_parens: | select_clause sort_clause { insertSelectOptions((SelectStmt *) $1, $2, NIL, - NULL, NULL, NULL, + NULL, NULL, NULL, NULL, yyscanner); $$ = $1; } @@ -11217,6 +11218,7 @@ select_no_parens: { insertSelectOptions((SelectStmt *) $1, $2, $3, list_nth($4, 0), list_nth($4, 1), + (list_nth($4, 2)), NULL, yyscanner); $$ = $1; @@ -11225,6 +11227,7 @@ select_no_parens: { insertSelectOptions((SelectStmt *) $1, $2, $4, list_nth($3, 0), list_nth($3, 1), + (list_nth($3, 2)), NULL, yyscanner); $$ = $1; @@ -11233,7 +11236,7 @@ select_no_parens: { insertSelectOptions((SelectStmt *) $2, NULL, NIL, NULL, NULL, - $1, + NULL,$1, yyscanner); $$ = $2; } @@ -11241,7 +11244,7 @@ select_no_parens: { insertSelectOptions((SelectStmt *) $2, $3, NIL, NULL, NULL, - $1, + NULL,$1, yyscanner); $$ = $2; } @@ -11249,6 +11252,7 @@ select_no_parens: { insertSelectOptions((SelectStmt *) $2, $3, $4, list_nth($5, 0), list_nth($5, 1), + list_nth($5, 2), $1, yyscanner); $$ = $2; @@ -11257,6 +11261,7 @@ select_no_parens: { insertSelectOptions((SelectStmt *) $2, $3, $5, list_nth($4, 0), list_nth($4, 1), + list_nth($4, 2), $1, yyscanner); $$ = $2; @@ -11550,20 +11555,20 @@ 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 { $$ = list_make3($2, list_nth($1, 0), list_nth($1, 1)); } + | offset_clause limit_clause { $$ = list_make3($1, list_nth($2, 0), list_nth($2, 1)); } + | limit_clause { $$ = list_make3(NULL, list_nth($1, 0), list_nth($1, 1)); } + | offset_clause { $$ = list_make3($1, NULL, NULL); } ; opt_select_limit: select_limit { $$ = $1; } - | /* EMPTY */ { $$ = list_make2(NULL,NULL); } + | /* EMPTY */ { $$ = list_make3(NULL, NULL, NULL); } ; limit_clause: LIMIT select_limit_value - { $$ = $2; } + { $$ = list_make2($2, NULL); } | LIMIT select_limit_value ',' select_offset_value { /* Disabled because it was too confusing, bjm 2002-02-18 */ @@ -11581,9 +11586,11 @@ 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; } + { $$ = list_make2($3, makeString("WITH_ONLY")); } + | FETCH first_or_next select_fetch_first_value row_or_rows WITH TIES + { $$ = list_make2($3, makeString("WITH_TIES")); } | FETCH first_or_next row_or_rows ONLY - { $$ = makeIntConst(1, -1); } + { $$ = list_make2(makeIntConst(1, -1), NULL); } ; offset_clause: @@ -15840,6 +15847,7 @@ static void insertSelectOptions(SelectStmt *stmt, List *sortClause, List *lockingClause, Node *limitOffset, Node *limitCount, + void *limitOption, WithClause *withClause, core_yyscan_t yyscanner) { @@ -15878,6 +15886,21 @@ insertSelectOptions(SelectStmt *stmt, parser_errposition(exprLocation(limitCount)))); stmt->limitCount = limitCount; } + if (limitOption) + { + if (stmt->limitOption) + ereport(ERROR, + (errcode(ERRCODE_SYNTAX_ERROR), + errmsg("multiple limit options not allowed"))); + if (!stmt->sortClause && strcmp(strVal(limitOption), "WITH_TIES") == 0) + ereport(ERROR, + (errcode(ERRCODE_SYNTAX_ERROR), + errmsg("WITH TIES options can not be specified without ORDER BY clause"))); + if (strcmp(strVal(limitOption), "WITH_ONLY") == 0) + stmt->limitOption = WITH_ONLY; + else + stmt->limitOption = WITH_TIES; + } if (withClause) { if (stmt->withClause) diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h index dbd7ed0363..d469c1364e 100644 --- a/src/include/nodes/execnodes.h +++ b/src/include/nodes/execnodes.h @@ -2294,12 +2294,15 @@ typedef struct LimitState PlanState ps; /* its first field is NodeTag */ ExprState *limitOffset; /* OFFSET parameter, or NULL if none */ ExprState *limitCount; /* COUNT parameter, or NULL if none */ + LimitOption limitOption; /* limit specification type */ int64 offset; /* current OFFSET value */ int64 count; /* current COUNT, if any */ bool noCount; /* if true, ignore count */ LimitStateCond lstate; /* state machine status, as above */ int64 position; /* 1-based index of last tuple returned */ TupleTableSlot *subSlot; /* tuple last obtained from subplan */ + ExprState *eqfunction; /* tuple equality qual in case of WITH TIES option */ + TupleTableSlot *last_slot; /* slot for evaluation of ties */ } LimitState; #endif /* EXECNODES_H */ diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.h index ffb4cd4bcc..e5f72188f5 100644 --- a/src/include/nodes/nodes.h +++ b/src/include/nodes/nodes.h @@ -821,4 +821,16 @@ 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 +{ + WITH_ONLY, /* FETCH FIRST... ONLY */ + 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 94c0b7a9dd..4b7357910f 100644 --- a/src/include/nodes/parsenodes.h +++ b/src/include/nodes/parsenodes.h @@ -159,6 +159,7 @@ typedef struct Query Node *limitOffset; /* # of result tuples to skip (int8 expr) */ Node *limitCount; /* # of result tuples to return (int8 expr) */ + LimitOption limitOption; /* limit type [WITH TIES | WITH ONLY] */ 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 88c8973f3c..a88781122a 100644 --- a/src/include/nodes/pathnodes.h +++ b/src/include/nodes/pathnodes.h @@ -1785,6 +1785,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 */ + LimitOption limitOption; /* FETCH FIRST with ties or exact number */ } LimitPath; diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h index 24740c31e3..ff61e057a2 100644 --- a/src/include/nodes/plannodes.h +++ b/src/include/nodes/plannodes.h @@ -953,6 +953,11 @@ typedef struct Limit Plan plan; Node *limitOffset; /* OFFSET parameter, or NULL if none */ Node *limitCount; /* COUNT parameter, or NULL if none */ + LimitOption limitOption; /* fetch first with ties or exact number */ + int numCols; /* number of columns to check for Similarity */ + AttrNumber *uniqColIdx; /* their indexes in the target list */ + Oid *uniqOperators; /* equality operators to compare with */ + Oid *uniqCollations; /* collations for equality comparisons */ } Limit; diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h index 9e79e1cd63..33838952d0 100644 --- a/src/include/optimizer/pathnode.h +++ b/src/include/optimizer/pathnode.h @@ -264,6 +264,7 @@ extern ModifyTablePath *create_modifytable_path(PlannerInfo *root, extern LimitPath *create_limit_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, Node *limitOffset, Node *limitCount, + LimitOption limitOption, int64 offset_est, int64 count_est); extern Path *reparameterize_path(PlannerInfo *root, Path *path, diff --git a/src/include/optimizer/planmain.h b/src/include/optimizer/planmain.h index 6d10bf3ee8..52d86bd6fb 100644 --- a/src/include/optimizer/planmain.h +++ b/src/include/optimizer/planmain.h @@ -56,7 +56,8 @@ 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, + LimitOption limitOption,int ordNumCols, AttrNumber *ordColIdx, Oid *ordOperators, Oid *ordCollations); /* * prototypes for plan/initsplan.c diff --git a/src/test/regress/expected/limit.out b/src/test/regress/expected/limit.out index c18f547cbd..199725ec7f 100644 --- a/src/test/regress/expected/limit.out +++ b/src/test/regress/expected/limit.out @@ -503,3 +503,38 @@ 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 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..8009b746cb 100644 --- a/src/test/regress/sql/limit.sql +++ b/src/test/regress/sql/limit.sql @@ -141,3 +141,20 @@ 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 2 ROW ONLY; +-- should fail +SELECT ''::text AS two, unique1, unique2, stringu1 + FROM onek WHERE unique1 > 50 + FETCH FIRST 2 ROW WITH TIES; -- 2.20.1 --WIyZ46R2i8wDzkSu Content-Type: text/plain; charset=us-ascii Content-Disposition: attachment; filename="0002-fixes-and-comments.patch" From 93671bd11f03367c9a0adaefb6d992de3bfde57a Mon Sep 17 00:00:00 2001 From: Tomas Vondra Date: Sun, 31 Mar 2019 00:48:37 +0100 Subject: [PATCH 2/2] fixes and comments --- doc/src/sgml/ref/select.sgml | 6 +++--- src/backend/executor/nodeLimit.c | 24 ++++++++++++++---------- src/backend/nodes/outfuncs.c | 29 +++-------------------------- src/include/nodes/parsenodes.h | 2 +- src/include/optimizer/planmain.h | 2 +- 5 files changed, 22 insertions(+), 41 deletions(-) diff --git a/doc/src/sgml/ref/select.sgml b/doc/src/sgml/ref/select.sgml index b3b045ea87..e83d309c5b 100644 --- a/doc/src/sgml/ref/select.sgml +++ b/doc/src/sgml/ref/select.sgml @@ -44,7 +44,7 @@ SELECT [ ALL | DISTINCT [ ON ( expressionexpression [ ASC | DESC | USING operator ] [ NULLS { FIRST | LAST } ] [, ...] ] [ LIMIT { count | ALL } ] [ OFFSET start [ ROW | ROWS ] ] - [ FETCH { FIRST | NEXT } [ count ] { ROW | ROWS } [ ONLY | WITH TIES ] ] + [ FETCH { FIRST | NEXT } [ count ] { ROW | ROWS } { ONLY | WITH TIES } ] [ FOR { UPDATE | NO KEY UPDATE | SHARE | KEY SHARE } [ OF table_name [, ...] ] [ NOWAIT | SKIP LOCKED ] [...] ] where from_item can be one of: @@ -1430,7 +1430,7 @@ OFFSET start which PostgreSQL also supports. It is: OFFSET start { ROW | ROWS } -FETCH { FIRST | NEXT } [ count ] { ROW | ROWS } [ ONLY | WITH TIES ] +FETCH { FIRST | NEXT } [ count ] { ROW | ROWS } { ONLY | WITH TIES } In this syntax, the start or count value is required by @@ -1442,7 +1442,7 @@ FETCH { FIRST | NEXT } [ count ] { omitted in a FETCH clause, it defaults to 1. ROW . WITH TIES option is used to return two or more rows - that tie for last place in the limit results set according to ORDER BY + that tie for the last place in the result set according to ORDER BY clause (ORDER BY clause must be specified in this case). and ROWS as well as FIRST and NEXT are noise words that don't influence diff --git a/src/backend/executor/nodeLimit.c b/src/backend/executor/nodeLimit.c index e8aed10177..68ade28c75 100644 --- a/src/backend/executor/nodeLimit.c +++ b/src/backend/executor/nodeLimit.c @@ -127,9 +127,12 @@ ExecLimit(PlanState *pstate) { /* * Forwards scan, so check for stepping off end of window. If - * we are at the end of the window, return NULL without - * advancing the subplan or the position variable; but change - * the state machine state to record having done so. + * we are at the end of the window, the behavior depends whether + * ONLY or WITH TIES was specified. In case of ONLY, we return + * NULL without advancing the subplan or the position variable; + * but change the state machine state to record having done so. + * In the WITH TIES mode, we need to advance the subplan until + * we find the first row with different ORDER BY pathkeys. */ if (!node->noCount && node->position - node->offset >= node->count && @@ -159,6 +162,7 @@ ExecLimit(PlanState *pstate) node->lstate = LIMIT_SUBPLANEOF; return NULL; } + /* * Test if the new tuple and the last tuple match. * If so we return the tuple. @@ -176,9 +180,9 @@ ExecLimit(PlanState *pstate) node->lstate = LIMIT_WINDOWEND; /* - * If we know we won't need to back up, we can release - * resources at this point. - */ + * If we know we won't need to back up, we can release + * resources at this point. + */ if (!(node->ps.state->es_top_eflags & EXEC_FLAG_BACKWARD)) (void) ExecShutdownNode(outerPlan); @@ -197,12 +201,12 @@ ExecLimit(PlanState *pstate) node->lstate = LIMIT_SUBPLANEOF; return NULL; } - if (node->limitOption == WITH_TIES) - { - ExecCopySlot(node->last_slot, slot); - } node->subSlot = slot; node->position++; + + /* XXX We probably only need to do this for the last tuple in the regular window, no? */ + if (node->limitOption == WITH_TIES) + ExecCopySlot(node->last_slot, slot); } } else diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c index 2d2ea588d2..6c1d9e4c25 100644 --- a/src/backend/nodes/outfuncs.c +++ b/src/backend/nodes/outfuncs.c @@ -910,32 +910,9 @@ _outLimit(StringInfo str, const Limit *node) WRITE_NODE_FIELD(limitCount); WRITE_ENUM_FIELD(limitOption, LimitOption); WRITE_INT_FIELD(numCols); - if (node->numCols > 0) - { - appendStringInfoString(str, " :uniqColIdx"); - for (i = 0; i < node->numCols; i++) - appendStringInfo(str, " %d", node->uniqColIdx[i]); - - appendStringInfoString(str, " :uniqOperators"); - for (i = 0; i < node->numCols; i++) - appendStringInfo(str, " %u", node->uniqOperators[i]); - - appendStringInfoString(str, " :uniqCollations"); - for (i = 0; i < node->numCols; i++) - appendStringInfo(str, " %u", node->uniqOperators[i]); - } - else - { - appendStringInfoString(str, " :uniqColIdx"); - appendStringInfo(str, " NULL"); - - appendStringInfoString(str, " :uniqOperators"); - appendStringInfo(str, " NULL"); - - appendStringInfoString(str, " :uniqCollations"); - appendStringInfo(str, " NULL"); - } - + WRITE_ATTRNUMBER_ARRAY(uniqColIdx, node->numCols); + WRITE_OID_ARRAY(uniqOperators, node->numCols); + WRITE_OID_ARRAY(uniqCollations, node->numCols); } static void diff --git a/src/include/nodes/parsenodes.h b/src/include/nodes/parsenodes.h index 4b7357910f..40b9f2eeb8 100644 --- a/src/include/nodes/parsenodes.h +++ b/src/include/nodes/parsenodes.h @@ -159,7 +159,7 @@ typedef struct Query Node *limitOffset; /* # of result tuples to skip (int8 expr) */ Node *limitCount; /* # of result tuples to return (int8 expr) */ - LimitOption limitOption; /* limit type [WITH TIES | WITH ONLY] */ + LimitOption limitOption; /* limit type {ONLY | WITH TIES} */ List *rowMarks; /* a list of RowMarkClause's */ diff --git a/src/include/optimizer/planmain.h b/src/include/optimizer/planmain.h index 52d86bd6fb..924f82ab25 100644 --- a/src/include/optimizer/planmain.h +++ b/src/include/optimizer/planmain.h @@ -57,7 +57,7 @@ extern Agg *make_agg(List *tlist, List *qual, List *groupingSets, List *chain, double dNumGroups, Plan *lefttree); extern Limit *make_limit(Plan *lefttree, Node *limitOffset, Node *limitCount, - LimitOption limitOption,int ordNumCols, AttrNumber *ordColIdx, Oid *ordOperators, Oid *ordCollations); + LimitOption limitOption, int ordNumCols, AttrNumber *ordColIdx, Oid *ordOperators, Oid *ordCollations); /* * prototypes for plan/initsplan.c -- 2.20.1 --WIyZ46R2i8wDzkSu--