Date: Sat, 8 Feb 2020 15:22:17 +0100
From: Tomas Vondra <tomas.vondra@2ndquadrant.com>
To: Dmitry Dolgov <9erthalion6@gmail.com>
Cc: Kyotaro Horiguchi <horikyota.ntt@gmail.com>, florisvannee@optiver.com,
	pg@bowt.ie, jesper.pedersen@redhat.com,
	david.rowley@2ndquadrant.com, alvherre@2ndquadrant.com,
	thomas.munro@gmail.com, jtc331@gmail.com, rafia.pghackers@gmail.com,
	jeff.janes@gmail.com, bhushan.uparkar@gmail.com,
	pgsql-hackers@postgresql.org, a.korotkov@postgrespro.ru
Subject: Re: Index Skip Scan
Message-ID: <20200208142217.fhsiymg3szfnniih@development>
References: <20200205163730.eqvoxh6eb3do52r5@localhost>
 <20200206.102450.1514793516830965023.horikyota.ntt@gmail.com>
 <20200206105707.fuidmdsi6oapieoz@localhost>
 <20200206.212220.642002310227620136.horikyota.ntt@gmail.com>
 <20200207162543.zlj2tvcwy7jku6vu@localhost>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Disposition: inline
In-Reply-To: <20200207162543.zlj2tvcwy7jku6vu@localhost>
Precedence: bulk

Hi,

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

There are four benchmark groups, depending on how the data are generated
and availability of extended stats and if the columns are independent:

1) skipscan - just indexes, columns are independent

2) skipscan-with-stats - indexes and extended stats, independent columns

3) skipscan-correlated - just indexes, correlated columns

4) skipscan-correlated-with-stats - indexes and extended stats,
correlated columns

The github repository contains *.ods spreadsheet comparing duration with
the regular query plan (no skip scan) and skip scan. In general, there
are pretty massive speedups, often by about two orders of magnitude.

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.

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.

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?


regards

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