Методы разбиения таблиц

Разбиение таблиц базы данных

Разбиение таблиц (splitting partition) является одним из общих методов денормализации, который применяется в физическом проектировании ХД. Разбиение таблиц бывает двух видов – вертикальное разбиение и горизонтальное разбиение.

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

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

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

Вертикальное разбиение таблиц

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

· длина строки больше, чем длина физической страницы базы данных (>1 КБ);

· использование так называемого индекса хеширования (cluster hashed index).

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

Метод вертикального разбиения принципиально прост, если вспомнить, что разбиение эквивалентно реляционной операции проекции на таблице. Ясно, что некоторые колонки просто переносятся в новую таблицу так, чтобы длина оставшейся строки была подходящей (< 1 КБ). Разбиение не должно нарушать функциональных зависимостей между колонками. Поскольку мы предполагаем, что исходная таблица нормализована (в частности, все неключевые колонки функционально полно зависят от первичного ключа), первичный ключ новой таблицы является точной копией первичного ключа исходной таблицы.

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

Пример 19.5.

Предположим, что в таблице "Служащие" (EMPLOYEE) необходимо дополнительно сохранять фотографию сотрудника и его автобиографию (рис. 19.6). Эти два новых поля имеют достаточно большой размер, и длина строки таблицы заведомо превысит 1 КБ.

Рис. 19.6. Таблица "Служащие" (EMPLOYEE)

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

Частота использования полей в транзакциях приведена в табл. 19.1.

Таблица 19.1. Таблица частот использования полей таблицы "Служащие" (EMPLOYEE)
№	Наименование атрибута	Наименование колонки	Частота использования полей в транзакциях
1	Номер личной карточки	EMPNO (PK)	60
2	Фамилия	ENAME	60
3	Имя	LNAME	50
4	Номер подразделения	DEPNO	50
5	Должность	JOB	20
6	Дата рождения	AGE	4
7	Стаж	HIREDATE	4
8	Доплаты	COMM	50
9	Зарплата	SAL	50
10	Штрафы	FINE	50
11	Автобиография	Biog	4
12	Фотография	Foto	4

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

Таким образом, имеется основание для принятия решения о разбиении таблицы "Служащие" (EMPLOYEE) на две — скажем, "Служащие" (EMPLOYEE_BASE) и "Дополнительные данные" (ADD_EMPL), как показано на рис. 19.7.

Рис. 19.7. Вертикальное разбиение таблицы "Служащие" (EMPLOYEE) на две таблицы: "Служащие" (EMPLOYEE_BASE) и "Дополнительные данные" (ADD_EMPL)

Последовательность команд SQL для создания вертикального разбиения таблицы "Служащие" приведена ниже.

create table ADD_EMPL (

EMPNO integer not null,

AGE date null,

HIREDATE date not null with default,

Biog text null,

Foto image null,

constraint PK_ADD_EMPL primary key (EMPNO)

)

create table EMPLOYEE_BASE (

EMPNO integer not null,

ENAME char(20) null,

LNAME char(15) null,

DEPNO integer null,

JOB char(20) null,

COMM decimal(8,2) null,

SAL decimal(8,2) null,

FINE decimal(8,2) null,

constraint PK_EMPLOYEE_BASE primary key (EMPNO)

)

alter table ADD_EMPL

add constraint FK_ADD_EMPL_REFERENCE_EMPLOYEE foreign key (EMPNO)

references EMPLOYEE_BASE (EMPNO)

alter table EMPLOYEE_BASE

add constraint FK_EMPLOYEE_REFERENCE_DEPARTAMENT (DEPNO)

references DEPARTAMENT (DEPNO)

Мы определили ограничение ссылочной целостности между таблицами "Служащие" (EMPLOYEE_BASE) и "Дополнительные данные" (ADD_EMPL) с помощью команды ALTER TABLE, поэтому она будет поддерживаться встроенными механизмами СУБД MS SQL Server 2008.

Помимо повышения производительности операций выборки в качестве обоснования вертикального разбиения таблиц следует указать на повышение производительности при операциях вставки и удаления, а также при операциях резервного копирования и восстановления БД или ХД.

Длинные строки в таблицах хеширования

Во многих реляционных СУБД поддерживаются так называемые хеш-кластерные индексы (clustered hashed index). Такие объекты правильнее называть таблицами хеширования, а не индексами. Таблица хеширования представляет собой таблицу реляционной БД, доступ к строкам которой осуществляется с помощью преобразования ключа. Значения колонок, которые объявлены ключевыми, преобразуются в позиции строк таблицы (и при их вставке там и размещаются) – хешируются. Такую функцию называют хеш-функцией. Ключ таблицы, который подвергается преобразованию, называется хеш-ключом.

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

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

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

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

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

Такая таблица создается при помощи команды, например (как в СУБД SQLBase):

CREATE CLUSTERED HASHES INDEX CHXNAME ON EMPLOYEE

(EMPNO) SIZE 2000 ROWS;

Предложение SIZE задает вероятное количество строк в индексе, а ROWS определяет число строк для хранения индекса. Размер можно задавать в блоках (BUCKETS). Таким образом, по значению первичного ключа адресуется блок, содержащий целое число строк, или строка, если ее размер сопоставим с размером физического блока. В последнем случае считается, что блок содержит одну строку.

Для таблицы хеширования определяется параметр "число строк на странице" (rows per page), или кластеризация страницы (page clustering)), или коэффициент блокировки, равный

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

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

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

В СУБД семейства MS SQL Server таблицы хеширования не поддерживаются в явном виде. Однако они могут быть созданы с помощью функции CHECKSUM () и вычисляемой колонки в индексе. Индекс должен быть неуникальным, чтобы было возможно разрешать коллизии хеш-функции.

Горизонтальное разбиение таблиц

На практике горизонтальное разбиение (horizontally partition) применяется для изоляции одной группы строк таблицы от другой, когда использование этих групп строк в транзакциях почти не пересекается. Типичный пример — изоляция текущих данных от архивных данных.

Рассмотрим систему обработки заказов. Менеджеры и продавцы работают с текущими заказами. Обработка выполненных заказов (архивные данные) выполняется при подготовке разного рода отчетов (в частности, путем создания киоска данных). Даже если готовится ежедневный отчет с обращением к архивным данным, то в организациях среднего размера частота использования текущих данных все равно превышает частоту использования архивных данных на 2-3 порядка, а отношение объема текущих данных к архивным данным может составлять менее 0.001.

Одним из практических критериев в данном случае может служить классическое правило 80-20. Если активно работают с 20-ю процентами данных, то вероятнее всего, остальные 80% можно перенести в архивную таблицу.

Пример 19.6.

Таблицей – кандидатом на горизонтальное разбиение является таблица "Проект" (PROJECT), структура которой показана на рис. 19.8. В этой таблице хранятся архивные данные – выполненные проекты.

Рис. 19.8. Таблица "Проект" (PROJECT)

Предположим, что число выполненных проектов в год в организации где-то около 1000. Данные в таблицы нужно хранить 10 лет (10000 записей). Средняя продолжительность проекта равна двум месяцам, т. е. число незавершенных проектов в данный момент времени не превышает 200. Через 5 лет отношение числа текущих проектов к архивным проектам достигнет 0.04.

Следовательно, можно рассмотреть вопрос о горизонтальном разбиении этой таблицы и выполнить его, как показано на рис. 19.9.

Рис. 19.9. Горизонтальное разбиение таблицы "Проект" (PROJECT) на две таблицы: "Текущие проекты" (PROJECT_CUR) и "Архивные проекты" (PROJECT_OLD)

Мы разбили таблицу "Проект" (PROJECT) горизонтально на две таблицы — "Текущие проекты" (PROJECT_CUR) и "Архивные проекты" (PROJECT_OLD). Последовательность команд для создания таблиц разбиения приведена ниже.

create table PROJECT_CUR (

PROJNO char(8) not null,

PROJ_NAME char(40) not null,

BUDGET decimal(9,2) not null,

constraint PK_PROJECT_CUR primary key (PROJNO)

)

create table PROJECT_OLD (

PROJNO char(8) not null,

PROJ_NAME char(40) not null,

BUDGET decimal(9,2) not null,

constraint PK_PROJECT_OLD primary key (PROJNO)

)

Для совместного использования двух этих таблиц можно предусмотреть представление "Все проекты" (ALL_PROJECT), которое показано на рис. 19.10.

Рис. 19.10. Представление "Все проекты" (ALL_PROJECT)

Команда SQL для создания представления "Все проекты" (ALL_PROJECT) приведена ниже.

CREATE VIEW ALL_PROJECT

SELECT PROJNO, PROJ_NAME, BUDGET FROM PROJECT_CUR

UNION

SELECT PROJNO, PROJ_NAME, BUDGET FROM PROJECT_OLD;

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

Разбиение таблиц и ссылочная целостность

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

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

Пример 19.7.

Для разрешения отношения "многие ко многим" между таблицами "Служащий" (EMPLOYEE) и "Проект" (PROJECT) была введена связывающая таблица "Служащий Проект" (EMP_PROJ), которая имеет ограничения ссылочной целостности, с таблицей "Проект" (PROJECT), как показано на рис. 19.11.

Рис. 19.11. Разрешение отношения "многие ко многим" между таблицами "Служащий" (EMPLOYEE) и "Проект" (PROJECT)

Связывающая таблица "Служащий Проект" (EMP_PROJ) была создана с помощью команды SQL, приведенной ниже.

create table EMP_PROJ (

PROJNO char(8) not null,

EMPNO integer not null,

WORKS integer null,

constraint PK_EMP_PROJ primary key (PROJNO, EMPNO).

constraint FK_EMP_PROJ_REFERENCE_PROJECT foreign key (PROJNO)

references PROJECT (PROJNO),

constraint FK_EMP_PROJ_REFERENCE_EMPLOYEE foreign key (EMPNO)

references EMPLOYEE (EMPNO)

)

Ноунастеперь, после разбиениятаблицы "Проект" (PROJECT), появилисьдвеновыетаблицы: "Текущиепроекты" (PROJECT_CUR) вместотаблицы "Проекты" (PROJECT) и "Архивныепроекты" (PROJECT_OLD), какпоказанона рис. 19.12.

Рис. 19.12. Разрешение отношения "многие ко многим" после разбиения таблицы "Проекты" (PROJECT)

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

Однако если взаимосвязь между исполнителями и завершенными проектами должна отслеживаться (например, руководство будет изучать вопрос: кто, когда, какой проект выполнял), ее следует распространить и на таблицу "Архивные проекты" (PROJECT_OLD), как показано на рис. 19.13.

Чтобы учесть в БД проделанную нами работу, достаточно внести ограничение внешнего ключа в таблицу "Служащий Проект" (EMP_PROJ), как показано ниже:

Рис. 19.13. Разрешение отношения "многие ко многим" таблицы "Архивные проекты" (PROJECT_OLD)

drop table EMP_PROJ

create table EMP_PROJ (

PROJNO char(8) not null,

EMPNO integer not null,

WORKS integer null,

constraint PK_EMP_PROJ primary key (PROJNO, EMPNO).

constraint FK_EMP_PROJ_REFERENCE_PROJECT foreign key (PROJNO)

references PROJECT_CUR (PROJNO),

constraint FK_EMP_PROJ_REFERENCE_PROJECT_OLD foreign key (PROJNO)

references PROJECT_OLD (PROJNO),

constraint FK_EMP_PROJ_REFERENCE_EMPLOYEE foreign key (EMPNO)

references EMPLOYEE (EMPNO)

)

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

Рис. 19.14. Взаимосвязь "один к одному" между таблицами "Текущие проекты" (PROJECT_CUR) и "Архивные проекты" (PROJECT_OLD)

Если определено каскадное правило удаления для этого внешнего ключа (см. "Знакомство с CASE инструментом"), то СУБД будет автоматически удалять строки новой таблицы, когда соответствующая строка исходной таблицы будет удалена, хотя управление вставкой строк придется перенести в приложение ХД. Команда SQL для этого случая приведена ниже.

create table PROJECT_OLD (

PROJNO char(8) not null,

PROJ_NAME char(40) not null,

BUDGET decimal(9,2) not null,

constraint PK_PROJECT_OLD primary key (PROJNO),

constraint FK_EMP_PROJ_REFERENCE_PROJECT_OLD_1 foreign key (PROJNO)

references PROJECT_СUR (PROJNO)

)

При принятии решения о разбиении таблицы следует придерживаться следующего алгоритма:

· определить, какие колонки исходной таблицы в какие новые таблицы будут перемещены;

· создать новые таблицы с первичным ключом, идентичным первичному ключу исходной таблицы;

· если СУБД будет управлять декларативной ссылочной целостностью для новых таблиц таким же образом, как и для исходной таблицы, в случае если она является дочерней таблицей во взаимосвязи, следует добавить колонку внешнего ключа каждой родительской таблицы во взаимосвязи в новую таблицу, т.е. новая таблица должна содержать ограничение внешнего ключа, идентичное родительской таблице, для каждой взаимосвязи. Альтернативой этому решению является создание связи "один к одному" между новой таблицей и исходной таблицей, определение внешнего ключа обратно к исходной таблице тождественным первичному ключу;

· если СУБД будет управлять ссылочной целостностью для новых таблиц таким же образом, как и для исходной таблицы, в случае если она является родительской таблицей во взаимосвязи, то следует добавить внешний ключ в каждую дочернюю таблицу исходной таблицы, чтобы идентифицировать эту новую таблицу как дочернюю. Можно так же поступить, как в первой части предыдущего пункта, при этом новые таблицы не следует объявлять как родительские в других взаимоотношениях. Исходная таблица поддерживает все взаимосвязи, в которых она выступает родителем;

· следует прописать для разработчиков приложений все команды INSERT для полученных в результате разбиения таблиц или указать правила, которым должна следовать вставка строк в эти таблицы;

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

Объединение таблиц базы данных

Объединение таблиц (Table collapsing) является процессом перемещения строк нескольких таблиц в одну, новую таблицу для ограничения числа соединений таблиц БД и улучшения производительности запросов.

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

Рассмотрим примеры.

Пример. 13.8.

Предположим, что было принято решение об объединении таблиц "Покупатель" (Customer) и "Заказ" (Order), — их необходимо объединить, чтобы исключить операцию соединения в запросах к этим таблицам. Физическая модель данных до объединения приведена на рис. 19.15.

Рис. 19.15. Таблицы "Покупатель" (Customer) и "Заказ" (Order) до их объединения

В результате объединения таблиц будет создана одна таблица "Покупатель Счет" (Cust_Order), содержащая все колонки объединяемых таблиц (рис. 19.16).

Рис. 19.16. Таблица "Покупатель Счет" (Cust_Order), объединяющая таблицы "Покупатель" (Customer) и "Заказ" (Order)

Команда SQL для создания объединяющей таблицы приведена ниже.

create table Cust_Order (

Order_ID bigint not null,

Cust_ID bigint not null,

Amount decimal(8,2) null,

Delivery char(40) null,

Name char(20) null,

Address char(30) null,

constraint PK_CUST_ORDER primary key (Order_ID)

)

Для ХД целесообразно рассматривать объединение нормализованных таблиц иерархии — например, таблиц измерений, представляющих измерение "Время" (Time), как на рис. 19.17. Денормализованная таблица измерений для иерархии "Время" приведена на рис. 19.18.