Subject: Re: Index Skip Scan

From: Peter Geoghegan <[email-masked]>
Date: Mon, 3 Dec 2018 19:26:31 -0800

On Wed, Nov 21, 2018 at 12:55 PM Dmitry Dolgov <[email-masked]> wrote:
> Well, no, it's callled with ScanDirectionIsForward(dir). But as far as I
> remember from the previous discussions the entire topic of backward scan is
> questionable for this patch, so I'll try to invest some time in it.

Another thing that I think is related to skip scans that you should be
aware of is dynamic prefix truncation, which I started a thread on
just now [1]. While I see one big problem with the POC patch I came up
with, I think that that optimization is going to be something that
ends up happening at some point. Repeatedly descending a B-Tree when
the leading column is very low cardinality can be made quite a lot
less expensive by dynamic prefix truncation. Actually, it's almost a
perfect case for it.

I'm not asking anybody to do anything with that information. "Big
picture" thinking seems particularly valuable when working on the
B-Tree code; I don't want anybody to miss a possible future
opportunity.

[1] https://postgr.es/m/[email-masked]
-- 
Peter Geoghegan

---

From: Dmitry Dolgov <[email-masked]>
Date: Thu, 20 Dec 2018 14:46:09 +0100

> On Wed, Nov 21, 2018 at 9:56 PM Dmitry Dolgov <[email-masked]> wrote:
>
> > On Wed, Nov 21, 2018 at 4:38 PM Alexander Kuzmenkov <[email-masked]> wrote:
> >
> > On 11/18/18 02:27, Dmitry Dolgov wrote:
> > >
> > > [0001-Index-skip-scan-v4.patch]
> >
> > I ran a couple of tests on this, please see the cases below. As before,
> > I'm setting total_cost = 1 for index skip scan so that it is chosen.
> > Case 1 breaks because we determine the high key incorrectly, it is the
> > second tuple on page or something like that, not the last tuple.
>
> From what I see it wasn't about the high key, just a regular off by one error.
> But anyway, thanks for noticing - for some reason it wasn't always
> reproduceable for me, so I missed this issue. Please find fixed patch attached.
> Also I think it invalidates my previous performance tests, so I would
> appreciate if you can check it out too.

I've performed some testing, and on my environment with a dataset of 10^7
records:

* everything below 7.5 * 10^5 unique records out of 10^7 was faster with skip
  scan.

* above 7.5 * 10^5 unique records skip scan was slower, e.g. for 10^6 unique
  records it was about 20% slower than the regular index scan.

For me these numbers sound good, since even in quite extreme case of
approximately 10 records per group the performance of index skip scan is close
to the same for the regular index only scan.

> On Tue, Dec 4, 2018 at 4:26 AM Peter Geoghegan <[email-masked]> wrote:
>

Thanks, sounds cool. I'll try it out as soon as I'll have some spare time.

---

From: Dmitry Dolgov <[email-masked]>
Date: Sat, 26 Jan 2019 18:45:54 +0100

> On Thu, Dec 20, 2018 at 2:46 PM Dmitry Dolgov <[email-masked]> wrote:
>

Rebased version after rd_amroutine was renamed.

---

From: Dmitry Dolgov <[email-masked]>
Date: Sun, 27 Jan 2019 18:17:46 +0100

> On Sat, Jan 26, 2019 at 6:45 PM Dmitry Dolgov <[email-masked]> wrote:
>

And one more to fix the documentation. Also I've noticed few TODOs in the patch
about the missing docs, and replaced them with a required explanation of the
feature.

---

From: Dmitry Dolgov <[email-masked]>
Date: Wed, 30 Jan 2019 18:19:05 +0100

> On Sun, Jan 27, 2019 at 6:17 PM Dmitry Dolgov <[email-masked]> wrote:
>

A bit of adjustment after nodes/relation -> nodes/pathnodes.

---

From: Kyotaro HORIGUCHI <[email-masked]>
Date: Thu, 31 Jan 2019 15:31:53 +0900 (Tokyo Standard Time)

Hello.

At Wed, 30 Jan 2019 18:19:05 +0100, Dmitry Dolgov <[email-masked]> wrote in <CA+q6zcVP18wYiO=[email-masked]>
> A bit of adjustment after nodes/relation -> nodes/pathnodes.

I had a look on this.

The name "index skip scan" is a different feature from the
feature with the name on other prodcuts, which means "index scan
with postfix key (of mainly of multi column key) that scans
ignoring the prefixing part" As Thomas suggested I'd suggest that
we call it "index hop scan". (I can accept Hopscotch, either:p)

Also as mentioned upthread by Peter Geoghegan, this could easly
give worse plan by underestimation. So I also suggest that this
has dynamic fallback function.  In such perspective it is not
suitable for AM API level feature.

If all leaf pages are on the buffer and the average hopping
distance is less than (expectedly) 4 pages (the average height of
the tree), the skip scan will lose. If almost all leaf pages are
staying on disk, we could win only by 2-pages step (skipping over
one page).

=====
As I'm writing the above, I came to think that it's better
implement this as an pure executor optimization.

Specifically, let _bt_steppage count the ratio of skipped pages
so far then if the ratio exceeds some threshold (maybe around
3/4) it gets into hopscotching mode, where it uses index scan to
find the next page (rather than traversing). As mentioned above,
I think using skip scan to go beyond the next page is a good
bet. If the success ration of skip scans goes below some
threshold (I'm not sure for now), we should fall back to
traversing.

Any opinions?

====

Some comments on the patch below.

+     skip scan approach, which is based on the idea of
+     <ulink url="https://wiki.postgresql.org/wiki/Free_Space_Map_Problems">
+     Loose index scan</ulink>. Rather than scanning all equal values of a key,
+     as soon as a new value is found, it will search for a larger value on the

I'm not sure it is a good thing to put a pointer to rather
unstable source in the documentation.

This adds a new AM method but it seems avaiable only for ordered
indexes, specifically btree. And it seems that the feature can be
implemented in btgettuple since btskip apparently does the same
thing. (I agree to Robert in the point in [1]).

[1] https://www.postgresql.org/message-id/CA%2BTgmobb3uN0xDqTRu7f7WdjGRAXpSFxeAQnvNr%3DOK5_kC_SSg%40mail.gmail.com

Related to the above, it seems better that the path generation of
skip scan is a part of index scan. Whether skip scan or not is a
matter of index scan itself.

regards.

-- 
Kyotaro Horiguchi
NTT Open Source Software Center