Внутреннее устройство базы данных: реализация ограничения внешнего ключа

Как реализован внешний ключ, например, в PostgreSQL?

Я заметил, что при создании внешнего ключа задействовано много хеширования, поэтому я полагаю, что индекс на основе хеша создается в столбце внешнего ключа, который ссылается на столбец первичного ключа. Если это так (например, когда мы хотим удалить строку из указанной таблицы - с первичным ключом или с так называемой главной таблицей), мы можем легко проверить, действительно ли имеется ссылка на строку из указанной таблицы. Более того, вероятно, СУБД требует, чтобы в указанном столбце первичного ключа был хотя бы индекс дерева B +, потому что, когда мы хотим вставить новую строку в ссылочную таблицу, мы можем легко проверить, существует ли строка с требуемым значением первичного ключа. в указанной таблице. Некоторые источники утверждают, что триггер используется для обеспечения ограничения внешнего ключа.


postgresql database foreign-keys database-design
person ady    schedule 15.03.2015    source источник
comment
Ограничение (внешнего ключа) - это абстрактное понятие. Реализации могут реализовать это как угодно. На практике по соображениям производительности почти необходимо добавлять индекс. По теоретическим причинам требуется, чтобы указанные поля в FK были по крайней мере уникальным способом адресации строки в целевой таблице. Этот на практике часто подразумевает индекс.   -  person wildplasser    schedule 16.03.2015
comment
Да, я знаю, что есть индекс дерева b + для первичного (или уникального) ключа, но есть ли какая-либо дополнительная структура (например, хеш-индекс) в ссылочных столбцах?   -  person ady    schedule 17.03.2015

Ответы (2)


arrow_upward
2
arrow_downward

В Postgres столбцы, на которые указывает ссылка, в главной таблице должны иметь ограничение UNIQUE или PRIMARY KEY. Согласно документации:

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

Оба из них в настоящее время всегда реализуются с индексом btree. Таким образом, всегда есть индекс btree для указанного столбца (столбцов):

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

Фактическая реализация самого ограничения FK - это запись в системном каталоге pg_constraint, специальный внутренний триггер и еще одна запись в pg_depend.

person Erwin Brandstetter    schedule 16.03.2015
comment
Спасибо за ваш ответ. Насколько мне известно, индекс дерева b + создается по умолчанию, когда определяется новый первичный ключ (так что это задача с интенсивным использованием ЦП, потому что строки должны быть отсортированы перед созданием дерева b + в массовом режиме). Я заметил, что при создании FK в postgres было задействовано много хеширования, поэтому я предполагаю, что, вероятно, дополнительная структура (возможно, индекс на основе хэша) создается в ссылочном столбце (столбцах) помимо новых записей в pg_constraint и pg_depend. - person ady; 17.03.2015
comment
@ adam.cajf: Никакой дополнительной структуры, кроме той, что я уже перечислил, не создается. Вы наблюдаете проверку целостности отношений. После создания Postgres должен установить, что существующие значения подчиняются новому ограничению. - person Erwin Brandstetter; 17.03.2015
comment
Да, имеет смысл проверить, существуют ли значения, но в этом случае следует использовать дерево b + на первичном ключе. Итак, почему много хеширования? - person ady; 18.03.2015
comment
@ adam.cajf: Не понимаю, что вы имеете в виду. Но в любом случае индекс вряд ли пригодится при посещении большей части таблицы. Индекс, вероятно, не будет использоваться для этой конкретной цели. - person Erwin Brandstetter; 18.03.2015
comment
Вероятно, вы видели реализацию внешнего соединения между первичным ключом и внешним ключом для обнаружения записей внешнего ключа не в первичном ключе. - person David Aldridge; 11.04.2015

arrow_upward
0
arrow_downward

Я проверил, действительно ли PostgreSQL не создает индекса для внешнего ключа (используя этот запрос: https://stackoverflow.com/a/25596855/1245175).

С другой стороны, для внешнего ключа создается несколько триггеров:

test=# SELECT tgname AS trigger_name
  FROM pg_trigger
 WHERE tgname !~ '^pg_';
 trigger_name
--------------
(0 rows)

test=# ALTER TABLE LINEITEM ADD CONSTRAINT LINEITEM_FK1 FOREIGN KEY (L_ORDERKEY)  REFERENCES ORDERS;
ALTER TABLE
test=# SELECT tgname AS trigger_name                                                               
  FROM pg_trigger
 WHERE tgname !~ '^pg_';
         trigger_name        
------------------------------
 RI_ConstraintTrigger_a_16419
 RI_ConstraintTrigger_a_16420
 RI_ConstraintTrigger_c_16421
 RI_ConstraintTrigger_c_16422

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

Интересно, что MonetDB создает индексы разных типов для первичных и внешних ключей (возможно, индекс соединения и индекс хеширования соответственно).

sql>select * from sys.idxs;
+------+----------+------+-------------+
| id   | table_id | type | name        |
+======+==========+======+=============+
| 6467 |     6446 |    0 | orders_pk   |
| 6470 |     6464 |    1 | lineitem_fk |
+------+----------+------+-------------+
2 tuples (3.921ms)

Более того, Oracle применяет ограничения первичного ключа с помощью индексов и по умолчанию не создает никакого индекса для внешнего ключа, однако есть несколько советов по индексации внешнего ключа: https://asktom.oracle.com/pls

person ady    schedule 10.04.2015