Re: Index Skip Scan

On Sat, Feb 08, 2020 at 04:24:40PM +0100, Dmitry Dolgov wrote:
>> On Sat, Feb 08, 2020 at 03:22:17PM +0100, Tomas Vondra wrote:
>>
>> I've done some testing and benchmarking of the v31 patch, looking for
>> regressions, costing issues etc. Essentially, I've ran a bunch of SELECT
>> DISTINCT queries on data sets of various size, number of distinct values
>> etc. The results are fairly large, so I've uploaded them to github
>>
>> https://github.com/tvondra/skip-scan-test
>
>Thanks a lot for testing!
>
>> There are a couple of regressions, where the plan with skipscan enables
>> is ~10x slower. But this seems to happen only in high-cardinality cases
>> where we misestimate the number of groups. Consider a table with two
>> independent columns
>>
>> CREATE TABLE t (a text, b text);
>> INSERT INTO t SELECT
>> md5((10000*random())::int::text),
>> md5((10000*random())::int::text)
>> FROM generate_series(1,1000000) s(i);
>>
>> CREATE INDEX ON t(a,b);
>>
>> ANALYZE;
>>
>> which then behaves like this:
>>
>> test=# select * from (select distinct a,b from t) foo offset 10000000;
>> Time: 3138.222 ms (00:03.138)
>> test=# set enable_indexskipscan = off;
>> Time: 0.312 ms
>> test=# select * from (select distinct a,b from t) foo offset 10000000;
>> Time: 199.749 ms
>>
>> 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.
>

Yeah. I'm not sure there's room for further improvements. The regressed
cases were subject to the 10% cap, and with ndistinct being more than
10% of the table, we probably can find many distinct keys on each index
page - we know that every ~10 rows the values change.

>> I don't think this is an issue the skipscan patch needs to fix, though.
>> Firstly, the regressed cases are a tiny minority. Secondly, we already
>> have a way to improve the root cause - creating extended stats with
>> ndistinct coefficients generally makes the problem go away.
>
>Yes, I agree.
>
>> One interesting observation however is that this regression only
>> happened with text columns but not with int or bigint. My assumption is
>> that this is due to text comparisons being much more expensive. Not sure
>> if there is something we could do to deal with this - reduce the number
>> of comparisons or something?
>
>Hm, interesting. I need to check that we do not do any unnecessary
>comparisons.
>
>> On Sat, Feb 08, 2020 at 02:11:59PM +0100, Tomas Vondra wrote:
>> > Yes, I've mentioned that already in one of the previous emails :) The
>> > simplest way I see to achieve what we want is to do something like in
>> > attached modified version with a new hasDeclaredCursor field. It's not a
>> > final version though, but posted just for discussion, so feel free to
>> > suggest any improvements or alternatives.
>>
>> IMO the proper fix for this case (moving forward, reading backwards) is
>> simply making it work by properly checking deleted tuples etc. Not sure
>> why that would be so much complex (haven't tried implementing it)?
>
>It's probably not that complex by itself, but requires changing
>responsibilities isolation. At the moment current implementation leaves
>jumping over a tree fully to _bt_skip, and heap visibility checks only
>to IndexOnlyNext. To check deleted tuples properly we need to either
>verify a corresponding heap tuple visibility inside _bt_skip (as I've
>mentioned in one of the previous emails, checking if an index tuple is
>dead is not enough), or teach the code in IndexOnlyNext to understand
>that _bt_skip can lead to returning the same tuple while moving forward
>& reading backward. Do you think it's still makes sense to go this way?

Not sure. I have to think about this first.

regards

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services