Subject: Re: Index Skip Scan
To: jesper.pedersen@redhat.com, Dmitry Dolgov <9erthalion6@gmail.com>
Cc: pg@bowt.ie, Thomas Munro <thomas.munro@enterprisedb.com>,
 Bhushan Uparkar <bhushan.uparkar@gmail.com>,
 PostgreSQL-development <pgsql-hackers@postgresql.org>,
 Alexander Korotkov <a.korotkov@postgrespro.ru>
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>
 <522092c7-3cb7-a1ec-410b-dfa97ae722f3@postgrespro.ru>
 <11b7c9d1-ae00-4385-97b2-fcd45f0a1a71@redhat.com>
 <3cfd317e-2a8b-8681-0833-8f2ead3af4d4@postgrespro.ru>
 <CA+q6zcUW=GXiw24iiLee3ZhA4JY4wc1hmGE8+20v-W47sOQjNA@mail.gmail.com>
 <cc30955d-2ee9-4c36-e5d7-fc5b552fbbb6@redhat.com>
From: Alexander Kuzmenkov <a.kuzmenkov@postgrespro.ru>
Message-ID: <aa0e6d35-5772-d5cb-04b7-65166eaa399f@postgrespro.ru>
Date: Thu, 15 Nov 2018 14:41:41 +0300
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101
 Thunderbird/60.2.1
MIME-Version: 1.0
In-Reply-To: <cc30955d-2ee9-4c36-e5d7-fc5b552fbbb6@redhat.com>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Content-Language: en-US
Precedence: bulk

On 9/27/18 16:59, Jesper Pedersen wrote:
> Hi Dmitry,
>
> On 9/15/18 3:52 PM, Dmitry Dolgov wrote:
>>> On Thu, 13 Sep 2018 at 21:36, Alexander Kuzmenkov 
>>> <a.kuzmenkov@postgrespro.ru> wrote:
>>> El 13/09/18 a las 18:39, Jesper Pedersen escribió:
>>>> I think we can improve this,
>>>> and the skip scan can be strictly faster than index scan regardless of
>>>> the data.
>>>> <...>
>>>>
>>>
>>> This is something to look at -- maybe there is a way to use
>>> btpo_next/btpo_prev instead/too in order to speed things up. Atm we 
>>> just
>>> have the scan key in BTScanOpaqueData. I'll take a look after my
>>> upcoming vacation; feel free to contribute those changes in the 
>>> meantime
>>> of course.
>>
>> But having this logic inside _bt_next means that it will make a 
>> non-skip index
>> only scan a bit slower, am I right?
>
> Correct.

Well, it depends on how the skip scan is implemented. We don't have to 
make normal scans slower, because skip scan is just a separate thing.

My main point was that current implementation is good as a proof of 
concept, but it is inefficient for some data and needs some unreliable 
planner logic to work around this inefficiency. And now we also have 
execution-time fallback because planning-time fallback isn't good 
enough. This looks overly complicated. Let's try to design an algorithm 
that works well regardless of the particular data and doesn't need these 
heuristics. It should be possible to do so for btree.

Of course, I understand the reluctance to implement an entire new type 
of btree traversal. Anastasia Lubennikova suggested a tweak for the 
current method that may improve the performance for small groups of 
equal values. When we search for the next unique key, first check if it 
is contained on the current btree page using its 'high key'. If it is, 
find it on the current page. If not, search from the root of the tree 
like we do now. This should improve the performance for small equal 
groups, because there are going to be several such groups on the page. 
And this is exactly where we have the regression compared to unique + 
index scan.

By the way, what is the data for which we intend this feature to work? 
Obviously a non-unique btree index, but how wide are the tuples, and how 
big the equal groups? It would be good to have some real-world examples.

-- 
Alexander Kuzmenkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company