pg.ddx.io pgsql-performance@postgresql.org mailing list archive
help / color / mirror / Atom feedRe: Bitmap scan is undercosted? - overestimated correlation and cost_index
5+ messages / 2 participants
[nested] [flat]
* Re: Bitmap scan is undercosted? - overestimated correlation and cost_index
@ 2017-12-06 21:46 Justin Pryzby <pryzby@telsasoft.com>
0 siblings, 1 reply; 5+ messages in thread
From: Justin Pryzby @ 2017-12-06 21:46 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Jeff Janes <jeff.janes@gmail.com>; Vitaliy Garnashevich <vgarnashevich@gmail.com>; pgsql-performance@lists.postgresql.org
On Tue, Dec 05, 2017 at 01:50:11PM -0500, Tom Lane wrote:
> Jeff Janes <jeff.janes@gmail.com> writes:
> > On Dec 3, 2017 15:31, "Tom Lane" <tgl@sss.pgh.pa.us> wrote:
> >> Jeff Janes <jeff.janes@gmail.com> writes:
> >>> But I do see that ties within the logical order of the column values are
> >>> broken to agree with the physical order. That is wrong, right? Is there
> >>> any argument that this is desirable?
>
> >> Uh ... what do you propose doing instead? We'd have to do something with
> >> ties, and it's not so obvious this way is wrong.
>
> > Let them be tied.
...
> I thought some more about this. What we really want the correlation stat
> to do is help us estimate how randomly an index-ordered scan will access
> the heap. If the values we've sampled are all unequal then there's no
> particular issue. However, if we have some group of equal values, we
> do not really know what order an indexscan will visit them in. The
> existing correlation calculation is making the *most optimistic possible*
> assumption, that such a group will be visited exactly in heap order ---
> and that assumption isn't too defensible.
I'm interested in discusstion regarding bitmap cost, since it would have helped
our case discussed here ~18 months ago:
https://www.postgresql.org/message-id/flat/20160524173914.GA11880%40telsasoft.com#20160524173914.GA1...
...but remember: in Vitaliy's case (as opposed to mine), the index scan is
*faster* but being estimated at higher cost than bitmap (I have to keep
reminding myself). So the rest of this discussion is about the
overly-optimistic cost estimate of index scans, which moves in the opposite
direction for this reported problem. For the test cases I looked at, index
scans were used when RPC=1 and redundant conditions were avoided, so I'm not
sure if there's any remaining issue (but I haven't looked at the latest cases
Vitaliy sent).
> In any case, given that we do this calculation without regard
> to any specific index,
One solution is to compute stats (at least correlation) for all indices, not
just expr inds. I did that earlier this year while throwing around/out ideas.
https://www.postgresql.org/message-id/20170707234119.GN17566%40telsasoft.com
> We do have an idea, from the data we have, whether the duplicates are close
> together in the heap or spread all over.
I think you just mean pg_stats.correlation for all values, not just duplicates
(with the understanding that duplicates might be a large fraction of the
tuples, and high weight in correlation).
Another issue I noted in an earlier thread is that as table sizes increase, the
existing correlation computation approaches 1 for correlated insertions, (like
"append-only" timestamps clustered around now()), due to ANALYZE sampling a
fraction of the table, and thereby representing only large-scale correlation,
and, to an increasing degree, failing to represent small-scale variations
between adjacent index TIDs, which has real cost (and for which the mitigation
by cache effects probably decreases WRT table size, too). I think any solution
needs to handle this somehow.
Generated data demonstrating this (I reused this query so it's more complicated
than it needs to be):
[pryzbyj@database ~]$ time for sz in 9999{,9{,9{,9{,9}}}} ; do psql postgres -tc "DROP TABLE IF EXISTS t; CREATE TABLE t(i float, j int); CREATE INDEX ON t(i);INSERT INTO t SELECT i/99999.0+pow(2,(-random())) FROM generate_series(1,$sz) i ORDER BY i; ANALYZE t; SELECT $sz, correlation, most_common_freqs[1] FROM pg_stats WHERE attname='i' AND tablename='t'"; done
9999 | 0.187146 |
99999 | 0.900629 |
999999 | 0.998772 |
9999999 | 0.999987 |
Trying to keep it all in my own head: For sufficiently large number of pages,
bitmap scan should be preferred to idx scan due to reduced random-page-cost
outweighing its overhead in CPU cost. Probably by penalizing index scans, not
discounting bitmap scans. Conceivably a correlation adjustment can be
conditionalized or weighted based on index_pages_fetched() ...
x = ln (x/999999);
if (x>1) correlation/=x;
I think one could look at the fraction of duplicated index keys expected to be
returned: if we expect to return 1000 tuples, with 200 duplicates from MCV,
cost_index would multiply correlation by (1 - 200/1000), meaning to use
something closer to max_IO_cost rather than min_IO_cost. I imagine it'd be
possible to limit to only those MCVs which pass quals - if none pass, then
there may be few tuples returned, so apply no correction to (additionally)
penalize index scan.
In my tests, at one point I implemented idx_corr_fudge(), returning a value
like "fragmentation" from pgstatindex (which I'm sure is where I got the phrase
when reporting the problem). That only uses the leaf nodes' "next" pointer,
and not the individual tuples, which probably works if there's a sufficiently
number of repeated keys.
I think that's all for now..
Justin
^ permalink raw reply [nested|flat] 5+ messages in thread
* Re: Bitmap scan is undercosted? - overestimated correlation and cost_index
@ 2017-12-12 09:29 Jeff Janes <jeff.janes@gmail.com>
parent: Justin Pryzby <pryzby@telsasoft.com>
0 siblings, 1 reply; 5+ messages in thread
From: Jeff Janes @ 2017-12-12 09:29 UTC (permalink / raw)
To: Justin Pryzby <pryzby@telsasoft.com>; +Cc: Tom Lane <tgl@sss.pgh.pa.us>; Vitaliy Garnashevich <vgarnashevich@gmail.com>; pgsql-performance@lists.postgresql.org
On Wed, Dec 6, 2017 at 1:46 PM, Justin Pryzby <pryzby@telsasoft.com> wrote:
> On Tue, Dec 05, 2017 at 01:50:11PM -0500, Tom Lane wrote:
> > Jeff Janes <jeff.janes@gmail.com> writes:
> > > On Dec 3, 2017 15:31, "Tom Lane" <tgl@sss.pgh.pa.us> wrote:
> > >> Jeff Janes <jeff.janes@gmail.com> writes:
> > >>> But I do see that ties within the logical order of the column values
> are
> > >>> broken to agree with the physical order. That is wrong, right? Is
> there
> > >>> any argument that this is desirable?
> >
> > >> Uh ... what do you propose doing instead? We'd have to do something
> with
> > >> ties, and it's not so obvious this way is wrong.
> >
> > > Let them be tied.
> ...
> > I thought some more about this. What we really want the correlation stat
> > to do is help us estimate how randomly an index-ordered scan will access
> > the heap. If the values we've sampled are all unequal then there's no
> > particular issue. However, if we have some group of equal values, we
> > do not really know what order an indexscan will visit them in. The
> > existing correlation calculation is making the *most optimistic possible*
> > assumption, that such a group will be visited exactly in heap order ---
> > and that assumption isn't too defensible.
>
> I'm interested in discusstion regarding bitmap cost, since it would have
> helped
> our case discussed here ~18 months ago:
> https://www.postgresql.org/message-id/flat/20160524173914.GA11880%
> 40telsasoft.com#20160524173914.GA11880@telsasoft.com
>
> ...but remember: in Vitaliy's case (as opposed to mine), the index scan is
> *faster* but being estimated at higher cost than bitmap (I have to keep
> reminding myself). So the rest of this discussion is about the
> overly-optimistic cost estimate of index scans, which moves in the opposite
> direction for this reported problem. For the test cases I looked at, index
> scans were used when RPC=1 and redundant conditions were avoided, so I'm
> not
> sure if there's any remaining issue (but I haven't looked at the latest
> cases
> Vitaliy sent).
>
> > In any case, given that we do this calculation without regard
> > to any specific index,
>
> One solution is to compute stats (at least correlation) for all indices,
> not
> just expr inds. I did that earlier this year while throwing around/out
> ideas.
> https://www.postgresql.org/message-id/20170707234119.
> GN17566%40telsasoft.com
When is the correlation of a column which is not the leading column of a
btree index or in a brin index ever used? If we did compute index-specific
correlations, we could maybe just drop pure-column correlations.
>
> > We do have an idea, from the data we have, whether the duplicates are
> close
> > together in the heap or spread all over.
>
> I think you just mean pg_stats.correlation for all values, not just
> duplicates
> (with the understanding that duplicates might be a large fraction of the
> tuples, and high weight in correlation).
>
> Another issue I noted in an earlier thread is that as table sizes
> increase, the
> existing correlation computation approaches 1 for correlated insertions,
> (like
> "append-only" timestamps clustered around now()), due to ANALYZE sampling a
> fraction of the table, and thereby representing only large-scale
> correlation,
>
That isn't due to sampling. That is due to the definition of linear
correlation. Large scale is what it is about.
> Generated data demonstrating this (I reused this query so it's more
> complicated
> than it needs to be):
>
> [pryzbyj@database ~]$ time for sz in 9999{,9{,9{,9{,9}}}} ; do psql
> postgres -tc "DROP TABLE IF EXISTS t; CREATE TABLE t(i float, j int);
> CREATE INDEX ON t(i);INSERT INTO t SELECT i/99999.0+pow(2,(-random())) FROM
> generate_series(1,$sz) i ORDER BY i; ANALYZE t; SELECT $sz, correlation,
> most_common_freqs[1] FROM pg_stats WHERE attname='i' AND tablename='t'";
> done
>
> 9999 | 0.187146 |
> 99999 | 0.900629 |
> 999999 | 0.998772 |
> 9999999 | 0.999987 |
>
Because the amount of jitter introduced is constant WRT $sz, but the range
of i/99999.0 increases with $sz, the correlation actually does increase; it
is not a sampling effect.
Trying to keep it all in my own head: For sufficiently large number of
> pages,
> bitmap scan should be preferred to idx scan due to reduced random-page-cost
> outweighing its overhead in CPU cost.
But CPU cost is probably not why it is losing anyway.
Index scans get a double bonus from high correlation. It assumes that only
a small fraction of the table will be visited. And then it assumes that
the visits it does make will be largely sequential. I think that you are
saying that for a large enough table, that last assumption is wrong, that
the residual amount of non-correlation is enough to make the table reads
more random than sequential. Maybe. Do you have a test case that
demonstrates this? If so, how big do we need to go, and can you see the
problem on SSD as well as HDD?
The thing is, the bitmap scan gets cheated out of one of these bonuses. It
gets no credit for visiting only a small part of the table when the
correlation is high, but does get credit for being mostly sequential in
whatever visits it does make (even if the correlation is low, because of
course the bitmap perfects the correlation).
I think it would be easier to give bitmap scans their due rather than try
to knock down index scans. But of course a synthetic test case would go a
long way to either one.
Probably by penalizing index scans, not
> discounting bitmap scans. Conceivably a correlation adjustment can be
> conditionalized or weighted based on index_pages_fetched() ...
> x = ln (x/999999);
> if (x>1) correlation/=x;
>
I think we should go with something with some statistical principle behind
it if we want to do that. There is the notion of "restricted range" in
correlations, that if there is a high correlation over the full range of
data, but you zoom into only a small fraction of that range, the
correlation you see over that restricted range will be much less than the
full correlation is. I don't know that field well enough to give a formula
off the top of my head, but I think it will be based on the fraction of the
key space which is being scanned, and (1-RSQ), rather than an arbitrary
number like 999999.
Cheers,
Jeff
^ permalink raw reply [nested|flat] 5+ messages in thread
* Re: Bitmap scan is undercosted? - overestimated correlation and cost_index
@ 2017-12-15 20:54 Justin Pryzby <pryzby@telsasoft.com>
parent: Jeff Janes <jeff.janes@gmail.com>
0 siblings, 2 replies; 5+ messages in thread
From: Justin Pryzby @ 2017-12-15 20:54 UTC (permalink / raw)
To: Jeff Janes <jeff.janes@gmail.com>; +Cc: Tom Lane <tgl@sss.pgh.pa.us>; Vitaliy Garnashevich <vgarnashevich@gmail.com>; pgsql-performance@lists.postgresql.org
On Tue, Dec 12, 2017 at 01:29:48AM -0800, Jeff Janes wrote:
> On Wed, Dec 6, 2017 at 1:46 PM, Justin Pryzby <pryzby@telsasoft.com> wrote:
> > On Tue, Dec 05, 2017 at 01:50:11PM -0500, Tom Lane wrote:
> > > In any case, given that we do this calculation without regard
> > > to any specific index,
> >
> > One solution is to compute stats (at least correlation) for all indices,
> > not
> > just expr inds. I did that earlier this year while throwing around/out
> > ideas.
> > https://www.postgresql.org/message-id/20170707234119.
> > GN17566%40telsasoft.com
>
> When is the correlation of a column which is not the leading column of a
> btree index or in a brin index ever used? If we did compute index-specific
> correlations, we could maybe just drop pure-column correlations.
Yes I think so - correlation is collected for every column, but only used for
indices.
I also have a comment to myself in that patch to force attstattarget=0 for
non-expr indices, to avoid keeping MCV/histogram which duplicates that of their
column.
> Trying to keep it all in my own head: For sufficiently large number of
> > pages,
> > bitmap scan should be preferred to idx scan due to reduced random-page-cost
> > outweighing its overhead in CPU cost.
>
>
> But CPU cost is probably not why it is losing anyway.
>
> Index scans get a double bonus from high correlation. It assumes that only
> a small fraction of the table will be visited. And then it assumes that
> the visits it does make will be largely sequential. I think that you are
> saying that for a large enough table, that last assumption is wrong, that
> the residual amount of non-correlation is enough to make the table reads
> more random than sequential. Maybe. Do you have a test case that
> demonstrates this? If so, how big do we need to go, and can you see the
> problem on SSD as well as HDD?
Right: The "residual"/fine-scale variations (those which are not adequately
represented by correlation metric) are/may be non-sequential, so don't get good
readahead.
The original issue was with an 75GB table (an inheritence child) and an
analytic query previously taking ~30min at that point taking 4-5 hours due to
random seeks (from duplicate values in a timestamp column with 1second
resolution). There would've been very little if any of the previous day's
table cached: the child table being queried (by way of its parent) had size
roughly same as the server's RAM, and would've been loaded over the course of
the preceding 6-30hours, and not frequently accessed. It may be that there's a
sharp change once cache no longer effectively mitigates the random heap reads.
SSD: good question.
Here's an rackspace VM with PG9.6.6, 2GB shared_buffers, 8GB RAM (~4GB of which
is being used as OS page cache), and 32GB SSD (with random_page_cost=1). The
server is in use by our application.
I believe you could scale up the size of the table to see this behavior with
any cache size. 0.0001 controls the "jitter", with smaller values being more
jittery..
postgres=# CREATE TABLE t(i int,j int) TABLESPACE tmp; CREATE INDEX ON t(i); INSERT INTO t SELECT (0.0001*a+9*(random()-0.5))::int FROM generate_series(1,99999999) a; VACUUM ANALYZE t;
public | t | table | pryzbyj | 3458 MB |
relpages | 442478
For comparison purposes/baseline; here's a scan on an SEPARATE index freshly
built AFTER insertions:
postgres=# explain(analyze,buffers) SELECT COUNT(j) FROM t WHERE i BETWEEN 0 AND 4000;
First invocation:
#1 -> Index Scan using t_i_idx1 on t (cost=0.57..1413352.60 rows=39933001 width=4) (actual time=25.660..52575.127 rows=39996029 loops=1)
Buffers: shared hit=1578644 read=286489 written=1084
Subsequent invocations with (extra) effect from OS cache:
#2 -> Index Scan using t_i_idx1 on t (cost=0.57..1413352.60 rows=39933001 width=4) (actual time=61.054..37646.556 rows=39996029 loops=1)
Buffers: shared hit=1578644 read=286489 written=2223
#3 -> Index Scan using t_i_idx1 on t (cost=0.57..1413352.60 rows=39933001 width=4) (actual time=9.344..31265.398 rows=39996029 loops=1)
Buffers: shared hit=1578644 read=286489 written=1192
Dropping that index, and scanning a different range on the non-fresh index:
postgres=# explain(analyze,buffers) SELECT COUNT(j) FROM t WHERE i BETWEEN 4000 AND 8000;
#1 -> Index Scan using t_i_idx on t (cost=0.57..1546440.47 rows=40298277 width=4) (actual time=95.815..139152.147 rows=40009853 loops=1)
Buffers: shared hit=1948069 read=316536 written=3411
Rerunning with cache effects:
#2 -> Index Scan using t_i_idx on t (cost=0.57..1546440.47 rows=40298277 width=4) (actual time=203.590..87547.287 rows=40009853 loops=1)
Buffers: shared hit=1948069 read=316536 written=5712
#3 -> Index Scan using t_i_idx on t (cost=0.57..1546440.47 rows=40298277 width=4) (actual time=164.504..83768.890 rows=40009853 loops=1)
Buffers: shared hit=1948069 read=316536 written=1979
Compare to seq scan:
-> Seq Scan on t (cost=0.00..1942478.00 rows=40298277 width=4) (actual time=1173.162..20980.069 rows=40009853 loops=1)
Buffers: shared hit=47341 read=395137
Bitmap:
-> Bitmap Heap Scan on t (cost=975197.91..2022150.06 rows=40298277 width=4) (actual time=24396.270..39304.813 rows=40009853 loops=1)
Buffers: shared read=316536 written=1431
The index scan reads 2.3e6 pages, compared to 4e5 pages (seq) and 3e5 pages
(bitmap). And idx scans were 4-7x slower than seq scan. Was the index scan
actually that badly affected by CPU cost of revisiting pages (rather than IO
costs)? Or did the OS actually fail to cache the 3e5 pages "read"? That would
be consistent with running almost 2x faster on the 3rd invocation.
The "hits" are largely from pages being revisited and recently accessed. Are
the misses (reads) mostly from pages being revisited after already falling out
of cache ? Or mostly initial access ? Or ??
If the index scan is really paying an high IO cost for rereads and not
primarily a CPU cost, this seems to be something like the "correlated index
scan" variant of traditional failure to effectively cache doing seq scan on a
sufficiently large table using a MRU buffer - the cache is ineffective for
adequately mitigating IO costs when the (re)reads have sufficient "spread".
postgres=# SELECT tablename, attname, correlation FROM pg_stats WHERE tablename='t';
tablename | t
attname | i
correlation | 1
I still want to say that's unreasonble due to (I think) high fraction of
nonrandom reads and associated absense of readahead.
> I think it would be easier to give bitmap scans their due rather than try
> to knock down index scans. But of course a synthetic test case would go a
> long way to either one.
As Tom said: index scans involving repeated keys are assuming best-case
sequential reads for a given computed correlation. I'd be happy if they were
costed to avoid that assumption, and instead used some "middle of the road"
interpretation (probably based on correlation and MCV fraction?), but, in the
alternate, need to distinguish the cost_index cases, rather than adjusting
bitmap. This is what led me to play around with stats computation for all
indices.
Justin
^ permalink raw reply [nested|flat] 5+ messages in thread
* Re: Bitmap scan is undercosted? - overestimated correlation and cost_index
@ 2017-12-16 19:18 Justin Pryzby <pryzby@telsasoft.com>
parent: Justin Pryzby <pryzby@telsasoft.com>
1 sibling, 0 replies; 5+ messages in thread
From: Justin Pryzby @ 2017-12-16 19:18 UTC (permalink / raw)
To: Jeff Janes <jeff.janes@gmail.com>; +Cc: Tom Lane <tgl@sss.pgh.pa.us>; Vitaliy Garnashevich <vgarnashevich@gmail.com>; pgsql-performance@lists.postgresql.org
On Fri, Dec 15, 2017 at 02:54:06PM -0600, Justin Pryzby wrote:
> SSD: good question.
>
> Here's an rackspace VM with PG9.6.6, 2GB shared_buffers, 8GB RAM (~4GB of which
> is being used as OS page cache), and 32GB SSD (with random_page_cost=1). The
> server is in use by our application.
>
> I believe you could scale up the size of the table to see this behavior with
> any cache size. 0.0001 controls the "jitter", with smaller values being more
> jittery..
>
> postgres=# CREATE TABLE t(i int,j int) TABLESPACE tmp; CREATE INDEX ON t(i); INSERT INTO t SELECT (0.0001*a+9*(random()-0.5))::int FROM generate_series(1,99999999) a; VACUUM ANALYZE t;
> public | t | table | pryzbyj | 3458 MB |
> relpages | 442478
I realized I've made a mistake here; the table is on SSD but not its index...
So all this cost is apparently coming from the index and not the heap.
-> Bitmap Heap Scan on t (cost=855041.91..1901994.06 rows=40298277 width=4) (actual time=14202.624..27754.982 rows=40009853 loops=1)
-> Bitmap Index Scan on t_i_idx1 (cost=0.00..844967.34 rows=40298277 width=0) (actual time=14145.877..14145.877 rows=40009853 loops=1)
Let me get back to you about that.
Justin
^ permalink raw reply [nested|flat] 5+ messages in thread
* Re: Bitmap scan is undercosted? - overestimated correlation and cost_index
@ 2017-12-17 02:37 Justin Pryzby <pryzby@telsasoft.com>
parent: Justin Pryzby <pryzby@telsasoft.com>
1 sibling, 0 replies; 5+ messages in thread
From: Justin Pryzby @ 2017-12-17 02:37 UTC (permalink / raw)
To: Jeff Janes <jeff.janes@gmail.com>; +Cc: Tom Lane <tgl@sss.pgh.pa.us>; Vitaliy Garnashevich <vgarnashevich@gmail.com>; pgsql-performance@lists.postgresql.org
On Fri, Dec 15, 2017 at 02:54:06PM -0600, Justin Pryzby wrote:
> SSD: good question.
>
> Here's an rackspace VM with PG9.6.6, 2GB shared_buffers, 8GB RAM (~4GB of which
> is being used as OS page cache), and 32GB SSD (with random_page_cost=1). The
> server is in use by our application.
>
> I believe you could scale up the size of the table to see this behavior with
> any cache size. 0.0001 controls the "jitter", with smaller values being more
> jittery..
On Sat, Dec 16, 2017 at 01:18:38PM -0600, Justin Pryzby wrote:
> I realized I've made a mistake here; the table is on SSD but not its index...
> So all this cost is apparently coming from the index and not the heap.
>
> -> Bitmap Heap Scan on t (cost=855041.91..1901994.06 rows=40298277 width=4) (actual time=14202.624..27754.982 rows=40009853 loops=1)
> -> Bitmap Index Scan on t_i_idx1 (cost=0.00..844967.34 rows=40298277 width=0) (actual time=14145.877..14145.877 rows=40009853 loops=1)
I'm rerunning with this:
postgres=# CREATE TABLE t(i int,j int) TABLESPACE tmp; CREATE INDEX ON t(i) TABLESPACE tmp; INSERT INTO t SELECT (0.0001*a+9*(random()-0.5))::int FROM generate_series(1,99999999) a; VACUUM ANALYZE t; CREATE INDEX ON t(i) TABLESPACE tmp;
That doesn't seem to invalidate my conclusions regarding the test data.
The non-fresh index:
#1 -> Index Scan using t_i_idx on t (cost=0.57..1103588.59 rows=39536704 width=4) (actual time=2.295..60094.704 rows=40009646 loops=1)
Rerun:
#2 -> Index Scan using t_i_idx on t (cost=0.57..1103588.59 rows=39536704 width=4) (actual time=1.671..54209.037 rows=40009646 loops=1)
#3 -> Index Scan using t_i_idx on t (cost=0.57..1103588.59 rows=39536704 width=4) (actual time=1.743..46436.538 rows=40009646 loops=1)
Scan fresh index:
-> Index Scan using t_i_idx1 on t (cost=0.57..1074105.46 rows=39536704 width=4) (actual time=1.715..16119.720 rows=40009646 loops=1)
bitmap scan on non-fresh idx:
-> Bitmap Heap Scan on t (cost=543141.78..1578670.34 rows=39536704 width=4) (actual time=4397.767..9137.541 rows=40009646 loops=1)
Buffers: shared hit=91235 read=225314
-> Bitmap Index Scan on t_i_idx (cost=0.00..533257.61 rows=39536704 width=0) (actual time=4346.556..4346.556 rows=40009646 loops=1)
Buffers: shared read=139118
seq scan:
-> Seq Scan on t (cost=0.00..1942478.00 rows=39536704 width=4) (actual time=6093.269..17880.164 rows=40009646 loops=1)
I also tried an idx only scan (note COUNT i vs j / "eye" vs "jay"), which I
think should be like an index scan without heap costs:
postgres=# SET max_parallel_workers_per_gather=0;SET enable_bitmapscan=off;SET enable_indexscan=on; begin; DROP INDEX t_i_idx1; explain(analyze,buffers) SELECT COUNT(i) FROM t WHERE i BETWEEN 4000 AND 8000; rollback;
-> Index Only Scan using t_i_idx on t (cost=0.57..928624.65 rows=39536704 width=4) (actual time=0.515..12646.676 rows=40009646 loops=1)
Buffers: shared hit=276 read=139118
However, in this test, random reads on the INDEX are still causing a large
fraction of the query time. When cached by the OS, this is much faster.
Compare:
#1 -> Bitmap Heap Scan on t (cost=543141.78..1578670.34 rows=39536704 width=4) (actual time=25498.978..41418.870 rows=40009646 loops=1)
Buffers: shared read=316549 written=497
-> Bitmap Index Scan on t_i_idx (cost=0.00..533257.61 rows=39536704 width=0) (actual time=25435.865..25435.865 rows=40009646 loops=1)
Buffers: shared read=139118 written=2
#2 -> Bitmap Heap Scan on t (cost=543141.78..1578670.34 rows=39536704 width=4) (actual time=5863.003..17531.860 rows=40009646 loops=1)
Buffers: shared read=316549 written=31
-> Bitmap Index Scan on t_i_idx (cost=0.00..533257.61 rows=39536704 width=0) (actual time=5799.400..5799.400 rows=40009646 loops=1)
Buffers: shared read=139118 written=31
Note that for the test data, the index is a large fraction of the table data
(since the only non-indexed column is nullfrac=1):
public | t | table | pryzbyj | 3458 MB |
public | t_i_idx | index | pryzbyj | t | 2725 MB |
public | t_i_idx1 | index | pryzbyj | t | 2142 MB |
(that could be 10% smaller with fillfactor=100)
I think the test case are reasonably reproducing the original issue. Note that
the 2nd invocation of the bitmap scan scanned the index in 5.8sec and the heap
in 11sec, but the 2nd invocation of the index scan took 54sec, of which I
gather ~6sec was from the index. So there's still 48sec spent accessing the
heap randomly, rather than 11sec sequentially.
I'm also playing with the tables which were the source of the original problem,
for which index reads in bitmap scan do not appear to be a large fraction of
the query time, probably because the index are 1-2% of the table size rather
than 60-70%. I'll mail about that separately.
Justin
^ permalink raw reply [nested|flat] 5+ messages in thread
end of thread, other threads:[~2017-12-17 02:37 UTC | newest]
Thread overview: 5+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2017-12-06 21:46 Re: Bitmap scan is undercosted? - overestimated correlation and cost_index Justin Pryzby <pryzby@telsasoft.com>
2017-12-12 09:29 ` Jeff Janes <jeff.janes@gmail.com>
2017-12-15 20:54 ` Justin Pryzby <pryzby@telsasoft.com>
2017-12-16 19:18 ` Justin Pryzby <pryzby@telsasoft.com>
2017-12-17 02:37 ` Justin Pryzby <pryzby@telsasoft.com>
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox