From: Alexander Kuzmenkov <a.kuzmenkov@postgrespro.ru>
To: jesper.pedersen@redhat.com, Dmitry Dolgov <9erthalion6@gmail.com>
Cc: pg@bowt.ie, Thomas Munro <thomas.munro@enterprisedb.com>
Cc: bhushan.uparkar@gmail.com, PostgreSQL-development <pgsql-hackers@postgresql.org>
Cc: Alexander Korotkov <a.korotkov@postgrespro.ru>
Subject: Re: Index Skip Scan
Date: Thu, 13 Sep 2018 16:01:13 +0300
Message-ID: <522092c7-3cb7-a1ec-410b-dfa97ae722f3@postgrespro.ru> (raw)
In-Reply-To: <c87d41ae-7c18-a3a1-96f2-f366a43412dc@redhat.com>
References: <707b6f68-16fa-7aa7-96e5-eeb4865e6a30@redhat.com>
<CAPpHfducUiDw7hVT=Vui8rxTmawCkVc0H--v=jdbztMUGhzuRg@mail.gmail.com>
<89F84E17-D684-4717-B66F-0F05CB00168E@gmail.com>
<CAEepm=1ikXHVgSNruQ1HydDZm3OLnLNb5qT2c8S=Mh-VsFQXcQ@mail.gmail.com>
<CAH2-WznxAN940e=2D8Auz06d=_ZK6F5LVH0HUMbCXGAa=Tirpw@mail.gmail.com>
<CAEepm=0S1JUUwKCK4jhmtTWm9VUTsCe3+b5tSvddpMpkzas7Hw@mail.gmail.com>
<CAH2-Wzkk0+vSAiaRSkX84KR0SofKkY1yGHEcLoRBXT-JjM37bw@mail.gmail.com>
<CA+q6zcV-wgnSMu-YOEmyXVckncQyriiKtUZXm=Gx2s+FV=5MDw@mail.gmail.com>
<c87d41ae-7c18-a3a1-96f2-f366a43412dc@redhat.com>
Hi Jesper,
While testing this patch I noticed that current implementation doesn't
perform well when we have lots of small groups of equal values. Here is
the execution time of index skip scan vs unique over index scan, in ms,
depending on the size of group. The benchmark script is attached.
group size skip unique
1 2,293.85 132.55
5 464.40 106.59
10 239.61 102.02
50 56.59 98.74
100 32.56 103.04
500 6.08 97.09
So, the current implementation can lead to performance regression, and
the choice of the plan depends on the notoriously unreliable ndistinct
statistics. The regression is probably because skip scan always does
_bt_search to find the next unique tuple. I think we can improve this,
and the skip scan can be strictly faster than index scan regardless of
the data. As a first approximation, imagine that we somehow skipped
equal tuples inside _bt_next instead of sending them to the parent
Unique node. This would already be marginally faster than Unique + Index
scan. A more practical implementation would be to remember our position
in tree (that is, BTStack returned by _bt_search) and use it to skip
pages in bulk. This looks straightforward to implement for a tree that
does not change, but I'm not sure how to make it work with concurrent
modifications. Still, this looks a worthwhile direction to me, because
if we have a strictly faster skip scan, we can just use it always and
not worry about our unreliable statistics. What do you think?
--
Alexander Kuzmenkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company
Attachments:
[application/sql] test-skip.sql (571B, ../522092c7-3cb7-a1ec-410b-dfa97ae722f3@postgrespro.ru/3-test-skip.sql)
download
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: a.kuzmenkov@postgrespro.ru, 9erthalion6@gmail.com, thomas.munro@enterprisedb.com, a.korotkov@postgrespro.ru
Subject: Re: Index Skip Scan
In-Reply-To: <522092c7-3cb7-a1ec-410b-dfa97ae722f3@postgrespro.ru>
* 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