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

Пересказ статьи lukaseder. The Cost of Useless Surrogate Keys in Relationship Tables

Насколько хорош естественный ключ?

Это очень сложный вопрос для большинства сущностей на этапе проектирования схемы. В некоторых редких случаях, кажется, имеется «очевидный» кандидат, обусловленный различными стандартами ISO, например:

  • ISO 639 language codes
  • ISO 3166 country codes
  • ISO 4217 currency codes

Но даже в этих случаях возможны исключения, и худшее, что может случиться — это изменение ключа. Большинство проектов баз данных предохраняет себя от этого использованием суррогатных ключей. В этом нет ничего плохого. Однако…

Таблицы связей

Есть одно исключение, когда суррогатный ключ действительно никогда не требуется. Это таблицы связей. Например, в базе данных Sakila все таблицы связей не имеют суррогатного ключа, а используют соответствующие внешние ключи в качестве составного «естественного» первичного ключа:

Так, например, таблица FILM_ACTOR определена следующим образом:

CREATE TABLE film_actor (
  actor_id INT NOT NULL REFERENCES actor,
  film_id INT NOT NULL REFERENCES film,
 
  CONSTRAINT film_actor_pkey PRIMARY KEY (actor_id, film_id)
);

Здесь действительно нет оснований для добавления еще одного столбца FILM_ACTOR_ID или ID для каждой отдельной строки в этой таблице, даже если множество ORM и не-ORM схем будут это делать, просто по причинам «унификации» (а в некоторых случаях и потому, что не могут работать с составными ключами).

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

Однако в отношении производительности это может дать огромную разницу!

Кластеризованные индексы

Во многих СУБД при создании таблицы вы стоите перед выбором использовать «кластеризованный индекс» или «некластеризованный индекс» в структуре таблицы. Основное различие состоит в следующем:

Кластеризованный индекс

…есть индекс на первичном ключе, который «кластеризует» определяемые им данные данные вместе. Другими словами:

  • Значения всех индексных столбцов содержатся в древовидной структуре индекса.
  • Значения всех остальных столбцов содержатся на листовых узлах индекса.

Преимуществом такой структуры таблицы является значительно более быстрый поиск по первичному ключу, поскольку вся строка располагается в индексе, что требует меньше дисковых операций ввода/вывода, чем при использовании некластеризованного индекса при поиске по ключу. Плата за это — более медленный вторичный поиск по индексу (например, поиск по фамилии). Cложность алгоритмов:

  • O(log N) для поиска по первичному ключу.
  • O(log N) для поиска по вторичному ключу, плюс O(M log N) для проекций неключевых вторичных столбцов поиска (слишком высокая плата).

…где

  • N — размер таблицы,
  • M — число строк, которые находятся по вторичным ключам.

Кластеризованные индексы часто дают выгоду при использовании в OLTP-приложениях.

Некластеризованные индексы

…это индекс на первичном ключе, который находится «вне» структуры таблицы, которая является таблицей кучи. Другими словами:

  • Все значения индексных столбцов находятся в структуре дерева индекса.
  • Все значения индексных столбцов и значения других столбцов содержатся в таблице кучи.

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

  • O(log N) для поиска по первичному ключу, плюс O(1) для проекций столбцов, не входящих в первичный ключ (умеренная плата).
  • O(log N) для поиска по вторичному ключу, плюс O(M) для проекций столбцов, не входящих во вторичный ключ (умеренная плата).

Преимущественное использование таблиц кучи в OLAP-приложениях.

Данность

  • InnoDB в MySQL предоставляют только кластеризованные индексы.
  • MyISAM в MySQL предоставляют только таблицы кучи.
  • Oracle предоставляет и те, и другие индексы; по умолчанию создаются таблицы кучи.
  • PostgreSQL предоставляет и те, и другие индексы; по умолчанию создаются таблицы кучи.
  • SQL Server предоставляет и те, и другие индексы; по умолчанию создаются кластеризованные индексы.

Заметим, что в Oracle кластеризованные индексы называются «индексно-организованные таблицы» (“index organised tables”).

Производительность

В этой статье я проверяю производительность MySQL, поскольку MySQL InnoDB не позволяет менять структуру таблицы. Забавно, что описанные ниже проблемы не воспроизводятся на PostgreSQL, что было показано пользователем reddit /u/ForeverAlot.

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

CREATE TABLE film_actor_surrogate (
  id INT NOT NULL,
  actor_id INT NOT NULL REFERENCES actor,
  film_id INT NOT NULL REFERENCES film,
 
  CONSTRAINT film_actor_surrogate_pkey PRIMARY KEY (id)
);
 
CREATE TABLE film_actor_natural (
  actor_id INT NOT NULL REFERENCES actor,
  film_id INT NOT NULL REFERENCES film,
 
  CONSTRAINT film_actor_pkey PRIMARY KEY (actor_id, film_id)
);

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

  • FILM_ACTOR_SURROGATE.ID, которая является совершенно бесполезной;
  • (FILM_ACTOR_NATURAL.ACTOR_ID, FILM_ACTOR_NATURAL.FILM_ID), которая весьма полезна.

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

В первом случае мы должны полагаться на дополнительный индекс по вторичному ключу, который содержит (ACTOR_ID, FILM_ID), с перспективой, что вторичный индекс не является покрывающим, если мы имеем дополнительные проекции.

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

Какое это имеет значение?

Мы можем легко разработать тесты для этого случая. Тест использует следующую схему базы данных:

CREATE TABLE parent_1 (id INT NOT NULL PRIMARY KEY);
CREATE TABLE parent_2 (id INT NOT NULL PRIMARY KEY);
 
CREATE TABLE child_surrogate (
  id INT AUTO_INCREMENT, 
  parent_1_id INT NOT NULL REFERENCES parent_1, 
  parent_2_id INT NOT NULL REFERENCES parent_2, 
  payload_1 INT, 
  payload_2 INT, 
  PRIMARY KEY (id), 
  UNIQUE (parent_1_id, parent_2_id)
) -- ENGINE = MyISAM /* раскомментируйте, чтобы использовать таблицы кучи MyISAM (heap tables) */
;
 
CREATE TABLE child_natural (
  parent_1_id INT NOT NULL REFERENCES parent_1, 
  parent_2_id INT NOT NULL REFERENCES parent_2, 
  payload_1 INT, 
  payload_2 INT, 
  PRIMARY KEY (parent_1_id, parent_2_id)
) -- ENGINE = MyISAM /* раскомментируйте, чтобы использовать таблицы кучи MyISAM (heap tables) */
;

В отличии от базы данных Sakila, теперь мы добавляем некоторую «полезную нагрузку (payload)» в таблицу связей, которая не маловероятна. Последние версии MySQL по умолчанию используют InnoDB, которая поддерживает только кластеризованную структуру хранения. Вы можете раскомментировать предложение ENGINE storage, чтобы посмотреть поведение с MyISAM, которая поддерживает только таблицы кучи.

Параметры тестирования:

  • 10000 строк в Parent_1
  • 100 строк в Parent_2
  • 1000000 строк в обеих таблицах CHILD (просто cross join двух предыдущих)

Теперь запускаются 5 итераций по 10000 повторений двух следующих запросов, следуя нашей стандартной методике тестов SQL:

-- Запрос 1
SELECT c.payload_1 + c.payload_2 AS a 
FROM parent_1 AS p1 
JOIN child_surrogate AS c ON p1.id = c.parent_1_id 
WHERE p1.id = 4;
 
-- Запрос 2
SELECT c.payload_1 + c.payload_2 AS a 
FROM parent_1 AS p1 
JOIN child_natural AS c ON p1.id = c.parent_1_id 
WHERE p1.id = 4;

Заметим, что в MySQL не применяется устранение соединения (join elimination), в противном случае бесполезное соединение с Parent_1 исключалось бы. Результаты теста говорят сами за себя:

Использование InnoDB (кластеризованные индексы)

Run 0, Statement 1 : 3104
Run 0, Statement 2 : 1910
Run 1, Statement 1 : 3097
Run 1, Statement 2 : 1905
Run 2, Statement 1 : 3045
Run 2, Statement 2 : 2276
Run 3, Statement 1 : 3589
Run 3, Statement 2 : 1910
Run 4, Statement 1 : 2961
Run 4, Statement 2 : 1897

Использование MyISAM (таблицы кучи)

Run 0, Statement 1 : 3473
Run 0, Statement 2 : 3288
Run 1, Statement 1 : 3328
Run 1, Statement 2 : 3341
Run 2, Statement 1 : 3674
Run 2, Statement 2 : 3307
Run 3, Statement 1 : 3373
Run 3, Statement 2 : 3275
Run 4, Statement 1 : 3298
Run 4, Statement 2 : 3322

Вы не должны рассматривать эти результаты только как сравнение между InnoDB и MyISAM, а как сравнение различных структур таблицы в пределах границ того же самого движка. Очевидно, что дополнительная сложность поиска плохо кластеризованного индекса в CHILD_SURROGATE приводит к замедлению на 50 % выполнения запроса такого типа, не получая ничего взамен.

В случае таблицы кучи дополнительный столбец суррогатного ключа не оказывает какого-либо заметного эффекта.

Заключение

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

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

MySQL InnoDB и SQL Server используют кластеризованные индексы по умолчанию, поэтому, если вы используете одну из этих реляционных СУБД, проверьте, возможно ли существенное улучшение в результате удаления суррогатных ключей.

Добавить комментарий