Интернет, компьютеры, софт и прочий Hi-Tech

SQLite: расширения FTS3 и FTS4

Содержание

1. Введение в FTS3 и FTS4
   1. Различия между FTS3 и FTS4
   2. Создание и удаление таблиц FTS
   3. Заполнение таблиц FTS
   4. Простейшие FTS-запросы
   5. Резюме
2. Компиляция и включение FTS3 и FTS4
3. Запросы с использованием полнотекстового индекса
   1. Набор операций в расширенном языке запросов
   2. Набор операций в стандартном языке запросов
4. Вспомогательные функции — Snippet, Offsets и Matchinfo
   1. Функция Offsets
   2. Функция Snippet
   3. Функция Matchinfo
5. Токенайзеры
   1. Кастомные токенайзеры (реализуемые пользователями)
6. Структуры данных
   1. Формат целых чисел переменного размера (varint)
   2. Формат сегмента B-дерева
      1. Листовые вершины сегмента B-дерева
      2. Внутренние узлы сегмента B-дерева
   3. Формат Doclist
7. Приложение A: Советы по разработке приложений поиска

Предисловие

FTS3 и FTS4 — это модули виртуальных таблиц SQLite, которые позволяют пользователям выполнять полнотекстовый поиск на множестве документов. Наиболее общий (и эффективный) способ описать полнотекстовый поиск — следующий: "То, что делают Google, Yahoo и Altavista с документами, находящимися во всемирной сети". Пользователь вводит слово или набор слов, возможно соединённые бинарным оператором или сгруппированные во фразу, и система полнотекстового поиска находит множество документов, которые наилучшим образом соответствуют введенным словам с учетом операторов и группировок, заданных пользователем. Эта статья описывает установку и использование FTS3 и FTS4.

FTS1 и FTS2 являются устаревшими модулями полнотекстового поиска для SQLite. Существуют известные проблемы с этими старыми модулями и их использования следует избегать. Часть первоначального кода FTS3 была предоставлена проекту SQLite Скоттом Хессом (Scott Hess) из Google. С тех пор этот модуль разрабатывается и распространяется как часть SQLite.

1. Введение в FTS3 и FTS4

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

Например, вставим каждый из 517430 документов "Энроновской коллекции E-Mail" в таблицу FTS и в обычную таблицу SQLite, созданные следующим скриптом SQL:

CREATE VIRTUAL TABLE enrondata1 USING fts3(content TEXT);  /* таблица FTS3 */
CREATE TABLE enrondata2(content TEXT);                     /* обычная таблица */

Затем выполним следующие два запроса для поиска в базе данных числа документов (351), содержащих слово "linux". В проведённом авторами эксперименте на одном и том же настольном компьютере запрос к таблице FTS отработал примерно за 0.03 секунды против 22.5 секунд для обычной таблицы:

SELECT count(*) FROM enrondata1 WHERE content MATCH 'linux';  /* 0.03 секунды */
SELECT count(*) FROM enrondata2 WHERE content LIKE '%linux%'; /* 22.5 секунды */

Конечно, два вышеприведённых запроса в целом неэквивалентны. Например, запрос LIKE находит также строки, которые содержат такие термины как "linuxophobe" или "EnterpriseLinux". В нашем случае этого не происходит только потому, что Энроновская коллекция E-Mail не содержит таких термов. А запрос MATCH на таблице FTS3 выбирает только те строки, которые содержат "linux" как отдельный токен. Оба поиска регистронезависимы. Таблица FTS3 занимает 2006 MB дискового пространства, а обычная таблица — 1453 MB. На том же самом компьютере, на котором тестировались запросы SELECT, таблица FTS3 заполнялась данными 31 минуту, тогда как обычная таблица — 25 минут.

1.1. Различия между FTS3 и FTS4

FTS3 и FTS4 почти идентичны. Они делят друг с другом большую часть своего кода и имеют одинаковые интерфейсы. Но имеют следующие различия:

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

• FTS4 поддерживает некоторые дополнительные опции, которые могут быть использованы с функцией matchinfo().

• Поскольку вся дополнительная информация для повышения производительности и для дополнительных опций matchinfo() сохраняется на диске в двух новых скрытых таблицах, таблицы FTS4 требуют больше дискового пространства, чем эквивалентные таблицы, созданные с помощью FTS3. Это превышение обычно составляет 1-2% или меньше, но если документы очень малы, то превышение может оказаться и больше 10%. Чтобы уменьшить это превышение, можно воспользоваться директивой "matchinfo=fts3" при декларации таблицы FTS4, но при этом придется пожертвовать некоторыми дополнительными опциями matchinfo().

FTS4 является усовершенствованным FTS3. FTS3 доступен в SQLite начиная с версии 3.5.0, вышедшей 04.09.2007. Усовершенствованный FTS4 был добавлен в SQLite версии 3.7.4 от 08.12.2010.

Какой из модулей, FTS3 или FTS4, следует использовать в своем приложении? FTS4 иногда работает значительно быстрее чем FTS3. Для некоторых запросов даже на несколько порядков быстрее, хотя в общем случае производительность этих двух модулей аналогична. Кроме того FTS4 поддерживает усовершенствованный вывод для matchinfo(), который может быть использован для ранжирования результатов поиска с помощью оператора MATCH. С другой стороны, при отсутствии директивы matchinfo=fts3 модуль FTS4 требует несколько больше дискового пространства, чем FTS3, хотя в большинстве случаев это превышение составляет не более двух процентов.

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

1.2. Создание и удаление таблиц FTS

Подобно другим типам виртуальных таблиц, новые таблицы FTS создаются с помощью запроса CREATE VIRTUAL TABLE. Имя модуля, следующее после ключевого слова USING, должно быть "fts3" или "fts4". Аргументы модуля виртуальной таблицы могут не указываться. В этом случае будет создана таблица FTS с единственным определенным пользователем столбцом по имени "content". Вместо этого в аргументах можно указать список разделенных запятыми имен столбцов.

Если имена столбцов таблицы FTS явно перечислены в выражении CREATE VIRTUAL TABLE, то для каждого столбца можно опционально указать его тип данных. Но следует знать, что такое указание является не более чем синтаксической плюшкой, поскольку ни FTS, ни ядро SQLite никак не будет использовать эти объявления типов. Никакие ограничения, сопоставляемые именам столбцов FTS, не используются системой хотя и корректно парсятся.

-- Создаем таблицу FTS с названием "data" и одним столбцом — "content":
CREATE VIRTUAL TABLE data USING fts3();

-- Создаем таблицу FTS с названием "pages" и тремя столбцами:
CREATE VIRTUAL TABLE pages USING fts4(title, keywords, body);

-- Создаем таблицу FTS с названием "mail" и двумя столбцами.
-- Для каждого столбца указываем тип данных и ограничения,
-- которые полностью игнорируются FTS и SQLite.
CREATE VIRTUAL TABLE mail USING fts3(
  subject VARCHAR(256) NOT NULL,
  body TEXT CHECK(length(body)<10240)
);

Так же как список столбцов, в качестве аргументов модуля в запросе "CREATE VIRTUAL TABLE" при создании таблицы FTS можно указать используемый токенайзер. Это делается указанием строки в форме "tokenize=<tokenizer name> <tokenizer args>" в ряду имен столбцов. Здесь <tokenizer name> является именем используемого токенайзера, а <tokenizer args> — опциональный список разделенных пробелами спецификаторов, предусмотренных реализацией токенайзера. Объявление токенайзера может быть помещено где угодно в списке столбцов, но для каждого "CREATE VIRTUAL TABLE" можно указать только один токенайзер. Детальное описание использования и (если нужно) реализации токенайзеров можно прочесть ниже.

-- Создаем таблицу FTS с названием "papers" и двумя столбцами,
-- которые используют токенайзер "porter".
CREATE VIRTUAL TABLE papers USING fts3(author, document, tokenize=porter);

-- Создаем таблицу FTS с единственным столбцом — "content",
-- который использует токенайзер "simple".
CREATE VIRTUAL TABLE data USING fts4(tokenize=simple);

-- Создаем таблицу FTS с двумя столбцами, которые используют токенайзер
-- "icu". Спецификатор "en_AU" указывает на локализацию токенайзера.
CREATE VIRTUAL TABLE names USING fts3(a, b, tokenize=icu en_AU);

Если в запросе "CREATE VIRTUAL TABLE" указан модуль FTS4 (а не FTS3), то можно указать также специальную директиву "matchinfo=fts3" в ряду имен столбцов. Если это сделано, то некоторая дополнительная информация, сохраняемая в FTS4, будет опущена. Это приведет к уменьшению дискового пространства, занятого под таблицу FTS4 до размера, который имеет эквивалентная таблица FTS3. Однако при этом станут недоступными данные, которая выдавала бы функция matchinfo() при задании для нее флага 'l'. Например:

-- Создаем таблицу FTS4 экономя дисковое пространство.
CREATE VIRTUAL TABLE papers USING fts4(author, document, matchinfo=fts3);

При использовании FTS4 указание имени столбца, содержащего символ "=" и не совпадающего с директивами "tokenize=*" или "matchinfo=fts3", является ошибкой. В FTS3 первый токен нераспознанной директивы интерпретируется как имя столбца. По этой причине указание нескольких директив "tokenize=*" для одной таблицы является ошибкой при использовании FTS4, тогда как в FTS3 вторая директива "tokenize=*" будет интерпретирована как имя столбца. Примеры:

-- Ошибка. FTS4 не понимает директиву "xyz=abc".
CREATE VIRTUAL TABLE papers USING fts4(author, document, xyz=abc);

-- Создаем таблицу FTS3 с тремя столбцами —
-- "author", "document" и "xyz".
CREATE VIRTUAL TABLE papers USING fts3(author, document, xyz=abc);

-- Ошибка. FTS4 не разрешает несколько директив "tokenize=*"
CREATE VIRTUAL TABLE papers USING fts4(tokenize=porter, tokenize=simple);

-- Создаем таблицу FTS3 с единственным столбцом под названием "tokenize".
-- Таблица использует токенайзер "porter".
CREATE VIRTUAL TABLE papers USING fts3(tokenize=porter, tokenize=simple);

-- Ошибка. Нельзя создавать два столбца с названием "tokenize".
CREATE VIRTUAL TABLE papers USING fts3(tokenize=porter, tokenize=simple, tokenize=icu);

Таблицы FTS могут удаляться из базы данных с помощью обычного запроса DROP TABLE. Например:

-- Создаем и сразу уничтожаем таблицу FTS4.
CREATE VIRTUAL TABLE data USING fts4();
DROP TABLE data;

1.3. Заполнение таблиц FTS

Таблицы FTS заполняются и редактируются с помощью запросов INSERT, UPDATE и DELETE так же как и обычные таблицы SQLite.

Вместе с заданными пользователем столбцами (или со столбцом "content", если в выражении CREATE VIRTUAL TABLE не было указано никаких аргументов модуля) каждая таблица FTS имеет столбец "rowid". Этот rowid для таблиц FTS ведет себя практически так же, как столбец rowid в обычной таблице SQLite за исключением того, что значения, сохраняемые в rowid таблицы FTS, остаются неизменными при выполнении над базой данных команды VACUUM. В таблицах FTS этот столбец доступен также по алиасу "docid" вместе с обычными алиасами "rowid", "oid" и "_oid_". Попытка вставить строку с уже существующим в таблице docid или изменить docid строки на docid другой существующей строки является ошибкой, как и в случае с обычной таблицей SQLite.

Существует одно тонкое отличие "docid" от обычных алиасов SQLite для столбца rowid. Как правило, если запросы INSERT или UPDATE назначают разные значения двум или более алиасам столбца rowid, SQLite сохраняет в базе самое правое из этих значений, в порядке их вождения в запросы INSERT или UPDATE. Однако, когда запись вставляется в таблицу FTS или когда она изменяется, попытка одновременно назначить не-NULL значение столбцу "docid" и какому-то другому алиасу столбца rowid принимается за ошибку. Это иллюстрируется ниже:

-- Создать таблицу FTS
CREATE VIRTUAL TABLE pages USING fts4(title, body);

-- Вставляем строку с указаннием значения docid.
INSERT INTO pages(docid, title, body) VALUES(53, 'Главная', 'SQLite — это...');

-- Вставляем строку и позволяем FTS назначить значение docid с
-- использованием того же алгоритма, который SQLite применяет для обычных
-- таблиц. В этом случае новый docid будет иметь значение 54, т.е. на единицу
-- больше, чем наибольший docid, существующий в таблице на момент запроса.
INSERT INTO pages(title, body) VALUES('Скачать', 'Весь исходный код SQLite...');

-- Изменяем title только что добавленной строки.
UPDATE pages SET title = 'Скачать SQLite' WHERE rowid = 54;

-- Удаляем все содержимое таблицы.
DELETE FROM pages;

-- Следующий код приведет к ошибке. Для таблиц FTS нельзя указывать
-- различные не-NULL значения для обоих полей — rowid и docid.
INSERT INTO pages(rowid, docid, title, body) VALUES(1, 2, 'Заголовок', 'Документ');

Для поддержки полнотекстового поиска FTS создает инвертированный индекс, которые назначает каждому уникальному терму или слову, которое встречается в наборе данных, карту его расположения в содержимом таблицы. Если интересно, можете ознакомиться с полным описанием структуры данных, используемой для хранения этого индекса в файле базы данных. Особенностью этой структуры данных является то, что база данных может содержать не одно индексное b-дерево, а несколько различных b-деревьев, которые постепенно сливаются по мере вставки, редактирования и удаления строк. Эта техника улучшает производительность при записи в таблицу FTS, но приводит к некоторым накладкам при использовании индекса в полнотекстовых запросах. Выполнение SQL-запроса в форме "INSERT INTO <fts-table>(<fts-table>) VALUES('optimize')" заставит FTS объединить все индексные b-деревья в одно большое b-дерево, содержащее весь индекс. Эта операция может оказаться дорогостоящей в смысле вычислительных ресурсов, но повысит скорость выполнения запросов.

Вот так, например, оптимизируется полнотекстовый индекс для FTS-таблицы под названием "docs":

-- Оптимизация внутренней структуры FTS-таблицы "docs".
INSERT INTO docs(docs) VALUES('optimize');

Вышеприведённый запрос может показаться синтаксически неправильным. Разъяснения можно прочитать в следующем разделе "Простые запросы FTS".

Существует также другой, нежелательный метод вызова операции оптимизации с помощью запроса SELECT. Но в новом коде для оптимизации FTS следует использовать запросы, аналогичные вышеприведённому INSERT.

1.4. Простейшие FTS-запросы

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

Таблицы FTS могут эффективно запрашиваться с использованием выражений SELECT двух различных форм:

• Запрос по rowid. Если выражение WHERE запроса SELECT содержит подвыражение в форме "rowid = ?", где ? является каким-то условием SQL, то FTS может быстро отыскать требуемую строку с использованием индекса, эквивалентного индексу INTEGER PRIMARY KEY в SQLite.

• Полнотекстовый поиск. Если выражение WHERE запроса SELECT содержит подвыражение в форме "<column> MATCH ?", то FTS будет использовать заранее созданный полнотекстовый индекс для нахождения документов, которые удовлетворяют строке полнотекстового запроса, находящейся в правой части выражения MATCH.

Если в запросе нельзя использовать ни одну из этих стратегий, то запрос на таблице FTS будет выполнен с использованием полного сканирования содержимого таблицы. Если таблица содержит большое количество данных, это может оказаться непрактичным подходом. В первом примере этого руководства демонстрировалось, что на современном ПК линейное сканирование 1.5 ГБ данных выполнялось около 30 секунд.

-- В примерах этого блока используется следующая таблица FTS:
CREATE VIRTUAL TABLE mail USING fts3(subject, body);

-- Быстро. Запрос по rowid.
SELECT * FROM mail WHERE rowid = 15;

-- Быстро. Полнотекстовый запрос.
SELECT * FROM mail WHERE body MATCH 'sqlite';

-- Быстро. Полнотекстовый запрос.
SELECT * FROM mail WHERE mail MATCH 'search';

-- Медленно. Полное сканирование.
SELECT * FROM mail WHERE rowid BETWEEN 15 AND 20;

-- Медленно. Полное сканирование.
SELECT * FROM mail WHERE subject = 'database';

-- Быстро. Полнотекстовый запрос.
SELECT * FROM mail WHERE subject MATCH 'database';

Все вышеприведённые полнотекстовые запросы имеют в правой части оператора MATCH строку из единственного терма. В этом случае выражение MATCH оценивает как true все документы, которые имеют одно или более вхождений указанного слова (в приведённых нами примерах это "sqlite", "search" или "database"). Указание единственного терма в правой части оператора MATCH — это простейший и наиболее общий тип всех полнотекстовых запросов. Однако возможны и более сложные запросы, включающие поиск фраз, поиск термов с указанным префиксом и поиск документов, содержащих комбинации термов в нужной близости друг от друга. Различные варианты запросов по полнотекстовому индексу описываются ниже.

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

Абзацем выше было замечено, что оператор MATCH с простым термом в правой части принимает значение true на всех документах, которые содержат этот терм. В данном контексте под "документом" могут пониматься данные, сохранённые в единственном поле любой строки таблицы FTS, или содержимое всех полей в зависимости от того, что указано в левой части оператора MATCH. Если имя, указанное в левой части оператора MATCH, является именем столбца таблицы FTS, то под документом, в котором ищется данный терм, понимается значение, сохранённое в указанном столбце. Однако, если слева от MATCH указано имя самой таблицы FTS, то этот оператор будет принимать true для тех строк таблицы FTS, которые содержат искомый терм в любом из столбцов. Это демонстрирует следующий пример:

-- Схема примера
CREATE VIRTUAL TABLE mail USING fts3(subject, body);

-- Заполняем таблицу примера
INSERT INTO mail(docid, subject, body)
       VALUES(1, 'software feedback', 'found it too slow');
INSERT INTO mail(docid, subject, body)
       VALUES(2, 'software feedback', 'no feedback');
INSERT INTO mail(docid, subject, body)
       VALUES(3, 'slow lunch order',  'was a software problem');

-- Примеры запросов
-- Будут выбраны строки 1 и 2
SELECT * FROM mail WHERE subject MATCH 'software';

-- Будет выбрана строка 2
SELECT * FROM mail WHERE body    MATCH 'feedback';

-- Будут выбраны строки 1, 2 и 3
SELECT * FROM mail WHERE mail    MATCH 'software';

-- Будут выбраны строки 1 и 3
SELECT * FROM mail WHERE mail    MATCH 'slow';

На первый взгляд, последние два полнотекстовых запроса этого примера являются синтаксически некорректными из-за той позиции в SQL-выражении, в которой используется имя таблицы ("mail"). Однако это допустимо по той причине, что таблица FTS действительно имеет скрытый (HIDDEN) столбец с тем же самым именем, что и сама таблица (в нашем случае "mail"). Значения, хранящиеся в этом столбце, не являются осмысленными для поискового приложения, но могут быть использованы в качестве правого операнда для оператора MATCH. Этот специальный столбец может использоваться также и как аргумент для вспомогательных функций FTS.

Следующий пример иллюстрирует сказанное выше. Все выражения "docs", "docs.docs" и "main.docs.docs" ссылаются на столбец "docs". Однако выражение "main.docs" не ссылается на какой-то из столбцов. Оно может использоваться только для ссылки на таблицу, но в данном контексте не разрешается ссылаться на имя таблицы.

-- Схема примера
CREATE VIRTUAL TABLE docs USING fts4(content);

-- Примеры запросов
SELECT * FROM docs WHERE docs MATCH 'sqlite';           -- Правильно.
SELECT * FROM docs WHERE docs.docs MATCH 'sqlite';      -- Правильно.
SELECT * FROM docs WHERE main.docs.docs MATCH 'sqlite'; -- Правильно.
SELECT * FROM docs WHERE main.docs MATCH 'sqlite';      -- Ошибка.

1.5. Резюме

С точки зрения пользователя таблицы FTS во многом похожи на обычные таблицы SQLite. Данные в таблицах FTS могут добавляться, редактироваться и удаляться с использованием команд INSERT, UPDATE и DELETE также как для обычных таблиц. Аналогично, для запроса данных можно использовать команду SELECT. В следующий список сведены различия между FTS и обычными таблицами:

1. Как и для других типов виртуальных таблиц, для таблиц FTS невозможно создавать индексы и триггеры. Также невозможно использовать команду ALTER TABLE для создания дополнительных столбцов в таблицах FTS, хотя можно использовать ALTER TABLE для переименования таблицы FTS.

2. Типы данных, указанные в запросе "CREATE VIRTUAL TABLE" при создании таблицы FTS, полностью игнорируются. Вместо обычных правил по применению аффинированных типов к сохраняемым значениям, все значения, сохраняемые в столбцах таблиц FTS (за исключением специального столбца rowid) конвертируются перед сохранением в тип TEXT.

3. Таблицы FTS позволяют использовать специальный алиас "docid" для обращения к столбцу rowid, поддерживаемому для всех виртуальных таблиц.

4. Для запросов с использованием встроенного полнотекстового индекса поддерживается оператор FTS MATCH.

5. Для использования в полнотекстовых запросах доступны вспомогательные функции FTS snippet(), offsets() и matchinfo().

6. Каждая таблица FTS имеет скрытый столбец с тем же именем, что и сама таблица. Значения, сохраняемые в скрытом столбце, имеют тип BLOB. Этот столбец может использоваться только в качестве левого операнда оператора MATCH или в качестве самого левого аргумента для вспомогательных функций FTS.

Перевод Дмитрия Скоробогатова, 01.06.2011
Оригинальный текст может быть найден по адресу http://www.sqlite.org/fts3.html

Предыдущие публикации:

Последнее редактирование: 2011-06-02 20:19:09

Метки материала: sqlite, fts3, fts4, базы данных, программирование, разработка по, db, sql, алгоритмы поисковых систем

Оставьте, пожалуйста, свой комментарий к публикации

Представиться как

Антибот:

Просьба не постить мусор. Если вы хотите потестить xBB, воспользуйтесь кнопкой предварительного просмотра на панели инструментов xBBEditor-а.