Re: BUG #16846: "retrieved too many tuples in a bounded sort" - Mailing list pgsql-bugs

James Coleman <jtc331@gmail.com> writes:
> I didn't see this thread until now (unfortunately I'm not able to
> consistently keep up with mailing list traffic, though I'm happy to be
> tagged on any incremental sort issue so I see that discussion). I
> reviewed the patch, and I believe it's correct.

Thanks for looking.

> I did have to stare a bit at nodeIncrementalSort.c for a while though
> to realize that the test case works because the full sort state was
> bounded (so 5 tuples is enough to trigger the case even though a
> cursory reading of the code and the bug description would imply that
> 64 tuples are needed to trigger it). So I have a mild preference for
> noting that in the test case comment, and I also lean towards having
> an EXPLAIN on the test case query to make sure it remains a valid test
> case in the future (i.e., making sure other changes don't change plan
> such that this case no longer has regression coverage.)

No objection to doing that, however ...

> We can simplify the code a bit so that lastTuple is only set to true
> when necessary, rather than setting it only to unset it in this case.

I stared at this for awhile and eventually convinced myself that it
implemented the same logic, but it still seems overly complex.  We
do not need either the firstTuple or lastTuple flags, and we could
convert the nTuple adjustments into a normal for-loop with (IMO)
much greater intelligibility.  What do you think of the attached?

            regards, tom lane

diff --git a/src/backend/executor/nodeIncrementalSort.c b/src/backend/executor/nodeIncrementalSort.c
index 82fa800cb1..459c879f0b 100644
--- a/src/backend/executor/nodeIncrementalSort.c
+++ b/src/backend/executor/nodeIncrementalSort.c
@@ -288,9 +288,7 @@ switchToPresortedPrefixMode(PlanState *pstate)
 {
     IncrementalSortState *node = castNode(IncrementalSortState, pstate);
     ScanDirection dir;
-    int64        nTuples = 0;
-    bool        lastTuple = false;
-    bool        firstTuple = true;
+    int64        nTuples;
     TupleDesc    tupDesc;
     PlanState  *outerNode;
     IncrementalSort *plannode = castNode(IncrementalSort, node->ss.ps.plan);
@@ -343,20 +341,16 @@ switchToPresortedPrefixMode(PlanState *pstate)
      * Copy as many tuples as we can (i.e., in the same prefix key group) from
      * the full sort state to the prefix sort state.
      */
-    for (;;)
+    for (nTuples = 0; nTuples < node->n_fullsort_remaining; nTuples++)
     {
-        lastTuple = node->n_fullsort_remaining - nTuples == 1;
-
         /*
          * When we encounter multiple prefix key groups inside the full sort
          * tuplesort we have to carry over the last read tuple into the next
          * batch.
          */
-        if (firstTuple && !TupIsNull(node->transfer_tuple))
+        if (nTuples == 0 && !TupIsNull(node->transfer_tuple))
         {
             tuplesort_puttupleslot(node->prefixsort_state, node->transfer_tuple);
-            nTuples++;
-
             /* The carried over tuple is our new group pivot tuple. */
             ExecCopySlot(node->group_pivot, node->transfer_tuple);
         }
@@ -376,7 +370,6 @@ switchToPresortedPrefixMode(PlanState *pstate)
             if (isCurrentGroup(node, node->group_pivot, node->transfer_tuple))
             {
                 tuplesort_puttupleslot(node->prefixsort_state, node->transfer_tuple);
-                nTuples++;
             }
             else
             {
@@ -395,27 +388,10 @@ switchToPresortedPrefixMode(PlanState *pstate)
                  */
                 ExecClearTuple(node->group_pivot);

-                /*
-                 * Also make sure we take the didn't-consume-all-the-tuples
-                 * path below, even if this happened to be the last tuple of
-                 * the batch.
-                 */
-                lastTuple = false;
+                /* Break out of for-loop early */
                 break;
             }
         }
-
-        firstTuple = false;
-
-        /*
-         * If we've copied all of the tuples from the full sort state into the
-         * prefix sort state, then we don't actually know that we've yet found
-         * the last tuple in that prefix key group until we check the next
-         * tuple from the outer plan node, so we retain the current group
-         * pivot tuple prefix key group comparison.
-         */
-        if (lastTuple)
-            break;
     }

     /*
@@ -428,14 +404,15 @@ switchToPresortedPrefixMode(PlanState *pstate)
     node->n_fullsort_remaining -= nTuples;
     SO1_printf("Setting n_fullsort_remaining to " INT64_FORMAT "\n", node->n_fullsort_remaining);

-    if (lastTuple)
+    if (node->n_fullsort_remaining == 0)
     {
         /*
-         * We've confirmed that all tuples remaining in the full sort batch is
-         * in the same prefix key group and moved all of those tuples into the
-         * presorted prefix tuplesort. Now we can save our pivot comparison
-         * tuple and continue fetching tuples from the outer execution node to
-         * load into the presorted prefix tuplesort.
+         * We've found that all tuples remaining in the full sort batch are in
+         * the same prefix key group and moved all of those tuples into the
+         * presorted prefix tuplesort.  We don't know that we've yet found the
+         * last tuple in the current prefix key group, so save our pivot
+         * comparison tuple and continue fetching tuples from the outer
+         * execution node to load into the presorted prefix tuplesort.
          */
         ExecCopySlot(node->group_pivot, node->transfer_tuple);
         SO_printf("Setting execution_status to INCSORT_LOADPREFIXSORT (switchToPresortedPrefixMode)\n");
diff --git a/src/test/regress/expected/incremental_sort.out b/src/test/regress/expected/incremental_sort.out
index d574583844..68ca321163 100644
--- a/src/test/regress/expected/incremental_sort.out
+++ b/src/test/regress/expected/incremental_sort.out
@@ -676,6 +676,21 @@ select * from (select * from t order by a) s order by a, b limit 70;
 (70 rows)

 -- Checks case where we hit a group boundary at the last tuple of a batch.
+-- Because the full sort state is bounded, we scan 64 tuples (the mode
+-- transition point) but only retain 5. Thus when we transition modes, all
+-- tuples in the full sort state have different prefix keys.
+explain (costs off) select * from (select * from t order by a) s order by a, b limit 5;
+           QUERY PLAN
+---------------------------------
+ Limit
+   ->  Incremental Sort
+         Sort Key: t.a, t.b
+         Presorted Key: t.a
+         ->  Sort
+               Sort Key: t.a
+               ->  Seq Scan on t
+(7 rows)
+
 select * from (select * from t order by a) s order by a, b limit 5;
  a | b
 ---+---
diff --git a/src/test/regress/sql/incremental_sort.sql b/src/test/regress/sql/incremental_sort.sql
index 9965fcd777..81429164d4 100644
--- a/src/test/regress/sql/incremental_sort.sql
+++ b/src/test/regress/sql/incremental_sort.sql
@@ -150,6 +150,10 @@ analyze t;
 explain (costs off) select * from (select * from t order by a) s order by a, b limit 70;
 select * from (select * from t order by a) s order by a, b limit 70;
 -- Checks case where we hit a group boundary at the last tuple of a batch.
+-- Because the full sort state is bounded, we scan 64 tuples (the mode
+-- transition point) but only retain 5. Thus when we transition modes, all
+-- tuples in the full sort state have different prefix keys.
+explain (costs off) select * from (select * from t order by a) s order by a, b limit 5;
 select * from (select * from t order by a) s order by a, b limit 5;

 -- Test rescan.