Reply-To: jesper.pedersen@redhat.com
Subject: Re: Index Skip Scan
To: David Rowley <david.rowley@2ndquadrant.com>
Cc: Floris Van Nee <florisvannee@optiver.com>,
 Dmitry Dolgov <9erthalion6@gmail.com>,
 Rafia Sabih <rafia.pghackers@gmail.com>, Jeff Janes <jeff.janes@gmail.com>,
 Thomas Munro <thomas.munro@gmail.com>,
 Alexander Kuzmenkov <a.kuzmenkov@postgrespro.ru>,
 Peter Geoghegan <pg@bowt.ie>, Tomas Vondra <tomas.vondra@2ndquadrant.com>,
 Thomas Munro <thomas.munro@enterprisedb.com>,
 Bhushan Uparkar <bhushan.uparkar@gmail.com>,
 PostgreSQL-development <pgsql-hackers@postgresql.org>,
 Alexander Korotkov <a.korotkov@postgrespro.ru>,
 James Coleman <jtc331@gmail.com>
References: <2685f020-f302-9bf6-1b5c-ebc2bcebc635@2ndquadrant.com>
 <CA+q6zcUSuFBhGVFZN_AVSxRbt5wr_4_YEYwv8PcQB=m6J6Zpvg@mail.gmail.com>
 <20190315.125452.252656146.horiguchi.kyotaro@lab.ntt.co.jp>
 <CA+q6zcXcSftAxfwuK5c186E8ckZeWmOO07GFvpoOx-wpsDGGzA@mail.gmail.com>
 <CA+q6zcVn10QzbSh686PaZpxgxMhxABRj7aJJpsJ=tKkmcSrBew@mail.gmail.com>
 <CA+q6zcUVAnfSOaSk3s9Sbj6yC7LrDYChSyJd0t7u6Q=97k5a=A@mail.gmail.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>
From: Jesper Pedersen <jesper.pedersen@redhat.com>
Organization: Red Hat
Message-ID: <9b36ad5c-53c2-47cc-2cc7-10588d24cb47@redhat.com>
Date: Fri, 14 Jun 2019 13:24:20 -0400
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101
 Thunderbird/60.7.0
MIME-Version: 1.0
In-Reply-To: 
 <CAKJS1f86FgODuUnHiQ25RKeuES4qTqeNxm1QbqJWrBoZxVGLiQ@mail.gmail.com>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 7bit
Precedence: bulk

Hi David,

On 6/14/19 3:19 AM, David Rowley wrote:
> I read over this thread a few weeks ago while travelling back from
> PGCon. (I wish I'd read it on the outward trip instead since it would
> have been good to talk about it in person.)
> 
> First off. I think this is a pretty great feature. It certainly seems
> worthwhile working on it.
> 
> I've looked over the patch just to get a feel for how the planner part
> works and I have a few ideas to share.
> 
> The code in create_distinct_paths() I think should work a different
> way. I think it would be much better to add a new field to Path and
> allow a path to know what keys it is distinct for.  This sort of goes
> back to an idea I thought about when developing unique joins
> (9c7f5229ad) about an easier way to detect fields that a relation is
> unique for. I've been calling these "UniqueKeys" in a few emails [1].
> The idea was to tag these onto RelOptInfo to mention which columns or
> exprs a relation is unique by so that we didn't continuously need to
> look at unique indexes in all the places that call
> relation_has_unique_index_for().  The idea there was that unique joins
> would know when a join was unable to duplicate rows. If the outer side
> of a join didn't duplicate the inner side, then the join RelOptInfo
> could keep the UniqueKeys from the inner rel, and vice-versa. If both
> didn't duplicate then the join rel would obtain the UniqueKeys from
> both sides of the join.  The idea here is that this would be a better
> way to detect unique joins, and also when it came to the grouping
> planner we'd also know if the distinct or group by should be a no-op.
> DISTINCT could be skipped, and GROUP BY could do a group aggregate
> without any sort.
> 
> I think these UniqueKeys ties into this work, perhaps not adding
> UniqueKeys to RelOptInfo, but just to Path so that we create paths
> that have UniqueKeys during create_index_paths() based on some
> uniquekeys that are stored in PlannerInfo, similar to how we create
> index paths in build_index_paths() by checking if the index
> has_useful_pathkeys().  Doing it this way would open up more
> opportunities to use skip scans. For example, semi-joins and
> anti-joins could make use of them if the uniquekeys covered the entire
> join condition. With this idea, the code you've added in
> create_distinct_paths() can just search for the cheapest path that has
> the correct uniquekeys, or if none exist then just do the normal
> sort->unique or hash agg.  I'm not entirely certain how we'd instruct
> a semi/anti joined relation to build such paths, but that seems like a
> problem that could be dealt with when someone does the work to allow
> skip scans to be used for those.
> 
> Also, I'm not entirely sure that these UniqueKeys should make use of
> PathKey since there's no real need to know about pk_opfamily,
> pk_strategy, pk_nulls_first as those all just describe how the keys
> are ordered. We just need to know if they're distinct or not. All
> that's left after removing those fields is pk_eclass, so could
> UniqueKeys just be a list of EquivalenceClass? or perhaps even a
> Bitmapset with indexes into PlannerInfo->ec_classes (that might be
> premature for not since we've not yet got
> https://commitfest.postgresql.org/23/1984/ or
> https://commitfest.postgresql.org/23/2019/ )  However, if we did use
> PathKey, that does allow us to quickly check if the UniqueKeys are
> contained within the PathKeys, since pathkeys are canonical which
> allows us just to compare their memory address to know if two are
> equal, however, if you're storing eclasses we could probably get the
> same just by comparing the address of the eclass to the pathkey's
> pk_eclass.
> 
> Otherwise, I think how you're making use of paths in
> create_distinct_paths() and create_skipscan_unique_path() kind of
> contradicts how they're meant to be used.
> 

Thank you very much for this feedback ! Will need to revise the patch 
based on this.

> I also agree with James that this should not be limited to Index Only
> Scans. From testing the patch, the following seems pretty strange to
> me:
> 
> # create table abc (a int, b int, c int);
> CREATE TABLE
> # insert into abc select a,b,1 from generate_Series(1,1000) a,
> generate_Series(1,1000) b;
> INSERT 0 1000000
> # create index on abc(a,b);
> CREATE INDEX
> # explain analyze select distinct on (a) a,b from abc order by a,b; --
> this is fast.
>                                                           QUERY PLAN
> -----------------------------------------------------------------------------------------------------------------------------
>   Index Only Scan using abc_a_b_idx on abc  (cost=0.42..85.00 rows=200
> width=8) (actual time=0.260..20.518 rows=1000 loops=1)
>     Scan mode: Skip scan
>     Heap Fetches: 1000
>   Planning Time: 5.616 ms
>   Execution Time: 21.791 ms
> (5 rows)
> 
> 
> # explain analyze select distinct on (a) a,b,c from abc order by a,b;
> -- Add one more column and it's slow.
>                                                                  QUERY PLAN
> ------------------------------------------------------------------------------------------------------------------------------------------
>   Unique  (cost=0.42..50104.43 rows=200 width=12) (actual
> time=1.201..555.280 rows=1000 loops=1)
>     ->  Index Scan using abc_a_b_idx on abc  (cost=0.42..47604.43
> rows=1000000 width=12) (actual time=1.197..447.683 rows=1000000
> loops=1)
>   Planning Time: 0.102 ms
>   Execution Time: 555.407 ms
> (4 rows)
> 
> [1] https://www.postgresql.org/search/?m=1&q=uniquekeys&l=1&d=-1&s=r
> 

Ok, understood.

I have put the CF entry into "Waiting on Author".

Best regards,
  Jesper