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

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

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

Одной из СУБД, в которой реализованы все эти возможности и которая оказала большое влияние на развитие всех других СУБД, является свободно-распространяемая СУБД PostgreSQL [1, 2], в которой еще на этапе проектирования предусматривалось расширение функциональности от управления данными в рамках стандартной реляционной модели в сторону управления объектами и знаниями [3].

В докладе приводятся сведения об основных механизмах расширяемости PostgreSQL, разрабатываемых авторами, таких как Обобщенное Поисковое Дерево (GiST) [4], Обобщенный Обратный Индекс (GIN) [5], и о нескольких приложениях, их использующих.

Первоначальный подход [6] к расширяемости СУБД в PostgreSQL, основанный на использовании хорошо изученных структур, таких как B+-tree и R-tree, и абстрагирования процедур доступа и обновления записей, позволял добавлять поддержку новых типов данных, но был ограничен теми запросами и методами доступа, которые предоставляли эти базовые структуры.

Для того чтобы преодолеть это ограничение, Хеллерстейн и др. [4] предложили структуру индекса, называемую GiST (Generalized Search Tree, Обобщенное поисковое дерево), которое является обобщенной разновидностью R-tree и предоставляет стандартные методы навигации по дереву и его обновления (расщепление и удаление узлов). Было отмечено, что очень многие методы доступа можно представить как иерархию предикатов, в которой каждый предикат выполняется для всех ключей, содержащихся в подузлах этой иерархии. Таким образом, такая структура данных может служить шаблоном для реализации многих методов доступа, не накладывая существенных ограничений. Например, в B+-tree записи во внутренних узлах представляют диапазоны, которые задают ограничения на ключи в концевых узлах соответствующего поддерева. GiST предоставляет индексный доступ к новым типам данных и поддерживает расширяемый набор запросов.

Современная реализация GiST в PostgreSQL поддерживает ключи переменной длины, композитные (multi-key) ключи, параллелизм и восстановление после краха (concurrency и recovery), что позволяет разрабатывать расширения экспертам в области данных, не будучи экспертами-разработчиками ядра СУБД. Практически все наши расширения имеют индексную поддержку с помощью GiST. Программный интерфейс GiST и практические примеры рассмотрены в [7].

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

При этом постинг лист состоит из ссылок на массивы, документы, записи. GIN поддерживает типичные операции со множествами - contains, overlap и contained. Обобщенность означает то, что GIN не знает, какую именно операцию он ускоряет, и все определяется интерфейсными функциями, определенными для конкретного типа. В этом отношении GIN схож с GiST и отличается от B-tree индексов, которые используют фиксированный набор операций сравнения.

В качестве примеров использования расширяемости PostgreSQL в докладе рассматриваются хранилище для очень больших (терабайтных) астрономических каталогов [8,9], разработанное в рамках программы Виртуальная Обсерватория ГАИШ, и система полнотекстового поиска в PostgreSQL [10, 11].

Слайды к докладу в формате PDF: bartunov20080529.pdf

Литература:

1. СУБД PostgreSQL, http://www.postgresql.org
2. О.С. Бартунов "Что такое PostgreSQL?",2005, http://www.sai.msu.su/~megera/postgres/talks/what_is_postgresql.html
3. Lawrence A. Rowe, Michael Stonebraker, "The POSTGRES Data Model", Proceedings of the 13th International Conference on Very Large Data Bases, 1987, http://www.vldb.org/conf/1987/P083.pdf
4. Joseph M. Hellerstein, Jeffrey F. Naughton and Avi Pfeffer, "Generalized Search Trees for Database Systems", 1996, Proceedings of the 21th International Conference on Very Large Data Bases, http://db.cs.berkeley.edu/papers/vldb95-gist.pdf
5. GIN Presentation, http://www.sigaev.ru/gin/Gin.pdf
6. Michael Stonebraker, "Inclusion of new types in relational database systems", In Proceedings of the 4th IEEE International Conference on Data Engineering, pp. 262-269, Washington, D.C., 1986
7. О.С. Бартунов, Ф.Г. Сигаев, "Написание расширений для PostgreSQL с использованием GiST",2005, http://www.sai.msu.su/~megera/postgres/talks/gist_tutorial.html
8. Виртуальная Обсерватория ГАИШ, http://vo.astronet.ru
9. Поддержка данных со сферическими атрибутами в PostgreSQL, http://www.sai.msu.su/~megera/wiki/SkyPixelization, http://q3c.sourceforge.net
10. О.С. Бартунов, Ф.Г. Сигаев, "Введение в полнотекстовый поиск в PostgreSQL", http://www.sai.msu.su/~megera/postgres/talks/fts_pgsql_intro.html
11. Full-Text Search in PostgreSQL, http://www.postgresql.org/docs/current/static/textsearch.html