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

Подписаться через RSS2Email.ru

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

SQLite

Содержание

  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: Советы по разработке приложений поиска

6. Структуры данных

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

Для каждой виртуальной таблицы FTS в базе данных создается от трех до пяти реальных (невиртуальных) таблиц для хранения данных и индекса. Эти реальные таблицы называются "скрытыми таблицами". Они имеют следующие названия: "%_content", "%_segdir", "%_segments", "%_stat" и "%_docsize", где вместо "%" следует подставлять имя виртуальной таблицы FTS.

Самый левый столбец таблицы %_content является INTEGER PRIMARY KEY и называется "docid". За ним идут столбцы, соответствующие столбцам виртуальной таблицы FTS, в том порядке, в каком они были декларированы пользователем. Их названия составляются из названий столбцов виртуальной таблицы с предшествующими им строками "cN", где N — это индекс столбца виртуальной таблицы. Нумерация ведется слева направо и начинается с 0. Типы данных, заявленные в декларации виртуальной таблицы не используются при декларации таблицы "%_content". Например:

-- Объявление виртуальной таблицы
CREATE VIRTUAL TABLE abc USING fts4(a NUMBER, b TEXT, c);

-- Соответствующее объявление таблицы %_content
CREATE TABLE abc_content(docid INTEGER PRIMARY KEY, c0a, c1b, c2c);

Таблица %_content содержит данные, введенные пользователем в виртуальную таблицу FTS в неизменном виде. Если пользователь не указывал значение "docid" явно при вставке записей, оно будет автоматически назначаться системой.

Таблицы %_stat и %_docsize создаются только для таблиц FTS, использующих модуль FTS4 а не FTS3. Кроме того, таблица %_docsize не создается, если таблица FTS4 создавалась с указанием директивы "matchinfo=fts3" в запросе CREATE VIRTUAL TABLE. Если же эти таблицы создаются, то их схемы являются следующими:

CREATE TABLE %_stat(
  id INTEGER PRIMARY KEY,
  value BLOB
);

CREATE TABLE %_docsize(
  docid INTEGER PRIMARY KEY,
  size BLOB
);

Для каждой строки таблицы FTS таблица %_docsize содержит соответствующую строку с тем же значением docid. Поле "size" этой строки содержит BLOB, состоящий из N целых чисел переменной длины (в формате varint), где N — это число объявленных пользователем столбцов виртуальной таблицы. Каждое число типа varint, хранящееся в поле "size", является числом токенов в соответствующем столбце ассоциированной строки из таблицы FTS. Таблица %_stat всегда содержит единственную строку, в которой значение столбца "id" установлено в 0. Столбец "value" этой строки содержит BLOB, состоящий из N+1 чисел типа varint, где N — также число объявленных пользователем столбцов таблицы FTS. Первое из этих чисел является числом всех строк в таблице FTS. Второе и каждое последующие число типа varint является общим числом всех токенов, хранящихся в соответствующем столбце всех строк таблицы FTS.

Для хранения полнотекстового индекса используются две таблицы: "%_segments" и "%_segdir". Концептуально, этот индекс предназначен для поиска по таблице и является картой, которая сопоставляет каждому терму (слову) набор значений docid, соответствующих записям в таблице "%_content", которые содержат одно или более вхождений этого терма. Для отыскания всех документов, содержащих нужный терм, модуль FTS запрашивает этот индекс для определения набора docid этих документов, хранящихся в таблице "%_content". Независимо от схемы виртуальной таблицы FTS, таблицы "%_segments" и "%_segdir" создаются как указано ниже:

CREATE TABLE %_segments(
  blockid INTEGER PRIMARY KEY, -- идентификатор узла B-дерева
  block blob                   -- данные узла B-дерева
);

CREATE TABLE %_segdir(
  level INTEGER,
  idx INTEGER,
  start_block INTEGER,      -- blockid первого узла в %_segments
  leaves_end_block INTEGER, -- blockid последнего узла-листа в %_segments
  end_block INTEGER,        -- blockid последнего узла в %_segments
  root BLOB,                -- Корневой узел B-дерева
  PRIMARY KEY(level, idx)
);

Показанная выше схема не предназначена для непосредственного хранения полнотекстового индекса. Вместо этого она используется для одной или более структур b-дерева. Для каждой строки таблицы %_segdir существует одно b-дерево. Строка таблицы %_segdir содержит корневой узел и различные метаданные, соответствующие определенной структуре b-дерева, а таблица %_segments содержит все остальные (не-корневые) узлы b-дерева. Каждое b-дерево распадается на "сегменты". Будучи однажды созданным сегмент b-дерева никогда не изменяется (хотя может быть полностью удален).

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

  • Идентификатора документа — docid, и
  • Списка смещений терма — по одному смещению для каждого вхождения терма в данный документ. Смещение терма указывает число токенов (слов) которые расположены перед данным термом. Оно не указывает числа символов или байтов. Например, смещение терма "war" во фразе "Ancestral voices prophesying war!" есть 3.

Составные части doclist сортируются по docid. Внутри doclist их позиции также следуют в возрастающем порядке.

Содержимое логического полнотекстового индекса является объединением содержимого всех сегментов b-деревьев. Если терм представлен более чем в одном сегменте b-дерева, то карта его расположения составляется объединением всех его отдельных doclist-ов. Если для какого-то терма один и тот же docid находится в нескольких doclist-ах, то правильным будет считаться только тот doclist, который является частью более молодого сегмента b-дерева (т.е. созданного позже).

Множество структур b-дерева используется взамен единственного b-дерева для уменьшения стоимости вставки записей в таблицы FTS. Если новая запись вставляется в таблицу FTS, уже содержащую какие-то данные, то некоторые ее термы, возможно, уже представлены в большом числе ранее добавленных записей. При использовании единственного b-дерева из базы данных нужно извлечь множество doclist-ов, изменить их для добавления нового docid и списка смещений термов, а затем записать все это обратно в базу данных. Использование нескольких b-деревьев позволяет избежать этого посредством создания нового b-дерева, которое затем может быть объединено с другим существующим b-деревом (b-деревьями). Объединение структур b-деревьев может осуществляться как фоновая задача или один раз после накопления скольких-то отдельных структур b-деревьев. Конечно, это делает запросы более затратными, поскольку коду FTS придется искать каждый терм в более чем одном b-дереве, а потом еще и объединять результаты, однако на практике эти накладки являются очень незначительными.

6.1. Формат целых чисел переменного размера (varint)

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

Числа, кодированные как FTS varint, занимают от одного до десяти байт. Число необходимых байтов определяется знаком и величиной кодируемого целочисленного значения. Более точно, число байтов, используемых для хранения кодированного целого, зависит от позиции наибольшего значащего набора битов в 64-битном дополняемом до двойки представлении целочисленного значения. Отрицательные значения также имеют наибольший значащий набор битов (знаковый разряд) и потому всегда сохраняются с использованием всех десяти байтов. Положительные целочисленные значения могут сохраняться с использованием меньшего пространства.

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

ДесятичноеШестнадцатеричноеКодированное представление
430x000000000000002B0x2B
2008150x000000000003106F0x9C 0xA0 0x0C
-1 0xFFFFFFFFFFFFFFFF 0xFF 0xFF 0xFF 0xFF 0xFF 0xFF 0xFF 0xFF 0xFF 0x01

6.2. Формат сегмента B-дерева

Сегмент b-дерева — это b+-дерево с префиксным сжатием. Для каждой строки таблицы %_segdir (смотрите выше) существует один сегмент b-дерева. Корневой узел сегмента b-дерева сохраняется как BLOB в поле "root" соответствующей строки таблицы %_segdir. Все остальные узлы (если они существуют) сохраняются в столбце "blob" таблицы %_segments. Узлы из таблицы %_segments имеют целочисленные идентификаторы, сохраняемые в поле blockid соответствующих строк. Следующая таблица описывает поля таблицы %_segdir:

СтолбецИнтерпретация
level Содержимое полей "level" и "idx" определяет относительный возраст сегмента b-дерева. Наименьшее значение в поле "level" соответствует тем сегментам b-дерева, которые были созданы позже. Если два сегмента b-дерева имеют одинаковый "level", то сегмент с большим значением "idx" является более молодым. Ограничение PRIMARY KEY на таблице %_segdir предохраняет от того, чтобы два сегмента имели одинаковые значения для обоих полей "level" и "idx".
idxСмотрите выше.
start_block blockid, который соответствует узлу с наименьшим blockid, принадлежащему данному сегменту b-дерева. Либо ноль, если внутренний сегмент соответствует корневому узлу. Если не ноль, то данный узел обязательно является листовым узлом.
leaves_end_block Идентификатор блока (blockid), который соответствует листовой ноде с наибольшим blockid, принадлежащей этому сегменту b-дерева. Либо ноль, если весь сегмент b-дерева соответствует корневому узлу.
end_block blockid, соответствующий внутреннему узлу с наибольшим blockid, который принадлежит данному сегменту b-дерева. Либо ноль, если внутренний сегмент b-дерева соответствует корневому узлу. Если не ноль, то данный узел обязательно является внутренним узлом.
root Бинарное значение, содержащее корневой узел сегмента b-дерева.

Те узлы, помимо корневого узла, которые составляют единственный сегмент b-дерева, всегда сохраняются с использованием последовательных blockid. Кроме того, узлы, которые составляют единственный уровень b-дерева, сохраняются как смежные блоки в порядке обхода b-дерева. Непрерывная последовательность blockid, используемая для сохранения листьев b-дерева, начинается со значения столбца "start_block", соответствующего строке %_segdir, и заканчивается значением поля "leaves_end_block" для той же строки. Это делает возможной итерацию по всем листам сегмента b-дерева в порядке их ключей от "start_block" до "leaves_end_block".

6.2.1. Листовые вершины сегмента B-дерева

Следующая схема объясняет формат листового узла сегмента b-дерева.

Формат листового узла сегмента B-дерева

Формат листового узла сегмента B-дерева

Первый терм, сохраняемый в каждом узле ("Term 1" на рисунке выше) сохраняется буквально. Каждый последующий терм подвергается префиксному сжатию (prefix-compressed) по отношению к своего предшественнику. Термы на странице сохраняются в отсортированном с помощью memcmp виде.

6.2.2. Внутренние узлы сегмента B-дерева

Следующая схема объясняет формат внутреннего (не листового) узла сегмента b-дерева.

Формат внутреннего узла сегмента B-дерева

Формат внутреннего узла сегмента B-дерева

6.3. Формат Doclist

Doclist содержит массив 64-битных знаковых целых, сериализованных с применением формата FTS для целых переменного размера (varint). Каждый экземпляр Doclist создается как последовательность двух или более целых чисел, как это показано ниже:

  1. Значение docid. При первом вхождении в Doclist сохраняется полное значение docid. Первое поле каждого следующего экземпляра Doclist содержит разницу между новым docid и предыдущим к нему (всегда положительное число).
  2. Ноль или больше списков смещений термов. Список смещений термов составляется для каждого столбца виртуальной таблицы FTS, содержащего терм. Список смещений термов состоит из следующего:
    1. Фиксированное значение 1. Это поле пропускается для всех списков смещений термов, ассоциированных со столбцом 0.
    2. Номер столбца (1 для второго слева столбца и т.д.). Это поле опускается для любых списков смещений термов, соответствующих столбцу 0.
    3. Список смещений термов сортируется от наименьшего к наибольшему. Вместо сохранения полных значений смещений термов сохраняются только целочисленная разница между текущим смещением терма и предыдущим к нему (или ноль, если текущее смещение терма является первым) плюс 2.
  3. Фиксированное значение 0.
Формат Doclist в FTS3

Формат Doclist в FTS3

Формат ввода Doclist в FTS

Формат ввода Doclist в FTS

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


Назад Вперед
5. Токенайзеры Приложение A: Советы по разработке приложений поиска

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


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

Биржа долевых инвестиций SIMEX.

Последнее редактирование: 2011-06-04 04:05:44

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

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

Представиться как     Антибот:
   

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


© 2007-2017, Дмитрий Скоробогатов.
Разрешается воспроизводить, распространять и/или изменять материалы сайта
в соответствии с условиями GNU Free Documentation License,
версии 1.2 или любой более поздней версии, опубликованной FSF,
если только иное не указано в самих материалах.