GrAndSE's blog

Повнотекстовий пошук в PostgreSQL

На багатьох інформаційних інтернет ресурсах дуже часто можна побачити форму для пошуку сайтом. В більшості випадків такі системи пошуку є дуже обмеженими. Обмеженими в силу тих інструментів, які для його організації використовуються. Я кажу про СУБД MySQL та запити типу "like". Такий підхід дозволяє за пошуковим запитом сформувати шаблон, і кожен запит в БД перевіряється на відповідність цьому шаблону. Недоліками такого підходу є швибкодія, відсутність можливостей для ранжування результатів пошукового запиту, проблеми з гнучкістю побудови запитів та ігнорування правил морфології. Наприклад, за словом "стаття" як результат повернено буде лише матеріали, що включають це слово повністю і в тому вигляді, в якому воно й було введено.

Звичайно можна вигадувати обхідні шляхи для подолання таких проблем "like-пошуку". Наприклад, обробляти рядок пошуку якимось алгоритмом стемінгу з метою виділення можливих коренів слів і використовувати для пошуку ці корені. А щоб пошукати за декількома словами додамо до пошукового запиту для кожного додаткового слова "AND like" і т.д.

Однак це не вихід

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

Повнотекстовий пошук

Для реалізації більш повноцінного пошуку можна та рекомендовано використовувати алгоритми повнотекстового пошуку. Головна ідея такого пошуку полагає в тому, що замість like використовуються інші способи порівняння, що працюють не зі звичайними текстовими полями, а зі спеціальним чином побудованими індексованими деревами пошуку, що звичайно ж дає кращі показники швидкодії. У випадку, коли дерево добре спроектоване, додаткова логіка в самому запиті (зібльшення кількості слів, OR, дужки, що змінюють порядок виконання операцій) значно менше впливають на швидкість виконання запиту.

Під час пошуку в базі даних можна також обраховувати ступінь відповідності запиту до кожного матеріалу, оскільки індекси зберігають і кількість входжень кожного слова і положення входжень слів у текст. Тобто вирішується ще одна проблема.

Що до боротьби з "різноманітністю форм слів", то якщо раніше системи повнотекстового пошуку самі базувались на різноманітних стемерах, то тепер кожна така система має можливість працювати зі словниками, що враховують правила словотворення та виключення. А такі потужні комерційні системи як Oracle на основі таких словників можуть виконувати навіть багатомовний пошук.

Що добре для розробника, вся логіка побудови дерев, морфологія, оцінки релевантності і вже є в самій бд. Тобто відпадає необхідність написання складного аналізатора отриманих від користувача даних, на основі яких буде побудовано запит до БД та аналізатора результатів відповідей БД, щоб отримати якусь додаткову інформацію про результати (наприклад ступінь релевантності). Достатньо просто перевірки запиту від корситувача на SQL Injection та можливо заміни деяких слів (наприклад, AND та OR) на їх еквіваленти для системі запитів для двигунця повнотекстового пошуку, що використовується в запиті.

Якщо все так добре, то чому б не перейти до практики?

Перейдемо до PostgreSQL

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

Деталі можна почитати в офіційній документації. Ознайомитись корисно, однак необов'язково.

Спочатку потрібно встановити саму СУБД PostgreSQL. Наприклад, в Debian чи Ubuntu це можна викноати так:

<сode class=code-block> sudo apt-get install postgresql-8.3

Для Windows можна завантажити та інсталятор. Хоча моя подальша розповідь буде орієнтована на *nix системи, однак маючи достатнє бажання, аналогічні операції можна виконати і в Windows.

Оскільки для індексації документів та побудови внутрішніх запитів використовується система словників ispell, то для організації україномовного повнотекстового пошуку необхідно спочатку запавнтажити словники. Три роки тому, коли я тільки знайомився з PostgreSQL та tsearch2, знайти словники мені так просто не вдалось, а цього разу потрапив на велику зібрку словників ispell проекту OpenOffice. Також мені зустрічались інші редакції словників, що підтримуються окремими спільнотами, які якщо виникне бажання Ви можите легко відшукати.

Словник складається з двох файлів: dic та aff. Перший

Оскільки ці файли знаходяться в кодування kio8r, для використання в більшості *nix систем, словник треба перекодувати до utf-8, виконавши в консолі маючи права root:

iconv -f koi8-r -t utf-8 < uk_UA.aff > /usr/share/postgresql/8.3/tsearch_data/ukrainian.affix
iconv -f koi8-r -t utf-8 < uk_UA.dic > /usr/share/postgresql/8.3/tsearch_data/ukrainian.dict


Наведені команди орієнтовані на Debian та його нащадків. В інших системах може виникнути необхідність використовувати інші шляхи чи інше кодування. Так для Gentoo шлях буде: /usr/share/postgresql/8.3/tsearch_data/.

Окрім того, в PostgreSQL за замовчуванням відсутній словник стопслів для укаїнскої мови. Тому його можна взяти в мене та покласти в директорію разом з іншими словниками.

Тепер настав час увійти в якості адміністратора СУБД:

sudo -u postgres bash


Створимо користувача для управління СУБД та базу дуних для роботи:

createuser -DRSlP username
createdb -O username search


Тепер перейдемо в консоль для роботи з PostgreSQL:

psql search


Виконаэмл скрипт, для створення конфігурації tsearch2:

CREATE TEXT SEARCH DICTIONARY ukrainian_ispell (
TEMPLATE = ispell,
DictFile = ukrainian,
AffFile = ukrainian,
StopWords = ukrainian
);

CREATE TEXT SEARCH CONFIGURATION ua ( COPY = ukrainian );

CREATE TEXT SEARCH DICTIONARY english_ispell (
TEMPLATE = ispell,
DictFile = english,
AffFile = english,
StopWords = english
);

CREATE TEXT SEARCH CONFIGURATION ua ( COPY = ukrainian );

ALTER TEXT SEARCH CONFIGURATION ua ALTER MAPPING FOR hword, hword_part, word WITH ukrainian_ispell, ukrainia_stem;
ALTER TEXT SEARCH CONFIGURATION ua ALTER MAPPING FOR asciihword, asciiword, hword_asciipart WITH english_ispell, english_stem;


Тепер залишається використовувати за замовчуванням створену конфігурацію. В рамках сесії це можна виконати за допомогою:

SET default_text_search_config = 'ua';


А можна підти іншим шляхом, встановиши в конфігураційному файлі postgresql.conf (що знаходиться для Debian в /etc/postgresql/8.3/main/, для Gentoo в /var/lib/postgresql/data/postgresql.conf і т.д.):

default_text_search_config = 'ua'


Таким чином ми все підготували для використання.

Приклад використання

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

CREATE TABLE "index"
(
id bigserial NOT NULL,
url character varying(255) NOT NULL,
title character varying(255),
body text NOT NULL,
idxfti tsvector,
CONSTRAINT id PRIMARY KEY (id)
)
WITH (OIDS=TRUE);
ALTER TABLE "index" OWNER TO username;


Тут поле idxfti має тип tsvector, спеціально призначений для зберігання індексу. Побудова дерев можливо виконувати двома типами індексів GING та GIST. GIN - однозначний індекс, що випереджає GIST за швидкістю пошуку, однак має нижчу швидкість додавання. Особисто я використовую GIN, окільки мені критичнішою є швидкість пошуку а не додевання.

Тепер додамо трігер, що буде створювати індекс при додаванні елементу в таблицю:

CREATE TRIGGER index_update
BEFORE INSERT OR UPDATE
ON "index"
FOR EACH ROW
EXECUTE PROCEDURE tsvector_update_trigger('idxfti', 'pg_catalog.ukrainian', 'title', 'body');


Тепер при додаванні чи зміні елементу в таблиці звичайним запитом автоматично буде створювати індекс за полями body та title.

Щоб підготувати рядок пошуку для пошуку в полі виконаємо:

SELECT to_tsquery('ukrainian', 'робота&test&search') AS q;


Аналогом оператора порывняння поля-індексу є з вектором пошуку є оператор @@. Виберемо елементи, що відповідають нашому запиту:

SELECT
id, title
FROM
index, to_tsquery('ukrainian', 'робота&test&search') AS q
WHERE
(idxfti @@ q)


Для того, щоб знайти місце, що відповідає пошуковому рядку, використовується функція ts_headline:

SELECT
id, title, ts_headline(body, q) AS head
FROM
index, to_tsquery('ukrainian', 'робота&test&search') AS q
WHERE
(idxfti @@ q)


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

Залишається доадти останній штрих, а саме ранжування результатів. Зробимо це за допомогою функції ts_rank:

SELECT
id, title, ts_headline(body, q) AS head
FROM
index, to_tsquery('ukrainian', 'робота&test&search') AS q
WHERE
(idxfti @@ q)
ORDER BY ts_rank(idxfti, q) DESC


Все доволі просто і тривіально.

А в реузльтаті

Для більше ніж двох тисяч елементів реузльтат пошуку слова було повернено для повнотекстового пошуку за 215 мілісекунд (ранжування та обмеження кількості результатів не використовувалось), а для звичайного за 372 мілісекунд. При цьому для деяих запитів, коли традиційний пошук за шаблоном не повернув жодного результату, повнотекстовий пошук повертав декілька релевантних результатів. Тобто все працює і працює ефективно.

Звичайно ж, використання в реальних задача потребує розумної побудови системи та запитів і має ряд нюансів, до яких я спробую найближчим часом повернутись. Одник сам потенціал системи є достатнім для того щоб хоча б поглянути в її сторону, та ознайомитись з СУБД PostgreSQL.