RE: Index Skip Scan - Mailing list pgsql-hackers

Hello hackers,

Recently I've put some effort in extending the functionality of this patch. So far, we've been trying to keep the scope
ofthis patch relatively small to DISTINCT-clauses only. The advantage of this approach was that it keeps impact to the
indexamapi to a minimum. However, given the problems we've been facing in getting the implementation to work correctly
inall cases, I started wondering if this implementation was the right direction to go in. My main worry is that the
currentindexam api for skipping is not suited to other future use cases of skipping, but also that we're already
strugglingwith it now to get it to work correctly in all edge cases.
 

In the approach taken so far, the amskip function is defined taking two ScanDirection parameters. The function
amgettupleis left unchanged. However, I think we need amgettuple to take two ScanDirection parameters as well (or
createa separate function amgetskiptuple). This patch proposes that.
 

Currently, I've just added 'skip' functions to the indexam api for beginscan and gettuple. Maybe it'd be better to just
modifythe existing functions to take an extra parameter instead. Any thoughts on this?
 

The result is a patch that can apply skipping in many more cases than previous patches. For example, filtering on
columnsthat are not part of the index, properly handling visibility checks without moving these into the nbtree code,
skippingnot only on prefix but also on extra conditions that become available (eg. prefix a=1 and we happen to have a
WHEREclause with b=200, which we can now use to skip all the way to a=1 AND b=200). There's a fair amount of changes in
thenbtree code to support this.
 

Patch 0001 is Jesper's unique keys patch.
Patch 0002 modifies executor-level code to support skip scans and enables it for DISTINCT queries.
Patch 0003 just provides a very basic planner hack that enables the skip scan for practically all index scans (index,
indexonly and bitmap index). This is not what we would normally want, but this way I could easily test the skip scan
code.It's so large because I modify all the test cases expected results that now include an extra line 'Skip scan:
All'.The actual code changed is only a few lines in this patch.
 

The planner part of the code still needs work. The planner code in this patch is similar to the previous patch. David's
commentsabout projection paths haven't been addressed yet. Also, there's no proper way of hooking up the index scan for
regular(non-DISTINCT) queries yet. That's why I hacked up patch 0003 just to test stuff.
 

I'd welcome any help on these patches. If someone with more planner knowledge than me is willing to do part of the
plannercode, please feel free to do so. I believe supporting this will speed up a large number of queries for all kinds
ofusers. It can be a really powerful feature.
 

Tomas, would you be willing to repeat the performance tests you did earlier? I believe this version will perform better
thanthe previous patch for the cases where you noticed the 10-20x slow-down. There will obviously still be a
performancepenalty for cases where the planner picks a skip scan that are not well suited, but I think it'll be
smaller.

-Floris

-----
To give a few simple examples:

Initialization:
-- table t1 has 100 unique values for a
-- and 10000 b values for each a
-- very suitable for skip scan
create table t1 as select a,b,b%5 as c, random() as d from generate_series(1, 100) a, generate_series(1,10000) b;
create index on t1 (a,b,c);

-- table t2 has 10000 unique values for a
-- and 100 b values for each a 
-- this is not very suitable for skip scan
-- because the next matching value is always either
-- on the current page or on the next page
create table t2 as select a,b,b%5 as c, random() as d from generate_series(1, 10000) a, generate_series(1,100) b;
create index on t2 (a,b,c);

analyze t1;
analyze t2;

-- First 'Execution Time' line is this patched version (0001+0002+0003) (without including 0003, the non-DISTINCT
querieswould be equal to master)
 
-- Second 'Execution Time' line is master
-- Third 'Execution Time' is previous skip scan patch version
-- Just ran a couple of times to give an indication 
-- on order of magnitude, not a full benchmark.
select distinct on (a) * from t1;
 Execution Time: 1.407 ms (current patch)
 Execution Time: 480.704 ms (master)
 Execution Time: 1.711 ms (previous patch)

select distinct on (a) * from t1 where b > 50;
 Execution Time: 1.432 ms
 Execution Time: 481.530 ms
 Execution Time: 481.206 ms

select distinct on (a) * from t1 where b > 9990;
 Execution Time: 1.074 ms
 Execution Time: 33.937 ms
 Execution Time: 33.115 ms

select distinct on (a) * from t1 where d > 0.5;
 Execution Time: 0.811 ms
 Execution Time: 446.549 ms
 Execution Time: 436.091 ms

select * from t1 where b=50;
 Execution Time: 1.111 ms
 Execution Time: 33.242 ms
 Execution Time: 36.555 ms

select * from t1 where b between 50 and 75 and d > 0.5;
 Execution Time: 2.370 ms
 Execution Time: 60.744 ms
 Execution Time: 62.820 ms

select * from t1 where b in (100, 200);
 Execution Time: 2.464 ms
 Execution Time: 252.224 ms
 Execution Time: 244.872 ms

select * from t1 where b in (select distinct a from t1);
 Execution Time: 91.000 ms
 Execution Time: 842.969 ms
 Execution Time: 386.871 ms

select distinct on (a) * from t2;
 Execution Time: 47.155 ms
 Execution Time: 714.102 ms
 Execution Time: 56.327 ms

select distinct on (a) * from t2 where b > 5;
 Execution Time: 60.100 ms
 Execution Time: 709.960 ms
 Execution Time: 727.949 ms

select distinct on (a) * from t2 where b > 95;
 Execution Time: 55.420 ms
 Execution Time: 71.007 ms
 Execution Time: 69.229 ms

select distinct on (a) * from t2 where d > 0.5;
 Execution Time: 49.254 ms
 Execution Time: 719.820 ms
 Execution Time: 705.991 ms

-- slight performance degradation here compared to regular index scan
-- due to data unfavorable data distribution
select * from t2 where b=50;
 Execution Time: 47.603 ms
 Execution Time: 37.327 ms
 Execution Time: 40.448 ms

select * from t2 where b between 50 and 75 and d > 0.5;
 Execution Time: 244.546 ms
 Execution Time: 228.579 ms
 Execution Time: 227.541 ms

select * from t2 where b in (100, 200);
 Execution Time: 64.021 ms
 Execution Time: 242.905 ms
 Execution Time: 258.864 ms

select * from t2 where b in (select distinct a from t2);
 Execution Time: 758.350 ms
 Execution Time: 1271.230 ms
 Execution Time: 761.311 ms

I wrote a few things here about the method as well:
https://github.com/fvannee/postgres/wiki/Index-Skip-Scan
Code can be found there on Github as well in branch 'skip-scan'