Horton

Re: [PATCH] Incremental sort (was: PoC: Partial sort)

James Coleman <jtc331@gmail.com>

View thread View on postgr.es
From: James Coleman <jtc331@gmail.com>
To: Tomas Vondra <tomas.vondra@2ndquadrant.com>
Cc: Michael Paquier <michael@paquier.xyz>, Rafia Sabih <rafia.pghackers@gmail.com>, Peter Geoghegan <pg@bowt.ie>, Simon Riggs <simon@2ndquadrant.com>, Shaun Thomas <shaun.thomas@2ndquadrant.com>, Dmitry Dolgov <9erthalion6@gmail.com>, Alexander Korotkov <a.korotkov@postgrespro.ru>, Tom Lane <tgl@sss.pgh.pa.us>, PostgreSQL Developers <pgsql-hackers@lists.postgresql.org>, Alvaro Herrera <alvherre@2ndquadrant.com>
Date: 2020-03-13T18:23:10Z
Lists: pgsql-hackers

Attachments

On Tue, Mar 10, 2020 at 10:44 PM Tomas Vondra
<tomas.vondra@2ndquadrant.com> wrote:
> 3) Most of the execution plans look reasonable, except that some of the
> plans look like this:
>
>
>                           QUERY PLAN
>    ---------------------------------------------------------
>     Limit
>       ->  GroupAggregate
>             Group Key: t.a, t.b, t.c, t.d
>             ->  Incremental Sort
>                   Sort Key: t.a, t.b, t.c, t.d
>                   Presorted Key: t.a, t.b, t.c
>                   ->  Incremental Sort
>                         Sort Key: t.a, t.b, t.c
>                         Presorted Key: t.a, t.b
>                         ->  Index Scan using t_a_b_idx on t
>    (10 rows)
>
> i.e. there are two incremental sorts on top of each other, with
> different prefixes. But this this is not a new issue - it happens with
> queries like this:
>
>    SELECT a, b, c, d, count(*) FROM (
>      SELECT * FROM t ORDER BY a, b, c
>    ) foo GROUP BY a, b, c, d limit 1000;
>
> i.e. there's a subquery with a subset of pathkeys. Without incremental
> sort the plan looks like this:
>
>                     QUERY PLAN
>    ---------------------------------------------
>     Limit
>       ->  GroupAggregate
>             Group Key: t.a, t.b, t.c, t.d
>             ->  Sort
>                   Sort Key: t.a, t.b, t.c, t.d
>                   ->  Sort
>                         Sort Key: t.a, t.b, t.c
>                         ->  Seq Scan on t
>    (8 rows)
>
> so essentially the same plan shape. What bugs me though is that there
> seems to be some sort of memory leak, so that this query consumes
> gigabytes os RAM before it gets killed by OOM. But the memory seems not
> to be allocated in any memory context (at least MemoryContextStats don't
> show anything like that), so I'm not sure what's going on.
>
> Reproducing it is fairly simple:
>
>    CREATE TABLE t (a bigint, b bigint, c bigint, d bigint);
>    INSERT INTO t SELECT
>      1000*random(), 1000*random(), 1000*random(), 1000*random()
>    FROM generate_series(1,10000000) s(i);
>    CREATE INDEX idx ON t(a,b);
>    ANALYZE t;
>
>    EXPLAIN ANALYZE SELECT a, b, c, d, count(*)
>    FROM (SELECT * FROM t ORDER BY a, b, c) foo GROUP BY a, b, c, d
>    LIMIT 100;

While trying to reproduce this, instead of lots of memory usage, I got
the attached assertion failure instead.

James

Commits

  1. Further adjustments to Hashagg EXPLAIN ANALYZE output

  2. Rework EXPLAIN format for incremental sort

  3. Fix typos and improve incremental sort comments

  4. Stabilize incremental_sort tests

  5. Minor improvements in Incremental Sort explain

  6. Consider Incremental Sort paths at additional places

  7. Fix representation of SORT_TYPE_STILL_IN_PROGRESS.

  8. Fix failures in incremental_sort due to number of workers

  9. Fix show_incremental_sort_info with force_parallel_mode

  10. Implement Incremental Sort

  11. Fix handling of "Subplans Removed" field in EXPLAIN output.

  12. Fix EXPLAIN (SETTINGS) to follow policy about when to print empty fields.

  13. Ensure plpgsql result tuples have the right composite type marking.

  14. Propagate sort instrumentation from workers back to leader.

  15. Make new regression test case parallel-safe, and improve its output.

  16. Push limit through subqueries to underlying sort, where possible.

  17. Fix inappropriate printing of never-measured times in EXPLAIN.

  18. Fix some infelicities in EXPLAIN output for parallel query plans.