Subject: index fragmentation on insert-only table with non-unique column

From: Justin Pryzby <[email-masked]>
Date: Tue, 24 May 2016 12:39:14 -0500

Summary: Non-unique btree indices are returning CTIDs for rows with same
value of indexed column not in logical order, imposing a high performance
penalty.

Running PG 9.5.3 now, we have a time-based partitions of append-only tables
with data loaded from other sources.  The tables are partitioned by time, and
timestamp column has an non-unique, not-null btree index.

The child tables are each ~75GB and expected to keep growing.  For a child
table with a week's worth of data:
relpages  | 11255802
reltuples | 5.90502e+07

The data is loaded shortly after it's available, so have high correlation in
pg_statistic:
[pryzbyj@viaero ~]$ psql ts -c "SELECT tablename, correlation, n_distinct FROM pg_stats s JOIN pg_class c ON (c.relname=s.tablename) WHERE tablename LIKE 'cdrs_huawei_pgwrecord%' AND attname='recordopeningtime' ORDER BY 1" |head
            tablename             | correlation | n_distinct 
----------------------------------+-------------+------------
 cdrs_huawei_pgwrecord            |    0.999997 |     102892
 cdrs_huawei_pgwrecord_2016_02_15 |    0.999658 |      96145
 cdrs_huawei_pgwrecord_2016_02_22 |    0.999943 |      91916
 cdrs_huawei_pgwrecord_2016_02_29 |    0.997219 |      50341
 cdrs_huawei_pgwrecord_2016_03_01 |    0.999947 |      97485

But note the non-uniqueness of the index column:
ts=# SELECT recordopeningtime, COUNT(1) FROM cdrs_huawei_pgwrecord WHERE recordopeningtime>='2016-05-21' AND recordopeningtime<'2016-05-22' GROUP BY 1 ORDER BY 2 DESC;
  recordopeningtime  | count
---------------------+-------
 2016-05-21 12:17:29 |   176
 2016-05-21 12:17:25 |   171
 2016-05-21 13:11:33 |   170
 2016-05-21 10:20:02 |   169
 2016-05-21 11:30:02 |   167
[...]

We have an daily analytic query which processes the previous day's data.  For
new child tables, with only 1 days data loaded, this runs in ~30min, and for
child tables with an entire week's worth of data loaded, takes several hours
(even though both queries process the same amount of data).

First, I found I was able to get 30-50min query results on full week's table by
prefering a seq scan to an index scan.  The row estimates seemed fine, and the
only condition is the timestamp, so the planner's use of index scan is as
expected.

AFAICT what's happening is that the index scan was returning pages
nonsequentially.  strace-ing the backend showed alternating lseek()s and
read()s, with the offsets not consistently increasing (nor consistently
decreasing):
% sudo strace -p 25588 2>&1 |grep -m9 'lseek(773'
lseek(773, 1059766272, SEEK_SET)        = 1059766272
lseek(773, 824926208, SEEK_SET)         = 824926208
lseek(773, 990027776, SEEK_SET)         = 990027776
lseek(773, 990330880, SEEK_SET)         = 990330880
lseek(773, 1038942208, SEEK_SET)        = 1038942208
lseek(773, 1059856384, SEEK_SET)        = 1059856384
lseek(773, 977305600, SEEK_SET)         = 977305600
lseek(773, 990347264, SEEK_SET)         = 990347264
lseek(773, 871096320, SEEK_SET)         = 871096320

.. and consecutive read()s being rare:
read(802, "g"..., 8192)                 = 8192
lseek(802, 918003712, SEEK_SET)         = 918003712
read(802, "c"..., 8192)                 = 8192
lseek(802, 859136000, SEEK_SET)         = 859136000
read(802, "a"..., 8192)                 = 8192
lseek(802, 919601152, SEEK_SET)         = 919601152
read(802, "d"..., 8192)                 = 8192
lseek(802, 905101312, SEEK_SET)         = 905101312
read(802, "c"..., 8192)                 = 8192
lseek(801, 507863040, SEEK_SET)         = 507863040
read(801, "p"..., 8192)                 = 8192
lseek(802, 914235392, SEEK_SET)         = 914235392
read(802, "c"..., 8192)                 = 8192

I was able to see great improvement without planner parameters by REINDEX the
timestamp index.  My theory is that the index/planner doesn't handle well the
case of many tuples with same column value, and returns pages out of logical
order.  Reindex fixes that, rewriting the index data with pages in order
(confirmed with pageinspect), which causes index scans to fetch heap data more
or less monotonically (if not consecutively).  strace shows that consecutive
read()s are common (without intervening seeks).  I gather this allows the OS
readahead to kick in.

Postgres seems to assume that the high degree of correlation of the table
column seen in pg_stats is how it will get data from the index scan, which
assumption seems to be very poor on what turns out to be a higly fragmented
index.  Is there a way to help it to understand otherwise??

Maybe this is a well-understood problem/deficiency; but, is there any reason
why Btree scan can't sort result by ctid for index tuples with same column
value (_bt_steppage() or btgettuple())?  Or maybe the problem could be
mitigated by changing the behavior during INESRT?  In the meantime, I'll be
implementing a reindex job.

Thanks,
Justin

-- 
Sent via pgsql-performance mailing list ([email-masked])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance

---

From: Peter Geoghegan <[email-masked]>
Date: Tue, 24 May 2016 21:16:20 -0700

> read()s are common (without intervening seeks).  I gather this allows the OS

The basic problem is that the B-Tree code doesn't maintain this
property. However, B-Tree index builds will create an index that
initially has this property, because the tuplesort.c code happens to
sort index tuples with a CTID tie-breaker.

> index.  Is there a way to help it to understand otherwise??

Your complaint is vague. Are you complaining about the planner making
a poor choice? I don't think that's the issue here, because you never
made any firm statement about the planner making a choice that was
worth than an alternative that it had available.

If you're arguing for the idea that B-Trees should reliably keep
tuples in order by a tie-break condition, that seems difficult to
implement, and likely not worth it in practice.

-- 
Peter Geoghegan

---

From: Stephen Frost <[email-masked]>
Date: Wed, 25 May 2016 00:26:25 -0400

> implement, and likely not worth it in practice.

The ongoing discussion around how to effectively handle duplicate values
in B-Tree seems relevant to this.  In particular, if we're able to store
duplicate values efficiently and all the locations under a single key
are easily available then we could certainly sort those prior to going
and visiting them.

That's not quite the same as keeping the tuples in order in the heap,
but would more-or-less achieve the effect desired, I believe?

Thanks!

Stephen

---

From: Tom Lane <[email-masked]>
Date: Wed, 25 May 2016 00:43:08 -0400

> sort index tuples with a CTID tie-breaker.

Yeah.  I wonder what would happen if we used the same rule for index
insertions.  It would likely make insertions more expensive, but maybe
not by much.  The existing "randomization" rule for where to insert new
items in a run of identical index entries would go away, because the
insertion point would become deterministic.  I am not sure if that's
good or bad for insertion performance, but it would likely help for
scan performance.

			regards, tom lane

---

From: Peter Geoghegan <[email-masked]>
Date: Tue, 24 May 2016 22:18:06 -0700

> good or bad for insertion performance, but it would likely help for

I think that if somebody tacked on a tie-breaker in the same way as in
tuplesort.c's B-Tree IndexTuple, there'd be significant negative
consequences.

The equal-to-high-key case gets a choice of which page to put the new
IndexTuple on, and I imagine that that's quite useful when it comes
up. I'd also have concerns about the key space in the index. I think
that it would seriously mess with the long term utility of values in
internal pages, which currently can reasonably have little to do with
the values currently stored in leaf pages. They're functionally only
separators of the key space that guide index scans, so it doesn't
matter if the actual values are completely absent from the leaf
pages/the table itself (perhaps some of the values in the internal
pages were inserted years ago, and have long since been deleted and
vacuumed away). Provided the distribution of values at the leaf level
is still well characterized at higher levels (e.g. many string values
that start with vowels, very few that start with the letters 'x' or
'z'), there should be no significant bloat. That's very valuable.
Unique indexes are another problem for this naive approach.

Maybe somebody could do better with a more sophisticated approach, but
it's probably better to focus on duplicate storage or even leaf page
compression, as Stephen mentioned.

-- 
Peter Geoghegan

---

From: Jeff Janes <[email-masked]>
Date: Tue, 24 May 2016 23:23:48 -0700

>             tablename             | correlation | n_distinct

That is not that much duplication.  You aren't going to have dozens or
hundreds of leaf pages all with equal values.   (and you only showed
the most highly duplicated ones, presumably the average is much less)

> (even though both queries process the same amount of data).

For an append only table, why would the first day of a new partition
be any less fragmented than that same day would be a week from now?
Are you sure it isn't just that your week-old data has all been aged
out of the cache?

> only condition is the timestamp, so the planner's use of index scan is as

Can you show us the query?  I would expect a bitmap scan of the index
(which would do what you want, but even more so), instead.

> read(802, "c"..., 8192)                 = 8192

Which of those are the table, and which the index?

Something doesn't add up here.  How could an index of an append-only
table possibly become that fragmented, when the highest amount of key
duplication is about 170?

Cheers,

Jeff

---

From: Justin Pryzby <[email-masked]>
Date: Wed, 25 May 2016 08:45:25 -0500

> worth than an alternative that it had available.

I was thinking there a few possible places to make improvements: the planner
could have understood that scans of non-unique indices don't result in strictly
sequential scans of the table, the degree of non-sequentialness being
determined by the column statistics, and perhaps by properties of the index
itself.

Or the INSERT code or btree scan could improve on this, even if tuples aren't
fully ordered.

> implement, and likely not worth it in practice.

I had the awful idea to change the index to use (recordopeningtime,ctid).
Maybe somebody will convince me otherwise, but may actually work better than
trying to reindex this table daily by 4am.

Thanks,
Justin

---

From: Justin Pryzby <[email-masked]>
Date: Wed, 25 May 2016 09:00:34 -0500

> the most highly duplicated ones, presumably the average is much less)

Point taken, but it's not that great of a range either:

ts=# SELECT recordopeningtime, COUNT(1) FROM cdrs_huawei_pgwrecord WHERE recordopeningtime>='2016-05-21' AND recordopeningtime<'2016-05-22' GROUP BY 1 ORDER BY 2 LIMIT 19;
  recordopeningtime  | count 
---------------------+-------
 2016-05-21 03:10:05 |    44
 2016-05-21 03:55:05 |    44
 2016-05-21 04:55:05 |    45

ts=# SELECT count(distinct recordopeningtime) FROM cdrs_huawei_pgwrecord WHERE recordopeningtime>='2016-05-21' AND recordopeningtime<'2016-05-22';
-[ RECORD 1 ]
count | 86400

ts=# SELECT count(recordopeningtime) FROM cdrs_huawei_pgwrecord WHERE recordopeningtime>='2016-05-21' AND recordopeningtime<'2016-05-22';
-[ RECORD 1 ]--
count | 8892865

> Are you sure it isn't just that your week-old data has all been aged
I don't think it's cache effect, since we're not using the source table for
(maybe anything) else the entire rest of the day.  Server has 72GB RAM, same
size one the largest of the tables being joined (beginning) at 4am.

I didn't mean that a given day is more fragmented now than it was last week
(but I don't know, either).  I guess when we do a query on the table with ~32
hours of data in, it might do a seq scan rather than index scan, too.

Compare the end of month partition tables:
ts=# select * FROM pgstatindex('cdrs_huawei_pgwrecord_2016_02_29_recordopeningtime_idx');
leaf_fragmentation | 48.6
ts=# select * FROM pgstatindex('cdrs_huawei_pgwrecord_2016_03_29_recordopeningtime_idx');
leaf_fragmentation | 48.38
ts=# select * FROM pgstatindex('cdrs_huawei_pgwrecord_2016_04_29_recordopeningtime_idx');
leaf_fragmentation | 48.6
ts=# SELECT * FROM pgstatindex('cdrs_huawei_pgwrecord_2016_04_22_recordopeningtime_idx');
leaf_fragmentation | 48.66
ts=# SELECT * FROM pgstatindex('cdrs_huawei_pgwrecord_2016_03_22_recordopeningtime_idx');
leaf_fragmentation | 48.27
ts=# SELECT * FROM pgstatindex('cdrs_huawei_pgwrecord_2016_02_22_recordopeningtime_idx');
leaf_fragmentation | 48

This one I reindexed as a test:
ts=# SELECT * FROM pgstatindex('cdrs_huawei_pgwrecord_2016_05_01_recordopeningtime_idx');
leaf_fragmentation | 0.01

.. and query ran in ~30min (reran a 2nd time, with cache effects: 25min).

> (which would do what you want, but even more so), instead.
See explain, also showing additional tables/views being joined.  It's NOT doing
a bitmap scan though, and I'd be interested to find why; I'm sure that would've
improved this query enough so it never would've been an issue.
https://explain.depesz.com/s/s8KP

 ->  Index Scan using cdrs_huawei_pgwrecord_2016_05_01_recordopeningtime_idx on cdrs_huawei_pgwrecord_2016_05_01  (cost=0.56..1601734.57 rows=8943848 width=349)
       Index Cond: ((recordopeningtime >= '2016-05-07 00:00:00'::timestamp without time zone) AND (recordopeningtime < '2016-05-08 00:00:00'::timestamp without time zone))

> > read()s, with the offsets not consistently increasing (nor consistently
..
> Which of those are the table, and which the index?
Those weren't necessarily strace of the same process; I believe both of these
were table data/heap, and didn't include any index access.

> duplication is about 170?

I'm certainly opened to alternate interpretations / conclusions :)

Justin

---

From: Claudio Freire <[email-masked]>
Date: Fri, 3 Jun 2016 18:26:33 -0300

>        Index Cond: ((recordopeningtime >= '2016-05-07 00:00:00'::timestamp without time zone) AND (recordopeningtime < '2016-05-08 00:00:00'::timestamp without time zone))

Please show your guc settings ( see
https://wiki.postgresql.org/wiki/Server_Configuration )

A plan node like that, if it would result in I/O, with proper
configuration should have selected a bitmap index/heap scan. If it
didn't, it probably thinks it has more cache than it really does, and
that would mean the wrong setting was set in effective_cache_size.

---

From: Justin Pryzby <[email-masked]>
Date: Fri, 3 Jun 2016 18:54:06 -0500

> that would mean the wrong setting was set in effective_cache_size.

ts=# SELECT name, current_setting(name), SOURCE FROM pg_settings WHERE SOURCE='configuration file';
 dynamic_shared_memory_type  | posix               | configuration file
 effective_cache_size        | 64GB                | configuration file
 effective_io_concurrency    | 8                   | configuration file
 huge_pages                  | try                 | configuration file
 log_autovacuum_min_duration | 0                   | configuration file
 log_checkpoints             | on                  | configuration file
 maintenance_work_mem        | 6GB                 | configuration file
 max_connections             | 200                 | configuration file
 max_wal_size                | 4GB                 | configuration file
 min_wal_size                | 6GB                 | configuration file
 shared_buffers              | 8GB                 | configuration file
 wal_compression             | on                  | configuration file
 work_mem                    | 1GB                 | configuration file

I changed at least maintenance_work_mem since I originally wrote, to try to
avoid tempfiles during REINDEX (though I'm not sure it matters, as the
tempfiles are effective cached and may never actually be written).

It's entirely possible those settings aren't ideal.  The server has 72GB RAM.
There are usually very few (typically n<3 but at most a handful) nontrivial
queries running at once, if at all.

I wouldn't expect any data that's not recent (table data last 2 days or index
from this month) to be cached, and wouldn't expect that to be entirely cached,
either:

ts=# SELECT sum(pg_table_size(oid))/1024^3 gb FROM pg_class WHERE relname~'_2016_05_..$';
gb | 425.783050537109

ts=# SELECT sum(pg_table_size(oid))/1024^3 gb FROM pg_class WHERE relname~'_2016_05_...*idx';
gb | 60.0909423828125

ts=# SELECT sum(pg_table_size(oid))/1024^3 gb FROM pg_class WHERE relname~'_201605.*idx';
gb | 4.85528564453125

ts=# SELECT sum(pg_table_size(oid))/1024^3 gb FROM pg_class WHERE relname~'_201605$';
gb | 86.8688049316406

As a test, I did SET effective_cache_size='1MB', before running explain, and
still does:

|	 ->  Index Scan using cdrs_huawei_pgwrecord_2016_05_29_recordopeningtime_idx on cdrs_huawei_pgwrecord_2016_05_29  (cost=0.44..1526689.49 rows=8342796 width=355)
|	       Index Cond: ((recordopeningtime >= '2016-05-29 00:00:00'::timestamp without time zone) AND (recordopeningtime < '2016-05-30 00:00:00'::timestamp without time zone))

I Set enable_indexscan=0, and got:

|	 ->  Bitmap Heap Scan on cdrs_huawei_pgwrecord_2016_05_29  (cost=168006.10..4087526.04 rows=8342796 width=355)
|	       Recheck Cond: ((recordopeningtime >= '2016-05-29 00:00:00'::timestamp without time zone) AND (recordopeningtime < '2016-05-30 00:00:00'::timestamp without time zone))
|	       ->  Bitmap Index Scan on cdrs_huawei_pgwrecord_2016_05_29_recordopeningtime_idx  (cost=0.00..165920.40 rows=8342796 width=0)
|		     Index Cond: ((recordopeningtime >= '2016-05-29 00:00:00'::timestamp without time zone) AND (recordopeningtime < '2016-05-30 00:00:00'::timestamp without time zone))

Here's a minimal query which seems to isolate the symptom:

ts=# explain (analyze,buffers) SELECT sum(duration) FROM cdrs_huawei_pgwrecord_2016_05_22 WHERE recordopeningtime>='2016-05-22' AND recordopeningtime<'2016-05-23';
| Aggregate  (cost=2888731.67..2888731.68 rows=1 width=8) (actual time=388661.892..388661.892 rows=1 loops=1)
|   Buffers: shared hit=4058501 read=1295147 written=35800
|   ->  Index Scan using cdrs_huawei_pgwrecord_2016_05_22_recordopeningtime_idx on cdrs_huawei_pgwrecord_2016_05_22  (cost=0.56..2867075.33 rows=8662534 w
|idth=8) (actual time=0.036..379332.910 rows=8575673 loops=1)
|         Index Cond: ((recordopeningtime >= '2016-05-22 00:00:00'::timestamp without time zone) AND (recordopeningtime < '2016-05-23 00:00:00'::timestamp
| without time zone))
|         Buffers: shared hit=4058501 read=1295147 written=35800
| Planning time: 0.338 ms
| Execution time: 388661.947 ms

And here's an older one to avoid cache, with enable_indexscan=0 
|ts=# explain (analyze,buffers)  SELECT sum(duration) FROM cdrs_huawei_pgwrecord_2016_05_08 WHERE recordopeningtime>='2016-05-08' AND recordopeningtime<'2016-05-09';
| Aggregate  (cost=10006286.58..10006286.59 rows=1 width=8) (actual time=44219.156..44219.156 rows=1 loops=1)
|   Buffers: shared hit=118 read=1213887 written=50113
|   ->  Bitmap Heap Scan on cdrs_huawei_pgwrecord_2016_05_08  (cost=85142.24..9985848.96 rows=8175048 width=8) (actual time=708.024..40106.062 rows=8179338 loops=1)
|         Recheck Cond: ((recordopeningtime >= '2016-05-08 00:00:00'::timestamp without time zone) AND (recordopeningtime < '2016-05-09 00:00:00'::timestamp without time zone))
|         Rows Removed by Index Recheck: 74909
|         Heap Blocks: lossy=1213568
|         Buffers: shared hit=118 read=1213887 written=50113
|         ->  Bitmap Index Scan on cdrs_huawei_pgwrecord_2016_05_08_recordopeningtime_idx1  (cost=0.00..83098.48 rows=8175048 width=0) (actual time=706.557..706.557 rows=12135680 loops=1)
|               Index Cond: ((recordopeningtime >= '2016-05-08 00:00:00'::timestamp without time zone) AND (recordopeningtime < '2016-05-09 00:00:00'::timestamp without time zone))
|               Buffers: shared hit=117 read=320
| Planning time: 214.786 ms
| Execution time: 44228.874 ms
|(12 rows)

Thanks for your help.

Justin

---

From: Claudio Freire <[email-masked]>
Date: Fri, 3 Jun 2016 23:05:17 -0300

> | Execution time: 44228.874 ms

Correct me if I'm wrong, but this looks like the planner not
accounting for correlation when using bitmap heap scans.

Checking the source, it really doesn't.

So correlated index scans look extra favourable vs bitmap index scans
because bitmap heap scans consider random page costs sans correlation
effects (even though correlation applies to bitmap heap scans as
well). While that sounds desirable a priori, it seems it's hurting
this case quite badly.

I'm not sure there's any simple way of working around that.

---

From: Kevin Grittner <[email-masked]>
Date: Sat, 4 Jun 2016 08:39:48 -0500

>  min_wal_size                | 6GB                 | configuration file

Just a minor digression -- it generally doesn't make sense to
configure the minimum for something greater than the maximum for
that same thing.  That should have no bearing the performance issue
raised on the thread, but you might want to fix it anyway.

--
Kevin Grittner
EDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

---

From: Tom Lane <[email-masked]>
Date: Sun, 05 Jun 2016 12:03:58 -0400

Claudio Freire <[email-masked]> writes:
> well).

Really?  How?  The index ordering has nothing to do with the order in
which heap tuples will be visited.

			regards, tom lane

---

From: Jeff Janes <[email-masked]>
Date: Sun, 5 Jun 2016 12:28:47 -0700

> which heap tuples will be visited.

It is not the order itself, but the density.

If the index is read in a range scan (as opposed to =ANY scan), and
the index lead column is correlated with the table ordering, then the
parts of the table that need to be visited will be much denser than if
there were no correlation.  But Claudio is saying that this is not
being accounted for.

Cheers,

Jeff

---

From: Justin Pryzby <[email-masked]>
Date: Sat, 13 Aug 2016 13:54:48 -0500

Regarding this earlier thread:
https://www.postgresql.org/message-id/flat/[email-masked]

> value of indexed column not in logical order, imposing a high performance

I have to point out that by "logical" I clearly meant "physical", hopefully
nobody was too misled..

> there were no correlation.  But Claudio is saying that this is not

I didn't completely understand Claudio/Jeff here, and not sure if we're on the
same page.  For queries on these tables, the index scan was very slow, due to
fragmented index on non-unique column, and seq scan would have been (was)
faster (even if it means reading 70GB and filtering out 6 of 7 days' data).
That was resolved by added a nightly reindex job (..  which sometimes competes
with other maintenance and has trouble running every table every night).

But I did find that someone else had previously reported this problem (in a
strikingly similar context and message, perhaps clearer than mine):
https://www.postgresql.org/message-id/flat/[email-masked]

I also found this older thread:
https://www.postgresql.org/message-id/flat/n6cmpug13b9rk1s[email-masked]

There was mention of a TODO item:

    * Compute index correlation on CREATE INDEX and ANALYZE, use it for index
    * scan cost estimation

.. but perhaps I misunderstand and that's long since resolved ?

Justin

---

From: Claudio Freire <[email-masked]>
Date: Mon, 15 Aug 2016 14:42:03 -0300

> with other maintenance and has trouble running every table every night).

Yes, but a bitmap index scan should be faster than both, but the
planner is discarding it beause it estimates it will be slower,
because it doesn't account for correlation between index keys and
physical location.

And, while what you clarify there would indeed affect the estimation
for index scans, it would only make the issue worse: the planner
thinks the index scan will be better than it really is, because it's
expecting correlation, but the "fragmentation" of same-key runs
destroys that correlation. A bitmap index scan would restore it,
though, so the bitmap index scan would be that much better.

---

From: Justin Pryzby <[email-masked]>
Date: Fri, 7 Jul 2017 18:41:19 -0500

Months ago I reported an issue with very slow index scan of tables with high
"correlation" of its indexed column, due to (we concluded at the time)
duplicate/repeated values of that column causing many lseek()s.  References:

My interim workarounds were an reindex job and daily granularity partitions
(despite having an excessive number of child tables) to query execution time]]
to encourage seq scans for daily analysis jobs rather than idx scan.  I've now
cobbled together a patch to throw around and see if we can improve on that.  I
tried several changes, hoping to discourage index scan.  The logic that seems
to most accurately reflect costs has two changes:  

Postgres' existing behavior stores table correlation (heap value vs. position)
but doesn't look at index correlation, so can't distinguish between a just-built
index, and a highly fragmented index, or one with highly-nonsequential TIDs.
My patch causes ANALYZE to do a TID scan (sampled across the MCVs) to determine
correlation of heap TID vs index tuple logical location (as opposed to the
table correlation, computed as: heap TID vs. heap value).

The second change averages separate correlation values of small lists of 300
consecutive TIDs, rather than the course-granularity/aggregate correlation of a
small sample of pages across the entire index.  Postgres' existing sampling is
designed to give an even sample across all rows.  An issue with this
course-granularity correlation is that the index can have a broad correlation
(to physical heap location), but with many small-scale deviations, which don't
show up due to sampling a relatively small fraction of a large table; and/or
the effect of the deviations is insignificant/noise and correlation is still
computed near 1.

I believe the "large scale" correlation that postgres computes from block
sample fails to well represent small-scale uncorrelated reads which contribute
large number of random reads, but not included in planner cost.

Not only are the index reads highly random (which the planner already assumes),
but the CTIDs referenced within a given btree leaf page are also substantially
non-sequential.  It seems to affect INSERTs which, over a short interval of
time have a small-moderate range of column values, but which still have a
strong overall trend in that column WRT time (and heap location).  Think of
inserting a "normal" distribution of timestamps centered around now().

My original report shows lseek() for nearly every read on the *heap*.  The
original problem was on a table of telecommunications CDRs, indexed by "record
opening time" (start time) and with high correlation value in pg_stats.  We
import data records from a file, which is probably more or less in order of
"end time".

That still displays broad correlation on "start time", but individual TIDs are
nowhere near sequential.  Two phone calls which end in the same 1 second
interval are not unlikely to have started many minutes apart...  but two calls
which end within the same second are very likely to have started within an hour
of each other.. since typical duration is <1h.  But, insert volume is high, and
there are substantial repeated keys, so the portion of an index scan returning
CTIDs for some certain key value (timestamp with second resolution in our case)
ends up reading heap tuples for a non-negligible fraction of the table: maybe
only 1%, but that's 300 seeks across 1% of a table which is 10s of GB ...
which is still 300 seeks, and takes long enough that cache is inadequate to
substantially mitigate the cost.

It's not clear to me that there's a good way to evenly *sample* a fraction of
the index blocks in a manner which is agnostic to different AMs.  Scanning the
entirety of all indices on relations during (auto) analyze may be too
expensive.  So I implemented index scan of the MCV list.  I'm guessing this
might cause the correlation to be under-estimated, and prefer bitmap scans
somewhat more than justified, due to btree insertion logic for repeated keys,
to reduce O(n^2) behavior.  MCV list isn't perfect since that can happen with
eg. normally distributed floating point values (or timestamp with fractional
seconds).

I ran pageinspect on a recent child of the table that triggered the original
report:

ts=# SELECT itemoffset, ctid FROM bt_page_items('cdrs_huawei_pgwrecord_2017_07_07_recordopeningtime_idx',6) LIMIT 22 OFFSET 1;
 itemoffset |  ctid  
------------+--------
          2 | (81,4)
          3 | (5,6)
          4 | (6,5)
          5 | (9,1)
          6 | (10,1)
          7 | (14,1)
          8 | (21,8)
          9 | (25,1)
         10 | (30,5)
         11 | (41,1)
         12 | (48,7)
         13 | (49,3)
         14 | (50,2)
         15 | (51,1)
         16 | (54,1)
         17 | (57,7)
         18 | (58,6)
         19 | (59,6)
         20 | (63,5)
         21 | (71,6)
         22 | (72,5)
         23 | (78,7)
(22 rows)

=> 22 adjacent tuples referencing 22 different heap pages, only 6 of which are sequential => 16 lseek() aka random page cost.

To generate data demonstrating this problem you can do things like:
| CREATE TABLE t(i int, j int);
| CREATE INDEX ON t(i);
\! time for a in `seq 99`; do psql -qc 'INSERT INTO t SELECT * FROM generate_series(1,99)'; done -- or, 
or:
| INSERT INTO t SELECT (0.001*a+9*(random()-0.5))::int FROM generate_series(1,99999) a; -- or, 

or this one, perhaps closest to our problem case:
| INSERT INTO t SELECT a FROM generate_series(1,999) a, generate_series(1,999) b ORDER BY a+b/9.9;

Note, I was able to create a case using floats without repeated keys:
| INSERT INTO w SELECT i/99999.0+pow(2,(-random())) FROM generate_series(1,999999) i ORDER BY i

| ANALYZE t;
-- note: the correlation is even higher for larger tables with same number of
-- repeated keys, which is bad since the cost should go up linearly with the
-- size and associated number of lseek().  That's one component of the problem
-- and I think a necessarily component of any solution.
postgres=# SELECT tablename, attname, correlation, array_length(most_common_vals,1) FROM pg_stats WHERE tablename LIKE 't%';
 tablename | attname | correlation | array_length 
-----------+---------+-------------+--------------
 t         | i       |    0.995212 |           87
 t         | j       |             |             
 t_i_idx   | i       |   -0.892874 |           87
 ^^^^^^^
... this last line is added by my patch.

That's a bad combination, high table correlation means the planner thinks only
a fraction of the heap will be read, and sequentially, so isn't discouraged
from doing index scan.  But index TIDs are much less well correlated (0.89 vs
0.99).

Note: the negative correlation at tuple-level seems to be related to this comment:
src/backend/access/nbtree/nbtinsert.c- *                Once we have chosen the page to put the key on, we'll insert it before
src/backend/access/nbtree/nbtinsert.c: *                any existing equal keys because of the way _bt_binsrch() works.

Note also:
|postgres=# SELECT leaf_fragmentation FROM pgstatindex('t_i_idx');
|leaf_fragmentation | 67.63
.. but keep in mind that leaf_fragmentation only checks leaf page order, and
not CTID order within index pages.  The planner already assumes index pages are
random reads.  Maybe it's a good indicator (?), but doesn't lend itself to an
accurate cost estimation.

For testing purposes, with:
| shared_buffers | 128kB
|  public | t    | table | pryzbyj | 35 MB | 
| SET enable_bitmapscan=off;
| SET enable_seqscan=off;
| SELECT pg_backend_pid();
| SELECT sum(j) FROM t WHERE i<99;
| Time: 3974.205 ms

% sudo strace -p 530 2>/tmp/strace-pg
% sed -r '/^\(read|lseek/!d; s/ .*//' /tmp/strace-pg |sort |uniq -c |sort -nr |head
  39474 lseek(41,
    359 lseek(44,
      8 lseek(18,
=> 40k seeks on an 35MB table, that's 10 seeks per heap page!

open("base/12411/16634", O_RDWR)        = 41
open("base/12411/16636", O_RDWR)        = 44

postgres=# SELECT relfilenode, relname FROM pg_class WHERE relfilenode>16630;
       16634 | t
       16636 | t_i_idx

2017-07-07 17:45:54.075 CDT [6360] WARNING:  HERE 1222: csquared=0.797225 minIO/R-P-C=109.750000 maxIO/R-P-C=4416.000000 costsize.c cost_index 702

With my patch, index scan estimated to take ~4400 seeks, rather than actual
40k, probably because max_IO_cost assumes that a given heap page will be
visited only once.  But in the worst case each of its tuples would require a
separate lseek()....  I'm not suggesting to change that, since making max_IO
100x higher will probably change query plans more dramatically than desired..
But also note that, unpatched, with table correlation >0.99, postgres would've
under-estimated min_IO_cost not by a factor of 10x but by 400x.

| postgres=# REINDEX INDEX t_i_idx;
| postgres=# ANALYZE t;
| postgres=# SELECT tablename, attname, correlation, array_length(most_common_vals,1) FROM pg_stats WHERE tablename LIKE 't%';
|  tablename | attname | correlation | array_length 
| -----------+---------+-------------+--------------
|  t         | i       |    0.995235 |           67
|  t_i_idx   | i       |           1 |           67

=> Correctly distinguishes freshly reindexed table.

% sudo strace -p 6428 2>/tmp/strace-pg8
% sed -r '/^\(read|lseek/!d; s/ .*//' /tmp/strace-pg8 |sort |uniq -c |sort -nr
     99 lseek(37,

2017-07-07 17:49:47.745 CDT [6428] WARNING:  HERE 1222: csquared=1.000000 minIO/R-P-C=108.500000 maxIO/R-P-C=4416.000000 costsize.c cost_index 702
=> csquared=1, so min_IO cost is used instead of something close to max_IO
(this patch doesn't change the computation of those values at all, just changes
correlation, which squared value is used to interpolate between correlated/min
cost and uncorrelated/max cost).

correlated estimate: 108 seeks vs 99 actual, is essentially what unpatched
postgres would've computed by using the table correlation of 0.9952, implicitly
assuming the index to be similarly correlated.

I hope that demonstrates the need to distinguish index correlation from table
correlation.  I'm hoping for comments on the existing patch, specifically if
there's a better way to sample the index than "MCVs or partial index scan".
I've left some fragments in place of earlier implementation involving btree
page level fragmentation (like statindex).  Also: does it make sense to keeping
MCV/histogram for non-expression index which duplicates table column ?  The
stats lookup in selfuncs.c btcostestimate() would have to check for correlation
from index, and rest of stats from its table.

A bitmap layer adds overhead, which should be avoided if not needed.  But it
shouldn't be a huge impact, and I think its relative effect is only high when
returning a small number of rows.  I'm thinking of a few cases.

 - unique / low cardinality index scans or without duplicate keys: should have
   low index_pages_fetched(), so max_IO_cost should not be very different from
   min_io_cost, and new index-based correlation shouldn't have much effect
   different from table correlation.
 - unclustered/uncorrelated tables: tables whose heap have low correlation
   already discouraged from index scan; this includes tables whose column is
   UPDATEd and not just INSERTed;
 - table with correlated heap AND index: csquared should still be ~0.99 and not
   change much;
 - correlated table with uncorrelated index: this is the target case with
   intended behavior change

My apologies: I think that's a bit of a brain dump.

Justin
diff --git a/src/backend/commands/analyze.c b/src/backend/commands/analyze.c
index 2b63827..1acf118 100644
--- a/src/backend/commands/analyze.c
+++ b/src/backend/commands/analyze.c
@@ -98,6 +98,11 @@ static int	compare_rows(const void *a, const void *b);
 static int acquire_inherited_sample_rows(Relation onerel, int elevel,
 							  HeapTuple *rows, int targrows,
 							  double *totalrows, double *totaldeadrows);
+static int acquire_sample_index(Relation onerel, Relation index, int elevel,
+					HeapTuple *rows, int targrows,
+					double *totalrows, double *totaldeadrows);
+static double correlation(int values_cnt, double corr_xysum);
+static double idx_correlation (Oid indexoid, VacAttrStatsP stats, int targrows, int num_mcvs, Datum *mcv_values);
 static void update_attstats(Oid relid, bool inh,
 				int natts, VacAttrStats **vacattrstats);
 static Datum std_fetch_func(VacAttrStatsP stats, int rownum, bool *isNull);
@@ -206,6 +211,7 @@ analyze_rel(Oid relid, RangeVar *relation, int options,
 	 * used to do this in get_rel_oids() but seems safer to check after we've
 	 * locked the relation.
 	 */
+	// TODO: if (onerel->rd_rel->relkind == RELKIND_INDEX) => needs a separate sample_rows function?
 	if (onerel->rd_rel->relkind == RELKIND_RELATION ||
 		onerel->rd_rel->relkind == RELKIND_MATVIEW)
 	{
@@ -433,37 +439,41 @@ do_analyze_rel(Relation onerel, int options, VacuumParams *params,
 		{
 			AnlIndexData *thisdata = &indexdata[ind];
 			IndexInfo  *indexInfo;
+			ListCell   *indexpr_item;
 
 			thisdata->indexInfo = indexInfo = BuildIndexInfo(Irel[ind]);
 			thisdata->tupleFract = 1.0; /* fix later if partial */
-			if (indexInfo->ii_Expressions != NIL && va_cols == NIL)
+			if (va_cols != NIL)
 			{
-				ListCell   *indexpr_item = list_head(indexInfo->ii_Expressions);
+				continue;
+			}
 
-				thisdata->vacattrstats = (VacAttrStats **)
+			indexpr_item = list_head(indexInfo->ii_Expressions);
+			thisdata->vacattrstats = (VacAttrStats **)
 					palloc(indexInfo->ii_NumIndexAttrs * sizeof(VacAttrStats *));
-				tcnt = 0;
-				for (i = 0; i < indexInfo->ii_NumIndexAttrs; i++)
-				{
-					int			keycol = indexInfo->ii_KeyAttrNumbers[i];
+			tcnt = 0;
+			for (i = 0; i < indexInfo->ii_NumIndexAttrs; i++)
+			{
+				int			keycol = indexInfo->ii_KeyAttrNumbers[i];
+				Node	   		*indexkey=NULL;
 
-					if (keycol == 0)
-					{
-						/* Found an index expression */
-						Node	   *indexkey;
-
-						if (indexpr_item == NULL)	/* shouldn't happen */
-							elog(ERROR, "too few entries in indexprs list");
-						indexkey = (Node *) lfirst(indexpr_item);
-						indexpr_item = lnext(indexpr_item);
-						thisdata->vacattrstats[tcnt] =
-							examine_attribute(Irel[ind], i + 1, indexkey);
-						if (thisdata->vacattrstats[tcnt] != NULL)
-							tcnt++;
-					}
+				if (keycol == 0)
+				{
+					/* Found an index expression */
+					if (indexpr_item == NULL)	/* shouldn't happen */
+						elog(ERROR, "too few entries in indexprs list");
+					indexkey = (Node *) lfirst(indexpr_item);
+					indexpr_item = lnext(indexpr_item);
 				}
-				thisdata->attr_cnt = tcnt;
+
+				thisdata->vacattrstats[tcnt] =
+					examine_attribute(Irel[ind], i + 1, indexkey);
+
+				if (thisdata->vacattrstats[tcnt] != NULL)
+					tcnt++;
 			}
+
+			thisdata->attr_cnt = tcnt;
 		}
 	}
 
@@ -548,11 +558,38 @@ do_analyze_rel(Relation onerel, int options, VacuumParams *params,
 			MemoryContextResetAndDeleteChildren(col_context);
 		}
 
+# if 0
+		for (ind = 0; ind < nindexes; ind++)
+		{
+			int						indnumrows;
+			double					indtotalrows,
+									indtotaldeadrows;
+			HeapTuple  *indrows= palloc(targrows * sizeof(HeapTuple));
+			/*
+			 * Attempted to do an index scan for each index, in order to get
+			 * correllation stats of the HEAP ; I was thinking
+			 * (probably incorrectly) that the high random cost was
+			 * due to index seeks, and that it was needed to
+			 * traverse the index in logical rather than physical
+			 * order to determine its correction.  But the planner
+			 * already assumes that index reads are random.
+			 */
+
+			indnumrows = acquire_sample_index (onerel, Irel[ind], elevel,
+					indrows, targrows, &indtotalrows, &indtotaldeadrows);
+			compute_index_stats(Irel[ind], indnumrows,
+					indexdata+ind, 1, /* XXX: should update c_i_s to do one index only? */
+					indrows, indnumrows,
+					col_context);
+
+		}
+# else
 		if (hasindex)
-			compute_index_stats(onerel, totalrows,
-								indexdata, nindexes,
-								rows, numrows,
-								col_context);
+			compute_index_stats(onerel, numrows,
+					indexdata, nindexes,
+					rows, numrows,
+					col_context);
+# endif
 
 		MemoryContextSwitchTo(old_context);
 		MemoryContextDelete(col_context);
@@ -721,10 +758,6 @@ compute_index_stats(Relation onerel, double totalrows,
 					rowno;
 		double		totalindexrows;
 
-		/* Ignore index if no columns to analyze and not partial */
-		if (attr_cnt == 0 && indexInfo->ii_Predicate == NIL)
-			continue;
-
 		/*
 		 * Need an EState for evaluation of index expressions and
 		 * partial-index predicates.  Create it in the per-index context to be
@@ -767,6 +800,7 @@ compute_index_stats(Relation onerel, double totalrows,
 				if (!ExecQual(predicate, econtext))
 					continue;
 			}
+
 			numindexrows++;
 
 			if (attr_cnt > 0)
@@ -790,6 +824,7 @@ compute_index_stats(Relation onerel, double totalrows,
 					VacAttrStats *stats = thisdata->vacattrstats[i];
 					int			attnum = stats->attr->attnum;
 
+					stats->rows=rows;
 					if (isnull[attnum - 1])
 					{
 						exprvals[tcnt] = (Datum) 0;
@@ -815,7 +850,7 @@ compute_index_stats(Relation onerel, double totalrows,
 		totalindexrows = ceil(thisdata->tupleFract * totalrows);
 
 		/*
-		 * Now we can compute the statistics for the expression columns.
+		 * Now we can compute the statistics.
 		 */
 		if (numindexrows > 0)
 		{
@@ -830,11 +865,16 @@ compute_index_stats(Relation onerel, double totalrows,
 				stats->exprvals = exprvals + i;
 				stats->exprnulls = exprnulls + i;
 				stats->rowstride = attr_cnt;
+// Low stats target for non-expr indices to avoid having an duplicate MCV and/or hist ?
+// avoid keeping an (duplicate) MCV list or
+// histogram for non-expression columns?
+// if (indexInfo->ii_KeyAttrNumbers[i]!=0) // && stats->attr->attstattarget!=0)
+// stats->attr->attstattarget=0;
+
 				(*stats->compute_stats) (stats,
 										 ind_fetch_func,
 										 numindexrows,
 										 totalindexrows);
-
 				/*
 				 * If the n_distinct option is specified, it overrides the
 				 * above computation.  For indices, we always use just
@@ -896,7 +936,7 @@ examine_attribute(Relation onerel, int attnum, Node *index_expr)
 	/*
 	 * When analyzing an expression index, believe the expression tree's type
 	 * not the column datatype --- the latter might be the opckeytype storage
-	 * type of the opclass, which is not interesting for our purposes.  (Note:
+	 * type of the opclass, which is not interesting for our purposes.  XXX (Note:
 	 * if we did anything with non-expression index columns, we'd need to
 	 * figure out where to get the correct type info from, but for now that's
 	 * not a problem.)	It's not clear whether anyone will care about the
@@ -1478,6 +1518,305 @@ acquire_inherited_sample_rows(Relation onerel, int elevel,
 }

+// this doesn't work, since broad/course correlation doesn't well represent
+// non-sequential heap page access which may happen at a small scale..
+static int
+acquire_sample_index(Relation onerel, Relation index, int elevel,
+					HeapTuple *rows, int targrows,
+					double *totalrows, double *totaldeadrows)
+{
+	int			numrows = 0;	/* # rows now in reservoir */
+	double		samplerows = 0; /* total # rows collected */
+	double		rowstoskip = -1;	/* -1 means not set yet */
+
+	HeapTuple       targtuple;
+	// Snapshot        snapshot = RegisterSnapshot(GetTransactionSnapshot());
+	// Snapshot        snapshot = GetLatestSnapshot();
+	Snapshot        snapshot = GetActiveSnapshot();
+	// Snapshot        snapshot = GetOldestSnapshot();
+
+	/* Prepare for sampling rows */
+	ReservoirStateData rstate;
+	IndexScanDesc index_scan;
+	reservoir_init_selection_state(&rstate, targrows);
+
+	// ScanKeyData	scankeys[1];
+	// ScanKeyEntryInitialize(scankeys, SK_ISNULL|SK_SEARCHNOTNULL, 1, InvalidStrategy, InvalidOid, InvalidOid, InvalidOid, (Datum) 0);
+	// XXX search not null ??
+	// SK_SEARCHNOTNULL
+	index_scan= index_beginscan(onerel, index, snapshot, 0, 0);
+	// index_rescan(index_scan, scankeys, 0, NULL, 0);
+	index_rescan(index_scan, NULL, 0, NULL, 0);
+
+	// while ((targtuple = index_getnext(index_scan, ForwardScanDirection)) != NULL)
+	// XXX: it's pretty unfortunate to do a full index scan for each table
+	// being analyzed ... esp. since a design goal is to avoid very
+	// inefficient random read patterns during index scans...  consider
+	// alternatives like index scanning for each MCV ?  However I suspect
+	// that would tend to strongly underestimate correlation in some cases
+	// and too strongly discourage index scans..
+	// Probably go back to a block sample of leaf pages, counting the
+	// linearity of its referenced heap blocks within an index page, but
+	// not from one index page to another???
+
+	// for (unsigned long int c=0; (targtuple = index_getnext(index_scan, BackwardScanDirection)) != NULL ; ++c) // Is there a more useful value to use here ???
+	for (unsigned long int c=0; (targtuple = index_getnext(index_scan, ForwardScanDirection)) != NULL ; ++c) // Is there a more useful value to use here ???
+	// ItemPointer tid;
+	// while ((tid = index_getnext_tid(index_scan, ForwardScanDirection)) != NULL)
+	{
+		HeapTuple h = heap_copytuple(targtuple);
+
+		// ItemPointerSet(&(h->t_self), c>>16, c&0xffff );
+		// index_fetch_heap(index_scan);
+
+		ItemPointerSet(&(h->t_self), c>>16, c&0xffff ); // no good, the correlation of heap value WRT index location is 100% ...
+		// h->t_self.ip_blkid.bi_lo=c&0xffff; // >>8; // ItemPointerSet(&(h->t_self), c>>16, c&0xffff );
+
+		/* Vitter's algorithm, see above */
+		// ItemPointerSetBlockNumber(&h->t_self, c);
+		// ItemPointerSetOffsetNumber(&h->t_self, c);
+		// h->t_self.ip_blkid.bi_hi=c>>16;
+		// h->t_self.ip_blkid.bi_lo=c&OffsetNumberMask;
+		// h->t_self.ip_blkid.bi_hi+=c/30;
+
+		if (numrows < targrows) {
+			rows[numrows++] = h;
+			samplerows += 1;
+			continue;
+		}
+
+		if (rowstoskip < 0)
+			rowstoskip = reservoir_get_next_S(&rstate, samplerows, targrows);
+
+		if (rowstoskip <= 0)
+		{
+			int k = (int) (targrows * sampler_random_fract(rstate.randstate));
+
+			Assert(k >= 0 && k < targrows);
+			heap_freetuple(rows[k]);
+			rows[k] = h;
+		}
+
+		rowstoskip -= 1;
+		samplerows += 1;
+	}
+
+	index_endscan(index_scan);
+
+	if (numrows == targrows)
+		qsort((void *) rows, numrows, sizeof(HeapTuple), compare_rows);
+
+	*totalrows = samplerows;
+	// totalblocks = RelationGetNumberOfBlocks(onerel);
+	// *totalrows = vac_estimate_reltuples(onerel, true, totalblocks, bs.m, liverows);
+	// if (bs.m > 0)
+	// 	*totaldeadrows = floor((deadrows / bs.m) * totalblocks + 0.5);
+	// else
+	// 	*totaldeadrows = 0.0;
+
+	ereport(elevel,
+			(errmsg("\"%s\": scanned %d of %u pages, "
+					"containing %.0f live rows and %.0f dead rows; "
+					"%d rows in sample, %.0f estimated total rows",
+					RelationGetRelationName(index),
+					-1, -1,
+					-1.0, -1.0,
+					numrows, *totalrows)));
+
+
+	return numrows ;
+}
+
+/*
+ * Return correlation coeffiecient given sum(x*y), where x is a list giving
+ * sort with values order by one thing, and y is list given order sorted by
+ * another thing (eg. heap value vs. heap location).
+ */
+static double
+correlation(int values_cnt, double corr_xysum)
+{
+	/*----------
+	 * Since we know the x and y value sets are both
+	 *		0, 1, ..., values_cnt-1
+	 * we have sum(x) = sum(y) =
+	 *		(values_cnt-1)*values_cnt / 2
+	 * and sum(x^2) = sum(y^2) =
+	 *		(values_cnt-1)*values_cnt*(2*values_cnt-1) / 6.
+	 *----------
+	 * ... and the correlation coefficient reduces to */
+	double corr_xsum = ((double) (values_cnt - 1)) *
+		((double) values_cnt) / 2.0;
+	double corr_x2sum = ((double) (values_cnt - 1)) *
+		((double) values_cnt) * (double) (2 * values_cnt - 1) / 6.0;
+
+	return (values_cnt * fabs(corr_xysum) - corr_xsum * corr_xsum) /
+		(values_cnt * corr_x2sum - corr_xsum * corr_xsum);
+}
+
+/*
+ * Compute avg of separately-computed correlation values, rather than
+ * correlation of single sample across entire table, which overestimates
+ * correlation for large tables.  targrows is the number of pages to sample in
+ * each batch.
+ */
+static double
+idx_correlation (Oid indexoid, VacAttrStatsP stats, int targrows, int num_mcvs, Datum *mcv_values)
+{
+	HeapTuple 	*rows= stats->rows; // reusing this allocation
+	double		corr_sum=0;
+	int		corr_samples=0;
+	int		numrows = 0;
+	double		deadrows = 0;
+	double		liverows = 0;
+	long int	batch;
+	double		samplerows = 0;
+
+	Snapshot        snapshot = GetActiveSnapshot();
+	Oid		heapoid = IndexGetRelation(indexoid, false);
+	Relation	heap = relation_open(heapoid, AccessShareLock);
+	Relation	index= RelationIdGetRelation(indexoid);
+	IndexScanDesc	index_scan = index_beginscan(heap, index, snapshot, 1, 0);
+
+	// int strategy=BTGreaterEqualStrategyNumber;
+	// Oid opfam=get_opfamily_member(opfamily, stats->attrtypid, stats->attrtypid, BTGreaterEqualStrategyNumber);
+
+	/* For sampling: read the first TARGROWS TIDs from each value in the MCV list */
+	// XXX: consider only the first handful of MCVs ?
+	// XXX: poor correlation in index can prolly happen without MCVs, eg. normally-distributed float values without repeated keys */
+	// XXX: .. should we just read the first targrows TIDs returned by the index or is there a better way ??
+
+	for (batch=0; batch<num_mcvs || (!num_mcvs && !batch); ) { // XXX: protect against empty index ?
+		ScanKeyData	scankeys;
+		double		corr_xysum=0;
+		ItemPointer	tid;
+
+		if (num_mcvs) {
+			// XXX: GreaterEqual ?
+			ScanKeyInit(&scankeys, stats->attr->attnum, BTEqualStrategyNumber, get_opcode( ((StdAnalyzeData *)stats->extra_data)->eqopr), mcv_values[batch]);
+		} else {
+			/* No MCVs: single iteration over first targrows tuples returned by index */
+			// XXX SK_SEARCHNOTNULL
+			ScanKeyEntryInitialize(&scankeys, SK_ISNULL|SK_SEARCHNOTNULL, stats->attr->attnum, InvalidStrategy, InvalidOid, InvalidOid, InvalidOid, (Datum)0);
+		}
+
+		index_rescan(index_scan, &scankeys, 1, NULL, 0);
+		for ( ; numrows<targrows && NULL!=(tid=index_getnext_tid(index_scan, ForwardScanDirection)); samplerows++) {
+			if (!ItemPointerIsValid(tid)) {
+				// Shouldn't happen ?
+				deadrows++;
+				continue;
+			}
+
+			// elog(WARNING, "%s %s %d TID: %d,%d", __FILE__, __FUNCTION__, __LINE__, ItemPointerGetBlockNumber(tid), ItemPointerGetOffsetNumber(tid) );
+			rows[numrows]->t_self = *tid;
+			rows[numrows]->t_len=numrows; // abusing this field;
+			numrows++;
+			liverows++;
+		}
+
+		// avoid NaN if many dead tuples? if (!numrows) continue;
+
+		/* Retrieved consecutive TIDs, now compute their (fine-level) correlation */
+		qsort((void *) rows, numrows, sizeof(*rows), compare_rows);
+		for (int j=0; j<numrows; ++j)
+			corr_xysum+=j*rows[j]->t_len;
+
+		corr_samples++;
+		corr_sum+=correlation(numrows, corr_xysum);
+
+		numrows=0;
+		++batch;
+		if (tid==NULL)
+			break;
+			/* Ran out of index in fewer than targrows */
+	}
+
+	ereport(LOG,
+			(errmsg("\"%s(%s)\": scanned %ld batches with total %.0f TIDs, "
+					"containing %.0f live and %.0f dead TIDs; ",
+					RelationGetRelationName(index),
+					NameStr(stats->attr->attname),
+					batch, samplerows,
+					liverows, deadrows)));
+
+	index_endscan(index_scan);
+	relation_close(index, NoLock);
+	relation_close(heap, NoLock);
+	return corr_sum/corr_samples;
+}
+
+#define IS_INDEX(r) ((r)->rd_rel->relkind == RELKIND_INDEX)
+#define IS_BTREE(r) ((r)->rd_rel->relam == BTREE_AM_OID)
+
+/*
+ * Do a Vitter block walk along entire index, in physical order, to determine
+ * fraction of LEAF nodes which have "next" pointers with a higher block number
+ * than themselves..  For a highly-correlated table, this will be ~1, for a
+ * poorly correlated table(???), or one with many repeated keys, this will be
+ * between 0 and ~0.5, and index scan across those duplicate keys will have a
+ * high random component.
+ * Logic bits stolen from pgstatindex.
+ */
+
+#include "access/nbtree.h"
+#include "catalog/pg_am.h"
+
+static double
+idx_corr_fudge(Relation index, int targrows)
+{
+	BlockNumber totalblocks;
+	BlockSamplerData bs;
+
+	double leaf_pages = 0;
+	double fragments = 0;
+
+	// TransactionId OldestXmin;
+	// OldestXmin = GetOldestXmin(onerel, PROCARRAY_FLAGS_VACUUM);
+	// Snapshot        snapshot = RegisterSnapshot(GetTransactionSnapshot());
+	// Snapshot        snapshot = GetLatestSnapshot();
+	// Snapshot        snapshot = GetActiveSnapshot();
+	// Snapshot        snapshot = GetOldestSnapshot();
+	if (!IS_BTREE(index)) {
+		relation_close(index, AccessShareLock);
+		return 1;
+	}
+
+	totalblocks = RelationGetNumberOfBlocks(index);
+	BlockSampler_Init(&bs, totalblocks-1, targrows, random());
+
+	while (BlockSampler_HasMore(&bs))
+	{
+		BlockNumber blkno = BlockSampler_Next(&bs);
+		Buffer		buffer;
+		Page		page;
+		BTPageOpaque opaque;
+
+		vacuum_delay_point();
+		CHECK_FOR_INTERRUPTS();
+
+		buffer = ReadBufferExtended(index, MAIN_FORKNUM, blkno, RBM_NORMAL, vac_strategy); // bstrategy
+		LockBuffer(buffer, BUFFER_LOCK_SHARE);
+
+		page = BufferGetPage(buffer);
+		opaque = (BTPageOpaque) PageGetSpecialPointer(page);
+
+		if (P_ISDELETED(opaque) || P_IGNORE(opaque))
+			continue;
+		else if (P_ISLEAF(opaque))
+		{
+			leaf_pages++;
+			if (opaque->btpo_next != P_NONE && opaque->btpo_next < blkno)
+				fragments++;
+		}
+
+		UnlockReleaseBuffer(buffer);
+
+	}
+
+	relation_close(index, AccessShareLock);
+	return fragments/leaf_pages;
+}
+
 /*
  *	update_attstats() -- update attribute statistics for one relation
  *
@@ -1658,6 +1997,7 @@ ind_fetch_func(VacAttrStatsP stats, int rownum, bool *isNull)
 	/* exprvals and exprnulls are already offset for proper column */
 	i = rownum * stats->rowstride;
 	*isNull = stats->exprnulls[i];
+
 	return stats->exprvals[i];
 }
 
@@ -2258,7 +2598,7 @@ compute_scalar_stats(VacAttrStatsP stats,
 							  stats->attrtype->typlen == -1);
 	bool		is_varwidth = (!stats->attrtype->typbyval &&
 							   stats->attrtype->typlen < 0);
-	double		corr_xysum;
+	double		corr_xysum=0;
 	SortSupportData ssup;
 	ScalarItem *values;
 	int			values_cnt = 0;
@@ -2352,10 +2692,17 @@ compute_scalar_stats(VacAttrStatsP stats,
 					dups_cnt;
 		int			slot_idx = 0;
 		CompareScalarsContext cxt;
+		float4	   *corrs;
 
 		/* Sort the collected values */
 		cxt.ssup = &ssup;
 		cxt.tupnoLink = tupnoLink;
+
+		/*
+		 * tuples were previously sorted by TID; now, sort by heap
+		 * value, as needed for stats computations, and, for order
+		 * relative to original sort for correlation computation.
+		 */
 		qsort_arg((void *) values, values_cnt, sizeof(ScalarItem),
 				  compare_scalars, (void *) &cxt);
 
@@ -2378,7 +2725,6 @@ compute_scalar_stats(VacAttrStatsP stats,
 		 * is the last item of its group of duplicates (since the group will
 		 * be ordered by tupno).
 		 */
-		corr_xysum = 0;
 		ndistinct = 0;
 		nmultiple = 0;
 		dups_cnt = 0;
@@ -2566,11 +2912,11 @@ compute_scalar_stats(VacAttrStatsP stats,
 			}
 		}
 
+		Datum	   *mcv_values=NULL;
 		/* Generate MCV slot entry */
 		if (num_mcv > 0)
 		{
 			MemoryContext old_context;
-			Datum	   *mcv_values;
 			float4	   *mcv_freqs;
 
 			/* Must copy the target values into anl_context */
@@ -2713,37 +3059,42 @@ compute_scalar_stats(VacAttrStatsP stats,
 			slot_idx++;
 		}
 
-		/* Generate a correlation entry if there are multiple values */
-		if (values_cnt > 1)
-		{
+		/* Will generate a correlation entry if there are multiple values */
+		if (values_cnt>1) {
 			MemoryContext old_context;
-			float4	   *corrs;
-			double		corr_xsum,
-						corr_x2sum;
-
-			/* Must copy the target values into anl_context */
 			old_context = MemoryContextSwitchTo(stats->anl_context);
+			/* Must copy the target values into anl_context */
 			corrs = (float4 *) palloc(sizeof(float4));
 			MemoryContextSwitchTo(old_context);
+		}
 
-			/*----------
-			 * Since we know the x and y value sets are both
-			 *		0, 1, ..., values_cnt-1
-			 * we have sum(x) = sum(y) =
-			 *		(values_cnt-1)*values_cnt / 2
-			 * and sum(x^2) = sum(y^2) =
-			 *		(values_cnt-1)*values_cnt*(2*values_cnt-1) / 6.
-			 *----------
-			 */
-			corr_xsum = ((double) (values_cnt - 1)) *
-				((double) values_cnt) / 2.0;
-			corr_x2sum = ((double) (values_cnt - 1)) *
-				((double) values_cnt) * (double) (2 * values_cnt - 1) / 6.0;
-
-			/* And the correlation coefficient reduces to */
-			corrs[0] = (values_cnt * corr_xysum - corr_xsum * corr_xsum) /
-				(values_cnt * corr_x2sum - corr_xsum * corr_xsum);
+		if (values_cnt>1 && fetchfunc==ind_fetch_func) { /* && num_mcv>0) { */
+			/* Compute alternate/fine-grained correlation if there are MCV list with repeated values... */
+			// elog(WARNING, "%s %s %d value0:%lu", __FILE__, __FUNCTION__, __LINE__, num_mcv?mcv_values[0] : 1 );
+			corrs[0] = idx_correlation (stats->attr->attrelid, stats, samplerows, num_mcv, mcv_values);
+			elog(WARNING, "%s %s %d cors %lf", __FILE__, __FUNCTION__, __LINE__, corrs[0]);
+			stats->stakind[slot_idx] = STATISTIC_KIND_CORRELATION;
+			stats->staop[slot_idx] = mystats->ltopr;
+			stats->stanumbers[slot_idx] = corrs;
+			stats->numnumbers[slot_idx] = 1;
+			slot_idx++;
+		}
+		else if (values_cnt>1) // XXX && fetchfunc==ind_fetch_func?  // correlation is now strictly a per-index attribute and not an per-column one
+		{
+			double fudge=1;
+
+			if (fetchfunc==ind_fetch_func) {
+				/* Compute correlation fudge factor for indices with
+				 * high number of duplicate values for an index column,
+				 * causing index scan to be highly random, due to btree
+				 * random insertion logic being used to avoid O(N^2)
+				 * insertion behavior in that case.
+				 */
+				fudge = 1-idx_corr_fudge(RelationIdGetRelation(stats->attr->attrelid), samplerows);
+			}
 
+			corrs[0] = correlation(values_cnt, corr_xysum);
+			// XXX: corrs[0] *= fudge;
 			stats->stakind[slot_idx] = STATISTIC_KIND_CORRELATION;
 			stats->staop[slot_idx] = mystats->ltopr;
 			stats->stanumbers[slot_idx] = corrs;
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index eb653cf..4529725 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -693,8 +693,13 @@ cost_index(IndexPath *path, PlannerInfo *root, double loop_count,
 	/*
 	 * Now interpolate based on estimated index order correlation to get total
 	 * disk I/O cost for main table accesses.
+	 * Note the sign of this expression: as csquared approaches 0, the
+	 * estimate approaches max_IO_cost estimate;
 	 */
 	csquared = indexCorrelation * indexCorrelation;
+	elog(WARNING, "HERE 1222: csquared=%f minIO/R-P-C=%f maxIO/R-P-C=%f %s %s %d",
+			csquared, min_IO_cost/spc_random_page_cost, max_IO_cost/spc_random_page_cost,
+			__FILE__, __FUNCTION__, __LINE__);
 
 	run_cost += max_IO_cost + csquared * (min_IO_cost - max_IO_cost);
 
diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
index e103f5e..f097580 100644
--- a/src/backend/utils/adt/selfuncs.c
+++ b/src/backend/utils/adt/selfuncs.c
@@ -6874,9 +6874,34 @@ btcostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
 	 */
 	MemSet(&vardata, 0, sizeof(vardata));
 
-	if (index->indexkeys[0] != 0)
+	/* Expression --- maybe there are stats for the index itself */
+	relid = index->indexoid;
+	colnum = 1;
+	if (get_index_stats_hook &&
+		(*get_index_stats_hook) (root, relid, colnum, &vardata))
+	{
+		/*
+		 * The hook took control of acquiring a stats tuple.  If it did
+		 * supply a tuple, it'd better have supplied a freefunc.
+		 */
+		elog(WARNING, "HERE 1223: indexCorrelation %s %s %d", __FILE__, __FUNCTION__, __LINE__);
+
+		if (HeapTupleIsValid(vardata.statsTuple) &&
+			!vardata.freefunc)
+			elog(ERROR, "no function provided to release variable stats with");
+	}
+	else if ( NULL != (vardata.statsTuple = SearchSysCache3(STATRELATTINH,
+											 ObjectIdGetDatum(relid),
+											 Int16GetDatum(colnum),
+											 BoolGetDatum(false))))
+	{
+		elog(WARNING, "HERE 1224: indexCorrelation %s %s %d", __FILE__, __FUNCTION__, __LINE__);
+		vardata.freefunc = ReleaseSysCache;
+	}
+	else if (index->indexkeys[0] != 0)
 	{
 		/* Simple variable --- look to stats for the underlying table */
+		elog(WARNING, "HERE 1225: indexCorrelation %s %s %d", __FILE__, __FUNCTION__, __LINE__);
 		RangeTblEntry *rte = planner_rt_fetch(index->rel->relid, root);
 
 		Assert(rte->rtekind == RTE_RELATION);
@@ -6904,32 +6929,6 @@ btcostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
 			vardata.freefunc = ReleaseSysCache;
 		}
 	}
-	else
-	{
-		/* Expression --- maybe there are stats for the index itself */
-		relid = index->indexoid;
-		colnum = 1;
-
-		if (get_index_stats_hook &&
-			(*get_index_stats_hook) (root, relid, colnum, &vardata))
-		{
-			/*
-			 * The hook took control of acquiring a stats tuple.  If it did
-			 * supply a tuple, it'd better have supplied a freefunc.
-			 */
-			if (HeapTupleIsValid(vardata.statsTuple) &&
-				!vardata.freefunc)
-				elog(ERROR, "no function provided to release variable stats with");
-		}
-		else
-		{
-			vardata.statsTuple = SearchSysCache3(STATRELATTINH,
-												 ObjectIdGetDatum(relid),
-												 Int16GetDatum(colnum),
-												 BoolGetDatum(false));
-			vardata.freefunc = ReleaseSysCache;
-		}
-	}
 
 	if (HeapTupleIsValid(vardata.statsTuple))
 	{

---

From: Peter Geoghegan <[email-masked]>
Date: Fri, 7 Jul 2017 20:27:02 -0700

> large number of random reads, but not included in planner cost.

All of that may well be true, but I've actually come around to the
view that we should treat TID as a first class part of the keyspace,
that participates in comparisons as an implicit last column in all
cases (not just when B-Trees are built within tuplesort.c). That would
probably obviate the need for a patch like this entirely, because
pg_stats.correlation would be unaffected by duplicates. I think that
this would have a number of advantages, some of which might be
significant. For example, I think it could make LP_DEAD cleanup within
nbtree more effective for some workloads, especially workloads where
it is important for HOT pruning and LP_DEAD cleanup to work in concert
-- locality of access probably matters with that. Also, with every
entry in the index guaranteed to be unique, we can imagine VACUUM
being much more selective with killing index entries, when the TID
array it uses happens to be very small. With the freeze map stuff
that's now in place, being able to do that matters more than before.

The original Lehman & Yao algorithm is supposed to have unique keys in
all cases, but we don't follow that in order to make duplicates work,
which is implemented by changing an invariant (see nbtree README for
details). So, this could simplify some aspects of how binary searches
must work in the face of having to deal with non-unique keys. I think
that there are cases where many non-HOT UPDATEs have to go through a
bunch of duplicate leaf tuples and do visibility checking on old
versions for no real benefit. With the TID as part of the keyspace, we
could instead tell the B-Tree code to insert a new tuple as part of an
UPDATE while using the TID as part of its insertion scan key, so
rummaging through many duplicates is avoided.

That having been said, it would be hard to do this for all the reasons
I went into in that thread you referenced [1]. If you're going to
treat TID as a part of the keyspace, you have to totally embrace that,
which means that the internal pages need to have heap TIDs too (not
just pointers to the lower levels in the B-Tree, which the
IndexTuple's t_tid pointer is used for there). Those are the place
where you need to literally append this new, implicit heap TID column
as if it was just another user-visible attribute, since that
information isn't stored in the internal pages today at all. Doing
that has a cost, which isn't going to be acceptable if we naively
append a heap TID to every internal page IndexTuple. With a type like
int4, you're going to completely bloat those pages, with big
consequences for fan-in.

So, really, what needs to happen to make it work is someone needs to
write a suffix truncation patch, which implies that only those cases
that actually benefit from increasing the width of internal page
IndexTuples (those with many "would-be duplicates") pay the cost. This
is a classic technique, that I've actually already prototyped, though
that's extremely far from being worth posting here. That was just to
verify my understanding.

I think that I should write and put up for discussion a design
document for various nbtree enhancements. These include internal page
suffix truncation, prefix compression, and key normalization. I'm
probably not going to take any of these projects on, but it would be
useful if there was at least a little bit of clarity about how they
could be implemented. Maybe we could reach some kind of weak consensus
without going to great lengths. These optimizations are closely
intertwined things, and the lack of clarity on how they all fit
together is probably holding back an implementation of any one of
them.

[1] https://www.postgresql.org/message-id/flat/[email-masked]
-- 
Peter Geoghegan