Understanding correlation in PostgreSQL

user_1863229 0
Viewed 1182

When a database has to perform a join to another table, it may broadly choose from one of the three following strategies:

  • sequential scan (when we want most of the records)
  • bitmap index scan (when we want some of the records)
  • index scan (when we want relatively few records, with a correlated index)

The reasoning here is that if most records need to be retained, it is more efficient to completely ignore the index, avoid I/O penalties, and just read the entire table sequentially. At the other extreme, clearly if we just need to read a few leaf nodes from an index, this would be faster than reading the entire table.

What is not clear to me is what role correlation plays here, and how we should be thinking about it.

Focusing on Postgres, the documentation describes correlation here:

Statistical correlation between physical row ordering and logical ordering of the column values. This ranges from -1 to +1. When the value is near -1 or +1, an index scan on the column will be estimated to be cheaper than when it is near zero, due to reduction of random access to the disk. (This column is null if the column data type does not have a < operator.)

Here is a way by which we can obtain a correlation value for each column in a given table:

SELECT attname, correlation
FROM pg_stats
WHERE tablename = 'your_table';

From what I understand, using a secondary index always requires doing an I/O seek to the clustered index, to find the data. As far as I can tell, the only thing which would make I/O better or worse would be if the secondary index were very near to the clustered index on disk. But it is not clear to me how correlation would be significant for determining how costly an I/O seek is, since a seek is always required.

Can someone give an explanation about what correlation physically means here? Perhaps my confusion is arising from not understanding how a database performs an index scan.

correlation indexing postgresql
3 Answers

The correlation only makes sense for columns of a data type that has a total ordering, that is, it supports an operator family that belongs to the btree access method (the <, <=, =, >= and > operators).

The correlation is positive if bigger values tend to occur near the physical end of the table and small values near the beginning. A value of 1 means that the values are stored in the table in sorted order, -1 means that they are stored in descending order.

An index scan in PostgreSQL works like this:

  1. The first matching entry is located in the index.

  2. If the visibility map indicates that the corresponding table block contains only tuples that are visible to everybody and we need no column that is not stored in the index, we have a result and continue with step 4 (if the optimizer thinks that this works for most index entries, it will plan an index only scan).

  3. The corresponding row is fetched from the table and checked for visibility. If it is visible and satisfies the filter condition, we have found a result.

  4. traverse the index in the scan direction to find the next index entry and see if it satisfies the scan condition. If yes, go back to the second step, else we are done.

This causes random reads of table blocks, unless they are already in shared buffers.

Now if the correlation is high, two things are more likely to happen:

  • The next tuple found in the index scan is in the same table block as the previous tuple. Then it is already in shared buffers and does not cause a read.

    All in all, you'll end up hitting fewer distinct table blocks: the index entries next to each other tend to be close to each other too, often in the same block.

  • If the next index entry does not point to the same table block as the previous one, it is likely to point to the next table block. This leads to sequential reads of the table blocks, which on spinning disks is more efficient than random reads.

Let me illustrate that with an example, assuming an index on a perfectly correlated column:

The first index entry found points to table block 42, the second one too, the third to the 30th one point to block 43, the next 20 index entries will point to block 44.

So the index scan will visit 50 tuples, but it will only read 3 blocks from disk, and these it reads in sequential order (first block 42, then block 43, then block 44).

If there were no correlation, the 50 tuples would likely be in different table blocks (assuming the table is large), which would mean 50 random disk reads.

So index scans are cheaper when the correlation is high, and backwards index scans are cheaper if the correlation is low. The optimizer uses the correlation to adjust the estimated costs accordingly.

user_64643080

I think the real definition could be found by reading the source ;-)

  • The statistics collector probably uses {ctid,attribvalue} pairs to estimate the physical<-->logical correlation
  • The planner may use these coefficents to estimate the number of pages to be fetched

As an example, here are the stats for my twitter-sucker-DB, running on a Raspberry Pi: (currently circa 3.5M rows)

\connect twitters

SELECT version();
SELECT count(*) from tweets;

\d tweets

SELECT attname, correlation, n_distinct -- , null_frac
FROM pg_stats
WHERE tablename = 'tweets'
AND schemaname = 'public';

You are now connected to database "twitters" as user "postgres".
                                                          version                                                           
----------------------------------------------------------------------------------------------------------------------------
 PostgreSQL 9.6.9 on armv6l-unknown-linux-gnueabihf, compiled by gcc (Raspbian 6.3.0-18+rpi1+deb9u1) 6.3.0 20170516, 32-bit
(1 row)

  count  
---------
 3525068
(1 row)

                                      Table "public.tweets"
     Column     |           Type           |                      Modifiers                       
----------------+--------------------------+------------------------------------------------------
 seq            | bigint                   | not null default nextval('tweets_seq_seq'::regclass)
 id             | bigint                   | not null
 user_id        | bigint                   | not null
 sucker_id      | integer                  | not null default 0
 created_at     | timestamp with time zone | 
 is_dm          | boolean                  | not null default false
 body           | text                     | 
 in_reply_to_id | bigint                   | not null default 0
 parent_seq     | bigint                   | not null default 0
 is_reply_to_me | boolean                  | not null default false
 is_retweet     | boolean                  | not null default false
 did_resolve    | boolean                  | not null default false
 is_stuck       | boolean                  | not null default false
 need_refetch   | boolean                  | not null default false
 is_troll       | boolean                  | not null default false
 fetch_stamp    | timestamp with time zone | not null default now()
Indexes:
    "tweets_pkey" PRIMARY KEY, btree (seq)
    "tweets_id_key" UNIQUE CONSTRAINT, btree (id)
    "tweets_userid_id" UNIQUE, btree (user_id, id)
    "tweets_created_at_idx" btree (created_at)
    "tweets_du_idx" btree (created_at, user_id)
    "tweets_id_idx" btree (id) WHERE need_refetch = true
    "tweets_in_reply_to_id_created_at_idx" btree (in_reply_to_id, created_at) WHERE is_retweet = false AND did_resolve = false AND in_reply_to_id > 0
    "tweets_in_reply_to_id_fp" btree (in_reply_to_id)
    "tweets_parent_seq_fk" btree (parent_seq)
    "tweets_ud_idx" btree (user_id, created_at)
Foreign-key constraints:
    "tweets_parent_seq_fkey" FOREIGN KEY (parent_seq) REFERENCES tweets(seq)
    "tweets_user_id_fkey" FOREIGN KEY (user_id) REFERENCES tweeps(id)
Referenced by:
    TABLE "tweets" CONSTRAINT "tweets_parent_seq_fkey" FOREIGN KEY (parent_seq) REFERENCES tweets(seq)

    attname     | correlation | n_distinct 
----------------+-------------+------------
 seq            |   -0.519016 |         -1  #<<-- PK
 id             |   -0.519177 |         -1  #<<-- NaturalKey
 user_id        |  -0.0994714 |       1024  # FK to tweeps, cadinality ~= 5000)
 sucker_id      |    0.846975 |          5  # Low Card
 created_at     |   -0.519177 |  -0.762477  # High Card
 is_dm          |           1 |          1
 body           |   0.0276537 |  -0.859618
 in_reply_to_id |    0.104481 |      25956  # FK to self
 parent_seq     |    0.954938 |       1986  # FK To self
 is_reply_to_me |           1 |          2
 is_retweet     |    0.595322 |          2
 did_resolve    |    0.909326 |          2
 is_stuck       |           1 |          1
 need_refetch   |           1 |          1
 is_troll       |           1 |          1
 fetch_stamp    |   -0.519572 |      95960  # High Card
(16 rows)

The strange thing here is that the (mostly)ascending columns {seq,id,created_at,fetch_stamp} have negative correlations, the self-reference-FKs {in_reply_to_id,parent_seq} positive ones. My guess is that for n_distinct = -1 (:=unique) columns, the correlation is not used at all, maybe only the sign.

user_9059020

First, we've got several things at play that are making it difficult to fully explain, but I'll try, and pardon me if some of this is just plain obvious to you already.

So, random IOs are expensive because we're reading random blocks of data all over the disk. It's much faster to bulk read several blocks in a row (especially on a magnetic drive, non-ssd)

Now one step further, the docs you're quoting are specifically talking about an index scan, which is typically a range, not an exact value.

So when an index is correlated (can be forced by clustering the table by the index in question), and it's looking for a range of values IE (where Id between 1000000 and 1001000), the locations (block locations) returned by "scanning" the index are going to most likely be in nearly the same location on the disk.

So it can go to index ABC, find the 1000 rows and figure out which blocks it needs to read, and perhaps get them in a very few number of seeks. The 1 (or so) extra seeks to get the index was worth it.

Now, if there is no correlation and it does a seek through the index and finds that those 1000 rows are all in different blocks, in varying locations on the drive, it's going to have to do up to 1000 seeks to find said data. It might have been better to just bulk read the entire table from beginning to end. The extra seeks on the index just made it worse, and bulk reads are now not going to do much to improve the speed.

Please let me know if this helps explain it at all.

user_22839540
Related