From: Jesper Pedersen <jesper.pedersen@redhat.com>
To: David Rowley <david.rowley@2ndquadrant.com>
To: Thomas Munro <thomas.munro@gmail.com>
Cc: Dmitry Dolgov <9erthalion6@gmail.com>
Cc: Floris Van Nee <florisvannee@optiver.com>
Cc: James Coleman <jtc331@gmail.com>
Cc: Rafia Sabih <rafia.pghackers@gmail.com>
Cc: Jeff Janes <jeff.janes@gmail.com>
Cc: Peter Geoghegan <pg@bowt.ie>
Cc: Tomas Vondra <tomas.vondra@2ndquadrant.com>
Cc: Thomas Munro <thomas.munro@enterprisedb.com>
Cc: Bhushan Uparkar <bhushan.uparkar@gmail.com>
Cc: PostgreSQL-development <pgsql-hackers@postgresql.org>
Cc: Alexander Korotkov <a.korotkov@postgrespro.ru>
Subject: Re: Index Skip Scan
Date: Wed, 3 Jul 2019 13:31:21 -0400
Message-ID: <9f4ef571-2f9e-2f5f-e2e3-c1632f3a3d7b@redhat.com> (raw)
In-Reply-To: <CAKJS1f_v5X1Sb42ShOhsLzuMA6iX52PcBwpf4P-L9H_GDYA3-Q@mail.gmail.com>
References: <2685f020-f302-9bf6-1b5c-ebc2bcebc635@2ndquadrant.com>
<CA+q6zcVQG0ufA_5m_7eeHLN2VRy+z8Kf9FoZ2NnF=yd0_43ndg@mail.gmail.com>
<CA+q6zcXxwU1FZ=Tj0kWeTkrJ1N9=fhrUH1t5N_yHEcKsG=+qUw@mail.gmail.com>
<1559361698401.22864@Optiver.com>
<1559362223126.18661@Optiver.com>
<CA+FpmFeKh9BAhDTAf-ZWQ=pvVaRy+Lnahb_8=OOFqcVXJDBWWQ@mail.gmail.com>
<988b7763-5c55-1be1-b7b6-f3a68eff0d40@redhat.com>
<CA+q6zcVnRRqktw4cg2Vddy3S+VY3Tsmit0kausYtctvsTum7tA@mail.gmail.com>
<1559763453006.85615@Optiver.com>
<1559763570329.85227@Optiver.com>
<4d469bf2-49ff-bc3d-a428-6c7b5d87d526@redhat.com>
<CAKJS1f86FgODuUnHiQ25RKeuES4qTqeNxm1QbqJWrBoZxVGLiQ@mail.gmail.com>
<CA+q6zcXoYjCtyU-jFU_=p2DL_K3BHbBEEbJHaJTxdvRX3cU-Sg@mail.gmail.com>
<CA+q6zcVVigO_1KRBxvzKfnR593CEE7FKR-bwP-XcH6AVHOo4+g@mail.gmail.com>
<a8b5c2d9-7b23-e12b-fc6b-eee63dc8dacf@redhat.com>
<CA+hUKGKo30N5VNuRWhDuMGVZ3hTcv4J5RGXe286GRJZLk_jBYQ@mail.gmail.com>
<CAKJS1f_v5X1Sb42ShOhsLzuMA6iX52PcBwpf4P-L9H_GDYA3-Q@mail.gmail.com>
Hi Thomas and David,
Thanks for the feedback !
On 7/2/19 8:27 AM, David Rowley wrote:
> On Tue, 2 Jul 2019 at 21:00, Thomas Munro <thomas.munro@gmail.com> wrote:
>> I took this for a quick spin today. The DISTINCT ON support is nice
>> and I think it will be very useful. I've signed up to review it and
>> will have more to say later. But today I had a couple of thoughts
>> after looking into how src/backend/optimizer/plan/planagg.c works and
>> wondering how to do some more skipping tricks with the existing
>> machinery.
>>
>> 1. SELECT COUNT(DISTINCT i) FROM t could benefit from this. (Or
>> AVG(DISTINCT ...) or any other aggregate). Right now you get a seq
>> scan, with the sort/unique logic inside the Aggregate node. If you
>> write SELECT COUNT(*) FROM (SELECT DISTINCT i FROM t) ss then you get
>> a skip scan that is much faster in good cases. I suppose you could
>> have a process_distinct_aggregates() in planagg.c that recognises
>> queries of the right form and generates extra paths a bit like
>> build_minmax_path() does. I think it's probably better to consider
>> that in the grouping planner proper instead. I'm not sure.
>
> I think to make that happen we'd need to do a bit of an overhaul in
> nodeAgg.c to allow it to make use of presorted results instead of
> having the code blindly sort rows for each aggregate that has a
> DISTINCT or ORDER BY. The planner would also then need to start
> requesting paths with pathkeys that suit the aggregate and also
> probably dictate the order the AggRefs should be evaluated to allow
> all AggRefs to be evaluated that can be for each sort order. Once
> that part is done then the aggregates could then also request paths
> with certain "UniqueKeys" (a feature I mentioned in [1]), however we'd
> need to be pretty careful with that one since there may be other parts
> of the query that require that all rows are fed in, not just 1 row per
> value of "i", e.g SELECT COUNT(DISTINCT i) FROM t WHERE z > 0; can't
> just feed through 1 row for each "i" value, since we need only the
> ones that have "z > 0". Getting the first part of this solved is much
> more important than making skip scans work here, I'd say. I think we
> need to be able to walk before we can run with DISTINCT / ORDER BY
> aggs.
>
I agree that the above is outside of scope for the first patch -- I
think the goal should be the simple use-cases for IndexScan and
IndexOnlyScan.
Maybe we should expand [1] with possible cases, so we don't lose track
of the ideas.
>> 2. SELECT i, MIN(j) FROM t GROUP BY i could benefit from this if
>> you're allowed to go forwards. Same for SELECT i, MAX(j) FROM t GROUP
>> BY i if you're allowed to go backwards. Those queries are equivalent
>> to SELECT DISTINCT ON (i) i, j FROM t ORDER BY i [DESC], j [DESC]
>> (though as Floris noted, the backwards version gives the wrong answers
>> with v20). That does seem like a much more specific thing applicable
>> only to MIN and MAX, and I think preprocess_minmax_aggregates() could
>> be taught to handle that sort of query, building an index only scan
>> path with skip scan in build_minmax_path().
>
> For the MIN query you just need a path with Pathkeys: { i ASC, j ASC
> }, UniqueKeys: { i, j }, doing the MAX query you just need j DESC.
>
Ok.
> The more I think about these UniqueKeys, the more I think they need to
> be a separate concept to PathKeys. For example, UniqueKeys: { x, y }
> should be equivalent to { y, x }, but with PathKeys, that's not the
> case, since the order of each key matters. UniqueKeys equivalent
> version of pathkeys_contained_in() would not care about the order of
> individual keys, it would say things like, { a, b, c } is contained in
> { b, a }, since if the path is unique on columns { b, a } then it must
> also be unique on { a, b, c }.
>
I'm looking at this, and will keep this in mind.
Thanks !
[1] https://wiki.postgresql.org/wiki/Loose_indexscan
Best regards,
Jesper
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-hackers@postgresql.org
Cc: jesper.pedersen@redhat.com, david.rowley@2ndquadrant.com, thomas.munro@gmail.com, 9erthalion6@gmail.com, florisvannee@optiver.com, jtc331@gmail.com, rafia.pghackers@gmail.com, jeff.janes@gmail.com, pg@bowt.ie, tomas.vondra@2ndquadrant.com, thomas.munro@enterprisedb.com, bhushan.uparkar@gmail.com, a.korotkov@postgrespro.ru
Subject: Re: Index Skip Scan
In-Reply-To: <9f4ef571-2f9e-2f5f-e2e3-c1632f3a3d7b@redhat.com>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox