Re: [HACKERS] [PATCH] Incremental sort

Alexander Korotkov <a(dot)korotkov(at)postgrespro(dot)ru> wrote:

> On Wed, Nov 22, 2017 at 1:22 PM, Antonin Houska <ah(at)cybertec(dot)at> wrote:
>
> Alexander Korotkov <a(dot)korotkov(at)postgrespro(dot)ru> wrote:
>
> > Antonin Houska <ah(at)cybertec(dot)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...

I expected the number of groups actually that actually appear in the output,
you consider it the number of groups started. I can't find similar case
elsewhere in the code (e.g. Agg node does not report this kind of
information), so I have no clue. Someone else will have to decide.

>
> 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;

ok, understood, thanks. Perhaps it's worth a comment in the test script.

I'm afraid I still see a problem. The diff removes a query that (although a
bit different from the one above) lets the CROSS JOIN to be pushed down and
does introduce the IncrementalSort in the remote database. This query is
replaced with one that does not allow for the join push down.

*** a/contrib/postgres_fdw/sql/postgres_fdw.sql
--- b/contrib/postgres_fdw/sql/postgres_fdw.sql
*************** SELECT t1.c1 FROM ft1 t1 WHERE NOT EXIST
*** 510,517 ****
SELECT t1.c1 FROM ft1 t1 WHERE NOT EXISTS (SELECT 1 FROM ft2 t2 WHERE t1.c1 = t2.c2) ORDER BY t1.c1 OFFSET 100 LIMIT 10;
-- CROSS JOIN, not pushed down
EXPLAIN (VERBOSE, COSTS OFF)
! SELECT t1.c1, t2.c1 FROM ft1 t1 CROSS JOIN ft2 t2 ORDER BY t1.c1, t2.c1 OFFSET 100 LIMIT 10;
! SELECT t1.c1, t2.c1 FROM ft1 t1 CROSS JOIN ft2 t2 ORDER BY t1.c1, t2.c1 OFFSET 100 LIMIT 10;
-- different server, not pushed down. No result expected.
EXPLAIN (VERBOSE, COSTS OFF)
SELECT t1.c1, t2.c1 FROM ft5 t1 JOIN ft6 t2 ON (t1.c1 = t2.c1) ORDER BY t1.c1, t2.c1 OFFSET 100 LIMIT 10;
--- 510,517 ----
SELECT t1.c1 FROM ft1 t1 WHERE NOT EXISTS (SELECT 1 FROM ft2 t2 WHERE t1.c1 = t2.c2) ORDER BY t1.c1 OFFSET 100 LIMIT 10;
-- CROSS JOIN, not pushed down
EXPLAIN (VERBOSE, COSTS OFF)
! SELECT t1.c3, t2.c3 FROM ft1 t1 CROSS JOIN ft2 t2 ORDER BY t1.c3, t2.c3 OFFSET 100 LIMIT 10;
! SELECT t1.c3, t2.c3 FROM ft1 t1 CROSS JOIN ft2 t2 ORDER BY t1.c3, t2.c3 OFFSET 100 LIMIT 10;
-- different server, not pushed down. No result expected.
EXPLAIN (VERBOSE, COSTS OFF)
SELECT t1.c1, t2.c1 FROM ft5 t1 JOIN ft6 t2 ON (t1.c1 = t2.c1) ORDER BY t1.c1, t2.c1 OFFSET 100 LIMIT 10;

Shouldn't the test contain *both* cases?

--
Antonin Houska
Cybertec Schönig & Schönig GmbH
Gröhrmühlgasse 26
A-2700 Wiener Neustadt
Web: http://www.postgresql-support.de, http://www.cybertec.at