Что надо знать о полнотекстовой конфигурации

1) FTS конфигурация объединяет все необходимое для организации полнотекстового поиска, а именно:

Парсер, который разбивает текст на токены и каждому токену приписывает его тип;

Правила, по которым токен превращается в лексему.

2) FTS конфигураций может быть много, они могут быть определены в разных схемах, но только одна в данной схеме может иметь флаг DEFAULT, т.е., быть активной по умолчанию. Имя активной FTS конфигурации содержится в переменной tsearch_conf_name. По умолчанию, она выбирается из всех конфигураций, имеющих флаг DEFAULT, которые созданы для серверной локали, в соответствии с правилом видимости объектов в PostgreSQL, т.е. определяется переменной search_path. Здесь надо уточнить, что специальная схема pg_catalog неявно ставится первой в search_path, если только ее положение не указали явно. Так как встроенные FTS конфигурации определены в схеме pg_catalog, то они могут маскировать конфигурации, созданные в схеме по умолчанию, обычно public, совпадающие по имени, если search_path не содержит явно pg_catalog. Предположим, что мы имеем две конфигурации с именем russian_utf8 определенные для локали ru_RU.UTF-8 и имеющие флаг DEFAULT.

В зависимости от search_path мы будем иметь разную активную FTS конфигурацию.

=# show tsearch_conf_name; tsearch_conf_name ------------------------- pg_catalog.russian_utf8 (1 row)

=# set search_path=public, pg_catalog; SET =# show tsearch_conf_name; tsearch_conf_name --------------------- public.russian_utf8

Таким образом, чтобы не возникали разного рода конфузы мы рекомендуем:

Использовать уникальные имена FTS конфигураций, которые не перекрываются с системными.

Использовать полное имя FTS конфигурации с указанием схемы

Следить за переменной search_path. Можно задать ее глобально в postgresql.conf, локально в ~/.psqlrc или на период сессии. Однако, это

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

4) Как правило, для успешного поиска требуется следить, чтобы использовалась одна и та же FTS конфигурация при индексировании и при поиске.

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

Что надо знать о словарях

1) Словарь - это программа, которая принимает на вход слово, а на выходе

выдает массив лексем, если словарь опознал слово

пустой массив (void array), если словарь знает слово, но оно является стоп-словом

NULL, если словарь не распознал слово.

2) Надо следить, чтобы все данные, которые используют словари,были в server_encoding.

Встроенные словари включают:

Simple - возвращает входное слово в нижнем регистре или NULL, если это стоп-слово.

Ispell - шаблон для создания словарей, которые могут использовать словари Ispell[ISPELL], которые доступны для большого количества языков. Также поддерживаются словари MySpell[MYSPELL] (OO < 2.01) и Hunspell [HUNSPELL] (OO >= 2.0.2). Большой список словарей доступен на странице [OODICTS].

Snowball stemmer - шаблон словаря, который по определенным правилам, специфическим для каждого языка, отрезает окончания у слов. Правила доступны для большого количества языков [SNOWBALL] и для 10 языков доступны в системе по умолчанию. Словарь принимает параметр, указывающий на положение файла со списком стоп-слов.

synonym шаблон используется для создания словарей, которые заменяют одно слово на другое. Для поддержки фраз используйте Thesaurus словарь. Одним из примеров использования синонимов - это решение лингвистических проблем. Например, слово 'Paris', распознается английским стеммером как 'pari'. Чтобы избежать этого, достаточно создать словарь синонимов

Paris paris

и поставить его перед стеммером.

=# select * from ts_debug('english','Paris'); Alias | Description | Token | Dicts list | Lexized token -------+-------------+-------+----------------------+---------------------------- lword | Latin word | Paris | {pg_catalog.en_stem} | pg_catalog.en_stem: {pari}

=# alter fulltext mapping on english for lword with synonym,en_stem; =# select * from ts_debug('english','Paris'); Alias | Description | Token | Dicts list | Lexized token -------+-------------+-------+-----------------------------------------+----------------------------- lword | Latin word | Paris | {pg_catalog.synonym,pg_catalog.en_stem} | pg_catalog.synonym: {paris} (1 row)

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

cat tz_astro.txt

supernovae stars : sn crab nebulae : crab

Далее, мы создаем словарь tz_astro и кроме файла с синонимами указываем словарь, который будет использоваться для нормализации слов, так что 'supernovae stars' и 'supernovae star' будут опознанны как 'sn'.

apod=# CREATE FULLTEXT DICTIONARY tz_astro OPTION 'DictFile="tz_astro.txt", Dictionary="en_stem"' LIKE thesaurus_template;

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

apod=# ALTER FULLTEXT MAPPING ON russian_utf8 FOR lword,lhword,lpart_hword WITH tz_astro,en_stem;

Теперь тестируем:

apod=# select plainto_tsquery('great supernovae stars'); plainto_tsquery ----------------- 'great' & 'sn' apod=# select plainto_tsquery('great supernovae star'); plainto_tsquery ----------------- 'great' & 'sn'

3) Тестировать словари можно с помощью функции lexize

=# select lexize('en_stem', 'stars'); lexize -------- {star}

=# select lexize('en_stem', 'a'); lexize -------- {}

4) Словари можно добавлять в систему, см. пример [FTSBOOKAPPC]

Что нужно знать об индексах

Индексы используются только для ускорения операций

Результат выполнения запроса не зависит от использования индексов

Индексы не всегда ускоряют операции

Для ускорения полнотекстового поиска можно использовать два индекса - на основе GiST [GIST] или GIN [GIN].

GIN индекс, или обобщенный обратный индекс - это структура данных, у которой для каждого ключа есть много значений. В случае полнотекстового поиска ключом является лексема, а значением - сортированный список идентификаторов документов, которые содержат эту лексему. Отметим, что позиционная информация не хранится в индексе, что связано с ограничениями PostgreSQL. Так как в обратном индексе используется бинарное дерево для поиска ключей, то он слабо зависит от их количества и потому хорошо шкалируется. Этот индекс используется практически всеми большими поисковыми машинами, однако его использование в базах данных для индексирования изменяющихся документов затруднено, так как любые изменения (добавление нового документа, обновление или удаление) приводят к большому количеству обновлений индекса. Например, добавление нового документа, который содержит N уникальных лексем приводит к обновлению N записей в индексе. Поэтому этот индекс лучше всего подходит для неменяющихся коллекций документов. GIN индекс поддерживает групповое обновление индекса, которое является очень эффективным, поэтому иногда быстрее создать индекс заново, чем обновлять индекс при добавке каждого документа.

В тоже время, GiST индекс является "прямым" индексом, т.е. для каждого документа ставится в соответствие битовая сигнатура, в которой содержится информация о всех лексемах, которые содержаться в этом документе, поэтому добавление нового документа приводит к добавлению только одной сигнатуры. Для быстрого поиска сигнатуры хранятся в сигнатурном дереве RD-Tree (russian doll, матрешка), реализованная помощью GiST.

Сигнатура - это битовая строка фиксированной длины, в которой все биты изначально выставленны в '0'. С помощью хэш-функции слово отображается в определенный бит сигнатуры, который становится '1'. Сигнатура документа является наложением индивидуальных сигнатур всех слов. Такая техника называется superimposed coding и реализуется как bitwise OR, что является очень быстрой операцией.

word signature ---------------- w1 -> 01000000 w2 -> 00010000 w3 -> 10000000 ---------------------- 11010000

В этом примере, '11010000' является сигнатурой документа, состоящего из трех уникальных слов w1,w2,w3. Сигнатура является некоторым компактным представлением документа, что приводит к значительному уменьшению размера коллекции. Кроме того, фиксированный размер cигнатуры сильно облегчает операции сравнения. Все это делает использование сигнатур вместо документов привлекательным с точки зрения производительности.

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

11010000 - сигнатура документа 00000001 - сигнатура запроса Q1, точно не содержится в документе 01000000 - сигнатура запроса Q2, возможно содержится в документе 01010000 - cигнатура запроса Q3, возможно содержится в документе

Сигнатура Q2 является сигнатурой слова w1 и, таким образом, является правильным попаданием, в то время как сигнатура Q3 - ложным попаданием (false drop), несмотря на то, что она удовлетворяет сигнатуре документа. Ясно, что конечность размера сигнатуры и увеличение количества уникальных слов приводит к насыщению сигнатуры, т.е., когда все биты будут '1', что сильно уменьшает избирательность сигнатуры и ухудшает производительность поиска.

Существуют несколько структур данных для хранения сигнатур, такие как сигнатурный файл (signature file),но они не являются индексами, так как требует полного просмотра. Дерево RD-Tree является аналогом R-Tree, приспособленное к работе со множествами для решения задачи поиска всех множеств, которые содержат в себе некое подмножество, является индексной структурой и может сильно ускорять поиск. Подробнее о RD-Tree можно прочитать в оригинальной статье [RDTREE]

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

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

ROOT 11011011

Internal nodes: 11011001 10010011 | | Leaves: 11010000, 11010001, 11011000 10010010,10010001

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

Найденные результаты приходится дополнительно проверять на наличие "false drops", т.е., проверять сами исходные документы, действительно ли они удовлетворяют поисковому запросу, что требует произвольного доступа к "heap" (таблице) и это сильно сказывается на производительности. Степень неоднозначности (lossiness), а следовательно и производительность GiST-индекса, зависит от кол-ва уникальных лексем и количества документов, что ограничивает применимость этого индекса для больших коллекций.

Но это не вся правда о GiST-индексе ! На самом деле, в листьях могут храниться не сигнатуры, а сами tsvector-а, если они не превышают TOAST_INDEX_TARGET байт, что-то около 512 байт. В этом случае попадание является точным и проверять ничего не надо. К сожалению, пока нет возможности индексу сказать какое было попадание, но в будущем, когда появится такая возможность, эта оптимизация может очень хорошо работать для новостных сайтов, где документы не очень большие. Чтобы изучить GiST-индекс, можно воспользоваться специальным модулем Gevel [GEVEL], который выдает полезную информацию об индексе. Вот пример такой выдачи для индекса gist_idx_50 для базы, которая содержит небольшие сообщения. Обратите внимание, что листья содержат как сами tsvector-а, так и сигнатуры, а внутренние ноды - только сигнатуры.

arxiv=# select gist_stat('gist_idx_90'); gist_stat -------------------------------------------- Number of levels: 4 Number of pages: 18296 Number of leaf pages: 17496 Number of tuples: 435661 Number of invalid tuples: 0 Number of leaf tuples: 417366 Total size of tuples: 124776048 bytes Total size of leaf tuples: 119803816 bytes Total size of index: 149880832 bytes

-- leaf node arxiv=# select * from gist_print('gist_idx_90') as t(level int,valid bool, fts gtsvector) where level =4; level | valid | fts -------+-------+-------------------------------- 4 | t | 130 true bits, 1886 false bits 4 | t | 95 unique words 4 | t | 33 unique words 4 | t | 77 unique words 4 | t | 68 unique words 4 | t | 86 unique words 4 | t | 77 unique words 4 | t | 51 unique words 4 | t | 122 unique words 4 | t | 127 true bits, 1889 false bits 4 | t | 105 unique words 4 | t | 170 true bits, 1846 false bits 4 | t | 77 unique words 4 | t | 121 true bits, 1895 false bits .................................... 4 | t | 61 unique words (417366 rows)

-- internal node arxiv=# select * from gist_print('gist_idx_90') as t(level int, valid bool, fts gtsvector) where level =3;

level | valid | fts -------+-------+-------------------------------- 3 | t | 852 true bits, 1164 false bits 3 | t | 861 true bits, 1155 false bits 3 | t | 858 true bits, 1158 false bits 3 | t | 872 true bits, 1144 false bits 3 | t | 858 true bits, 1158 false bits 3 | t | 855 true bits, 1161 false bits 3 | t | 853 true bits, 1163 false bits 3 | t | 857 true bits, 1159 false bits .................................................. 3 | t | 782 true bits, 1234 false bits 3 | t | 773 true bits, 1243 false bits (17496 rows)

Какой индекс использовать ?

После появления GIN-индекса, который хорошо шкалируется, может возникнуть ощущение, что GiST-индекс не нужен. Чтобы сравнить эти индексы мы взяли большую коллекцию абстрактов научных статей из arxiv.org (спасибо Сергею Карпову, который скачал и залил их в базу данных), которая содержит 459841 абстрактов. Вся база занимает чуть больше одного гигабайта. Подробнее можно прочитать на wiki [GINGIST], а здесь мы приведем только результаты (все времена приведены в миллисекундах). Тестировались три индекса - GiN-индекс и два GiST-индекса с разными факторами заполнения (fillfactor). GiN-индекс пока не поддерживате fillfactor.

index creation(ms) size (b) count(*) rank query ------------------------------------------------------------------------- GiN 532310.368 305864704 38.739 130.488 GIST100 189321.561 130465792 120.730 215.153 GIST50 164669.614 279306240 122.101 200.963

Здесь count(*) - это простой поисковый запрос, а rank query - это поисковый запрос с ранжированием.

Обновление индекса проверялось для 95,1035,10546 записей.

index (nlev) 95 1035 10546 ----------------------------------------------------------- GIN 3343.881 36337.733 217577.424 GIST50 (5) 238.101 2952.362 33984.443 GIST100 (4) 232.674 2460.621 27852.507

Выводы:

создание индекса - GIN требует в 3 раза больше времени чем GiST

размер индекса - GiN-индекс в 2-3 раза больше GiST-индекса

время поиска - GiN-индекс в 3 раза быстрее, чем GiST-индекс

обновление индекса - GiN-индекс обновляется в 10 раз медленнее

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

Очень простой парсер

Предположим, что мы хотим создать свой парсер, который выделяет только один тип токена - слово (3,word,Word) и подключить его к полнотекстовому поиску. Для этого нам нужен еще один тип токена - это разделитель (12, blank,Space symbols). Идентификаторы типов (3,12) выбраны таким образом, чтобы можно было использовать стандартную функцию headline.

Поместите файлы test_parser.c, Makefile, test_parser.sql.in

в директорию contrib/test_parser, затем загрузите парсер в базу данных (в данном примере regression).

make make install psql regression < test_parser.sql

Мы создали тестовую FTS конфигурацию testcfg, для которой определен парсер testparser.

Для написания своего парсера необходимо разработать как-минимум 4 функции, см. SQL команду .

=# SELECT * FROM parse('testparser','That''s my first own parser'); tokid | token -------+-------- 3 | That's 12 | 3 | my 12 | 3 | first 12 | 3 | own 12 | 3 | parser =# SELECT to_tsvector('testcfg','That''s my first own parser'); to_tsvector ------------------------------------------------- 'my':2 'own':4 'first':3 'parser':5 'that''s':1 =# SELECT headline('testcfg','Supernovae stars are the brightest phenomena in galaxies', to_tsquery('testcfg', 'star')); headline ----------------------------------------------------------------- Supernovae stars are the brightest phenomena in galaxies

Файл test_parser.c

#ifdef PG_MODULE_MAGIC PG_MODULE_MAGIC; #endif

/* * types */

/* self-defined type */ typedef struct { char * buffer; /* text to parse */ int len; /* length of the text in buffer */ int pos; /* position of the parser */ } ParserState;

/* copy-paste from wparser.h of tsearch2 */ typedef struct { int lexid; char *alias; char *descr; } LexDescr;

/* * prototypes */ PG_FUNCTION_INFO_V1(testprs_start); Datum testprs_start(PG_FUNCTION_ARGS);

PG_FUNCTION_INFO_V1(testprs_getlexeme); Datum testprs_getlexeme(PG_FUNCTION_ARGS);

PG_FUNCTION_INFO_V1(testprs_end); Datum testprs_end(PG_FUNCTION_ARGS);

PG_FUNCTION_INFO_V1(testprs_lextype); Datum testprs_lextype(PG_FUNCTION_ARGS);

/* * functions */ Datum testprs_start(PG_FUNCTION_ARGS) { ParserState *pst = (ParserState *) palloc(sizeof(ParserState)); pst->buffer = (char *) PG_GETARG_POINTER(0); pst->len = PG_GETARG_INT32(1); pst->pos = 0;

PG_RETURN_POINTER(pst); }

Datum testprs_getlexeme(PG_FUNCTION_ARGS) { ParserState *pst = (ParserState *) PG_GETARG_POINTER(0); char **t = (char **) PG_GETARG_POINTER(1); int *tlen = (int *) PG_GETARG_POINTER(2); int type;

*tlen = pst->pos; *t = pst->buffer + pst->pos;

if ((pst->buffer)[pst->pos] == ' ') { /* blank type */ type = 12; /* go to the next non-white-space character */ while (((pst->buffer)[pst->pos] == ' ') && (pst->pos < pst->len)) { (pst->pos)++; } } else { /* word type */ type = 3; /* go to the next white-space character */ while (((pst->buffer)[pst->pos] != ' ') && (pst->pos < pst->len)) { (pst->pos)++; } }

*tlen = pst->pos - *tlen;

/* we are finished if (*tlen == 0) */ if (*tlen == 0) type=0;

PG_RETURN_INT32(type); } Datum testprs_end(PG_FUNCTION_ARGS) { ParserState *pst = (ParserState *) PG_GETARG_POINTER(0); pfree(pst); PG_RETURN_VOID(); }

Datum testprs_lextype(PG_FUNCTION_ARGS) { /* Remarks: - we have to return the blanks for headline reason - we use the same lexids like Teodor in the default word parser; in this way we can reuse the headline function of the default word parser. */ LexDescr *descr = (LexDescr *) palloc(sizeof(LexDescr) * (2+1));

/* there are only two types in this parser */ descr[0].lexid = 3; descr[0].alias = pstrdup("word"); descr[0].descr = pstrdup("Word"); descr[1].lexid = 12; descr[1].alias = pstrdup("blank"); descr[1].descr = pstrdup("Space symbols"); descr[2].lexid = 0;

PG_RETURN_POINTER(descr); }

Файл Makefile

override CPPFLAGS := -I. $(CPPFLAGS)

MODULE_big = test_parser OBJS = test_parser.o

DATA_built = test_parser.sql DATA = DOCS = README.test_parser REGRESS = test_parser

ifdef USE_PGXS PGXS := $(shell pg_config --pgxs) include $(PGXS) else subdir = contrib/test_parser top_builddir = ../.. include $(top_builddir)/src/Makefile.global include $(top_srcdir)/contrib/contrib-global.mk endif

Файл test_parser.sql.in

SET search_path = public;

BEGIN;

CREATE FUNCTION testprs_start(internal,int4) RETURNS internal AS 'MODULE_PATHNAME' LANGUAGE 'C' with (isstrict);

CREATE FUNCTION testprs_getlexeme(internal,internal,internal) RETURNS internal AS 'MODULE_PATHNAME' LANGUAGE 'C' with (isstrict);

CREATE FUNCTION testprs_end(internal) RETURNS void AS 'MODULE_PATHNAME' LANGUAGE 'C' with (isstrict);

CREATE FUNCTION testprs_lextype(internal) RETURNS internal AS 'MODULE_PATHNAME' LANGUAGE 'C' with (isstrict);

CREATE FULLTEXT PARSER testparser START 'testprs_start' GETTOKEN 'testprs_getlexeme' END 'testprs_end' LEXTYPES 'testprs_lextype' ;

CREATE FULLTEXT CONFIGURATION testcfg PARSER 'testparser' LOCALE NULL; CREATE FULLTEXT MAPPING ON testcfg FOR word WITH simple;

END;

Поддержка в psql

Информацию о полнотекстовых объектах можно получить в psql

с помощью команд \dF{,d,p}[+] [PATTERN]. Здесь

знак + используется для показа расширенной информации

{,d,p} - указывает информацию о каких объектах показывать. По умолчанию показывается информация о полнотекстовых конифгурациях.

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

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

Поиск с очепятками

Часто полнотекстовый поиск используется совместно с модулем contrib/pg_trgm, который на основе статистики триграмм позволяет находить слова, наиболее близкие к запросу.

=# select show_trgm('supyrnova'); show_trgm ------------------------------------------------- {" s"," su",nov,ova,pyr,rno,sup,upy,"va ",yrn}

С помощью функции stat мы собираем информацию о всех индексируемых словах и затем строим триграммный индекс.

=# select * into apod_words from stat('select fts from apod') order by ndoc desc, nentry desc,word;

=# create index trgm_idx on apod_words using gist(word gist_trgm_ops);

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

=# select word, similarity(word, 'supyrnova') AS sml from apod_words where word % 'supyrnova' order by sml desc, word; word | sml ---------------+---------- supernova | 0.538462 pre-supernova | 0.411765 (2 rows)

Из соображений производительности, слова, у которых похожесть не превышает некоторый порог, отбрасываются. Посмотреть значение порога и изменить его можно с помощью функций show_limit() и set_limit(real). По умолчанию используется значение 0.3.

Полнотекстовый поиск в PostgreSQL

Как и многие современные СУБД, PostgreSQL [PGSQL] имеет встроенный механизм полнотекстового поиска. Отметим, что операторы поиска по текстовым данных существовали очень давно, это операторы LIKE, ILIKE, ~, ~*. Однако, они не годились для эффективного полнотекстового поиска, так как

у них не было лингвистической поддержки, например, при поиске слова satisfies будут не найдены документы со словом satisfy и никакими регулярными выражениями этому не помочь. В принципе, используя OR и все формы слова, можно найти все необходимые документы, но это очень неэффективно, так как в некоторых языках могут быть слова со многими тысячами форм!

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

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

Для улучшения ситуации авторы этой статьи предложили и реализовали новый полнотекстовый поиск, существовавший как модуль расширения и интегрированный в PostgreSQL, начиная с версии 8.3.

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

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

Таким образом, были созданы новые типы данных - tsvector, который является хранилищем для лексем из документа, оптимизированного для поиска, и tsquery - для запроса с поддержкой логических операций, полнотекстовый оператор "две собаки" @@ и индексная поддержка для него с использованием [GiST] и [GIN]. tsvector помимо самих лексем может хранить информацию о положении лексемы в документе и ее весе (важности), которая потом может использоваться для вычисления ранжирующей информации.

=# select 'cat & rat':: tsquery @@ 'a fat cat sat on a mat and ate a fat rat'::tsvector; ?column? ---------- t =# select 'fat & cow':: tsquery @@ 'a fat cat sat on a mat and ate a fat rat'::tsvector; ?column? ---------- f

Кроме этого, были реализованы вспомогательные функции

to_tsvector для преобразования документа в tsvector

=# select to_tsvector('a fat cat sat on a mat - it ate a fat rats'); to_tsvector ----------------------------------------------------- 'ate':9 'cat':3 'fat':2,11 'mat':7 'rat':12 'sat':4

to_tsquery - для получения tsquery

=# select to_tsquery('fat & cats'); to_tsquery --------------- 'fat' & 'cat'

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

=# select "Alias","Token","Description" from ts_debug('12 cats'); Alias | Token | Description -------+-------+------------------ uint | 12 | Unsigned integer blank | | Space symbols lword | cats | Latin word

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

=# select "Alias","Token","Dicts list","Lexized token" from ts_debug('as 12 cats'); Alias | Token | Dicts list | Lexized token -------+-------+----------------------+--------------------------- lword | as | {pg_catalog.en_stem} | pg_catalog.en_stem: {} blank | | | uint | 12 | {pg_catalog.simple} | pg_catalog.simple: {12} blank | | | lword | cats | {pg_catalog.en_stem} | pg_catalog.en_stem: {cat}

На этом примере мы видим, что токен 'as' обработался словарем pg_catalog.en_stem, распознался как стоп-слово и не попал в полнотекстовый индекс, в то время как токены '12' и 'cats' распознались словарями, нормализовались и попали в индекс.

Каждый словарь по-своему понимает, что такое "нормализация", однако, интуитивно понятно, что в результате нормализации, группы слов, объединенные по тому или иному признаку, приводятся к одному слову. Это позволяет при поиске этого "нормализованного" слова найти все документы, содержащие слова из этой группы. Наиболее привычная нормализация для нас - это приведение существительного к единственному числу и именительному падежу, например, слово 'стол' является нормальной формой слов 'столы', 'столов', 'столами', 'столу' и т.д. Не менее естественным представляется приведение имен директорий '/usr/local/bin', '/usr/local/share/../bin', '/usr/local/./bin/' к к стандартному виду '/usr/local/bin'.

Комбинация парсера и правил обработки токенов определяет полнотекстовую конфигурацию, которых может быть произвольное количество. Большое количество конфигураций для 10 европейских языков и разных локалей уже встроено в PostgreSQL и хранится в системном каталоге, в схеме pg_catalog. Практически все функции поиска зависят от полнотекстовой конфигурации, которая является необязательным параметром. Необязательность определяет необходимость наличия способа выбора конфигурации по умолчанию. Этим способом является соответствие названия серверной локали, которую можно посмотреть с помощью команд show lc_ctype; и show lc_collate; и локали, приписанной к полнотекстовой конфигурации.

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

Несмотря на богатые возможности по настраиванию полнотекстового поиска практически под любую задачу, возможности, предоставленные по умолчанию, вполне достаточны для организации полноценного поиска для широкого класса задач. Более того, для очень простого поиска, когда не требуется ранжирования документов, например, поиск по заголовкам новостей, когда есть естественный способ сортировки документов по времени, можно организовать с помощью всего одной команды. Для примера мы будем использовать таблицу apod, которая содержит архив известной Астрономической Картинки Дня [APOD].

=# \d apod Table "public.apod" Column | Type | Modifiers ----------+----------+----------- id | integer | not null title | text | body | text | sdate | date | keywords | text | Indexes: "apod_pkey" PRIMARY KEY, btree (id)

В этой таблице sdate - это дата документа, а атрибут keywords - строка с ключевыми словами через запятую, которые вручную редактор перевода присвоил документу. Создадим индекс по заголовкам:

CREATE INDEX tit_idx ON apod USING gin(title);

После этого уже можно искать

SELECT title FROM apod WHERE title @@ 'supernovae stars' ORDER by sdate limit 10;

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

Определяется активная полнотекстовая конфигурация по серверной локали. Название конфигурации можно посмотреть с помощью show tsearch_conf_name;

Атрибут title превращается в tsvector, по которому строится обратный индекс. При этом используется информация о парсерах и словарях, которая определяется полнотекстовой конфигурацией с именем tsearch_conf_name. Заметим, что так как tsvector

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

Полнофункциональный поиск требует создания нового атрибута для хранения tsvector, который оптимизирован для поиска и хранит позиционную информацию лексемы в документе и ее вес. Это можно сделать стандартными командами SQL

=# UPDATE apod SET fts= setweight( coalesce( to_tsvector(keywords),''),'A') setweight( coalesce( to_tsvector(title),''),'B') setweight( coalesce( to_tsvector(body),''),'D');

В этом примере мы добавили атрибут fts, который представляет собой конкатенацию текстовых полей keywords, title и body. При этом, с помощью функции setweight мы приписали разные веса лексемам из разных частей. Заметим, что мы приписали только "метки", не численные значения, которые будут приписаны этим самым меткам в момент поиска. Это позволяет настраивать поиск буквально налету, например, используя один и тот же полнотекстовый индекс можно организовывать поиск только по заголовкам и ключевым словам.

=# select * from apod where fts @@ to_tsquery('supernovae:ab');

На этом мы закончим введение в полнотекстовый поиск в PostgreSQL и приведем список основных возможностей.

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

Гибкая настройка всех компонентов поиска с помощью SQL команд. Встроенная поддержка для 10 европейских языков.

Подключение разных парсеров, которые можно писать с использованием API. Встроенный парсер поддерживает 23 типа токенов.

Богатая поддержка лингвистики, включая подключаемые словари с поддержкой стоп-слов. Встроенные словари-шаблоны для распространенных открытых словарей ispell, snowball позволяют использовать большое количество словарей для разных языков. Также, есть встроенные словари-шаблоны thesaurus, synonym. Открытый API позволяют разрабатывать новые словари для решения специфичных задач.

Полная поддержка многобайтных кодировок, в частности, UTF-8.

возможностью приписывания весов разным лексемам позволяют сортировку результатов поиска.

Поддержка индексов для ускорения поисков, при этом индексы поддерживают конкурентность и возможность восстановления после сбоев (concurrency and recovery), что очень важно для успешной работы в конкурентных условиях. Поддерживаются два типа индексов - GiST индексы очень хороши для частых обновлений, в то время как GIN индекс очень хорошо шкалируем с ростом коллекции. Это позволяет реализовывать полнотекстовый поиск по очень большим коллекциям документов, которые могут непрерывно обновляться.

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

Еще раз напомним, что полное и исчерпывающее описание полнотекстового поиска в PostgreSQL приведено в [FTSBOOK] (технический английский), советы и рекомендации можно посмотреть в презентации [RIT2007].

Астрономический поиск

Мы приведем пример организации полнотекстового поиска, который каждый может повторить с версией PostgreSQL 8.3+. Однако, большинство команд вполне должно работать и с PostgreSQL 8.2+, только вам для этого придется установить contrib/tsearch2 и загрузить в свою тестовую базу данных.

Исходные данные - архив [APOD].

> curl -O http://www.sai.msu.su/~megera/postgres/fts/apod.dump.gz > createdb apod (для PostgreSQL 8.2+ надо установить модуль contrib/tsearch2 и загрузить его в БД apod) > zcat apod.dump.gz | psql apod > psql apod

Структура таблицы apod. Отметим, что поле keywords

содержит ключевые слова, присвоенные экспертами вручную.

Текущая полнотекстовая конфигурация по умолчанию у нас pg_catalog.russian_utf8, так как наш кластер был создан командой с параметром --locale=ru_RU.UTF-8.

Выше, мы уже упоминали, что начиная с версии 8.3+ можно сделать простой полнотекстовый поиск в одну команду и приводили команду для добавления поля типа tsvector, чтобы получить полноценный поиск.

apod=# UPDATE apod SET fts= setweight( coalesce( to_tsvector(keywords),''),'A') setweight( coalesce( to_tsvector(title),''),'B') setweight( coalesce( to_tsvector(body),''),'D'); apod=# \d apod Table "public.apod" Column | Type | Modifiers ----------+----------+----------- id | integer | not null title | text | body | text | sdate | date | keywords | text | fts | tsvector | Indexes: "apod_pkey" PRIMARY KEY, btree (id)
После этого мы уже можем искать и ранжировать результаты поиска.
apod=# select title,rank_cd(fts, q) from apod, to_tsquery('supernovae & x-ray') q where fts @@ q order by rank_cd desc limit 5; title | rank_cd ------------------------------------------------+--------- Supernova Remnant E0102-72 from Radio to X-Ray | 1.59087 An X-ray Hot Supernova in M81 | 1.47733 X-ray Hot Supernova Remnant in the SMC | 1.34823 Tycho's Supernova Remnant in X-ray | 1.14318 Supernova Remnant and Neutron Star | 1.08116 (5 rows)
Time: 11.948 ms
Заметим, что никаких индексов не было создано, полнотекстовый поиск обязан работать и без них. Для ускорения поиска мы можем создать индекс и повторить запрос.
apod=# create index fts_idx on apod using gin (fts); apod=# select title,rank_cd(fts, q) from apod, to_tsquery('supernovae & x-ray') q where fts @@ q order by rank_cd desc limit 5; title | rank_cd ------------------------------------------------+--------- Supernova Remnant E0102-72 from Radio to X-Ray | 1.59087 An X-ray Hot Supernova in M81 | 1.47733 X-ray Hot Supernova Remnant in the SMC | 1.34823 Tycho's Supernova Remnant in X-ray | 1.14318 Supernova Remnant and Neutron Star | 1.08116 (5 rows)
Time: 1.998 ms
Видно, что результаты не изменились, как и должно быть, но время исполнения запросы уменьшилось на порядок. Что мы и хотели получить.
В запросе мы использовали функцию rank_cd, которая возвращает ранк документа относительно запроса. В нашем случае документ - это fts, а запрос - q или to_tsquery('supernovae & x-ray'). fts мы создавали из нескольких текстовых атрибутов, которым были присвоены разные веса. Их численные значения могут быть заданы в функции rank_cd, которые по умолчанию имеет следующие значения 0.1, 0.2, 0.4, 1.0, что соответствует D,C,B,A. Мы можем явно указать новые значения, например, подняв важность слов в заголовках, а важность ключевых слов сильно понизив, считая экспертов не очень компетентными.

apod=# select title,rank_cd('{0.1,0.2,1.0,0.1}',fts, q) from apod, to_tsquery('supernovae & x-ray') q where fts @@ q order by rank_cd desc limit 5; title | rank_cd ------------------------------------------------+---------- An X-ray Hot Supernova in M81 | 0.708395 X-ray Hot Supernova Remnant in the SMC | 0.646742 Supernova Remnant N132D in X-Rays | 0.577618 Cas A Supernova Remnant in X-Rays | 0.458009 Supernova Remnant E0102-72 from Radio to X-Ray | 0.44515 (5 rows)
Мы видим, как поменялись результаты. Отметим, что значения rank_cd
не имеют особенного смысла, имеет значение только порядок. Однако, иногда хочется иметь нормированное значение и в таком случае можно использовать rank_cd/(rank_cd+1), например.
Если мы хотим показать в результатах поиска выдержки из текста, то можно воспользоваться функцией headline.
apod=# select headline(body,q,'StartSel=<,StopSel=>,MaxWords=10,MinWords=5'), rank_cd(fts, q) from apod, to_tsquery('supernovae & x-ray') q where fts @@ q order by rank_cd desc limit 5; headline | rank_cd ----------------------------------------------------------------------+--------- <supernova> remnant E0102-72, however, is giving astronomers a clue | 1.59087 <supernova> explosion. The picture was taken in <X>-<rays> | 1.47733 <X>-<ray> glow is produced by multi-million degree | 1.34823 <X>-<rays> emitted by this shockwave made by a telescope | 1.14318 <X>-<ray> glow. Pictured is the <supernova> | 1.08116 (5 rows)
Time: 39.525 ms
Здесь мы указали, что выделять найденные слова надо с помощью уголков и размер текста должен быть не меньше 5 слов, но не более 10. Мы видим, что время поиска значительно увеличилось ! Это связано не только с тем, что действительно функция headline не очень быстрая, но и с распространенной ошибкой в нашем запросе - мы вычисляем довольно медленную функцию headline для всех найденных документов, которых 36, а не для нужных 5 !
apod=# select count(*) from apod where to_tsquery('supernovae & x-ray') @@ fts; count ------- 36

Правильный запрос использует subselect и мы получает тот же результат, но за гораздо меньшее время. Эффект может быть существенно выше, если общее количество найденных документов было бы не 36, а многие тысячи, например.
apod=# select headline(body,q, 'StartSel=<,StopSel=>,MaxWords=10,MinWords=5'), rank from ( select body,q, rank_cd(fts,q) as rank from apod, to_tsquery('supernovae & x-ray') q where fts @@ q order by rank desc limit 5 ) as foo; headline | rank_cd ----------------------------------------------------------------------+--------- <supernova> remnant E0102-72, however, is giving astronomers a clue | 1.59087 <supernova> explosion. The picture was taken in <X>-<rays> | 1.47733 <X>-<ray> glow is produced by multi-million degree | 1.34823 <X>-<rays> emitted by this shockwave made by a telescope | 1.14318 <X>-<ray> glow. Pictured is the <supernova> | 1.08116 (5 rows)
Time: 6.700 ms
Используя один и тот же полнотекстовый индекс fts мы можем искать по частям документа или их комбинациям. Например, можно потребовать, чтобы слово x-ray встречалось в заголовках документов.
apod=# select title,rank_cd(fts, q) from apod, to_tsquery('supernovae & x-ray:b') q where fts @@@ q order by rank_cd desc limit 5; title | rank_cd ------------------------------------------------+---------- Supernova Remnant E0102-72 from Radio to X-Ray | 1.59087 An X-ray Hot Supernova in M81 | 1.47733 X-ray Hot Supernova Remnant in the SMC | 1.34823 Tycho's Supernova Remnant in X-ray | 1.14318 Vela Supernova Remnant in X-ray | 0.703056 (5 rows)
Обратите внимание, что мы использовали новый оператор "три собаки" @@@, вместо двух. Это связано с особенностью использования GIN индекса совместно с заданием весов в запросе. Если не использовать индекс или использовать GIST индекс, то можно воспользоваться привычными "двумя собаками" @@.
apod=# set enable_bitmapscan to off; apod=# set enable_indexscan to off; apod=# select title,rank_cd(fts, q) from apod, to_tsquery('supernovae & x-ray:b') q where fts @@ q order by rank_cd desc limit 5; title | rank_cd ------------------------------------------------+---------- Supernova Remnant E0102-72 from Radio to X-Ray | 1.59087 An X-ray Hot Supernova in M81 | 1.47733 X-ray Hot Supernova Remnant in the SMC | 1.34823 Tycho's Supernova Remnant in X-ray | 1.14318 Vela Supernova Remnant in X-ray | 0.703056 (5 rows)

FTS конфигурация для www.postgresql.org

На сайтах postgresql.org вы можете увидеть полнотекстовый поиск в жизни. Объем индексированных документов - это около 600,0000 постингов в архивах рассылок и более 20,000 документов на сайте www.postgresql.org. Создадим полнотекстовую конфигурацию для такого поиска. Так как мы создаем тематический поиск, мы должны создать словарь синонимов pg_dict.txt, который содержит, например, все названия базы данных PostgreSQL и положим его в директорию $PGROOT/share/dicts_data.

postgres postgresql pgsql postgresql postgres postgresql

Теперь можно создать нашу конфигурацию public.pg

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

BEGIN; CREATE FULLTEXT CONFIGURATION public.pg LOCALE 'ru_RU.UTF-8' LIKE english WITH MAP; ALTER FULLTEXT CONFIGURATION public.pg SET AS DEFAULT; CREATE FULLTEXT DICTIONARY pg_dict OPTION 'pg_dict.txt' LIKE synonym; CREATE FULLTEXT DICTIONARY en_ispell OPTION 'DictFile="english-utf8.dict", AffFile="english-utf8.aff", StopFile="english-utf8.stop"' LIKE ispell_template; ALTER FULLTEXT DICTIONARY en_stem SET OPTION 'english-utf8.stop'; ALTER FULLTEXT MAPPING ON pg FOR lword,lhword,lpart_hword WITH pg_dict,en_ispell,en_stem; DROP FULLTEXT MAPPING ON pg FOR email, url, sfloat, uri, float; END;

Мы создали словарь на основе словаря ispell. Так как мы используем UTF-8, то мы используем конвертированные в UTF-8 файлы ispell. Далее, мы указали словарям en_ispell, en_stem

использовать стоп-слова для английского языка в директории $PGROOT/share/dicts_data. Затем, мы задали, что токены типа lword,lhword,lpart_hword, обозначающие английские слова, должны обрабатываться словарями pg_dict,en_ispell,en_stem

и именно в таком порядке. И напоследок, мы удалили правила для токенов, которые нас не интересуют - это email, url, sfloat, uri, float.

Более подробно можно прочитать в [FTSBOOKAPPA].

Распределение данных

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

select dblink_connect('pgweb','dbname=pgweb hostaddr='XXX.XXX.XXX.XXX');

select * from dblink('pgweb', 'select tid, title, rank_cd(fts_index, q) as rank from pgweb, to_tsquery(''table'') q where q @@ fts_index and tid >= 6000 order by rank desc limit 10' ) as t1 (tid integer, title text, rank real)

union all

select tid, title, rank_cd(fts_index, q) as rank from pgweb, to_tsquery('table') q where q @@ fts_index and tid < 6000 and tid > 0 order by rank desc limit 10

) as foo order by rank desc limit 10;

Отметим, что ранжирующая функция требует только локальной информации, что облегчает реализацию.

Сегментирование данных

Сегментирование данных можно организовать с помощью наследования (TABLE INHERITANCE) и CE (CONSTRAINT EXCLUSION). Идея состоит в том, чтобы иметь родительскую таблицу (класс), которая определяет основной набор атрибутов и таблицы, которые наследуют структуру родительской таблицы, но имеющие определенные ограничения на параметр, по которому проводится сегментирование. Механизм наследования в PostgreSQL обеспечивает выполнение запроса по всем таблицам автоматически, при этом наличие CE позволяет просматривать только те таблицы, которые удовлетворяют условию на параметр.

Типичная ситуация, когда сегментирование идет по времени, например, для хранение журналов веб-серверов.

В нашем примере мы создаем таблицу apod_class и две таблицы, которые наследуют ее. Эти таблицы наследуют структуру родительской таблицы, но при этом могут иметь свои специфические атрибуты. Таблица apod_new предназначена для новых сообщений, а apod_archive для неизменяющихся архивных документов. Заметим, что для новых сообщений мы создали GiST индекс, который очень хорошо обновляется, а для архивной таблицы создали GIN индекс, который очень хорошо шкалируется, но обновление, как и для всех обратных индексов, происходит очень медленно.

CREATE TABLE apod_class ( id integer, title text, body text, sdate date, keywords text, fts tsvector ); CREATE TABLE apod_new ( CHECK ( sdate >2001-08-08 ) ) INHERITS (apod_class); CREATE INDEX gist_idx ON apod_new USING gist(fts);

CREATE TABLE apod_archive ( CHECK ( sdate ≤2001-08-08 ) ) INHERITS (apod_class); CREATE INDEX gist_idx ON apod_new USING gin(fts);

PostgreSQL позволяет искать как по всей коллекции, указав таблицу apod_class, так и по отдельным частям. В зависимости от задачи, сегментировать данные можно и по большему количеству таблиц, например, распределять документы по годам, месяцам. Оптимизатор PostgreSQL автоматически выбирает только те таблицы, которые удовлетворяют условию CHECK, что очень благоприятно сказывается на производительности запросов. Например, для запроса

apod=# select title,rank_cd(fts, q) from apod_class, to_tsquery('stars') q where fts @@ q order by rank_cd desc limit 5;

будут просматриваться две таблицы, а для запроса

apod=# select title,rank_cd(fts, q) from apod_class, to_tsquery('stars') q where fts @@ q and sdate > 2001-08-08 order by rank_cd desc limit 5;

будет использоваться только таблица apod_new. Отметим, что для этого необходимо включить CONSTRAINT EXCLUSION

SET constraint_exclusion TO on;

Синхронизация полнотекстового индекса

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

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

CREATE FUNCTION dropatsymbol(text) RETURNS text AS 'select replace($1, ''@'', '' '');' LANGUAGE SQL;

CREATE TRIGGER tsvectorupdate BEFORE UPDATE OR INSERT ON tblMessages FOR EACH ROW EXECUTE PROCEDURE tsearch(tsvector_column,dropatsymbol, strMessage);

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

(не забудьте разрешить его использование с помощью команды createlang plpgsql DBNAME).

Создадим тестовую табличку со следующей структурой.

CREATE TABLE aa ( id integer primary key, t1 text, t2 text, fts tsvector );

=# create function my_update() returns trigger as $$ BEGIN NEW.fts= setweight( to_tsvector('english',NEW.t1),'A') setweight( to_tsvector('english',NEW.t2),'B'); RETURN NEW; END; $$ language plpgsql;

В этой функции мы для простоты опустили использование coalesce().

CREATE TRIGGER fts_update BEFORE INSERT OR UPDATE ON aa FOR EACH ROW EXECUTE PROCEDURE my_update();

=# insert into aa (id, t1,t2) values(1,'12,15,789,3','500'); =# insert into aa (id, t1,t2) values(2,'-546,3','150'); =# select * from aa; id | t1 | t2 | fts ----+-------------+-----+------------------------------------------ 1 | 12,15,789,3 | 500 | '3':4A '12':1A '15':2A '500':5B '789':3A 2 | -546,3 | 150 | '3':2A '150':3B '-546':1A (2 rows)

Как мы видим, вставка новых записей работает как и ожидалось. Проверим обновление.

=# update aa set t1 = '1234567' where id=1; =# select * from aa; id | t1 | t2 | fts ----+---------+-----+--------------------------- 2 | -546,3 | 150 | '3':2A '150':3B '-546':1A 1 | 1234567 | 500 | '500':2B '1234567':1A (2 rows)

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

If ( OLD.t1 <> NEW.t1 or OLD.t2 <> NEW.t2 ) Then -- получение fts Endif

Словарь для целых чисел

В качестве примера нового словаря для полнотекстового поиска мы рассмотрим словарь для целых чисел intdict, который "обрезает" целые числа, так что общее количество уникальных слов уменьшается, что в целом благоприятно сказывается на производительности поиска. У словаря есть два параметра MAXLEN, который контролирует максимальную длину числа, и REJECTLONG, который указывает считать ли длинное целое число стоп-словом или нет. По умолчанию MAXLEN=6,REJECTLONG=false.

Для создания словаря необходимо написать две функции, имена которых потом будут использованы в команде CREATE FULLTEXT DICTIONARY ниже. Функция init_intdict инициализирует словарь - задает значения параметров по умолчанию и принимает их новые значения, функция dlexize_intdict

делает всю основную работу - возвращает NULL, если слово неопознанно, пустой массив, если словарь решил, что входная строка это стоп-слово, или массив лексем, в противном случае.

Словарь просто обрезает длинные целые числа.

=# select lexize('intdict', 11234567890); lexize ---------- {112345}

Теперь будем трактовать длинные целые числа как стоп-слово.

=# ALTER FULLTEXT DICTIONARY intdict SET OPTION 'MAXLEN=6, REJECTLONG=TRUE'; =# select lexize('intdict', 11234567890); lexize -------- {}

Файлы dict_tmpl.c,Makefile,dict_intdict.sql.in

надо положить в директорию contrib/dict_intdict. После этого надо установить словарь и загрузить словарь в базу DBNAME.

make && make install psql DBNAME < dict_intdict.sql

Файл dict_tmpl.c:

#include "postgres.h" #include "utils/builtins.h" #include "fmgr.h"

#ifdef PG_MODULE_MAGIC PG_MODULE_MAGIC; #endif

#include "utils/ts_locale.h" #include "utils/ts_public.h" #include "utils/ts_utils.h"

typedef struct { int maxlen; bool rejectlong; } DictInt;

PG_FUNCTION_INFO_V1(dinit_intdict); Datum dinit_intdict(PG_FUNCTION_ARGS);

Datum dinit_intdict(PG_FUNCTION_ARGS) { DictInt *d = (DictInt*)malloc( sizeof(DictInt) ); Map *cfg, *pcfg; text *in;

if ( !d ) elog(ERROR, "No memory"); memset(d,0,sizeof(DictInt));

/* Your INIT code */ /* defaults */ d->maxlen = 6; d->rejectlong = false;

if ( PG_ARGISNULL(0) PG_GETARG_POINTER(0) == NULL ) { /* no options */ PG_RETURN_POINTER(d); } in = PG_GETARG_TEXT_P(0); parse_keyvalpairs(in,&cfg); PG_FREE_IF_COPY(in, 0); pcfg=cfg;

while (pcfg->key) { if ( strcasecmp("MAXLEN", pcfg->key) == 0 ) { d->maxlen=atoi(pcfg->value); } else if ( strcasecmp("REJECTLONG", pcfg->key) == 0 ) { if ( strcasecmp("true", pcfg->value) == 0 ) { d->rejectlong=true; } else if ( strcasecmp("false", pcfg->value) == 0 ) { d->rejectlong=false; } else { elog(ERROR,"Unknown value: %s => %s", pcfg->key, pcfg->value); } } else { elog(ERROR,"Unknown option: %s => %s", pcfg->key, pcfg->

value); } pfree(pcfg->key); pfree(pcfg->value); pcfg++; } pfree(cfg);

PG_RETURN_POINTER(d); }

PG_FUNCTION_INFO_V1(dlexize_intdict); Datum dlexize_intdict(PG_FUNCTION_ARGS); Datum dlexize_intdict(PG_FUNCTION_ARGS) { DictInt *d = (DictInt*)PG_GETARG_POINTER(0); char *in = (char*)PG_GETARG_POINTER(1); char *txt = pnstrdup(in, PG_GETARG_INT32(2)); TSLexeme *res=palloc(sizeof(TSLexeme)*2);

/* Your INIT dictionary code */ res[1].lexeme = NULL; if ( PG_GETARG_INT32(2) > d->maxlen ) { if ( d->rejectlong ) { /* stop, return void array */ pfree(txt); res[0].lexeme = NULL; } else { /* cut integer */ txt[d->maxlen] = '\0'; res[0].lexeme = txt; } } else { res[0].lexeme = txt; }

PG_RETURN_POINTER(res); }

Файл Makefile:

subdir = contrib/dict_intdict top_builddir = ../.. include $(top_builddir)/src/Makefile.global

MODULE_big = dict_intdict OBJS = dict_tmpl.o DATA_built = dict_intdict.sql DOCS =

include $(top_srcdir)/contrib/contrib-global.mk

Файл dict_intdict.sql.in:

SET search_path = public; BEGIN;

CREATE OR REPLACE FUNCTION dinit_intdict(internal) returns internal as 'MODULE_PATHNAME' language 'C';

CREATE OR REPLACE FUNCTION dlexize_intdict(internal,internal,internal,internal) returns internal as 'MODULE_PATHNAME' language 'C' with (isstrict);

CREATE FULLTEXT DICTIONARY intdict LEXIZE 'dlexize_intdict' INIT 'dinit_intdict' OPTION 'MAXLEN=6,REJECTLONG=false' ; END;

Советы по повышению производительности

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

SQL команды

CREATE FULLTEXT CONFIGURATION - создание полнотекстовой конфигурации

CREATE FULLTEXT CONFIGURATION cfgname PARSER prsname [ LOCALE localename] [AS DEFAULT];

CREATE FULLTEXT CONFIGURATION cfgname [{ PARSER prsname | LOCALE localename } [ ...]] LIKE template_cfg [WITH MAP] [AS DEFAULT];

FTS конфигурация принадлежит пользователю, который создал ее

Имя конфигурации cfgname может содержать название схемы, тогда она будет создана в этой схеме, иначе конфигурация будет создана в текущей схеме.

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

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

LIKE template_cfg указывает, что в качестве шаблона используется существующая FTS конфигурация template_cfg.

WITH MAP используется с LIKE template_cfg и означает, что также копируются правила обработки токенов словарями.

Примеры:

DROP FULLTEXT CONFIGURATION - удалить FTS конфигурацию

DROP FULLTEXT CONFIGURATION [IF EXISTS]cfgname [ CASCADE | RESTRICT ];

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

CASCADE - автоматически удалить все FTS объекты, зависящие от удаляемой FTS конфигурации.

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

ALTER FULLTEXT CONFIGURATION - изменить FTS конфигурацию

ALTER FULLTEXT CONFIGURATION cfgname RENAME TO newcfgname;

ALTER FULLTEXT CONFIGURATION cfgname SET { LOCALE localename | PARSER prsname } [, ...];

ALTER FULLTEXT CONFIGURATION cfgname { SET AS | DROP } DEFAULT;

Эта команда позволяет изменить параметры, задаваемые при ее создании.

CREATE FULLTEXT DICTIONARY - создать словарь

CREATE FULLTEXT DICTIONARY dictname LEXIZE lexize_function [INIT init_function ] [OPTION opt_text ] ;

CREATE FULLTEXT DICTIONARY dictname [ { INIT init_function | LEXIZE lexize_function | OPTION opt_text } [ ... ]] LIKE template_dictname;

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

LEXIZE lexize_function - название функции, которая занимается преобразованием токена в лексему.

INIT init_function - название функции, которая инициализирует словарь

OPTION opt_text - задает текстовую строку, которая доступна словарю. Обычно, ее используют для указания файлов, используемых словарем. Относительные пути для словарных файлов интерпретируются относительно директории $PGROOT/share/dicts_data.

LIKE template_dictname - задает словарь-шаблон, используемый для создания словаря. При этом, значения параметров INIT, LEXIZE, OPTION, если заданы, перекрывают значения по умолчанию.

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

=# CREATE FULLTEXT DICTIONARY public.my_simple OPTION 'english.stop' LIKE pg_catalog.simple; =# select lexize('public.my_simple','YeS'); lexize -------- {yes} =# select lexize('public.my_simple','The'); lexize -------- {}

Пример создания нового словаря можно посмотреть в .

DROP FULLTEXT DICTIONARY - удаляет словарь

DROP FULLTEXT DICTIONARY [IF EXISTS]dictname [ CASCADE | RESTRICT ];

ALTER FULLTEXT DICTIONARY - изменяет параметры словаря

ALTER FULLTEXT DICTIONARY dictname RENAME TO newdictname;

ALTER FULLTEXT DICTIONARY dictname SET OPTION opt_text;

CREATE FULLTEXT MAPPING - создать правила обработки токенов словарями

CREATE FULLTEXT MAPPING ON cfgname FOR tokentypename[, ...] WITH dictname1[, ...];

Для FTS конфигурации cfgname задается соответствие между списком tokentypename1,tokentypename2,...

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

tokentypename[, ...] - список типов токенов, например, lword,lhword,lpart_hword.

dictname1[, ...] - список словарей, которые будут пытаться опознать токены. Порядок словарей важен.

Например, создадим тестовую конфигурацию testcfg на основе шаблона russian_utf8 и зададим правила обработки английских слов lhword,lpart_hword,lword.

=# CREATE FULLTEXT CONFIGURATION testcfg LOCALE 'testlocale' LIKE russian_utf8; =# CREATE FULLTEXT MAPPING ON testcfg FOR lword,lhword,lpart_hword WITH simple,en_stem; =# \dF+ testcfg Configuration 'testcfg' Parser name: 'default' Locale: 'testlocale' Token | Dictionaries -------------+---------------- lhword | simple,en_stem lpart_hword | simple,en_stem lword | simple,en_stem

ALTER FULLTEXT MAPPING - изменить правило обработки токенов

ALTER FULLTEXT MAPPING ON cfgname FOR tokentypename[, ...] WITH dictname1[, ...];

ALTER FULLTEXT MAPPING ON cfgname [FOR tokentypename[, ...] ] REPLACE olddictname TO newdictname;

Позволяет добавлять новые правила обработки токенов или изменять старые. Изменим правило для токена типа lword, см. предыдущий пример.

=# ALTER FULLTEXT MAPPING ON testcfg FOR lhword WITH simple; =# \dF+ testcfg Configuration 'testcfg' Parser name: 'default' Locale: 'testlocale' Token | Dictionaries --------+---------------- lhword | simple,en_stem lpart_hword | simple,en_stem lword | simple

DROP FULLTEXT MAPPING - удалить правило обработки токена

DROP FULLTEXT MAPPING [IF EXISTS] ON cfgname FOR tokentypename;

CREATE FULLTEXT PARSER - создать FTS парсер

CREATE FULLTEXT PARSER prsname START= start_function GETTOKEN gettoken_function END end_function LEXTYPES lextypes_function [ HEADLINE headline_function ] ;

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

start_function - название функции, которая инициализирует парсер.

gettoken_function - название функции, которая возвращает токен.

end_function - название функции, которая вызывается после окончания работы парсера.

lextypes_function - название функции, которая возвращает массив, содержащий {id,alias,full descr} - идентификатор, краткое название токена и полное описание. Подробнее, смотри в src/include/utils/ts_public.h.

headline_function, - название функции, которая возвращает часть документа, содержащая запрос.

Встроенный парсер называется default и распознает 23 типа токенов, список которых можно получить с помощью функции token_type(prsname). Пример создания нового парсера можно посмотреть в

DROP FULLTEXT PARSER - удалить FTS парсер

DROP FULLTEXT PARSER [IF EXISTS] prsname [ CASCADE | RESTRICT ];

ALTER FULLTEXT PARSER - изменить имя FTS парсера

ALTER FULLTEXT PARSER prsname RENAME TO newprsname;

ALTER FULLTEXT ... OWNER - изменить владельца

ALTER FULLTEXT { PARSER|DICTIONARY|CONFIGURATION } name OWNER TO newowner;

По умолчанию, владельцем FTS объекта является тот, кто создал его. Команда ALTER FULLTEXT ... OWNER позволяет менять владельца.

COMMENT ON FULLTEXT - создать или изменить комментарий FTS объекта

COMMENT ON FULLTEXT { CONFIGURATION | DICTIONARY | PARSER } objname IS text;

Комментарий виден при использовании + в команде psql, например, \dFd+ - показать расширенную информацию о словарях.

Для того чтобы убрать комментарий, надо задать NULL для параметра text.

=# COMMENT ON FULLTEXT DICTIONARY intdict IS 'Dictionary for integers';

Ссылки

[PGSQL]	"Что такое PostgreSQL", О.Бартунов, Сайт проекта
[GIST]	"Написание расширений для PostgreSQL с использованием GiST", О.Бартунов, Ф. Сигаев
[RDTREE]	"THE RD-TREE: AN INDEX STRUCTURE FOR SETS", Joseph M. Hellerstein
[GIN]	"Gin for PostgreSQL", "GIN Presentation on PostgreSQL Anniversary Summit", 2006
[APOD]	Astronomical Picture of the Day, Русский перевод на сайте Астронет
[FTSBOOK]	"Full-Text Search in PostgreSQL", O.Bartunov, T.Sigaev
[FTSBOOKAPPA]	Краткий пример создания полнотекстового поиска
[FTSBOOKEBUG]	Тестирование и отладка полнотекстовой конфигурации
[ISPELL]	http://ficus-www.cs.ucla.edu/geoff/ispell.html
[MYSPELL]	http://en.wikipedia.org/wiki/MySpell
[HUNSPELL]	http://sourceforge.net/projects/hunspell
[SNOWBALL]	Проект Snowball
[OODICTS]	http://wiki.services.openoffice.org/wiki/Dictionaries
[RIT2007]	Презентация на RIT-2007
[GINGIST]	Gin or GiST?
[GEVEL]	http://www.sai.msu.su/~megera/wiki/Gevel

Тестирование настроек

Зачастую бывает необходимо потестировать свою полнотекстовую конфигурацию. Для этог существует встроенная функция ts_debug, которая наглядно показывает что происходит с текстом. Она подробно описана в документации [FTSBOOKDEBUG], мы приведем лишь пример:

apod=# select * from ts_debug('the Supernovae stars'); Alias | Description | Token | Dicts list | Lexized token -------+---------------+------------+----------------------+--------------------------------- lword | Latin word | the | {pg_catalog.en_stem} | pg_catalog.en_stem: {} blank | Space symbols | | | lword | Latin word | Supernovae | {pg_catalog.en_stem} | pg_catalog.en_stem: {supernova} blank | Space symbols | | | lword | Latin word | stars | {pg_catalog.en_stem} | pg_catalog.en_stem: {star} (5 rows)

Здесь заслуживает внимание последняя колонка, которая называется "Lexized token". В ней содержится имя словаря, который распознал токен и массив лексем, в который этот словарь преобразовал токен. Так как у нас настроен только один словарь pg_catalog.en_stem, который к тому же распознает любые слова, то все токены им и распознались. Токен the распознался как стоп-слово, поэтому мы получили пустой массив и оно не будет проиндексировано. Остальные токены были приведены к некоторому нормальному виду.

Можно указать явно название полнотекстовой конфигурации, что бы протестировать ее.

apod=# select * from ts_debug('simple','the Supernovae stars'); Alias | Description | Token | Dicts list | Lexized token -------+---------------+------------+---------------------+--------------------------------- lword | Latin word | the | {pg_catalog.simple} | pg_catalog.simple: {the} blank | Space symbols | | | lword | Latin word | Supernovae | {pg_catalog.simple} | pg_catalog.simple: {supernovae} blank | Space symbols | | | lword | Latin word | stars | {pg_catalog.simple} | pg_catalog.simple: {stars} (5 rows)

Как мы уже указывали выше, тестировать словари можно с помощью функции lexize.

Парсеры также можно тестировать использую функцию parse.

в базах данных является одним

Полнотекстовый поиск в базах данных является одним из востребованных механизмов доступа к содержимому любой современной информационной системы, которые хранят метаинформацию, а зачастую, и сами документы, в базе данных. Современные веб-сайты, по сути, являются интерфейсом, способом организации доступа к базам данных. По мере накопления документов в системе неминуемо возникает проблема организации эффективной навигации по системе, чтобы посетитель сайта смог за минимальное количество кликов найти нужный документ. Помимо стандартной, зачастую ручной, навигации с использованием рубрикации (тематической, по типу материалов, категории пользователей и т.д.), полнотекстовый поиск является одним из самых эффективных методов навигации, особенно для новичков, незнакомых с устройством сайта.
Из нашего повседневного опыта мы понимаем, что хороший поиск - это поиск, который в ответ на наш запрос быстро найдет релевантные документы. И такие машины, казалось бы, существуют, например, широко известные поисковые машины как глобальные - "Google", так и наши российские - "Яндекс", "Рамблер". Более того, существует большое количество поисковиков, платных и бесплатных, которые позволяют индексировать всю вашу коллекцию документов и организовать вполне качественный поиск. Владельцу сайта остается только "скармливать" таким поисковикам контент по мере его появления. Это можно организовать несколькими способами - доступ через http-протокол, используя URL документа, как это делают большие внешние поисковики, или организация доступа к содержимому базы данных. В обоих случаях полнотекстовый индекс является внешним по отношению к базе данных. Часто такой подход оправдан и хорошо работает на многих сайтах, несмотря на некоторые недостатки, такие как неполная синхронизация содержимого БД, нетранзакционность, отсутствие доступа к метаданным и использование их для ограничения области поиска или, например, организации определенной политики доступа к документам, и т.д.

Мы не будем касаться таких поисковых машин, а будем рассматривать полнотекстовый поиск, который полностью интегрирован с СУБД. Очевидно, что подобный поиск обязан соответствовать архитектуре СУБД, что налагает определенные ограничения на алгоритмы и методы доступа к данным. Несмотря на то, что подобные ограничения могут влиять на производительность поиска, полный доступ ко всем метаданным базы данных дает возможность для реализации очень сложных поисков, просто невозможных для внешних поисковиков. Например, понятие документа в БД отличается от обычного восприятия как страница на сайте, которую можно сохранить, открыть, модифицировать, удалить. То, что пользователь или поисковый робот видит на сайте является результатом лишь одной комбинацией метаданных, полное множество которых практически недоступно для поисковых роботов. Существует даже понятие "скрытого веба" (Hidden Web), недоступного для поисковых машин и который во много раз превышает размеры видимого веба. Одним из компонентов этой "скрытой" части веба является содержимое баз данных.
Что такое документ в базе данных ? Это может быть произвольный текстовый атрибут или их комбинация. Атрибуты могут храниться в разных таблицах и тогда документ может являться результатом сложной "связки" нескольких таблиц. Более того, текстовые атрибуты могут быть на самом деле результатом работы программ-конвертеров, которые вытаскивают текстовую информацию из бинарных полей (.doc, .pdf, .ps, ...). В большинстве случаев, документ является результатом работы SQL команд и виртуальным по своей природе. Очевидно, что единственное требование для документа является наличие уникального ключа, по которому его можно идентифицировать. Для внешнего поисковика такой документ является просто набором слов ("bag of words"), без никакого понимания структуры, т.е. из каких атрибутов этот документ был составлен, какова важность того или иного документа. Вот пример документа, составленного из нескольких текстовых атрибутов.

SELECT m.title m.author m.abstract d. body as document FROM messages m, docs d WHERE m.id = d.id and m.id = 12;
Интуитивно ясно, что не все части документа одинаково важны. Так, например, заголовок или абстракт обладают большей информативной плотностью, чем остальная часть документа.
Запрос имеет чисто иллюстративный характер, так как на самом деле, здесь надо было бы использовать функцию coalesce(), чтобы защититься от ситуации, когда один из атрибутов имеет значение NULL.
Как и обычный документ он состоит из слов, по которым его можно найти. Для этого документ надо уметь разбивать на эти слова, что также может быть не простой задачей, так как для разных задач понятие слова может быть разным. Мы используем термин "токен" для обозначения "слов", которые получаются после работы парсера, и термин "лексема" для обозначения того, что будет индексировано. Итак, парсер разбивает документ на токены, часть из которых индексируется. Каким образом токен становится лексемой - это определяется конкретной задачей, например, для поиска по цветам требуется индексировать не только обычные слова, обозначающие цвета красок, но и их различные эквиваленты, использующиеся в веб-технологиях, например, их шестнадцатеричные обозначения.

Введение в полнотекстовый поиск в PostgreSQL

Олег Бартунов, Федор Сигаев

Авторское неформальное описание полнотекстового поиска встроенного в PostgreSQL версии 8.3+, примеры и рекомендации по настройке. Также приведен справочник SQL команд для управления полнотекстовым поиском. Полное описание полнотекстового поиска доступно на сайте разработчиков [FTSBOOK].

Интерфейсные функции

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

GISTENTRY * compress( GISTENTRY * in )
GISTENTRY * decompress( GISTENTRY * in )

Эти функции отвечают за компрессию/декомпрессию ключей. Если функция меняет значение ключа (key), то:

она должна возвращать заново palloc'оченное значение как структуры, так и ключа( если ключ передавался по ссылке, pass-by-reference). скопировать в новую структуру значения rel, page, offset, leafkey. правильно установить bytes. не менять старую структуру (in), и не делать pfree ни in, ни in->key

При вызове compress in->leafkey=TRUE, если значение в key взято из таблицы, а не из индекса. В этом случае, если эта функция нетривиальна, даже если не меняется ключ, надо обязательно определить in->bytes и установить in->leafkey=FALSE.

Всем остальным интерфейсным функциям ключи передаются только после обработки ключа функции decompress.

bool equal( Datum a, Datum b)

Возвращает TRUE только в случае a==b.

float * penalty( GISTENTRY *origentry, GISTENTRY *newentry, float *result)

Вычисляет меру увеличения origentry->key при его объединении с newentry->key. Вычисленное значение должна поместить в *result и вернуть указатель на него.

Если эта функция не помечена как isstrict, то key может быть NULL. В противном случае, функция не вызывается и считается, что мера увеличения равно 0, если хотя бы один из параметров имеет значение NULL.

Datum union(GistEntryVector *entryvec, int *size)

Выполняет объединение (union) ключей. Возвращает объединенный ключ (не GISTENTRY!). В *size помещает размер результирующего ключа в байтах. Структура GistEntryVector:

typedef struct { int32 n; /* количество элементов в поле vector*/ GISTENTRY vector[1]; } GistEntryVector;

Массив никогда не содержит NULL элементов.

bool consistent( GISTENTRY *entry, Datum query, StrategyNumber strategy )

Проверяет ключ (entry->key) на соответствие запросу (query) с помощью операции с номером strategy и возвращает TRUE в случае соответствия, или FALSE в противном.

Если ключ находится на внутренней странице дерева, функция должна возвращать TRUE, если entry->key МОЖЕТ соответствовать query и FALSE, если entry->key ТОЧНО не соответствует query.

Если ключ находится на концевой странице (leaf page), то поведение определяется параметром RECHECK для конкретной операции (см. CREATE OPERATOR CLASS). Если задан параметр RECHECK, то это означает, что индекс является неточным ("lossy"), т.е. результат поиска требуется проверить на соответствие запросу (поведение consistent аналогично поведению на внутренних страницах в этом случае), в противном случае требуется вернуть ТОЧНЫЙ ответ.

Макрос GIST_LEAF(entry) возвращает TRUE, если ключ находится на leaf странице.

Узнать, какие операции какой strategy соответствуют можно с помощью следующего SQL( на примере box_ops, подробнее смотри раздел ):

select pg_amop.amopstrategy, pg_operator.oprname, pg_amop.amopreqcheck from pg_type, pg_operator, pg_opclass, pg_am, pg_amop where pg_type.typname = 'box' and pg_am.amname = 'gist' and pg_opclass.opcname = 'box_ops' and pg_am.oid=pg_opclass.opcamid and pg_opclass.oid = pg_amop.amopclaid and pg_opclass.opcintype = pg_type.oid and pg_amop.amopopr = pg_operator.oid;

Соответственно, при внесении нового opclass и/или операций надо позаботиться об обновлении системных таблиц.

GIST_SPLITVEC * split(GistEntryVector *entryvec, GIST_SPLITVEC *v)

Разделяет массив ключей entryvec на два. Массив entryvec не может содержать NULL значения.

Структура GIST_SPLITVEC: typedef struct GIST_SPLITVEC { OffsetNumber *spl_left; /* array of entries that go left */ int spl_nleft; /* size of this array */ Datum spl_ldatum; /* Union of keys in spl_left */ OffsetNumber *spl_right; /* array of entries that go right */ int spl_nright; /* size of the array */ Datum spl_rdatum; /* Union of keys in spl_right */ ... } GIST_SPLITVEC;

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

v->spl_left и v->spl_right должны аллоцироваться(palloc) самостоятельно, при возврате они должны содержать номера элементов массива entryvec. При этом, один номер НЕ может содержаться в spl_left и spl_right одновременно.

Внимание:

Значения в массиве entryvec начинаются с 1, а не с 0

Функция обязана определить spl_ldatum и spl_rdatum - объединяющие ключи, соответственно, для левого и правого массива.

Написание расширений для PostgreSQL с использованием GiST

Олег Бартунов, Федор Сигаев

Приводится краткое описание обобщенного поискового дерева (GiST), его реализация в ORDBMS PostgreSQL, пример написания пользовательских расширений с использованием GiST.

Общие замечания по программированию на С под PostgreSQL

Для понимания примеров мы приводим особенности написания пользовательских функций на языке C для PostgreSQL, полное описание можно найти в разделе C-Language Functions

документации.

Функции должны использовать интерфейс версии 1, версия 0 deprecated, хотя пока и поддерживается.

На уровне С PostgreSQL оперирует с базовыми типами данных

или SQL-типами в представлении С-типа Datum. Datum имеет размер, равный размеру указателя на данной архитектуре (PostgreSQL не поддерживает архитектуры с указателем, меньшим 32 бит). SQL-типы в PostgreSQL делятся на передаваемые по значению и по указателю. Передаваемые по значению типы не должны превышать размер 32 бита. Передаваемые по указателю типы подразделяются на типы с фиксированной длиной и переменной. Для типов с переменной длиной первым полем всегда должна быть длина значения int4 (в байтах, с учетом размера поля длины). Для преобразования Datum в тип и обратно существует набор макросов, см.,например, файлы postgres.h, fmgr.h:

int32 i = DatumGetInt32(datum); Datum datum = BoolGetDatum( true );

text *sometext = DatumGetTextP( datum );

Для абстрактного типа, передаваемого по указателю, можно использовать преобразование в указатель:

SOMETYPE *ptr = (SOMETYPE*)DatumGetPointer(datum);

Datum datum = PointerGetDatum( ptr );

Длинные значения типов с переменной длиной могут "тоститься", то есть нарезаться маленькими кусочками (TOAST - The Oversized Attribute Storage Technique, подробнее). Макросы для встроенных типов учитывают эту возможность, для user-defined это должно указываться непосредственно:
SOMETYPE *ptr = (SOMETYPE*)PG_DETOAST_DATUM( DatumGetPointer(datum) );

Для работы с типами переменной длины есть дополнительные макросы:

VARSIZE( ptr ) - размер в байтах VARDATA( ptr ) - возвращает указатель на данные после поля длины.

Т.е., если для типа определена структура: typedef struct { int32 length; char data[1]; } FOO; FOO *foo = f();

то f->length == VARSIZE(f) и f->data == (char*)VARDATA(f) всегда. Заметим, что длина поля не может превышать 1Gb. Два бита в поле длина используются PostgreSQL в своих целях. Функция должна возвращать тип Datum и объявляться как:

PG_FUNCTION_INFO_V1(function);

Datum function(PG_FUNCTION_ARGS);

Передача параметров вызываемой функции и возвращаемое значение прозводится посредством макросов. Порядковый номер аргумента задается параметром макроса. Datum function(PG_FUNCTION_ARGS) { /* целое число, передается по значению */ int32 i = PG_GETARG_INT32(0); /* указатель на прямоугольник */ BOX *b = PG_GETARG_BOX_P(1); /* указатель на текст */ text *t = PG_GETARG_TEXT_P(2); /* пользовательский тип с переменной длиной */ FOO *f = (FOO*)DatumGetPointer(PG_DETOAST_DATUM(PG_GETARG_DATUM(3));

....

/* * после того, как работа произведена, не плохо бы очистить память * "потостенных" значений, Аргументы: * первый - имя переменной-параметра функции, * второй - порядковый номер */ PG_FREE_IF_COPY(t,2); PG_FREE_IF_COPY(f,3);

PG_RETURN_INT32( i ); }

Функциям запрещено менять значения своих аргументов. Это правило не относится к некоторым специальным функциям, например к функциям penalty, equal, union и picksplit интерфейса к GiST.

Все управление динамической памятью должно осуществляться PostgreSQL-аналогами palloc/repalloc/pfree. Их использование, как правило, предохраняет от утечек памяти, быстрее, и облегчает отладку (если PostgreSQL скомпилен с флагами --enable-debug и --enable-cassert)

Память для типов, передаваемых по указателю и соответствующих какому-либо SQL-типу, должна быть зарезервирована вызовом palloc.

Ограничения и TODO

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

Хранение NULL - существенно только для кластеризации данных.
Существующий интерфейс GiST запрещает использование NULL, так как пока непонятно, каким образом эффективно помечать эти значения.

Поддержка уникальных индексов

Поддержка упорядоченных данных (ordered domains) - использование знания о порядке для оптимизации хранения данных и улучшения производительности.

Кроме того, оригинальный интерфейс GiST [HNP95] требует модификаций, см. работы Корнакер [Kor99] и Аоки [Aok98], необходимые как для поддержки более широкого класса данных и запросов, так и для повышения производительности поискового дерева. Например, оригинальный алгоритм поиска в GiST использует стратегию поиска в глубину (depth-first), что неявно предполагает использование запросов вида "содержит", "пересекается", но не поддерживает запросы вида "похожий", как подметил Аоки [Aok98], который и предложил расширение GiST для поддержки пользовательской стратегии поиска, например, поиска в ширину (breadth-first) для SS-tree (similarity tree), которое используется в задачах кластеризации данных.

Следует отметить SP-GiST - расширение GiST интерфейса для поддержки специального вида деревьев, используемых в GIS, CAD/CAM, цифровых деревьев (tries). Mohamed Eltabakh

работает над реализацией SP-GiST в виде модуля для PostgreSQL.

Несмотря на то, что изменение интерфейса GiST является "трудной" операцией, необходимо изучить все варианты и выделить оптимальное подмножество изменений, которое позволит с одной стороны улучшить "расширяемость" и производительность GiST, а с другой - сохранить простоту разработки расширений ([Kor99], например, предлагает использовать 11 интерфейсных функций, а [Aok98] - 13, вместо 7).

Для упрощения написания новых расширений мы планируем добавить некоторые методы в core GiST, которые можно использовать по умолчанию:

picksplit, реализующий Гуттмановский алгоритм. Практика показала, что во многих случаях этот алгоритм показывает удовлетворительные результаты.

R-tree интерфейс для GiST может быть полезен для быстрого создания opclass'ов подобных 2-D R-tree: индексы для n-размерных объектов, некоторые виды индексирования массивов (см. обсуждение).

Подключение интерфейсных функций

Процедура регистрации расширения в БД состоит из нескольких этапов (приводятся только SQL команды):

Создание нового типа данных (если требуется)

Написание функций преобразования типа в C-строку и обратно: _in, _out. Например: CREATE FUNCTION ltree_in(cstring) RETURNS ltree AS '$libdir/ltree' LANGUAGE 'C' WITH (isstrict);

Создание типа с помощью CREATE TYPE. CREATE TYPE ltree ( INTERNALLENGTH = -1, INPUT = ltree_in, OUTPUT = ltree_out, STORAGE = extended );

Создание новых операторов (если требуется)

Создание функций (CREATE FUNCTION) для работы операторов, например, функции сравнения типов для операторов сравнения. Например, CREATE FUNCTION ltree_eq(ltree,ltree) RETURNS bool AS '$libdir/ltree' LANGUAGE 'C' WITH (isstrict,iscachable);

Создание операторов с помощью CREATE OPERATOR. При этом задается соответствие знаков операторов, используемые в SQL, с вызываемыми функциями. CREATE OPERATOR = ( LEFTARG = ltree, RIGHTARG = ltree, PROCEDURE = ltree_eq, COMMUTATOR = '=', NEGATOR = '<>', RESTRICT = eqsel, JOIN = eqjoinsel, SORT1 = '<', SORT2 = '<' );

Регистрация интерфейсных функций GiST

Создать новый тип для хранения в GiST, если необходимо (это может потребоваться если тип ключа хранимый в дереве отличается от исходного типа данных, например, в модуле tsearch2 базовым типом является tsvector, а для хранения используется тип gtsvector, представляющий сигнатуру документа. В этом случае, для отладки с помощью модуля необходимо написать функцию _out.

Создать . Например, для метода consistent: CREATE FUNCTION ltree_consistent(internal,internal,int2) RETURNS bool as '$libdir/ltree' language 'C';

Создать новый оператор класс (opclass), см. CREATE OPERATOR CLASS, например, для типа данных box: CREATE OPERATOR CLASS gist_box_ops DEFAULT FOR TYPE box USING gist AS OPERATOR 1 << , OPERATOR 2 &< , OPERATOR 3 && , OPERATOR 4 &> , OPERATOR 5 >> , OPERATOR 6 ~= , OPERATOR 7 ~ , OPERATOR 8 @ , FUNCTION 1 gbox_consistent (internal, box, int4), FUNCTION 2 gbox_union (internal, internal), FUNCTION 3 gbox_compress (internal), FUNCTION 4 rtree_decompress (internal), FUNCTION 5 gbox_penalty (internal, internal, internal), FUNCTION 6 gbox_picksplit (internal, internal), FUNCTION 7 gbox_same (box, box, internal);

Здесь, номер FUNCTION используется в core GiST для идентификации интерфейсных функций. Номер OPERATOR должен совпадать с номером strategy в методе consistent, который используется для определения типа операции. Другими словами, стратегия - это уникальный номер оператора для данного opclass-а.

Полный пример можно посмотреть в ltree.sql из модуля ltree, который находится в поддиректории contrib в дистрибутиве PostgreSQL. Также, смотри раздел документации Interfacing Extensions To Indexes.

R-Tree GiST для полигонов

Хранимыми ключами для полигонов являются также прямоугольники, описывающие полигоны. Таким образом, все отличия от варианта R-Tree для прямоугольников заключаются всего в двух функциях. Такой индекс называют "with lossy compression" (неточный индекс) и это означает, что все данные, которые он выдает при поиске, необходимо проверить, т.е., сравнить с исходным значением, хранящимся в таблице.

compress

Datum gist_poly_compress(PG_FUNCTION_ARGS) { GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0); GISTENTRY *retval;

if (entry->leafkey) { /* значение entry->key содержит полигон, т.е. это новое значение для вставки в индекс */ retval = palloc(sizeof(GISTENTRY)); if (DatumGetPointer(entry->key) != NULL) { POLYGON *in = DatumGetPolygonP(entry->key); BOX *r;

r = (BOX *) palloc(sizeof(BOX)); memcpy((void *) r, (void *) &(in->boundbox), sizeof(BOX)); gistentryinit(*retval, PointerGetDatum(r), entry->rel, entry->page, entry->offset, sizeof(BOX), FALSE);

} else { gistentryinit(*retval, (Datum) 0, entry->rel, entry->page, entry->offset, 0, FALSE); } } else retval = entry; PG_RETURN_POINTER(retval); }

consistent

Обратите внимание, что всегда вызывается rtree_internal_consistent, даже для конечных страниц. Т.е. функция возвращает TRUE когда настоящее, точное сравнение МОЖЕТ быть истинно. Datum gist_poly_consistent(PG_FUNCTION_ARGS) { GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0); POLYGON *query = PG_GETARG_POLYGON_P(1); StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2); bool result;

if (DatumGetBoxP(entry->key) == NULL query == NULL) PG_RETURN_BOOL(FALSE);

result = rtree_internal_consistent(DatumGetBoxP(entry->key), &(query->boundbox), strategy);

PG_FREE_IF_COPY(query, 1);

PG_RETURN_BOOL(result); }

R-Tree GiST для прямоугольников

Для описания сложных объектов часто используют более простые фигуры, аппроксимирующие сложную форму, которые характерны тем, что полностью содержат в себе эти объекты. Такие фигуры называют bounding volume и их гораздо проще использовать для проверки на различные условия, например, на пересечение двух объектов. В качестве bounding volume часто используют сферу, цилиндр или куб. Мы будем рассматривать куб, который называют bounding box,или BB.

R-Tree - это структура данных, которая используется для индексирования многомерных данных. Она была предложена Гуттманом [Gut84] как расширение B-tree на многомерное пространство, которое разбивается на иерархически вложенные и возможно перекрывающиеся BB (прямоугольники для двумерного случая, в случае 3-х измерений - кубики), Каждый узел R-Tree может содержать переменное количество записей, но не больше заранее определенного максимума. Каждая запись во внутренних узлах содержит ссылку на дочерний узел и BB, который содержит все записи этого дочернего узла. Каждая запись концевого узла (leaf node) содержит ссылку на данные и BB этих данных. При вставке новых данных отслеживается, чтобы близкие данные лежали "близко", в одном концевом узле, в частности, это достигается с помощью правила наименьшего увеличения BB этого узла после вставки. При поиске сравниваются BB-ы запроса и текущего узла и если нет пересечений, то последующие проверки с узлами этого поддерева уже не нужны, чем сильно уменьшается количество просмотренных узлов и достигается выигрыш в производительности.

R-tree для для городов и деревень Греции. Данные взяты с rtreeportal.org

На рисунке изображен фрагмент дерева (полное дерево), построенного с помощью модуля rtree_gist и - специального модуля, предназначенного для разработчиков расширений с использованием GiST. Исходными данными являются MBR (minimum bounding rectangles) городов и деревень Греции. Изображены данные на концевых узлах (маленькие прямоугольники) и на 1-м уровне (большие прямоугольники). Подробнее можно прочитать здесь.

compress, decompress
Функции тривиальны, просто возвращают то, что получили. Datum gist_box_compress(PG_FUNCTION_ARGS) { PG_RETURN_POINTER(PG_GETARG_POINTER(0)); }
Datum gist_box_decompress(PG_FUNCTION_ARGS) { PG_RETURN_POINTER(PG_GETARG_POINTER(0)); }
equal
Сравнивает два прямоугольника и возвращает true если они равны или оба равны NULL Datum gist_box_same(PG_FUNCTION_ARGS) { BOX *b1 = PG_GETARG_BOX_P(0); BOX *b2 = PG_GETARG_BOX_P(1); bool *result = (bool *) PG_GETARG_POINTER(2);
if (b1 && b2) *result = DatumGetBool(DirectFunctionCall2(box_same, PointerGetDatum(b1), PointerGetDatum(b2))); else *result = (b1 == NULL && b2 == NULL) ? TRUE : FALSE; PG_RETURN_POINTER(result); }
Кстати, тут присутствует вызов встроенной в PostgreSQL функции box_same. Следует также обратить внимание на работу с переменной result: эта интерфейсная функция является исключением из правил и функция должна изменить значения своего параметра. Но это не касается двух первых аргументов.
penalty
Функция возвращает изменение (увеличение) площади прямоугольника после объединения обоих (получение bounding box) как меру изменения. static double size_box(Datum dbox) { /* Вычисление площади прямоугольника */ BOX *box = DatumGetBoxP(dbox);
if (box == NULL box->high.x <= box->low.x box->high.y <= box->low.y) return 0.0; return (box->high.x - box->low.x) * (box->high.y - box->low.y); }
Datum gist_box_penalty(PG_FUNCTION_ARGS) { /* исходный прямоугольник */ GISTENTRY *origentry = (GISTENTRY *) PG_GETARG_POINTER(0); /* добавляемый прямоугольник */ GISTENTRY *newentry = (GISTENTRY *) PG_GETARG_POINTER(1); float *result = (float *) PG_GETARG_POINTER(2); Datum ud;
/* получаем объединяющий прямоугольник */ ud = DirectFunctionCall2(rt_box_union, origentry->key, newentry->key); /* вычитаем площадь исходниго из полученного прямоугольника */ *result = (float) (size_box(ud) - size_box(origentry->key));
PG_RETURN_POINTER(result); }
union
Функция возвращает объединяющий прямоугольник для всех входящих прямоугольников Datum gist_box_union(PG_FUNCTION_ARGS) { GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0); int *sizep = (int *) PG_GETARG_POINTER(1); int numranges, i; BOX *cur, *pageunion;

numranges = entryvec->n; /* возвращаемое значение должно быть palloc'ировано! */ pageunion = (BOX *) palloc(sizeof(BOX)); /* инициация объединяющего прямоугольника первым прямоугольником */ cur = DatumGetBoxP(entryvec->vector[0].key); memcpy((void *) pageunion, (void *) cur, sizeof(BOX));
for (i = 1; i < numranges; i++) { cur = DatumGetBoxP(entryvec->vector[i].key); if (pageunion->high.x < cur->high.x) pageunion->high.x = cur->high.x; if (pageunion->low.x > cur->low.x) pageunion->low.x = cur->low.x; if (pageunion->high.y < cur->high.y) pageunion->high.y = cur->high.y; if (pageunion->low.y > cur->low.y) pageunion->low.y = cur->low.y; }
/* размер возвращаемого значения в байтах */ *sizep = sizeof(BOX);
PG_RETURN_POINTER(pageunion); }
consistent
Datum gist_box_consistent(PG_FUNCTION_ARGS) { GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0); BOX *query = PG_GETARG_BOX_P(1); StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
if (DatumGetBoxP(entry->key) == NULL query == NULL) PG_RETURN_BOOL(FALSE);
/* если значение находится на концевой странице, то выполняется точное сравнение, на внутренней мы должны вернуть true если значения на последующих страницах (детях) МОГУТ удовлетворять условию */
if (GIST_LEAF(entry)) PG_RETURN_BOOL(gist_box_leaf_consistent(DatumGetBoxP(entry->key), query, strategy)); else PG_RETURN_BOOL(rtree_internal_consistent(DatumGetBoxP(entry->key), query, strategy)); }
Реальные функции gist_box_leaf_consistent и rtree_internal_consistent довольно объемны, ограничимся их вариантами только для поиска на совпадение. static bool gist_box_leaf_consistent(BOX *key, BOX *query, StrategyNumber strategy) { bool retval = FALSE; switch (strategy) { case RTSameStrategyNumber: retval = DatumGetBool(DirectFunctionCall2(box_same, PointerGetDatum(key), PointerGetDatum(query))); break; default: elog(NOTICE,"Unsupported StrategyNumber %d", strategy); } return retval; }

static bool rtree_internal_consistent(BOX *key, BOX *query, StrategyNumber strategy) { bool retval=FALSE; switch (strategy) { case RTSameStrategyNumber: retval = DatumGetBool(DirectFunctionCall2(box_contain, PointerGetDatum(key), PointerGetDatum(query))); break; default: elog(NOTICE,"Unsupported StrategyNumber %d", strategy); } return retval; } Обратите внимание, что в функции gist_box_leaf_consistent поисковый прямоугольник тестируется на полное совпадение с испытуемым значением, а в rtree_internal_consistent поисковый прямоугольник должен полностью содержаться в испытуемом значении. Очевидно, что если поисковый прямоугольник не содержится, то совпадающих с ним прямоугольников в страница-наследниках просто не может быть.
picksplit
Обычно самая сложная функция в интерфейсе GiST. Полную версию можно найти в исходниках PostgreSQL, файл ./src/backend/access/gist/gistproc.c Можно использовать обычный Гуттмановский (квадратичный) алгоритм ([Gut84]). Для полноты мы будем использовать простой (неэффективный) алгоритм, который помещает четные элементы в "левый" массив, в нечетный - в "правый".
Datum gist_box_picksplit(PG_FUNCTION_ARGS) { GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0); GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1); OffsetNumber i, maxoff = entryvec->n - 1; int nbytes;
nbytes = (maxoff + 2) * sizeof(OffsetNumber); v->spl_left = (OffsetNumber *) palloc(nbytes); v->spl_right = (OffsetNumber *) palloc(nbytes); v->spl_ldatum = PointerGetDatum( palloc( sizeof(BOX) ) ); v->spl_rdatum = PointerGetDatum( palloc( sizeof(BOX) ) ); v->spl_nleft = 0; v->spl_nright = 0;
for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i)) { BOX *pageunion; /* указатель на объединяющий прямоугольник для страницы */
if ( i%2 == 0 ) { v->spl_left[ v->spl_nleft ] = i; v->spl_nleft++; pageunion = DatumGetBoxP( v->spl_ldatum ); } else { v->spl_right[ v->spl_nright ] = i; v->spl_nright++; pageunion = DatumGetBoxP( v->spl_rdatum ); }
if ( i<=OffsetNumberNext( FirstOffsetNumber ) ) { /* первоначальная инициализация объединяющего прямоугольника */ memcpy( pageunion, DatumGetBoxP(entryvec->vector[i].key), sizeof(BOX) ); } else { BOX *curbox = DatumGetBoxP(entryvec->vector[i].key); if (pageunion->high.x < curbox->high.x) pageunion->high.x = curbox->high.x; if (pageunion->low.x > curbox->low.x) pageunion->low.x = curbox->low.x; if (pageunion->high.y < curbox->high.y) pageunion->high.y = curbox->high.y; if (pageunion->low.y > curbox->low.y) pageunion->low.y = curbox->low.y; } }
PG_RETURN_POINTER(v); }

Примеры использования GiST

Для того, чтобы использовать модуль в вашей БД, необходимо установить модуль, загрузить расширение в вашу БД. Установка модуля обычно заключается в последовательности команд (на примере tsearch2):

cd contrib/tsearch2 make && make install && make installcheck

Если все прошло нормально (все тесты прошли), то можно загрузить расширение в вашу БД, например: psql foodb < /usr/local/pgsql/share/contrib/tsearch2.sql

После этого вы можете использовать новые типы данных, предоставляемые модулем, операции, указанные в CREATE OPERATOR CLASS и функции. Например, для модуля tsearch2: create table fts ( id integer, title text, body text, ftsindex tsvector); create index fts_idx on fts using gist(ftsindex);

Здесь колонка ftsindex в таблице fts имеет тип tsvector, который и был предоставлен модулем tsearch2. Обратите внимание на указание метода (gist), который используется при построении индекса. Иногда, можно указать параметр opclass для метода, если требуется использовать оператор отличный от умолчания для данного типа колонки. Например, для модуля contrib/intarray можно указать opclass gist__intbig_ops для эффективной работы с большими массивами, в то время как по умолчанию используется gist__int_ops, достаточный для работы с небольшими массивами. Разница между gist__intbig_ops и gist__int_ops заключается в том, что первый opclass использует специальное представление массива битовой сигнатурой ( superimposed signature ) длиной 4096 бит и поэтому индекс является "lossy", в то время как во втором случае индекс является точным и не требует проверки найденных записей на соответствие запросу. -- default opclass, could be omitted CREATE INDEX message_rdtree_idx on message using gist ( sections gist__int_ops); -- opclass for large arrays CREATE INDEX message_rdtree_idx on message using gist ( sections gist__intbig_ops);

Более подробно см. документацию CREATE INDEX

Используя GiST, авторами были разработаны ряд популярных расширений, которые входят в дистрибутив PostgreSQL. Все модули реализуют типы данных, оптимизированных под конкретную задачу, хранилище, индексный доступ к нему и специализированные запросы. Ниже приводится очень краткий обзор использования этих расширений. Формальное описание содержится в документации к модулю, а примеры использования можно найти в архивах списков рассылок PostgreSQL и c помощью поисковой машины www.pgsql.ru.

tsearch2 - реализация полнотекстового поиска
Этот модуль предназначен для организации полнотекстового поиска в БД. Его отличительной особенностью является online-индекс и полная интеграция с БД, что дает возможность проводить полнотекстовый поиск с ограничениями по атрибутам. Например, искать по документам, в зависимости от уровня доступа клиента и дате публикации. Tsearch2 поддерживает использование словарей, предоставляет API для их создания. Поддержка словарей популярных форматов ispell (для приведения слов к их нормальной форме) и стемминга на основе snowball позволяет использовать tsearch2 со многими языками. Гибкость настройки tsearch2, конфигурация которого хранится в базе данных и доступна с помощью стандартных команд SQL, позволяет разрабатывать различные поиски ориентированные на разные задачи. Модуль предоставляет два вида ранжирующих функций, использующие координатную информацию, и которые можно использовать для сортировки результатов поиска по их релевантности запросу.
С модулем tsearch2 полнотекстовый поиск становится простой и рутинной задачей. Пример поиска документов, которые содержат слова 'собака', 'на', 'сене':
SELECT mid, title from messages where ftsindex @@ to_tsquery('собака & на & сене');
Аналогично, но ищутся 10 самых релевантных запросу документов: SELECT mid, title, rank(ftsindex,to_tsquery('собака & на & сене')) as rank from messages where ftsindex @@ to_tsquery('собака & на & сене') ORDER BY rank DESC LIMIT 10;
Модуль поддерживает структурность документа, т.е. словам из разных частей документа (всего можно использовать 4 части) можно задавать разные веса. Так, например, вес слова, входящего в название документа, можно увеличить, по сравнению с другими частями. Также, можно ограничивать поиск по различным частям документов, используя один и тот же индекс. В примере ниже, поле ftsindex включает поле title и тело документа.
UPDATE messages SET ftsindex=setweight( to_tsvector(title), 'A' ) to_tsvector(body);

Можно поискать только по названиям документов: SELECT mid, title FROM messages WHERE ftsindex @@ to_tsquery('собака:a & на & сене');
Для визуализации результатов поиска модуль предоставляет функцию headline, которая выдает релевантные части документа с подсветкой слов из запроса.
SELECT mid, headline(body, to_tsquery('собака & на & сене')), rank(fts_index,to_tsquery('собака & на & сене')) AS rank FROM messages WHERE ftsindex @@ to_tsquery('собака & на & сене') ORDER BY rank DESC LIMIT 10;
Отметим, что в этом запросе, функция headline вызывается для каждого найденного документа, что может существенно влиять на время исполнения запроса. Это связано с тем как в PostgreSQL реализован LIMIT. Оптимизированный запрос с использованием подзапроса (subselect) выглядит следующим образом: SELECT mid, headline(body, to_tsquery('собака & на & сене')) FROM (SELECT mid, body, rank(fts_index,to_tsquery('собака & на & сене')) AS rank FROM messages WHERE ftsindex @@ to_tsquery('собака & на & сене') ORDER BY rank DESC LIMIT 10) AS foo;
Здесь функция headline вызывается только нужное (максимум 10) количество раз.
ltree - поддержка данных с древовидной структурой
Стандартный способ работы с иерархическими данными, например, с каталогами, заключается в использовании таблиц связей (parent_id,child_id), что приводит ,так или иначе, к необходимости использования рекурсивных запросов. Идея модуля ltree состоит в том, чтобы хранить иерархию связей в специальном типе данных ltree и предоставлять индексную
поддержку для основных операций. Например, для данных изображенных на рисунке
TOP / | \ Science Hobbies Collections / | \ Astronomy Amateurs_Astronomy Pictures / \ | Astrophysics Cosmology Astronomy / | \ Galaxies Stars Astronauts
запрос на поиска всех потомков, например, узла 'Top.Science' выглядит: SELECT path FROM test WHERE path <@ 'Top.Science'; path ------------------------------------ Top.Science Top.Science.Astronomy Top.Science.Astronomy.Astrophysics Top.Science.Astronomy.Cosmology

Кроме работы со связями, ltree предоставляет возможность поиска с использованием регулярных выражений и модификаторов. Например, запрос Top.*{0,2}.sport*@.!football|tennis.Russ*|Spain a) b) c) d) e)
означает, что узел должен:
a) - начинаться с узла с меткой 'Top' b) - дальше могут идти вплоть до 2-х узлов с произвольной меткой c) - после чего идет узел с именем начинающимся на 'sport' (маленькие и большие буквы не различаются) d) - далее идет узел, имя которого не должно содержать 'footbal' или 'tennis' e) - и кончаться на узел, начинающийся 'Russ' или 'Spain' (маленькие и большие буквы отличаются)
Пример: SELECT path FROM test WHERE path ~ '*.!pictures@.*.Astronomy.*'; path ------------------------------------ Top.Science.Astronomy Top.Science.Astronomy.Astrophysics Top.Science.Astronomy.Cosmology
Также, можно использовать поиск по названиям узлов, например, найти все узлы, которые содержать слово 'Europe', слово, начинающееся с 'Russia' (case insensitive), и не содержащее слово 'Transportation': 'Europe & Russia*@ & !Transportation'
Пример: SELECT path FROM test WHERE path @ 'Astro*% & !pictures@'; path ------------------------------------ Top.Science.Astronomy Top.Science.Astronomy.Astrophysics Top.Science.Astronomy.Cosmology Top.Hobbies.Amateurs_Astronomy
Удобство использования этого модуля и большое количество полезных функций делает ltree очень полезным для решения типичных портальных задач.
intarray - индексная поддержка целочисленных массивов
Этот модуль часто используется в тех случаях, когда требуется денормализовать БД для повышения производительности. Например, типичная задача поиска документов из нескольких разделов. Классическая нормализованная схема предусматривает использование трех таблиц - messages, sections и message_section_map. Документ может принадлежать нескольким секциям, так что таблица message_section_map содержит связи многие-ко-многим. При этом, поиск всех документов из секций 1,2 будет содержать связку (join) двух таблиц messages и message_section_map, что влияет на производительность и в некоторых случаях просто неприемлемо. Денормализация приводит к тому, что в таблицу messages добавляется поле sections которое является массивом целых чисел - идентификаторов секций, к которым принадлежит данный документ. Однако, несмотря на то, что теперь не требуется вторая таблица, поиск будет все равно медленным из-за того, что операция поиск в массиве не использует индекс. Наш модуль intarray как раз и решает эту проблему - он обеспечивает индексную поддержку для операций над целочисленными массивами.
CREATE TABLE message (mid int not null,sections int[]); -- select some messages with section in 1 OR 2 - OVERLAP operator SELECT message.mid FROM messages WHERE messages.sections && '{1,2}';

-- select messages contains in sections 1 AND 2 - CONTAINS operator SELECT message.mid FROM messages WHERE messages.sections @ '{1,2}'; -- the same, CONTAINED operator SELECT message.mid FROM messages WHERE '{1,2}' ~ messages.sections;
Другой интересный пример использования массивов - это реализация генеалогического подхода для работы с древовидной структурой, т.е. для каждого узла хранить путь от него до корня дерева (пример сообщил Achilleus Mantzios). CREATE TABLE tree( id integer PRIMARY KEY, name text not null, parents integer[] ) CREATE INDEX tree_parents on tree using gist (parents gist__int_ops); INSERT INTO tree VALUES (1,'root',null); INSERT INTO tree VALUES (2,'kid1',intset(1)); INSERT INTO tree VALUES (3,'kid2',intset(1)); INSERT INTO tree VALUES (4,'kid1.1',intset(2)+'{1}'::int4[]); INSERT INTO tree VALUES (5,'kid1.2',intset(2)+'{1}'::int4[]);
Здесь функция intset преобразует integer в элемент массива, а оператор '+' соединяет два массива. Теперь мы имеем дерево следующего вида: (1,root,null) / \ / \ / \ (2,kid1,'{1}') (3,kid2,'{1}') / \ / \ / \ (4,kid1.1,'{2,1}') (5,kid1.2,'{2,1}')
Теперь мы можем найти прямых потомков узла id=1 (root) SELECT * FROM tree WHERE intset(1) ~ parents and icount(parents)=1;
Функция icount дает количество элементов в массиве или "глубину" узла в нашем примере. Чтобы найти всех потомков узла id: SELECT * FROM tree WHERE intset() ~ parents;
pg_trgm - поиск похожих строк на основе триграм
Этот модель не только позволяет быстро находить похожие строки, но еще и не зависит от языка, так как использует только статистику используемых триграмм. Триграмма - это последовательность из трех соседних букв. Например, слово 'собака' содержит триграммы 'соб', 'оба', 'бак', 'ака'. Используя pg_trgm, можно найти все слова, упорядоченные по похожести слову 'собака': CREATE INDEX trgm_idx ON foo USING gist (word gist_trgm_ops);
SELECT word, similarity(word, 'собака') AS sml FROM foo WHERE word % 'собака' ORDER BY sml DESC, word;

При этом, будет использоваться индекс trgm_idx, построенный по полю word, что обеспечивает хорошую производительность даже для большого количества слов.
Этот модуль можно использовать вместе с tsearch2 для полнотекстового поиска с коррекцией ошибок ввода.
rtree_gist - реализация R-tree с использованием GiST
Этот модуль позволяет эффективно работать с данными с пространственными атрибутами. Начиная с 8.1 этот модуль интегрирован в ядро PostgreSQL.
btree_gist - реализация B-tree с использованием GiST
Модуль поддерживает практические все основные типы данных, используемые в PostgreSQL и самостоятельной ценности не имеет, так как встроенный btree гораздо лучше. btree_gist применяется для создания композитных индексов, так как PostgreSQL не поддерживает композитные индексы, созданные с разными AM, например, gist и btree. Типичным примером использования является создание индекса по (ftsindex, ts), где ftsindex - колонка типа tsvector, а ts - timestamp. Такой индекс можно использовать не только для обычного полнотекстового поиска, но и для его ускорения поиска в определенном временном интервале.
CREATE INDEX fts_ts_idx ON foo USING gist(ftsindex,ts);
Здесь, по полю ts будет автоматически использоваться методы модуля btree_gist, а не btree.
gevel - набор функций для изучения GiST индекса
Этот модуль предназначен в первую очередь для разработчиков расширений с использованием GiST. Мы будем использовать модуль rtree_gist и данные, которые использовались для получения этой . в виде:
create table cities (id int4, b box); \copy cities from 'cities_mbr.copy' with delimiter as '|' rtree=# \d bix Index "public.bix" Column | Type --------+------ b | box gist, for table "public.cities"
Показать статистику об индексе: rtree=# select gist_stat('bix'); Number of levels: 2 Number of pages: 64 Number of leaf pages: 63 Number of tuples: 6782 Number of leaf tuples: 6719 Total size of tuples: 298408 bytes Total size of leaf tuples: 295636 bytes Total size of index: 524288 bytes

Вывести информацию о дереве, вплоть до уровня MAXLEVEL - gist_tree(INDEXNAME,MAXLEVEL) regression=# select gist_tree('pix',0); 0(l:0) blk: 0 numTuple: 29 free: 6888b(15.63%)
Здесь (слева направо):
0 - page number (l:0) - tree level blk: 0 - block number numTuple: 29 - the number of tuples free: 6888b - free space in bytes (15.63%) - occupied space in percents
Для визуализации дерева (смотри ) можно использовать функцию gist_print(INDEXNAME). Например, для визуализации разбиения на уровне 1, мы направляем вывод в файл: \pset tuples_only \o cities-l-1.leaf -- для версии PostgreSQL < 8.1 SELECT * FROM gist_print('bix') AS t(level int, a box) WHERE level = 1; -- для версии PostgreSQL начиная с 8.1 SELECT * FROM gist_print('bix') AS t(level int, valid bool, a box) WHERE level =1;
Обратите внимание на разницу в запросах ! Аналогично, можно получить данные для концевых узлов (уровень 2). Полученные данные использовались для получения .
Внимание: Функция gist_print(INDEXNAME) можно использовать только для объектов в индексе, которые имеют текстовое представление. Для этого необходимо написать функцию type_out для рассматриваемого типа объекта, например, tsvector_out для полнотекстового типа tsvector из модуля tsearch2. Функция box_out определена в ./backend/utils/adt/geo_ops.c
и для полноты приведем ее здесь:
/* box_out - convert a box to external form */ Datum box_out(PG_FUNCTION_ARGS) { BOX *box = PG_GETARG_BOX_P(0); PG_RETURN_CSTRING(path_encode(-1, 2, &(box->high))); }
Полный список расширений и документацию можно прочитать на странице разработчиков GiST.

Программный интерфейс GiST

Для дальнейшего ознакомления полезно ознакомиться с некоторыми особенностями программирования функция для PostgreSQL на языке C, которые приведены в .

GiST предоставляет разработчикам новых типов данных основные методы для работы с ними: SEARCH, INSERT, DELETE. Управлять этими методами можно с помощью 7 интерфейсных функций, которые разработчик должен специфицировать.

Большинство функций интерфейса работают с ключами, передаваемыми в следующей структуре:

typedef struct GISTENTRY { Datum key; /* собственно ключ */ Relation rel; /* индекс */ Page page; /* страница индекса */ OffsetNumber offset; /* положение в индексе */ int bytes; /* длина ключа в байтах, может быть равной -1 */ bool leafkey; /* признак, указывающий, что в key находится не ключ, а значение из таблицы */ } GISTENTRY;

Как правило, для обычных реализаций представляют интерес поля key и leafkey.

Общие замечания:

Ни одна из интерфейсных функций не имеет права вернуть NULL Всем функциям, кроме penalty(см ), никогда не передаются NULL или GISTENTRY с значением key NULL.

Ссылки

www.postgresql.org - сервер проекта PostgreSQL

[B05] Олег Бартунов, Что такое PostgreSQL? - обзорная статья (на русском) о PostgreSQL

www.pgsql.ru - поиск по PostgreSQL ресурсам

[GBK] The GiST Indexing Project at Berkeley PostgreSQL GiST development page

[Sto86] 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 [HNP95] J. M. Hellerstein, J. F. Naughton, and Avi Pfeffer. "Generalized search trees for database systems." In Proceedings of the 21st International Conference on Very Large Data Bases, Zurich, Switzerland, 1995.

[Gut84] Antonin Guttman. "R-trees: a dynamic index structure for spatial searching." In ACM SIGMOD International Conference on Management of Data, pp. 47-54, 1984.

[Aok98] P.Aoki."Generalized 'Search' in Generalized Search Trees." In Proc. of the 14th Int. Conf. on Data Engineering, Orlando, USA, pp.380-389,1998.

[KMH97] Marcel Kornacker, C. Mohan, Joseph M. Hellerstein. "Concurrency and Recovery in Generalized Search Trees." SIGMOD Conference 1997, pp. 62-72.

[Kor99] Marcel Kornacker. "High-Performance Extensible Indexing." VLDB 1999, pp. 699-708.

При построении современных информационных систем

При построении современных информационных систем приходится решать разнообразные технологические задачи, связанные с хранением, доступом и поиском информации. Учитывая современные требования к производительности, надежности и шкалированию таких систем, такие задачи требуют использования достаточно сложных алгоритмов и специализированных структур данных (abstract data type, ADT).
Эффективный доступ к данным является одной из важнейшей задачей базы данных. Мы рассматриваем большие базы данных, которые не помещаются в оперативную память. Для таких БД эффективность доступа к данным определяется, в основном, количеством обращений к диску, поэтому основной задачей СУБД является минимизация этих обращений. Обычно, это достигается использованием индекса, который представляет собой вспомогательную структуру данных, предназначенную для ускорения получения данных удовлетворяющих определенным поисковым критериям. Индекс позволяет уменьшить количество дисковых операций необходимых для считывания данных с диска. Обычно, индекс представляет собой файл на диске, и, если этот файл становится очень большим, то может потребоваться дополнительный индекс для ускорения работы самого индекса. Методами доступа (access methods,AM), обычно, называют организацию (структуру) индексного файла и методы работы с ней. В традиционных реляционных СУБД для работы с одномерными данными, такими как строки, цифры, используются B+-tree и хэш, для которых разработаны очень эффективные алгоритмы работы. Однако, современные приложения, такие как ГИС (GIS), мультимедийные системы, CAD, цифровые библиотеки, которые по-сути используют многомерные данные, требуют других, более эффективных AM. Например, в ГИС основными типами данных являются точки, линии, полигоны. За последние годы было разработано десятки (около 70) различных специализированных AM, однако их реализация в серьезных СУБД связана с большими затратами из-за собственно программирования AM и обеспечения соответствующего уровня надежности, конкурентности, предоставляемых СУБД для обычных AM. Следует отметить, что для этого требуется работа очень квалифицированных программистов, знакомых с ядром СУБД, а также, тщательное и продолжительное тестирование.

Вместо написания новых AM для каждого нового типа данных, Майкл Стоунбрейкер [Sto86] предложил использовать существующие, хорошо изученные структуры, такие как B+-tree и R-tree. Эта идея нашла воплощение в СУБД Postgres, развиваемой в Беркли в 80-х годах (см. детали в [B05]). Идея Стоунбрейкера заключалась в повышении степени абстракции процедур доступа и обновления записей, которые и составляют АМ. Так, например, достаточно определить операторы сравнения, чтобы использовать B+-tree AM. На примере типа данных box Стоунбрейкер показал, как B+-tree можно использовать для операций AE (равенство), AL (меньше) и AG (больше). Однако, такой подход, несмотря на свои возможности, сильно ограничен, так как несмотря на тип данных, который хранится в B+-tree, нельзя использовать запросы кроме тех, которые предоставляет B+tree. Другими словами, этот подход поддерживал расширяемость типов, но не запросов и методов доступа.
Для того, чтобы преодолеть это ограничение, Hellerstein et al. [HNP95] предложили структуру индекса, называемую GiST ( Generalized Search Tree, Обобщенное поисковое дерево), которое является обобщенной разновидностью R-tree и предоставляет стандартные методы навигации по дереву и его обновления (расщепление и удаление узлов). Было отмечено, что очень многие AM можно представить как иерархию предикатов, в которой каждый предикат выполняется для всех ключей, содержащихся в подузлах этой иерархии. Таким образом, такая структура данных может служить шаблоном для реализации многих AM, не накладывая существенных ограничений. Например, в B+-tree записи во внутренних узлах представляют диапазоны, которые задают ограничения на ключи в концевых узлах соответствующего поддерева. GiST предоставляет индексный доступ к новым типам данным и поддерживает расширяемый набор запросов. Это позволяет разрабатывать расширения экспертам в области данных, не будучи экспертами-разработчиками ядра СУБД. Кроме этого, эти новые ADT автоматически наследуют конкурентный доступ и восстановление после краха (concurrency and recovery), реализация которых с нуля, является очень большой задачей, предоставленные ядром GiST.

Следует отметить, что первый рабочий прототип был реализован в СУБД Postgres Дж. Хеллерстейном и П. Аоки [GBK] и практические все коммерческие СУБД (IDS/UDO Virtual Index Interface, DB2 UDB table functions, Oracle Extensible Indexing Interface) тем или иным образом используют идеи и результаты этой исследовательской СУБД. Однако, в самом Postgres (PostgreSQL), GiST до 2000 года практически не развивался и не использовался. Более того, его реализация не поддерживала конкурентного доступа и восстановления после краха системы, что мешало его использования в промышленных системах.
Авторы этой статьи, при работе над порталом "Рамблер", начали использовать GiST и занялись исправлением ошибок и его улучшением. Так, авторы добавили поддержку ключей переменной длины, композитных ключей (multi-key), оптимизировали алгоритм вставки (однопроходный вместо рекурсивного). Кроме того, для версии 8.1 авторы добавили поддержку конкурентного доступа к GiST индексам и восстановление после краха системы, используя модифицированные алгоритмы из работы Корнакера и др. [KMH97], что окончательно сняло все ограничения, мешающие использование его в сильно нагруженных системах и работе с критическими данными. Отметим, что большое количество модулей, написанных на базе GiST, автоматически "приобрели" всю эту индустриальную мощь без какого-либо изменения !
GiST представляет собой сбалансированное (по высоте) дерево, концевые узлы (листья) которого содержат пары (key, rid), где key - ключ, а rid - указатель на соответствующую запись на странице данных. Внутренние узлы содержат пары (p,ptr), где p - это некий предикат (используется как поисковый ключ), выполняющийся для *всех* наследных узлов, а ptr - указатель на другой узел в дереве.
Для этого дерева определены базовые методы SEARCH, INSERT, DELETE, и интерфейс для написания пользовательских методов, которыми можно управлять работой этих (базовых) методов.
Метод SEARCH управляется функцией Consistent, возвращающая 'true', если узел удовлетворяет предикату, метод INSERT - функциями penalty, picksplit и union, которые позволяют оценить сложность операции вставки в узел, разделить узел при переполнении и перестроить дерево при необходимости, метод DELETE находит лист дерева, содержащий ключ, удаляет пару (key, rid) и, если нужно, с помощью функции union перестраивает родительские узлы.

Возможность разработки пользовательских расширений, которые

Возможность разработки пользовательских расширений, которые оптимизированы для конкретной задачи, является неотъемлемой составляющей любой современной ORDBMS.
Обобщенное поисковое дерево (GiST), которое входит в ядро PostgreSQL, дает возможность специалистам в конкретной области знаний создавать специализированные типы данных и обеспечивает индексный доступ к ним не будучи экспертами в области баз данных. При этом, пользовательские расширения будут отвечать всем требованиям безопасности данных, накладываемых на ORDMBS, и поддерживать конкурентный доступ к данным.

Администраторам баз данных

Данный раздел получился куцым, ибо многое из того, что призвано улучшить жизнь DBA, описано выше :-) Тем не менее, расскажем кратко о том, что осталось.

В планах запросов (команда EXPLAIN ANALYZE) теперь видно, какой именно алгоритм сортировки был выбран и сколько памяти было израсходовано: QUERY PLAN ------------------------------------------------------- Sort (cost=34.38..34.42 rows=13 width=176) (actual time=0.946..0.948 rows=6 loops=1) Sort Key: obj2tag.o2t_tag_name Sort Method: quicksort Memory: 18kB <-- см. сюда! -> Hash Join (cost=19.19..34.14 rows=13 width=176) (actual time=0.812..0.835 rows=6 loops=1) [...]

Специальный contrib-модуль pg_standby, написанный Саймоном Ригсом (Simon Riggs) упростит работу администраторам, настраивающим сервер «тёплого бэкапа» (Warm Standby) на основе трансфера журнала логов (WAL transfer). Модуль написан на чистом C, поэтому является легко расширяемым и портируемым на новые платформы (работоспособность проверена уже, по крайней мере, на Linux и Win32).

При определении функции теперь можно переопределять переменные окружения, которые будут действовать только в рамках выполнения данной функции (привязка значений переменных функциям). Например, вот так можно указать, что выполнение функции log _data() переключает транзакцию в режим асинхронности: ALTER FUNCTION log_data(text) SET synchronous_commit TO OFF;

Ну и, по традиции, краткий список других новинок данного раздела:

поддержка интерфейса GSSAPI; улучшенная сборка на платформе Win32 (теперь не требуется MinGW, сборка ведётся в MS VC++, что помимо прочего приводит к улучшению производительности в Windows); создание таблиц по подобию с учётом индексов (пример: CREATE TABLE dict2 (LIKE dictionary INCLUDING INDEXES)).

Дополнительные проекты

Компания EnterpriseDB (сотрудники которой являются активным разработчиками PostgreSQL, многие изменения версии 8.3 в области производительности являются именно их заслугой) выпустила отладчик pldebugger, который представляет собой contrib-модуль, позволяющий отлаживать PL/pgSQL-функции в стандартном инструменте для администрирования pgAdminIII и осуществлять профайлинг.

Проект в данный момент существует в виде независимого contrib-модуля (представлен на PgFoundry) и работает на большом количестве платформ (включая Linux и Win32). Стоит отметить, что данный модуль работает и с версией 8.2 Постгреса.

Как мы рассказывали не так давно, компания Skype (которая использует в широко известном одноимённом проекте именно PostgreSQL) выпустила в Open Source сразу несколько продуктов, которые могут быть полезны большому кругу разработчиков. Среди них прежде всего стоит отметить псевдо-язык PL/Proxy, позволяющий организовывать горизонтальное масштабирование практически без ограничений (при условии, если вся бизнес-логика приложения реализована в виде хранимых процедур), чрезвычайно лёгкий менеджер соединений PgBouncer. Загляните на страничку Skype Developers Zone, вы найдёте много интересного!

На рубеже весны и лета 2007-го года вышла версия 1.0 простого и удобного инструмента для анализа логов pgFouine. Данная программа поможет вам узнать, чем же занимался ваш процессор (процессоры) сервера баз данных. pgFoiune анализирует логи запросов Постгреса (при включении журнализации запросов рекомендуется вводить ограничение по времени снизу, см. описание параметра log_min_duration_statement), предоставляя отчёты по самым медленным запросам, ошибкам и общую статистику (см. примеры). Тем самым данный инструмент позволяет разработчику баз данных понять, какие запросы можно улучшить, чтобы ускорить работу приложения, использующего PostgreSQL.

И наконец, кратко об остальных продуктах:

проект pgSNMP является реализацией SNMP-агента для PostgreSQL (мониторинг состояния сервера); SEPostgres – расширение, основанное на модели обеспечения усиленной безопасности SELinux; создан инструмент, создающий рекомендации администратору баз данных по созданию индексов и показывающий возможный план выполнения запроса при условии наличия таких индексов (Index Advisor); в известном инструменте для web-администрирования phppgadmin появились (или вот-вот появятся) возможности настройки Slony-кластера, полнотекстового поиска, параметров автовакуума.

8 октября 2007 года Джош

Николай Самохвалов

8 октября 2007 года Джош Беркус (Josh Berkus) объявил о выходе PostgreSQL 8.3beta1 (см. официальный Changelog). Более полугода потребовалось разработчикам для того, чтобы завершить работу по обработке патчей (напомним, feature freeze состоялся 1-го апреля 2007 года). Так что самое время рассказать, чем же порадует нас в этом году самая развитая из открытых СУБД в мире.

Я разобью весь список на четыре части. В первой, для многих самой важной, части я перечислю изменения, которые так или иначе касаются производительности. Во второй — приведу список новых возможностей для программистов баз данных, призванных ещё более расширить и без того неслабый набор «фич» PostgreSQL. Третья часть посвящена нововведениям, предназначенным для администраторов баз данных. И, наконец, в конце я упомяну некоторые Open Source проекты, которые являются проектами-спутниками Постгреса (другими словами, имеют свой собственный цикл разработки).

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

Начнём с того, что сегодня (на данный момент стабильная ветка — 8.2, актуальная версия — 8.2.5) PostgreSQL успешно тягается в плане производительности не только с OpenSource-альтернативами, но и с ведущими коммерческими СУБД. Такими как Oracle. Это уже не пустой звук — взгляните на результаты тестирования, проведённого в компании Sun. Медленных слонов больше нет! Богатейший набор типов индексов, широчайшие возможности тюнинга системы, работа с очень большими объёмами и нагрузками, хороший выбор систем репликации и масштабирования — всё это «по зубам» современным слонам. Даже скорость разработки выгодно отличает Постгрес по сравнению с другими СУБД: каждый год мы неизменно получаем существенный шаг вперёд.

Что же нового в PostgreSQL версии 8.3 в плане производительности? Многие изменения нетривиальны. По словам координатора разработки PostgreSQL Брюса Момджана (Bruce Momjian), нанёсшего не так давно по приглашению компании «Постгресмен» визит в Москву, та работа по оптимизации производительности системы, которой заняты разработчики Постгреса в последние годы, является чрезвычайно сложной. Каждый шаг требует всё более и более существенных трудозатрат, занимает всё больше времени и сил разработчиков.

Одним из таких действительно нетривиальных изменений можно смело считать «фишку» под названием HOT (Heap Only Tuples). Это, пожалуй, одно из самых существенных изменений в плане производительности. Чтобы понять, в чём заключается данное изменение, необходимо вспомнить, что PostgreSQL реализует так называемую мультиверсионную модель разграничения доступа (MVCC, Multi-Version Concurrency Control).

Суть HOT в следующем. Ранее, до реализации данного подхода, при обновлении строки в таблице каждая новая её версия приводила к появлению новых версий всех индексов, независимо от того, затрагивали ли данные изменения проиндексированные столбцы или нет (см. рис. «Обновление без HOT»). Теперь же, если новая версия строки попадает в ту же страницу памяти, что и предыдущая, и столбцы, по которым был создан индекс, не изменялись, индекс остаётся прежним. Но это ещё не всё. Если есть такая возможность, происходит «моментальное» повторное использование места в странице Heap. Что, естественно, сокращает объём работы, производимой при операции VACUUM. На рис. «HOT-обновление» схематически отображено, каким образом происходит теперь обновление строки.

Следующая новинка придётся по вкусу, прежде всего, большому количеству веб-разработчиков. Начиная с версии 8.3 любую транзакцию в PostgreSQL можно делать «асинхронной».

Это означает, что при выполнении операции фиксации транзакции (COMMIT) сервер PostgreSQL не будет ждать завершения дорогостоящей операции синхронизации журнала транзакций (WAL fsync). Другими словами, транзакция будет считаться успешно завершённой сразу же, как только все логические условия будут выполнены (проверены все необходимые ограничения целостности). Физически запись в журнал транзакций произойдёт через очень малый промежуток времени (как правило, для нормально функционирующих систем это максимум 200-1000 мс).За состояние транзакции (синхронная/асинхронная) отвечает переменная окружения synchronous_commit. Перейти в асинхронный режим просто: SET synchronous_commit TO OFF;

Стоит отметить, что асинхронные транзакции не являются альтернативой режиму работы сервера с отключенной операций fsync. Дело в том, что режим fsync=off может привести к получению несогласованного состояния базы (к примеру, в случае непредвиденного отказа оборудования или потери питания) и рекомендуется только в тех случаях, когда используется оборудование высокой надёжности (например, контроллер дисков с батарейкой). Использование же новой возможности никак не может привести к рассогласованию данных. Максимум, что возможно, это потеря небольшой порции данных (опять-таки, в случае жёсткого сбоя сервера — ошибки ОС, оборудования, сбой питания). Типичным примером для асинхронных транзакций может служить задача сохранения большого количества информации в таблицу-журнал (например, лог действий пользователя), когда потеря нескольких строк не является критичной. При этом все важные транзакции могут по-прежнему быть синхронными.

Ещё одно улучшение в области производительности относится к ситуациям, когда при выполнении запросов PostgreSQL последовательно просматривает таблицы (операция SeqScan). Если до версии 8.3 в таких случаях нередко возникали ситуации, когда разные процесса Постгреса одновременно делали одну и ту же работу — просматривали одну и ту же таблицу — то теперь, благодаря реализации Synchronized Scans («синронизованные просмотры»), в один и тот же момент времени для одной таблицы может проводиться не более одной операции просмотра. Достигается это следующим образом. Если в рамках какой-либо сессии требуется проведение SeqScan-а для некоторой таблицы, для которой уже выполняется SeqScan (для другой сессии), то произойдёт «прыжок на ходу» к результатам уже выполняющегося SeqScan-а. По завершении данного процесса, если это необходимо, будет осуществлён «добор» результатов с помощью ещё одного неполного SeqScan-а (см. рис).

Работа над уменьшением стресс-эффекта, производимого выполнением системой процессов checkpoint («контрольная точка») продолжается: теперь checkpoint-ы выполняются не сразу, а постепенно: процесс как бы «размазан» во времени. Отсюда и название данного изменения — checkpoint smoothing. Стоит отметить, что при штатном выключении сервера и проведениия «явной» операции checkpoint (команда CHECKPOINT) запись данных на диск по-прежнему будет производиться с максимально возможной скоростью.

В завершение разговора о производительности, приведём краткий перечень других изменений, призванных улучшить быстродействие систем, использующих PostgreSQL:

теперь autovacuum включён по умолчанию; в некоторых ситуациях теперь возможнен запуск сразу нескольких процессов autovacuum (например, при продолжительном процессе чистки большой таблицы, небольшие таблицы теперь не вынуждены ждать завершения данного процесса); заметное уменьшение дискового пространства, занимаемого базами данных: 1) за счёт заголовков varlena-типов (типы данных переменной длины: текст, массивы и т. п.), которые ранее занимали строго 4 байта, а теперь в некоторых ситуациях всего 1 байт; 2) за счёт экономии заголовков строк таблицы (ранее 27 байт, теперь — 24); выполнение транзакций, не модифицирующих данные, не приводит к увеличению значения счётчика транзакций (xid), что существенно снижает вероятность ситуации «перекрытия» счётчика транзакций (xid wraparound); кроме того, данное изменение является значительным шагом вперёд к реализации встроенной Master-Slave репликации на основе трансфера журнала транзакций — теперь не возникнет рассинхронизации счётчика xid между Master- и Slave-узлами; реализован механизм автонастройки параметров процесса bgwriter (background writer — специальный процесс, занимающийся записью «грязных» разделяемых буферов на диск); оптимизирован механизм получения результата для запросов с использованием «…ORDER BY … LIMIT…» (т. н., Top-N sorting): в некоторых случаях система удерживает необходимые страницы данных в оперативной памяти, что обеспечивает очень высокую скорость выдачи результата; теперь можно задавать (пока только в виде двух констант) оценочную стоимость выполнения фунции и оценку количества рядов, которые она возвращает, что позволяет планнеру PostgreSQL выбирать лучший план запроса (пример: ALTER FUNCTION log_data(text) COST 100000 ROWS 1).

Разработчикам баз данных

Самое заметное и существенное изменение, которое следует здесь отметить, — это миграция модуля для полнотекстового поиска (contrib/tsearch2) в ядро системы. Разрабатываемый российскими разработчиками Олегом Бартуновым и Фёдором Сигаевым, tsearch2 долгое время являлся самым популярным contrib-модулем Постгреса. Патч для миграции полнотекстового поиска в ядро, который был принят этим летом в результате кропотливой и продолжительной работы (принятая версия патча — 58!) сразу нескольких ключевых разработчиков команды PostgreSQL, является самым большим за всю историю проекта.

Кроме того, что все возможности модуля tsearch2 теперь будут доступны по умолчанию и процессы миграции на новую версию PostgreSQL заметно упростятся, конфигурировать словари и правила обработки текстов теперь станет проще: все основные операции по конфигурированию осуществляются с помощью SQL-команд. Вот так, например, можно создать простой словарь-тезаурус: СREATE TEXT SEARCH DICTIONARY thesaurus_astro ( TEMPLATE = thesaurus, DictFile = thesaurus_astro, Dictionary = english_stem ); ALTER TEXT SEARCH CONFIGURATION russian ADD MAPPING FOR lword, lhword, lpart_hword WITH thesaurus_astro, english_stem;

Упростились и процессы создания индекса. Пример создания GIN-индекса над обычным текстовым столбцом (без создания дополнительных столбцов и триггеров):

CREATE INDEX pgweb_idx ON pgweb USING gin(to_tsvector('russian', title body));

А вот пример запроса с ранжированием по релевантности, использующий к тому же специальную функцию plainto_tsquery для получения tsquery (позволяет забыть об экранировании символов и быстро и просто преобразовать обычный текст в tsquery):

SELECT ts_rank_cd(textsearch_index, q) AS rank, title FROM pgweb, plainto_tsquery('supernova star') q WHERE q @@ textsearch_index ORDER BY rank DESC LIMIT 10;

Другое заметное изменение — поддержка XML, в работе над которой принимал участие автор данной статьи. Данный функционал реализован в соответствии со стандартом SQL:2003 (14-я часть стандарта, SQL/XML).

Прежде всего, появился специальный тип данных xml, встроенный в ядро. При использовании данного типа, сервер проверяет, правильно ли сформированы данные (проверка на well-formedness). Причём возможны варианты использования, при которых разрешена работа с частями документа (это позволяет обеспечить свойство «замкнутости» функций для работы с XML на тип данных xml).

В соответствии со стандартом SQL:2003 реализован набор функций для преобразования реляционных данных в XML (т. н., функции публикации SQL/XML). Вот простой пример запроса на формирование XML-данных: SELECT XMLROOT ( XMLELEMENT ( NAME 'some', XMLATTRIBUTES ( 'val' AS 'name', 1 + 1 AS 'num' ), XMLELEMENT ( NAME 'more', 'foo' ) ), VERSION '1.0', STANDALONE YES );

Кроме того, реализована поддержка DTD-валидации (функция xmlvalidatedtd()), поддержка оценки XPath-выражений (функция xpath(), возвращающая массив из данных типа xml ), и альтернативные функции для упрощённой публикации реляционных данных в виде XML (функции tabletoxml(), querytoxml() и другие).

Для ускорения выполнения запроса к XML-данным возможно использование функциональных btree-индексов и GIN-индексов, а также использования полнотекстового поиска для XML-данных. Приведём пример создания btree-индекса по результатам оценки XPath-выражения:

CREATE INDEX i_table1_xdata ON table1 USING btree( ((xpath(’//person/@name’, xdata))[1]) );

Что касается типов данных, PostgreSQL 8.3 представляет целый ряд нововведений: помимо встроенных в ядро системы типов tsquery/tsvector и xml, появились следующие:

enum (перечислимые типы данных, определяемые пользователем) для удобства некоторых пользователей, в том числе мигрирующих с TheirSQL; типы данных GUID/UUID (в виде contrib-модуля); массивы составных типов (например, определённых пользователем типов).

автоматическая инвалидация кэша плана запросов для PL/pgSQL-функций; конструкции «CREATE FUNCTION … RETURNS TABLE» и «RETURN TABLE…» для создания функций, результатом которых является таблица; поддержка операции обновления для курсоров; стандартная (ISO/ANSI SQL) конструкция «ORDER BY … NULLS FIRST/LAST» для упрощения установки порядка следования NULL-значений (также помогает при миграции с других СУБД); индексация NULL-значений в GiST-индексах.

является очередным шагом на

Версия 8. 3 является очередным шагом на пути к полноценной системе управления баз данных для корпоративного использования. Нетривиальные улучшения в области производительности, появление возможностей, которые продиктованы нуждами пользователей, расширение множества проектов-спутников — всё это демонстрирует уверенное и быстрое развитие PostgreSQL.

При написании данного обзора автор использовал следующие источники:
pgwiki/WhatsNew83 pgwiki/Feature_Matrix pgwiki/8.3_Changelog pgwiki/Todo:PatchStatus Доклад Брюса Момджана на конференции Highload-2007, Москва (pdf). Официальная документация PostgreSQL 8.3. Архив рассылки pgsql-hackers.

Что есть PostgreSQL сегодня ?

На сегодняшний день выпущена версия PostgreSQL v8 (19 января 2005 года), которая является значительным событием в мире баз данных, так как количество новых возможностей добавленных в этой версии, позволяет говорить о возникновении интереса крупного бизнеса. Так, крупнейшая компания в мире, Fujitsu поддержала работы над версией 8, выпустила коммерческий модуль .

Что ожидается в будущих версиях

Полный список новых возможностей приведен в большом списке TODO, который уже много лет поддерживает Брюс Момжан (Bruce Momjian), однако приоритеты для версии 8.1 еще не определены, более того, пока не определен продолжительность цикла разработки. Пока можно достаточно уверенно утверждать, что в 8.1 версии, помимо исправлений ошибок и улучшения существующей функциональности или приведение синтаксиса к стандарту SQL, будут: bitmap индексы интегрирование autovacuum в серверный процесс Two phase commit JDBC driver поддержка IN,OUT,INOUT параметров для pl/pgsql увеличение предела максимального количества аргументов у функции (100 по умолчанию) Также, недавно проходило обсуждение о возможных планах о поддержке table partitioning, что сильно увеличивает производительность базы данных при работе с большими таблицами.

Что такое PostgreSQL?

, Астрономический институт имени П.К. Штернберга , МГУ

Текст написан в 2005 году, приветствуются.

PostgreSQL - это свободно распространяемая объектно-реляционная система управления базами данных (ORDBMS), наиболее развитая из открытых СУБД в мире и являющаяся реальной альтернативой коммерческим базам данных.
PostgreSQL произносится как post-gress-Q-L (можно скачать mp3 файл ), в разговоре часто употребляется postgres. Также, употребляется сокращение pgsql (пэ-жэ-эс-ку-эль).

Цикл разработки

Цикл работой над новой версией обычно длится 10-12 месяцев (сейчас ведется дискуссия о более коротком цикле 2-3 месяца) и состоит из нескольких этапов (упрощенная версия):

Обсуждение предложений в списке -hackers. На собственном опыте могу заверить, что это очень непростой процесс и плохо подготовленный proposal не пройдет. Учитываются много факторов - алгоритмы, структуры данных, совместимость с существующей архитектурой, совместимость с SQL и так далее. После принятия решения о работе над новой версией в CVS открывается новая ветка и с этого момента все изменения, касающиеся новых возможностей, вносятся туда. Также, анализируются патчи, которые присылаются в список -patches. Все изменения протоколируются и доступны любому для рассмотрения (anonymous CVS, -commiters лист рассылки или через веб-интерфейс к CVS). Иногда, в процессе работы над новой версией вскрываются или исправляются старые ошибки, в этом случае, наиболее критические исправляются и в предыдущих версиях (backporting). По мере накопления таких исправлений принимается решение о выпуске новой стабильной версии, которая совместима со старой и не требует обновления хранилища. Например, 7.4.7 - является bugfix-ом стабильной версии 7.4. В некоторый момент объявляется этап code freeze(замораживания кода), после которого в CVS не допускается новая функциональность, а только исправление или улучшение кода. Граница между новой функциональностью и улучшением кода не описана и иногда возникают разногласия на этот счет, к документации и расширениям (contribution modules в поддиректории contrib/) обычно относятся более либерально. Замечу, что все это время все CVS версия проходит непрерывное тестирование на большом количестве машин, под разными архитектурами, операционными системами и компиляторами. Все это стало возможно благодаря проекту pgbuildfarm, который является распределенной системой тестирования, объединяющая добровольцев, которые предоставляют свои машины для тестирования. Проверяется не только корректность сборки, но и, благодаря обширному набору тестов (regression test), и правильность работы. Время от времени, проект OSDB помогает в обнаружении систематических изменений производительности (в обе стороны), иногда такие обнаружения приводят к необходимости "размораживания кода". После внутреннего тестирования "собирается" дистрибутив и объявляется выход бета версии, на тестирование и исправление ошибок отводится 1-3 месяца. Бета версия не рекомендуется для использования в продакшн проектах (production), но практика показала хорошее качество таких версий и многие начинают ее использовать ради апробирования новой функциональности. Как правило, окончательная версия совместима с бета-версией и не требует обновления хранилища. По мере исправления замеченных ошибок выпускаются новые бета-версии. После исправления всех замеченных ошибок, выпускается релиз-кандидат, который уже практически ничем не отличается от окончательной версии, разве что не хватает документации и списка изменений. В течении месяца выходит окончательная версия, которая анонсируется на главном проекта и его зеркалах, мэйлинг листах. Также, PR группа, которая к этому моменту подготовила анонсы на разных языках, распространяет их по всем ведущим сайтам и СМИ. Они принимают участие в конференциях, семинарах и прочих общественных мероприятиях.

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

Где используется

Если изначально POSTGRES использовался в основном в академических проектах для исследования алгоритмов баз данных, в университетах как отличная база для обучения, то сейчас PostgreSQL применяется практически повсеместно. Например, зоны .org, .info полностью обслуживаются PostgreSQL, известны многотерабайтные хранилища астрономических данных, Lycos, BASF. Из российских проектов, использующих PostgreSQL, наиболее известными является портал , в разработке которого я принимал участие в 2000-2002 годах, федеральные порталы Минобразования.

История развития PostgreSQL

Краткую историю PostgreSQL можно прочитать в документации, распространяемой с дистрибутивом или на сайте. Также, есть перевод на русский язык. Из нее следует, что современный проект PostgreSQL ведет происхождение из проекта POSTGRES, который разрабатывался под руководством Майкла Стоунбрейкера (Michael Stonebraker), профессора Калифорнийского университета в Беркли (UCB). Мне захотелось несколько подробнее показать взаимосвязи родословных баз данных, чтобы лучше понять место PostgreSQL среди основных игроков современного рынка баз данных.

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

Надо сказать, что несмотря на то, что вся история реляционных баз данных насчитывает менее 4 десятков лет, многие факты из истории создания трактуются по-разному, даты не согласуются, а сами участники событий зачастую просто вольно трактуют прошлое.Здесь надо принимать во внимание тот факт, что базы данных - это большой бизнес, в котором развитие одних БД часто связано с концом других. Кроме того, БД в то время были предметом научных исследований, поэтому приоритетность работ является не последним аргументом при написании воспоминаний и интервью. Наверное, учитывая такую запутанность, премия ACM Software System Award #6 была присуждена одновременно двум соперничающим группам исследователей из IBM за работу над "System R" и Беркли - за INGRES, хотя Стоунбрейкер получил награду от ACM SIGMOD (сейчас это премия названа в честь Теда Кодда - автора реляционной теории баз данных) #1 в 1992 г., а Грей (James Gray, Microsoft) - #2 в 1993 году.

Итак, как следует из рисунка, видно две ветви развития баз данных - одна следует из "System R", которая разрабатывалась в IBM в начале 70-х, и другая из проекта "INGRES", которым руководил Стоунбрейкер приблизительно в тоже время. Эти два проекта начались как необходимость практического использования реляционной модели баз данных, разработанной Тедом Коддом (Ted Codd) из IBM в 1969,1970 годах. Надо помнить, что в то время имелось две альтернативные модели баз данных - сетевая и иерархическая, причем за ними стояли мощные силы - CODASYL Data Base Task Group (сетевая) и сама IBM с ее базой IMS (Information Management System с иерархической моделью данных). Немного в стороне стоит "Oracle", взлет которой во многом связан с коммерческим талантом Эллисона быть в нужном месте и в нужное время, как сказал Стоунбрейкер в своем , хотя она вместе с IBM сыграла большую роль в создании и продвижении SQL.

"System R" сыграла большую роль в развитии реляционных баз данных, создании языка SQL (изначально SEQUEL, но из-за проблем с уже существующей торговой маркой пришлось выкинуть все гласные буквы). Из "System R" развилась SQL/DS и DB2. На самом деле, в IBM было еще несколько проектов, но они были чисто внутренними. Подробнее об этой ветви можно прочитать в весьма поучительном документе , русский перевод которого доступен на сайте CITForum.ru.

INGRES (или Ingres89), в отличие от "System R", вполне в духе Беркли развивалась как открытая база данных, коды которой распространялись на лентах практически бесплатно (оплачивались почтовые расходы и стоимость ленты). К 1980 году было распространено порядка 1000 копий. Название расшифровывается как "INteractive Graphics Retrieval System" и совершенно случайно связано с французским художником Jean Auguste Dominique Ingres. Отличительной особенностью этой системы являлось то, что она разрабатывалась для операционной системы UNIX, которая работала на распространенных тогда PDP 11, что и предопределило ее популярность, в то время как "System R" работала только на больших и дорогих mainframe. Был разработан язык запросов QUEL, который, как писал Стоунбрейкер, похож на SEQUEL в том отношении, что программист свободен от знания о структуре данных и алгоритмах, что способствует значительной степени независимости от данных. Доступность INGRES и очень либеральная лицензия BSD, а также творческая деятельность, способствовали появлению большого количества реляционных баз данных, как показано на рисунке.

Стоунбрейкер лично способствовал их появлению, так он конце 70-х он организовал компанию Ingres Corporation (как он сам объясняет, ему пришлось на это пойти, так как Аризонский университет, потребовал поддержки), которая выпустила коммерческую версию Ingres, в 1994 году она была куплена CA (Computer Associates) и которая в 2004 году стала открытой как Ingres r3.

"NonStop SQL" компании Tandem Computers являлась модифицированной версией Ingres, которая эффективно работала на параллельных компьютерах и с распределенными данными. Она умела выполнять запросы параллельно и масштабировалась почти линейно с количеством процессоров. Ее авторами были выпускники из Беркли. Впоследствии, Tandem Computers была куплена компанией Compaq (2000 г.), а затем компанией HP.

Компания Sybase тоже была организована человеком из Беркли (Роберт Эпстейн) и на основе Ingres. Известно, что база данных компании Мaйкрософт "SQL Server" - это не что иное как база данных Sybase, которая была лицензирована для Windows NT. С 1993 года пути Sybase и Mirosoft разошлись и уже в 1995 году Sybase переименовывает свою базу данных в ASE (Adaptive Server Enterprise), а Microsoft стала продолжать развивать MS SQL.

Informix тоже возник из Ingres, но на это раз людьми не из Беркли, хотя Стоунбрейкер все-таки поработал в ней CEO после того, как Informix купила в 1995 году компанию Ilustra, чтобы прибавить себе объектно-реляционности и расширяемости (DataBlade), которую организовал все тот же Майкл Стоунбрейкер как результат коммерциализации Postgres в 1992 году. В 2001 году она была куплена IBM, которая приобретала немалое количество пользователей Informix и технологию. Таким образом, DB2 также приобрела немного объектно-реляционности.

Проект Postgres возник как результат осмысления ошибок Ingres и желания преодолеть ограниченность типов данных, за счет возможности определения новых типов данных. Работа над проектом началась в 1985 и в период 1985-1988 было опубликовано несколько статей, описывающих модель данных, язык запросов POSTQUEL, и хранилище Postgres.

Еще при проектировании оригинальной версии POSTGRES основное внимание было уделено расширяемости и объектно-ориентированным возможностям. Уже тогда было ясна необходимость расширения функциональности DMBS от управления данными (data management) в сторону управления объектами (object management) и знаниями (knowledge management). При этом объектная функциональность позволит эффективно хранить и манипулировать нетрадиционными типами данных, а управление знаниями позволяет хранить и обеспечивать выполнения коллекции правил (rules), которые несут семантику приложения. Стоунбрейкер так и определил основную задачу POSTGRES как "обеспечить поддержку приложений, которые требуют службы управления данными, объектами и знаниями".

Одним из фундаментальным понятием POSTGRES является class. Class есть именованная коллекция экземпляров (instances) объектов. Каждый экземпляр имеет коллекцию именованных атрибутов и каждый атрибут имеет определенный тип. Классы могут быть трех типов - это основной класс, чьи экземпляры хранятся в базе данных, виртуальный (view), чьи экземпляры материализуются только при запросе (они поддерживаются системой управления правилами), и может быть версией другого (parent) класса. Первая версия была выпущена в 1989 году, затем последовало еще несколько переписываний системы правил (rule system). Отметим, что коды Ingres и Postgres не имели ничего общего ! В 1992 году была образована компания Illustra, а сам проект был закрыт в 1993 году выпуcком версии 4.2. Однако, несмотря на официальное закрытие проекта, открытый код и BSD лицензия сподвигли выпускников Беркли Andrew Yu и Jolly Chen в 1994 году взяться за его дальнейшее развитие. В 1995 году они заменили язык запросов POSTQUEL на общепринятый SQL, проект получил название Postgres95, изменилась нумерация версий, был создан веб сайт проекта и появились много новых пользователей (среди которых был и автор).

К 1996 году стало ясно, что название "Postgres95" не выдержит испытанием временем и было выбрано новое имя - "PostgreSQL", которое отражает связь с оригинальным проектом POSTGRES и приобретением SQL. Также, вернули старую нумерацию версий, таким образом новая версия стартовала как 6.0. В 1997 был предложен слон в качестве логотипа, сохранилось письмо в архивах рассылки -hackers за 3 марта 1997 года и последующая дискуссия. Слон был предложен Дэвидом Янгом в честь романа Агаты Кристи "Elephants can remember" (Слоны могут вспоминать). До этого, логотипом был бегущий леопард (ягуар). Проект стал большой и управление на себя взяла небольшая вначале группа инициативных пользователей и разработчиков, которая и получила название PGDG (PostgreSQL Global Development Group). Дальнейшее развитие проекта полностью документировано в документации и отражено в архивах списка рассылки -hackers.

Некоторые ограничения PostgreSQL

Название

Значение

Максимальный размер БД	Unlimited
Максимальный размер таблицы	32 TB
Максимальная длина записи	1.6 TB
Максимальный длина атрибута	1 GB
Максимальное количество записей в таблице	Unlimited
Максимальное количество атрибутов в таблице	250 - 1600 в зависимости от типа атрибута
Максимальное количество индексов на таблицу	Unlimited

Основные возможности и функциональность

Полный список всех возможностей предоставляемых PostgreSQL и подробное описание можно найти в объемной документации (1300 страниц).

Надежность PostgreSQL является проверенным и доказанным фактом и обеспечивается следующими возможностями:

полное соответствие принципам ACID - атомарность, непротиворечивость, изолированность, сохранность данных.

Atomicity - транзакция рассматривается как единая логическая единица, все ее изменения или сохраняются целиком, или полностью откатываются. Consistency - транзакция переводит базу данных из одного непротиворечивого состояния (на момент старта транзакции) в другое непротиворечивое состояние (на момент завершения транзакции). Непротиворечивым считается состояние базы, когда выполняются все ограничения физической и логической целостности базы данных, при этом допускается нарушение ограничений целостности в течение транзакции, но на момент завершения все ограничения целостности, как физические, так и логические, должны быть соблюдены. Isolation - изменения данных при конкурентных транзакциях изолированы друг от друга на основе системы версионности Durability - PostgreSQL заботится о том, что результаты успешных транзакций гарантировано сохраняются на жесткий диск вне зависимости от сбоев аппаратуры.

многоверсионность (Multiversion Concurrency Control,MVCC) используется для поддержания согласованности данных в конкурентных условиях, в то время как в традиционных базах данных используются блокировки. MVCC означает, что каждая транзакция видит копию данных (версию базы данных) на время начала транзакции, несмотря на то, что состояние базы могло уже измениться. Это защищает транзакцию от несогласованных изменений данных, которые могли быть вызваны (другой) конкурентной транзакцией, и обеспечивает изоляцию транзакций. Основной выигрыш от использования MVCC по сравнению с блокировкой заключается в том, что блокировка, которую ставит MVCC для чтения не конфликтует с блокировкой на запись, и поэтому чтение никогда не блокирует запись и наоборот. наличие Write Ahead Logging (WAL) - общепринятый механизм протоколирования всех транзакций, что позволяет восстановить систему после возможных сбоев. Основная идея WAL состоит в том, что все изменения должны записываться в файлы на диск только после того, как эти записи журнала, описывающие эти изменения будут и гарантировано записаны на диск. Это позволяет не сбрасывать страницы данных на диск после фиксации каждой транзакции, так как мы знаем и уверены, что сможем всегда восстановить базу данных используя журнал транзакций. Point in Time Recovery (PITR) - возможность восстановления базы данных (используя WAL) на любой момент в прошлом, что позволяет осуществлять непрерывное резервное копирование кластера PostgreSQL. Репликация также повышает надежность PostgreSQL. Существует несколько систем репликации, например, Slony, который является свободным и самым используемым решением, поддерживает master-slaves репликацию. Ожидается, что Slony-II будет поддерживать multi-master режим. Целостность данных является сердцем PostgreSQL. Помимо MVCC, PostgreSQL поддерживает целостность данных на уровне схемы - это внешние ключи (foreign keys), ограничения (constraints). Модель развития PostgreSQL, которая абсолютно прозрачна для любого, так как все планы, проблемы и приоритеты открыто обсуждаются. Пользователи и разработчики находятся в постоянном диалоге через мэйлинг листы. Все предложения, патчи проходят тщательное тестирование до принятия их в программное дерево. Большое количество бета-тестеров способствует тестированию версии до релиза и вычищению мелких ошибок. Открытость кодов PostgreSQL означает их абсолютную доступность для любого, а либеральная BSD лицензия не накладывает никаких ограничений на использование кода.

Производительность PostgreSQL основывается на использовании индексов, интеллектуальном планировщике запросов, тонкой системы блокировок, системой управления буферами памяти и кэширования, превосходной масштабируемости при конкурентной работе.

Поддержка индексов

Стандартные индексы - B-tree, hash, R-tree, GiST (обобщенное поисковое дерево, которое позволяет на пользовательском уровне создавать свои типы данных и индексные методы доступа к ним) Частичные индексы (partial indices) Функциональные индексы

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

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

На рисунке приведена ER диаграмма системного каталога PostgreSQL, в котором заложены все сведения об объектах системы, операторах и методах доступа к ним. При инициализации PostgreSQL кластера (команда initdb) создаются две базы данных - template0 и template1, которые содержат предопределенный по умолчанию набор функциональностей. Любая другая база данных наследует template1, таким образом, часто используемые объекты и методы можно добавить в системный каталог template1.

PostgreSQL предоставляет команды для работы с системным каталогом и создания новых объектов (например, CREATE DATABASE, CREATE DOMAIN, CREATE OPERATOR, CREATE TYPE,....).

Одной из примечательных особенностью PostgreSQL является обобщенное поисковое дерево или GiST (домашняя страница проекта), которое дает возможность специалистам в конкретной области знаний создавать специализированные типы данных и обеспечивает индексный доступ к ним не будучи экспертами в области баз данных. Аналогом GiST является технология DataBlade, которой сейчас владеет IBM (см. историческую справку выше). Идея GiST была придумана профессором Беркли Джозефом Хеллерстейном(Joseph M. Hellerstein) и опубликована в статье Generalized Search Trees for Database Systems. Оригинальная версия GiST была разработана в Беркли как патч к POSTGRES и позднее была инкорпорирована в PostgreSQL. Позже, в 2001 году код был сильно модифицирован для поддержки ключей переменной длины, много-атрибутных индексов и безопасной работы с NULL, также были исправлено несколько ошибок. К настоящему времени написано довольно много интересных расширений на основе GiST, в том числе:

модуль полнотекстового поиска tsearch2 модуль для работы с иерархическими данными (tree-like) ltree модуль для работы с массивами целых чисел intarray

GiST представляет собой сбалансированное ( по высоте) дерево, листья которого содержат пары (key, rid), где key - ключ, а rid - указатель на соответствующую запись на странице данных. Внутренние узлы содержат пары (p,ptr), где p - это некий предикат (используется как поисковый ключ), выполняющийся для всех наследных узлов, а ptr - указатель на другой узел в дереве. Для этого дерева определены базовые методы SEARCH, INSERT, DELETE, и интерфейс для написания 6-ти пользовательских методов, которыми можно управлять работой этих (базовых методов). Метод SEARCH управляется функцией Consistent, возвращающая 'true', если узел удовлетворяет предикату, метод INSERT - функциями penalty, picksplit и union, которые позволяют оценить сложность операции вставки в узел, разделить узел при переполнении и перестроить дерево при необходимости, метод DELETE находит лист дерева, содержащий ключ, удаляет пару (key, rid) и, если нужно, с помощью функции union подстраивает родительские узлы. Дополнительные функции compress, decompress используются для оптимизации хранения ключей. Поддержка SQL, кроме основных возможностей, присущих любой SQL базе данных, PostgreSQL поддерживает:

Очень высокий уровень соответствия ANSI SQL 92, ANSI SQL 99 и ANSI SQL 2003. Подробнее можно прочитать в документации.

Схемы, которые обеспечивают пространство имен на уровне SQL Sub queries - подзапросы Outer Joins - внешние связки Rules - правила Views - представления, виртуальные таблицы Cursors - курсоры Inheritance - наследование Prepared Statements - преподготовленные запросы Stored Procedures - серверные (хранимые) процедуры Savepoints/nested transactions Права доступа к объектам системы на основе системы привилегий Система обмена сообщениями между процессами Триггеры

Богатый набор типов данных PostgreSQL включает:

Символьные типы (character(n)) как определено в стандарте SQL и тип text с практически неограниченной длиной. Numeric тип поддерживает произвольную точность, очень востребованную в научных и финансовых приложениях. Массивы согласно стандарту SQL:2003 Большие объекты (Large Objects) позволяют хранить в базе данных бинарные данные размером до 2Gb Геометрические типы (point, line, circle,polygon, box,...) позволяют работать с пространственными данными на плоскости. ГИС (GIS) типы в PostgreSQL являются доказательством расширяемости PostgreSQL и позволяют эффективно работать с трехмерными данными. Сетевые типы (Network types) поддерживают типы данных inet для IPV4, IPV6, а также cidr (Classless Internet Domain Routing) блоки и macaddr Композитные типы (composite types) объединяют один или несколько элементарных типов и позволяют пользователям манипулировать со сложными объектами. Временные типы (timestamp, interval, date, time) реализованы с очень большой точностью

Поддержка 25 различных наборов символов (charsets), включая ASCII, LATIN, WIN, KOI8 и UNICODE, а также поддержка locale, что позволяет корректно работать с данными на разных языках. Поддержка NLS(Native Language Support) - документация, сообщения об ошибках доступны на различных языках, включая японский, немецкий, итальянский, французский, русский, испанский, португальский, словенский, словацкий и несколько диалектов китайского языков. Интерфейсы в PostgreSQL реализованы для доступа к базе данных из ряда языков (C,C++,C#,python,perl,ruby,php,Lisp и другие) и методов доступа к данным (JDBC, ODBC). Процедурные языки позволяют пользователям разрабатывать свои функции на стороне сервера, тем самым переносить логику приложения на сторону базы данных, используя языки программирования, отличные от встроенных SQL и C. К настоящему времени поддерживаются (включены в стандартный дистрибутив) PL/pgSQL, pl/Tcl, Pl/Perl и pl/Python. Кроме них, существует поддержка PHP, Java, Ruby, R, shell. Простота использования всегда являлась важным фактором для разработчиков. Утилита psql предоставляет удобный интерфейс для работы с базой данных, содержит краткий справочник по SQL, облегчает ввод команд (используя стрелки для повтора и табулятор для расширения), поддерживает историю и буфер запросов, а также позволяет работать как в интерактивном режиме, так и потоковом режиме. Безопасность данных также является важнейшим аспектом любой СУБД. В PostgreSQL она обеспечивается 4-мя уровнями безопасности:

PostgreSQL нельзя запустить под привилегированным пользователем - системный контекст SSL шифрование трафика между клиентом и сервером - сетевой контекст сложная система аутентификации на уровне хоста или IP адреса/подсети. Система аутентификации поддерживает пароли, шифрованные пароли, Kerberos, IDENT и прочие системы, которые могут подключаться используя механизм подключаемых аутентификационных модулей. Детализированная система прав доступа ко всем объектам базы данных, которая совместно со схемой, обеспечивающая изоляцию названий объектов для каждого пользователя, PostgreSQL предоставляет богатую и гибкую инфраструктуру.

PGDG - PostgreSQL Global Development Group

PostgreSQL развивается силами международной группы разработчиков (PGDG), в которую входят как непосредственно программисты, так и те, кто отвечают за продвижение PostgreSQL (Public Relation), за поддержание серверов и сервисов, написание и перевод документации, всего на 2005 год насчитывается около 200 человек. Другими словами, PGDG - это сложившийся коллектив, который полностью самодостаточен и устойчив. Проект развивается по общепринятой среди открытых проектов схеме, когда приоритеты определяются реальными нуждами и возможностями. При этом, практикуется публичное обсуждение всех вопросов в списке рассылке, что практически исключает возможность неправильных и несогласованных решений.

Это относится и к тем предложениям, которые уже имеют или рассчитывают на финансовую поддержку коммерческих компаний.

Поддержка

Основной источник актуальной информации о PostgreSQL является его официальный сайт www.postgresql.org, который имеет зеркала по всему миру. На нем публикуются сведения о всех событиях (анонсы релизов, семинаров, конференций), поддерживается список ресурсов, относящихся к PostgreSQL. Основная поддержка осуществляется через почтовую рассылку, архивы которой доступны через Web по адресам:

Архив pgsql-ru-general - русскоязычного списка рассылки,как подписаться.

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

Небольшая статистика списков рассылок PostgreSQL по данным www.pgsql.ru на 1 апреля 2005 года. Распределение постингов по годам: # | Year ------------- 19355 | 2005 68403 | 2004 71884 | 2003 61604 | 2002 58072 | 2001 38793 | 2000 25258 | 1999 16779 | 1998 15315 | 1997 612 | 1996 7 | 1995

Поисковая система предоставляет поиск по сайтам сообщества. На момент написания этой статьи проиндексировано 480000 страниц из 67 сайтов, индекс обновляется еженедельно. Много полезной информации по PostgreSQL можно найти на сайтах

Документация на русском (переводы и оригинальные статьи) доступны на сайте русскоязычного сообщества http://www.linuxshare.ru/postgresql/.

Ответы на ваши вопросы можно найти в "PostgreSQL FAQ " (часто задаваемые вопросы):

Оригинальная версия на русском языке на linuxshare.ru

или

Коммерческая поддержка осуществляется рядом компаний, список которых доступен по адресу www.postgresql.org/support/.

Postgre

Разработка

Для проектов, имеющих отношение к PostgreSQL, предоставляется возможность размещать их на специальных сайтах, поддерживаемые PGDG и предоставляющие практически все, необходимые для разработчиков, сервисы:

Сообщество

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

Структура

Управляющий комитет (6 человек).
Принимает решение о планах развития и выпусках новых версий. Заслуженные разработчики ( 2 человека ).
Бывшие члены управляющего комитета, которые отошли от участия в проекте. Основные разработчики (23). Разработчики (22)

Кроме PGDG, значительное участие в развитии PostgreSQL принимает некоммерческая организация "The PostgreSQL Foundation", созданная для продвижения и поддержки PostgreSQL. Сайт фонда находится по адресу http://www.thepostgresqlfoundation.org/.

Спонсорская помощь на развитие PostgreSQL поступает как от частных лиц, так и от коммерческих компаний, которые:

принимают на работу членов PGDG оплачивают разработку каких-либо новых возможностей предоставляют услуги в виде хостинга или оплаты трафика поддерживают публичные мероприятия PGDG

Кроме того, некоторые разработки поддерживаются государственными фондами, например, Российский Фонд Фундаментальных Исследований.

Сводная таблица основных реляционных баз данных

За основу взяты данные из Wikipedia

Название

ASE

DB2

FireBird

InterBase

MS SQL

MySQL

Oracle

PostgreSQL

Название

ASE

DB2

FireBird

InterBase

MS SQL

MySQL

Oracle

PostgreSQL

ACID	Yes	Yes	Yes	Yes	Yes	Depends1	Yes	Yes
Referential integrity	Yes	Yes	Yes	Yes	Yes	Depends1	Yes	Yes
Transaction	Yes	Yes	Yes	Yes	Yes	Depends1	Yes	Yes
Unicode	Yes	Yes	Yes	Yes	Yes	Yes	Yes	Yes
Schema	Yes	Yes	Yes	Yes	Yes	No	Yes	Yes
Temporary table	No	Yes	No	Yes	Yes	No	Yes	Yes
View	Yes	Yes	Yes	Yes	Yes	No	Yes	Yes
Materialized view	No	Yes	No	No	No	No	Yes	No3
Expression index	No	No	No	No	No	No	Yes	Yes
Partial index	No	No	No	No	No	No	No	Yes
Inverted index	No	No	No	No	No	Yes	No	No
Bitmap index	No	Yes	No	No	No	No	Yes	No
Domain	No	No	Yes	Yes	No	No	Yes	Yes
Cursor	Yes	Yes	Yes	Yes	Yes	No	Yes	Yes
User Defined Functions	Yes	Yes	Yes	Yes	Yes	No4	Yes	Yes
Trigger	Yes	Yes	Yes	Yes	Yes	No4	Yes	Yes
Stored procedure	Yes	Yes	Yes	Yes	Yes	No4	Yes	Yes
Tablespace	Yes	Yes	No	?	Yes	No1	Yes	Yes

Замечания:

1 - для поддержки транзакций и ссылочной целостности требуется InnoDB (не является типом таблицы по умолчанию) 3 - Materialized view могут быть эмулированы на PL/pgSQL 4 - только в MySQL 5.0, которая является экспериментальной версией

реляционной СУБД, готовой для практического

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