Re: [PATCH] Incremental sort (was: PoC: Partial sort) - Mailing list pgsql-hackers

On Tue, Mar 24, 2020 at 8:23 PM James Coleman <jtc331@gmail.com> wrote:
> While working on finding a test case to show rescan isn't implemented
> properly yet, I came across a bug. At the top of
> ExecInitIncrementalSort, we assert that eflags does not contain
> EXEC_FLAG_REWIND. But the following query (with merge and hash joins
> disabled) breaks that assertion:
>
> select * from t join (select * from t order by a, b) s on s.a = t.a
> where t.a in (1,2);
>
> The comments about this flag in src/include/executor/executor.h say:
>
> * REWIND indicates that the plan node should try to efficiently support
> * rescans without parameter changes. (Nodes must support ExecReScan calls
> * in any case, but if this flag was not given, they are at liberty to do it
> * through complete recalculation. Note that a parameter change forces a
> * full recalculation in any case.)
>
> Now we know that except in rare cases (as just discussed recently up
> thread) we can't implement rescan efficiently.
>
> So is this a planner bug (i.e., should we try not to generate
> incremental sort plans that require efficient rewind)? Or can we just
> remove that part of the assertion and know that we'll implement the
> rescan, albeit inefficiently? We already explicitly declare that we
> don't support backwards scanning, but I don't see a way to declare the
> same for rewind.

Other nodes seem to get a materialization node placed above them to
support this case "better". Is that something we should be doing?

> I'm going to try the latter approach now to see if it at least solves
> the immediate problem...

So a couple of interesting results here. First, it does seem to fix
the assertion failure, and rescan is being used in this case (as I
expected).

The plans have a bit of a weird shape, at least in my mind. First, to
get the incremental sort on the right side of the join I had to:
set enable_mergejoin = off;
set enable_hashjoin = off;
and got this plan:

 Gather  (cost=1000.47..108541.96 rows=2 width=16)
   Workers Planned: 2
   ->  Nested Loop  (cost=0.47..107541.76 rows=1 width=16)
         Join Filter: (t.a = t_1.a)
         ->  Parallel Seq Scan on t  (cost=0.00..9633.33 rows=1 width=8)
               Filter: (a = ANY ('{1,2}'::integer[]))
         ->  Incremental Sort  (cost=0.47..75408.43 rows=1000000 width=8)
               Sort Key: t_1.a, t_1.b
               Presorted Key: t_1.a
               ->  Index Scan using idx_t_a on t t_1
(cost=0.42..30408.42 rows=1000000 width=8)

To get rid of the parallelism but keep the same basic plan shape I had
to further:
set enable_seqscan = off;
set enable_material = off;
and got this plan:

 Nested Loop  (cost=0.89..195829.74 rows=2 width=16)
   Join Filter: (t.a = t_1.a)
   ->  Index Scan using idx_t_a on t  (cost=0.42..12.88 rows=2 width=8)
         Index Cond: (a = ANY ('{1,2}'::integer[]))
   ->  Incremental Sort  (cost=0.47..75408.43 rows=1000000 width=8)
         Sort Key: t_1.a, t_1.b
         Presorted Key: t_1.a
         ->  Index Scan using idx_t_a on t t_1  (cost=0.42..30408.42
rows=1000000 width=8)

Two observations:
1. Ideally the planner would have realized that the join condition can
be safely pushed down into both index scans. I was surprised this
didn't happen, but...maybe that's just not supported?

2. Ideally the nested loop node would have the smarts to know that the
right child is ordered, and therefore it can stop pulling nodes from
it as soon as it stops matching the join condition for each iteration
in the loop. I'm less surprised this isn't supported; it seems like a
fairly advanced optimization (OTOH it is the kind of interesting
optimization incremental sort opens up in more cases.

I don't *think* either of these are issues with the patch, but wanted
to mention them in case it piqued someone's curiosity or in case it
actually is a bug [in our patch or otherwise].

James