From: Dmitry Dolgov <9erthalion6@gmail.com>
To: James Coleman <jtc331@gmail.com>
Cc: Tomas Vondra <tomas.vondra@2ndquadrant.com>
Cc: Kyotaro Horiguchi <horikyota.ntt@gmail.com>
Cc: Floris Van Nee <florisvannee@optiver.com>
Cc: Peter Geoghegan <pg@bowt.ie>
Cc: Jesper Pedersen <jesper.pedersen@redhat.com>
Cc: David Rowley <david.rowley@2ndquadrant.com>
Cc: Alvaro Herrera <alvherre@2ndquadrant.com>
Cc: Thomas Munro <thomas.munro@gmail.com>
Cc: Rafia Sabih <rafia.pghackers@gmail.com>
Cc: Jeff Janes <jeff.janes@gmail.com>
Cc: Bhushan Uparkar <bhushan.uparkar@gmail.com>
Cc: pgsql-hackers <pgsql-hackers@postgresql.org>
Cc: Alexander Korotkov <a.korotkov@postgrespro.ru>
Subject: Re: Index Skip Scan
Date: Mon, 10 Feb 2020 20:30:56 +0100
Message-ID: <20200210193056.l4slz4bspqv44gqu@localhost> (raw)
In-Reply-To: <CAAaqYe8ATjgwJJnUe5O2KBy8HAAm1bPfYaGvaZrBh56-XP21AQ@mail.gmail.com>
References: <20200205163730.eqvoxh6eb3do52r5@localhost>
<20200206.102450.1514793516830965023.horikyota.ntt@gmail.com>
<20200206105707.fuidmdsi6oapieoz@localhost>
<20200206.212220.642002310227620136.horikyota.ntt@gmail.com>
<20200207162543.zlj2tvcwy7jku6vu@localhost>
<20200208142217.fhsiymg3szfnniih@development>
<20200208152440.l2sllrla7utvgexr@localhost>
<CAAaqYe8ATjgwJJnUe5O2KBy8HAAm1bPfYaGvaZrBh56-XP21AQ@mail.gmail.com>
> On Sat, Feb 08, 2020 at 01:31:02PM -0500, James Coleman wrote:
> On Sat, Feb 8, 2020 at 10:24 AM Dmitry Dolgov <9erthalion6@gmail.com> wrote:
> >
> > > On Sat, Feb 08, 2020 at 03:22:17PM +0100, Tomas Vondra wrote:
> > > So in this case the skip scan is ~15x slower than the usual plan (index
> > > only scan + unique). The reason why this happens is pretty simple - to
> > > estimate the number of groups we multiply the ndistinct estimates for
> > > the two columns (which both have n_distinct = 10000), but then we cap
> > > the estimate to 10% of the table. But when the columns are independent
> > > with high cardinalities that under-estimates the actual value, making
> > > the cost for skip scan much lower than it should be.
> >
> > The current implementation checks if we can find the next value on the
> > same page to do a shortcut instead of tree traversal and improve such
> > kind of situations, but I can easily imagine that it's still not enough
> > in some extreme situations.
>
> This is almost certainly rehashing already covered ground, but since I
> doubt it's been discussed recently, would you be able to summarize
> that choice (not to always get the next tuple by scanning from the top
> of the tree again) and the performance/complexity tradeoffs?
Yeah, this part of discussion happened already some time ago. The idea
[1] is to protect ourselves at least partially from incorrect ndistinct
estimations. Simply doing jumping over an index means that even if the
next key we're searching for is on the same page as previous, we still
end up doing a search from the root of the tree, which is of course less
efficient than just check right on the page before jumping further.
Performance tradeoff in this case is simple, we make regular use case
slightly slower, but can perform better in the worst case scenarios.
Complexity tradeoff was never discussed, but I guess everyone assumed
it's relatively straightforward to check the current page and return if
something was found before jumping.
[1]: https://www.postgresql.org/message-id/CA%2BTgmoY7QTHhzLWZupNSyyqFRBfMgYocg3R-6g%3DDRgT4-KBGqg%40mail...
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: 9erthalion6@gmail.com, jtc331@gmail.com, tomas.vondra@2ndquadrant.com, horikyota.ntt@gmail.com, florisvannee@optiver.com, pg@bowt.ie, jesper.pedersen@redhat.com, david.rowley@2ndquadrant.com, alvherre@2ndquadrant.com, thomas.munro@gmail.com, rafia.pghackers@gmail.com, jeff.janes@gmail.com, bhushan.uparkar@gmail.com, a.korotkov@postgrespro.ru
Subject: Re: Index Skip Scan
In-Reply-To: <20200210193056.l4slz4bspqv44gqu@localhost>
* 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