Понимание корреляции в PostgreSQL

Question

Когда базе данных необходимо выполнить соединение с другой таблицей, она может широко выбрать одну из трех следующих стратегий:

• последовательное сканирование (когда нам нужно большинство записей)
• сканирование индекса растрового изображения (когда нам нужны некоторые записи)
• сканирование индекса (когда мы хотим относительно небольшое количество записей с коррелированным индексом)

Причина заключается в том, что если необходимо сохранить большинство записей, более эффективно полностью игнорировать индекс, избегать штрафов за ввод-вывод и просто последовательно читать всю таблицу. С другой стороны, очевидно, что если нам просто нужно прочитать несколько конечных узлов из индекса, это будет быстрее, чем чтение всей таблицы.

Что не мне ясно, какую роль здесь играет корреляция и как мы должны думать об этом.

Ориентируясь на Postgres, документация описывает корреляцию здесь:

Статистическая корреляция между физическим упорядочением строк и логическим упорядочением значений столбцов. Это колеблется от -1 до +1. Когда значение около -1 или +1, сканирование индекса по столбцу будет оцениваться дешевле, чем когда оно близко к нулю, из-за сокращения произвольного доступа к диску. (Этот столбец является нулевым, если тип данных столбца не имеет оператора <.) </p>

Вот способ, которым мы можем получить значение корреляции для каждого столбца в данной таблице:

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

Из того, что я понимаю, использование вторичного индекса всегда требует поиска ввода-вывода для кластеризованного индекса, чтобы найти данные. Насколько я могу судить, единственное, что сделало бы ввод-вывод лучше или хуже, было бы, если бы вторичный индекс находился очень близко к кластерному индексу на диске. Но мне не ясно, как корреляция будет существенной для определения того, насколько дорогой поиск ввода / вывода, так как поиск всегда требуется.

Может ли кто-нибудь объяснить, что физически здесь означает корреляция? Возможно, мое замешательство связано с непониманием того, как база данных выполняет сканирование индекса.

Answer 1

Я думаю, что реальное определение можно найти, прочитав источник; -)

• Сборщик статистики , вероятно, использует пары {ctid, attribvalue} для оценки физического <--> логическая корреляция
• Планировщик может использовать эти коэффициенты для оценки количества страниц, которые нужно получить

В качестве примера приведем статистику для моегоtwitter-sucker-DB, работающий на Raspberry Pi: (в настоящее время около 3,5 млн рядов)

---

\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)

---

Странная вещь в том, чтоВосходящие столбцы {seq, id, create_at, fetch_stamp} имеют отрицательные корреляции, а самообращенные FKs {in_reply_to_id, parent_seq} положительные.Я предполагаю, что для n_distinct = -1 (: = уникальных) столбцов корреляция вообще не используется, может быть, только знак.

Answer 2

Корреляция имеет смысл только для столбцов с типом данных, который имеет общее упорядочение, то есть поддерживает семейство операторов , которое относится к методу доступа btree (операторы <, <=, =, >= и >).

Корреляция положительна, если большие значения имеют тенденцию появляться вблизи физического конца таблицы, а небольшие значения - вблизиначало.Значение 1 означает, что значения хранятся в таблице в отсортированном порядке, -1 означает, что они хранятся в порядке убывания.

Сканирование индекса в PostgreSQL работает следующим образом:

1. Первая подходящая запись находится в индексе.

2. Если карта видимости указывает, что соответствующий блок таблицы содержиттолько кортежи, которые видны всем и , нам не нужен столбец, который не хранится в индексе, у нас есть результат и мы продолжаем с шага 4 (если оптимизатор считает, что это работает для большинства записей индекса, он будетпланировать сканирование только по индексу ).

3. Соответствующая строка выбирается из таблицы и проверяется на видимость.Если он виден и удовлетворяет условию фильтра, мы нашли результат.

4. просматривают индекс в направлении сканирования, чтобы найти следующую запись индекса и посмотреть, удовлетворяет ли он условию сканирования.Если да, вернитесь ко второму шагу, иначе мы закончили.

Это вызывает случайное чтение блоков таблицы, если они уже не находятся в общих буферах.

Теперь, если корреляция высокая, более вероятно, что произойдут две вещи:

• Следующий кортеж, найденный при сканировании индекса, находится в том же блоке таблицы, что и предыдущий кортеж,Тогда он уже находится в общих буферах и не вызывает чтения.

  В итоге вы получите меньше отдельных блоков таблиц: элементы индекса рядом друг с другом, как правило, тоже близки друг к другучасто в одном и том же блоке.

• Если следующая индексная запись не указывает на тот же блок таблицы, что и предыдущий, она, вероятно, будет указывать на следующий блок таблицы.Это приводит к последовательному чтению блоков таблицы, что на вращающихся дисках более эффективно, чем случайное чтение.

Позвольте мне проиллюстрировать это на примере, предполагая индекс для идеально коррелированного столбца:

Первая найденная запись индекса указывает на блок таблицы 42, вторая тоже, с третьей на 30-ю точку указывает на блок 43, следующие 20 записей индекса будут указывать на блок 44.

Таким образом, сканирование индекса посетит 50 кортежей, но будет считывать только 3 блока с диска, и они будут читать их в последовательном порядке (сначала блок 42, затем блок 43, затем блок 44).

Если не былокорреляция, 50 кортежей, вероятно, будут находиться в разных блоках таблицы (при условии, что таблица большая), что будет означать 50 случайных операций чтения с диска.

Таким образом, сканирование индекса дешевле при высокой корреляции, а сканирование обратного индексадешевле, если корреляция низкая.Оптимизатор использует корреляцию для соответствующей корректировки предполагаемых затрат.

Answer 3

Во-первых, у нас есть несколько вещей, которые затрудняют полное объяснение, но я постараюсь и простите, если что-то из этого уже очевидно для вас.

ИтакСлучайные операции ввода-вывода обходятся дорого, потому что мы читаем случайные блоки данных по всему диску.Массовое чтение нескольких блоков подряд намного быстрее (особенно на магнитном диске, не-ssd)

Теперь, еще один шаг вперед, документы, которые вы цитируете, специально говорят о сканировании индекса, которое обычнодиапазон, а не точное значение.

Таким образом, когда индекс коррелируется (может быть принудительно кластеризован в таблице по рассматриваемому индексу), и он ищет диапазон значений IE (где Id между 1000000 и1001000), местоположения (местоположения блоков), возвращаемые при "сканировании" индекса, скорее всего, будут находиться почти в одном и том же месте на диске.

Таким образом, он может перейти к индексу ABC, найти 1000 строк ивыяснить, какие блоки нужно прочитать, и, возможно, получить их за очень небольшое количество запросов.1 (или около того) дополнительный поиск, чтобы получить индекс, стоил того.

Теперь, если нет корреляции, и он выполняет поиск по индексу и находит, что все эти 1000 строк находятся в разных блоках, вВ зависимости от расположения на диске, для поиска указанных данных потребуется до 1000 запросов.Возможно, было бы лучше просто выполнить массовое чтение всей таблицы от начала до конца.Дополнительные поиски по индексу только усугубили ситуацию, и массовые операции чтения теперь не помогут улучшить скорость.

Пожалуйста, дайте мне знать, если это поможет объяснить это вообще.