Re: [HACKERS] [PATCH] Incremental sort

On Wed, Nov 22, 2017 at 1:22 PM, Antonin Houska <ah@cybertec.at> wrote:

> Alexander Korotkov <a.korotkov@postgrespro.ru> wrote:
>
> > Antonin Houska <ah@cybertec.at> wrote:
>
> > >  * ExecIncrementalSort()
> > >
> > >  ** if (node->tuplesortstate == NULL)
> > >
> > >  If both branches contain the expression
> > >
> > >  node->groupsCount++;
> > >
> > >  I suggest it to be moved outside the "if" construct.
> >
> > Done.
>
> One more comment on this: I wonder if the field isn't incremented too
> early. It seems to me that the value can end up non-zero if the input set
> is
> to be empty (not sure if it can happen in practice).
>

That happens in practice.  On empty input set, incremental sort would count
exactly one group.

# create table t (x int, y int);
CREATE TABLE
# create index t_x_idx on t (x);
CREATE INDEX
# set enable_seqscan = off;
SET
# explain (analyze, buffers) select * from t order by x, y;
                                                     QUERY PLAN
---------------------------------------------------------------------------------------------------------------------
 Incremental Sort  (cost=0.74..161.14 rows=2260 width=8) (actual
time=0.024..0.024 rows=0 loops=1)
   Sort Key: x, y
   Presorted Key: x
   Sort Method: quicksort  Memory: 25kB
   Sort Groups: 1
   Buffers: shared hit=1
   ->  Index Scan using t_x_idx on t  (cost=0.15..78.06 rows=2260 width=8)
(actual time=0.011..0.011 rows=0 loops=1)
         Buffers: shared hit=1
 Planning time: 0.088 ms
 Execution time: 0.066 ms
(10 rows)

But from prospective of how code works, it's really 1 group.  Tuple sort
was defined, inserted no tuples, then sorted and got no tuples out of
there.  So, I'm not sure if it's really incorrect...

And finally one question about regression tests: what's the purpose of the
> changes in contrib/postgres_fdw/sql/postgres_fdw.sql ? I see no
> IncrementalSort node in the output.


But there is IncrementalSort node on the remote side.
Let's see what happens.  Idea of "CROSS JOIN, not pushed down" test is that
cross join with ORDER BY LIMIT is not beneficial to push down, because
LIMIT is not pushed down and remote side wouldn't be able to use top-N
heapsort.  But if remote side has incremental sort then it can be used, and
fetching first 110 rows is cheap.  Let's see plan of original "CROSS JOIN,
not pushed down" test with incremental sort.

# EXPLAIN (ANALYZE, VERBOSE) SELECT t1.c3, t2.c3 FROM ft1 t1 CROSS JOIN ft2
t2 ORDER BY t1.c1, t2.c1 OFFSET 100 LIMIT 10;

       QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=160.32..161.31 rows=10 width=46) (actual time=1.918..1.921
rows=10 loops=1)
   Output: t1.c3, t2.c3, t1.c1, t2.c1
   ->  Foreign Scan  (cost=150.47..66711.06 rows=675684 width=46) (actual
time=1.684..1.911 rows=110 loops=1)
         Output: t1.c3, t2.c3, t1.c1, t2.c1
         Relations: (public.ft1 t1) INNER JOIN (public.ft2 t2)
         Remote SQL: SELECT r1.c3, r1."C 1", r2.c3, r2."C 1" FROM ("S 1"."T
1" r1 INNER JOIN "S 1"."T 1" r2 ON (TRUE)) ORDER BY r1."C 1" ASC NULLS
LAST, r2."C 1" ASC NULLS LAST
 Planning time: 1.370 ms
 Execution time: 2.068 ms
(8 rows)

And "remote SQL" has following execution plan.  This is plan of full
execution while FDW is fetching only first 110 rows out of there.

# EXPLAIN ANALYZE SELECT r1.c3, r1."C 1", r2.c3, r2."C 1" FROM ("S 1"."T 1"
r1 INNER JOIN "S 1"."T 1" r2 ON (TRUE)) ORDER BY r1."C 1" ASC NULLS LAST,
r2."C 1" ASC NULLS LAST;
                                                             QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------
 Incremental Sort  (cost=50.47..53097.38 rows=675684 width=34) (actual
time=1.883..747.694 rows=675684 loops=1)
   Sort Key: r1."C 1", r2."C 1"
   Presorted Key: r1."C 1"
   Sort Method: quicksort  Memory: 114kB
   Sort Groups: 822
   ->  Nested Loop  (cost=0.28..8543.25 rows=675684 width=34) (actual
time=0.027..144.070 rows=675684 loops=1)
         ->  Index Scan using t1_pkey on "T 1" r1  (cost=0.28..73.93
rows=822 width=17) (actual time=0.015..0.537 rows=822 loops=1)
         ->  Materialize  (cost=0.00..25.33 rows=822 width=17) (actual
time=0.000..0.053 rows=822 loops=822)
               ->  Seq Scan on "T 1" r2  (cost=0.00..21.22 rows=822
width=17) (actual time=0.007..0.257 rows=822 loops=1)
 Planning time: 0.109 ms
 Execution time: 785.400 ms
(11 rows)

Thus, with incremental sort this test doesn't do what it was designed to
do.  Changing ORDER BY from t1.c1, t2.c1 to t1.c3, t2.c3 fixes this
problem, because there is no index on c3.  Query and result are slightly
different, but it serves original design.

Please, find rebased patch attached.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company