Re: Index Skip Scan

Hi,

On 11/15/18 6:41 AM, Alexander Kuzmenkov wrote:
>>> 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.
>

Robert suggested something similar in [1]. I'll try and look at that
when I'm back from my holiday.

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

Although my primary use-case is int I agree that we should test the
different data types, and tuple widths.

[1]
https://www.postgresql.org/message-id/CA%2BTgmobb3uN0xDqTRu7f7WdjGRAXpSFxeAQnvNr%3DOK5_kC_SSg%40mail.gmail.com

Best regards,
Jesper