Re: Index Skip Scan (new UniqueKeys)

From: Dmitry Dolgov <9erthalion6(at)gmail(dot)com>
To: PostgreSQL-development <pgsql-hackers(at)postgresql(dot)org>
Cc: Heikki Linnakangas <hlinnaka(at)iki(dot)fi>, Peter Geoghegan <pg(at)bowt(dot)ie>, PostgreSQL-development <pgsql-hackers(at)postgresql(dot)org>, Jesper Pedersen <jesper(dot)pedersen(at)redhat(dot)com>, David Rowley <dgrowleyml(at)gmail(dot)com>, Floris Van Nee <florisvannee(at)optiver(dot)com>, Kyotaro Horiguchi <horikyota(dot)ntt(at)gmail(dot)com>, Thomas Munro <thomas(dot)munro(at)gmail(dot)com>, Tomas Vondra <tomas(dot)vondra(at)2ndquadrant(dot)com>, Andy Fan <zhihui(dot)fan1213(at)gmail(dot)com>, Dilip Kumar <dilipbalaut(at)gmail(dot)com>, Tomas Vondra <tomas(dot)vondra(at)enterprisedb(dot)com>
Subject: Re: Index Skip Scan (new UniqueKeys)
Date: 2022-01-22 21:31:33
Message-ID: 20220122213133.5tpywygi4utwnncn@erthalion.local
Views: Raw Message | Whole Thread | Download mbox | Resend email
Lists: pgsql-hackers

> On Fri, May 21, 2021 at 05:31:38PM +0200, Dmitry Dolgov wrote:
> Hi,
> Here is another take on the patch with a couple of changes:
> * I've removed for now UniqueKeys parts. The interaction of skip scan &
> unique keys patch was actually not that big, so the main difference is
> that now the structure itself went away, a list of unique expressions
> is used instead. All the suggestions about how this feature should
> look like from the planning perspective are still there. On the one
> hand it will allow to develop both patches independently and avoid
> confusion for reviewers, on the other UniqueKeys could be easily
> incorporated back when needed.
> * Support for skipping in case of moving backward on demand (scroll
> cursor) is moved into a separate patch. This is implemented via
> returning false from IndexSupportsBackwardScan in case if it's a skip
> scan node, which in turn adds Materialize node on top when needed. The
> name SupportsBackwardScan was a bit confusing for me, but it seems
> it's only being used with a cursorOptions check for CURSOR_OPT_SCROLL.
> Eventually those cases when BackwardScanDirection is used are still
> handled by amskip. This change didn't affect the test coverage, all
> the test cases supported in previous patch versions are still there.
> About Materialize node, I guess it could be less performant than a
> "native" support, but it simplifies the implementation significantly
> to the point that most parts, which were causing questions before, are
> now located in the isolated patch. My idea here is to concentrate
> efforts on the first three patches in this series, and consider the
> rest of them as an experiment field.
> * IndexScan support was also relocated into a separate patch, the first
> three patches are now only about IndexOnlyScan.
> * Last bits of reviews were incorporated and rebased.

While the patch is still waiting for a review, I was motivated by the
thread [1] to think about it from the interface point of view. Consider
an index skip scan being just like a normal index scan with a set of
underspecified leading search keys. It makes sense to have the same
structure "begin scan" -> "get the next tuple" -> "end scan" (now I'm
not sure if amskip is a good name to represent that, don't have anything
better yet). But the "underspecified" part is currently indeed
interpreted in a limited way -- as "missing" keys -- and is expressed
only via the prefix size. Another option would be e.g. leading keys
constrained by a range of values, so generally speaking it makes sense
to extend amount of the information provided for skipping.

As a naive approach I've added a new patch into the series, containing
the extra data structure (ScanLooseKeys, doesn't have much meaning yet
except somehow representing keys for skipping) used for index skip scan.
Any thoughts about it?

Besides that the new patch version contains some cleaning up and
addresses commentaries around leaf page pinning from [1]. The idea
behind the series structure is still the same: the first three patches
contains the essence of the implementation (hoping to help concentrate
review), the rest are more "experimental".


Attachment Content-Type Size
v40-0001-Unique-expressions.patch text/x-diff 16.1 KB
v40-0002-Index-skip-scan.patch text/x-diff 40.7 KB
v40-0003-amskip-implementation-for-Btree.patch text/x-diff 33.2 KB
v40-0004-Extend-amskip-implementation-for-Btree.patch text/x-diff 20.6 KB
v40-0005-Extend-index-skip-scan-with-ScanLooseKey.patch text/x-diff 5.4 KB
v40-0006-Index-skip-scan-for-IndexScan.patch text/x-diff 14.4 KB

In response to


Browse pgsql-hackers by date

  From Date Subject
Next Message Dmitry Dolgov 2022-01-22 21:37:19 Re: MDAM techniques and Index Skip Scan patch
Previous Message Stephen Frost 2022-01-22 21:20:33 Re: CREATEROLE and role ownership hierarchies