Date: Mon, 10 Feb 2020 20:30:56 +0100
From: Dmitry Dolgov <9erthalion6@gmail.com>
To: James Coleman <jtc331@gmail.com>
Cc: Tomas Vondra <tomas.vondra@2ndquadrant.com>,
	Kyotaro Horiguchi <horikyota.ntt@gmail.com>,
	Floris Van Nee <florisvannee@optiver.com>,
	Peter Geoghegan <pg@bowt.ie>,
	Jesper Pedersen <jesper.pedersen@redhat.com>,
	David Rowley <david.rowley@2ndquadrant.com>,
	Alvaro Herrera <alvherre@2ndquadrant.com>,
	Thomas Munro <thomas.munro@gmail.com>,
	Rafia Sabih <rafia.pghackers@gmail.com>,
	Jeff Janes <jeff.janes@gmail.com>,
	Bhushan Uparkar <bhushan.uparkar@gmail.com>,
	pgsql-hackers <pgsql-hackers@postgresql.org>,
	Alexander Korotkov <a.korotkov@postgrespro.ru>
Subject: Re: Index Skip Scan
Message-ID: <20200210193056.l4slz4bspqv44gqu@localhost>
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>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: 
 <CAAaqYe8ATjgwJJnUe5O2KBy8HAAm1bPfYaGvaZrBh56-XP21AQ@mail.gmail.com>
Precedence: bulk

> 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.gmail.com