Re: Index Skip Scan

From: Dmitry Dolgov <9erthalion6(at)gmail(dot)com>
To: Peter Geoghegan <pg(at)bowt(dot)ie>
Cc: Alexander Kuzmenkov <a(dot)kuzmenkov(at)postgrespro(dot)ru>, Jesper Pedersen <jesper(dot)pedersen(at)redhat(dot)com>, Thomas Munro <thomas(dot)munro(at)enterprisedb(dot)com>, Bhushan Uparkar <bhushan(dot)uparkar(at)gmail(dot)com>, PostgreSQL Hackers <pgsql-hackers(at)postgresql(dot)org>, Alexander Korotkov <a(dot)korotkov(at)postgrespro(dot)ru>, James Coleman <jtc331(at)gmail(dot)com>
Subject: Re: Index Skip Scan
Date: 2018-12-20 13:46:09
Message-ID: CA+q6zcVPs2vA=ym5tkj7JJo2pjKRnJgYn91+PDkpmCTDwz=oyw@mail.gmail.com
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

> On Wed, Nov 21, 2018 at 9:56 PM Dmitry Dolgov <9erthalion6(at)gmail(dot)com> wrote:
>
> > On Wed, Nov 21, 2018 at 4:38 PM Alexander Kuzmenkov <a(dot)kuzmenkov(at)postgrespro(dot)ru> 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 <pg(at)bowt(dot)ie> wrote:
>
> On Wed, Nov 21, 2018 at 12:55 PM Dmitry Dolgov <9erthalion6(at)gmail(dot)com> 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.

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

In response to

Responses

Browse pgsql-hackers by date

  From Date Subject
Next Message Alvaro Herrera 2018-12-20 14:29:05 Re: lock level for DETACH PARTITION looks sketchy
Previous Message Surafel Temesgen 2018-12-20 13:02:11 START/END line number for COPY FROM