Имеется задача обеспечение быстрого поиска в базе (interbase firebird 1.5), размер базы 0,8 ГБ
главная таблица по которой необходимо произвести поиск содержит около 500 тыс. записей.
Поиск нужно производить по полю типа текстовый BLOB, информация в котором сжата gzip-ом.
Размер текстовой информации в одном поле колеблется от 200 байт (в среднем) до 65 кб (максимум).

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

Мои варианты решения задачи:

1). Создание отдельного несжатого поля в которое будет хранить все слова в одном экземпляре,
содержащиеся в поле соодержащем контент. Затем поиск по этому поля простой функцией like '%фраза%'.

плюсы: неплохая скорость построения полного индекса (около 9 мин.) или 1 мс на одну запись
минусы: достаточнао медленная скорость поиска (т.к. приходится перебирать все записи ибо в interbase по блоб и большим текстовым полям индекса не построишь)
размер индекса около 400 мб.

2). Создание отдельной таблицы для индекса со структурой (WordName varchar(50),Data blob), где
WordName - уникальное слово
Data - блоб поле, содержащее список всех записей, в которых упоминается данное слово

плюсы: скорость поиска - почти мгновенная
минусы: индекс строиться очень долго (около двух часов) и съедает огромное количество памяти

размер индекса около 700 мб!

3). Похожее на 2, только создается две таблицы WordsIndex (Id int,WordName varchar(50)) и TopicIndex (WordId int,TopicNo int), где

WordsIndex:
Id - уникальный номер уникального слова в таблице
WordName - уникальное слово

TopicIndex:
WordId - ссылка на слово в таблице WordsIndex
TopicNo - соответственно номер записи, где это слово встречается

плюсы: минимум использования памяти, скорость поиска - почти мгновенная
минусы: время на создание полного индекса - несколько часов, размер индекса более 1 гб., кол-во записей в таблице TopicIndex - 30 млн. !!!!, со всеми вытекающими отсюда последствиями по скорости добавления следующих данных

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

Оптимальное время поиска, как для меня - не более 10 сек. и размер индекса не более 50% от размера базы

AlexSuv,
Переходи на MySQL. И не надо будет думать. Там полнотекстовый поиск встроенный.

вот советик то!!! C InterBase на MySQL, вот фигня то.....
ну что такое MySQL - так, веб сервис с урезаной поддержкой SQL, неболее! Его даже СУБД назвать трудно. хоты попытка есть!
SergeBS, не в обиду сказоно, просто решив проблему твоим предложением, человек сталнется с более большими проблемами, ну к примеру: контроль ресурсов БД, распределение привелегий на объекты БД, возможности хранить, и выполнять математику(процедуры, функции, тригеры) на сервере.

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

Согласен с SergeBS, mysql В этом отношении лучше. Как бы хотелось поставить галочку fulltext index и забыть про все пробемы,
однако я уже вариант с MySql пробовал, непомню почему, но отсек я его по многим причинам основная из которых: база должна быть одним файлом и простопереносимой с одной машины на другую.

DimW,

Сударь, Вы видимо с ЖарПтицей работали. Но я тоже. А с MySQL Вы работали? А Вы в курсе, что у него есть возможности, которые очень вкусны по сравнению не только с FireBird/InterBase, но и с MS SQL (с ним я тоже работаю)? Например, 4 типа баз: с самой простой (сжатая и только на чтение - как раз то что надо для хранения больших объемов текста) до BDB, по сравнению с которой FB мягко говоря не блещет. Хотя бы потому, что поддерживается SAP/R. А как насчет 6 типов целых (не считая знаковое/беззнаковое для каждого) или 4 типов BLOB?
А фонетического LIKE (правда для русского языка до сих пор не релизован)? Или текстового поиска: полнотекстовый индекс и поиск с релевантностью - да без проблем. Что и нужно. Причем чем реже при поиске встречается слово - тем выше его вес для результата. Где это в ЖарПтице? Ну ладно. А как насчет штатных средств восстановления/ремонта и проверки БД? Единым бэкапом сыт не будешь.


Контроль ресурсов: я могу раскидать базу по 4 разным дискам средствами MySQL (RAID-base). И они будут примерно одинаково пухнуть примерно в одинаковой пропорции. А Вы? Я могу сказать Insert Delayed (типа не спеша). А Вы? Кэш (не план!) запросов? Где в FB?
Распределение привилегий: ну ваащее . Для любой базы я разный не только по имени и паролю и т.п., но еще и по маске сети. Локально и по Инету - я разный. С теми же именем и паролем. И могу рулить правами буквально до операции, например разрешить Insert, но запретить всякие Delete/Select и прочие мерзкие штуки - скорчу из себя черную дыру .
Где это в FB? Я могу хоть 50 серверов поставить на 1 машину (если крыша от такого количества не поедет ). Каждого могу натравить на свою задачу и нехай дерутся за ресурсы тачки. А я им еще каждому кэш ОЗУ запросов подкручу по своим потребностям. Ну и прочую мелочь...

В официальном (стабильном) релизе MySQL 5.0 есть и процедуры, и функции, и триггера. Привилегии разруливаются тоже не хуже, чем в FB, а даже лучше.
Два недостатка у MySQL по сравнению с FB: IBExpert мне как-то удобнее кажется, чем phpMyAdmin, и в мегабайтах на диске (но не в загрузке памяти/процессора) MySQL тяжелее. Раза в 3.
Зато доки на русском - завались. Самых разных авторов. Плюс отсутствие проблем с языками вообще (хоть китайский подключай). Для работы с текстами это IMNSHO наилучший выбор. По крайней мере MS SQL - хуже. Про Oracle не скажу - не щупал. Но это уж больно монстроид. Явно не по задаче.

AlexSuv,
Кстати переход будет не шибко сложен. По большому счету - избавиться от генераторов и навтыкать Autoincrement. А там ADO в руки и вперед. Или всяких SDAC/MyDAC/Zeos... До десятка наберется.
Тебе понравится. По крайней мере мне понравилось. Я даже думаю тихо свертывать возню с MS SQL - за него все-таки бабки надо платить... Простенький проект перекинул за день - обнадеживает.

AlexSuv,
ЭЭЭ. Вот только в пятницу отволок домой InnoDB базу одним файлом (180М -фигня). (плюс 1 файл - описание). Остановил сервис, скопировал, запустил - поехали работать (отгулы зарабатывать). Хотя я и послал бы эти отгулы. Не получилось . Сегодня притопал. Опять стоп, копи, пуск - продолжаем. Проверил, скинул тем же методом на рабочий сервак - все. Впочем, и на FB и на MS SQL у меня такое срабатывало тоже. Так что 1 или 2 файла - какая разница, если 2-й всего 50 кб?

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

А пока буду вспоминать может все-таки кто предложет что-нить дельное по fb.

2 SergeBS, насчет надежности я бы поспорил у меня на проектах с mysql при перезагрузке у меня несколько раз
падала вся база и пару раз восстановить ее не удалось ((, на fb такого ни разу не было

Господа не стоит вопрос о смене базы и платформы! И давайте не затевать здесь сравнение баз данных. Тем более что IB линейка и MySQL это немного разные продукты, и в сравнении там не всё так уж ясно и однозначно (какой бы точки зрения вы не придерживались), особенно если принимать во внимание не только такие очевидные показатели как производительность или наличие каких-то фишек.

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

Теперь о полнотекстовом поиске как таковом: это очень и очень сложная задача. Полнотекстовым поиском владеет не только MySQL, но и рад других баз данных (тот же MS SQL Server) и ... работает он неудовлетворительно, ни по скорости, ни по качеству результатов. К сожалению реализованных хороших алгоритмов поиска в открытом виде по всей видимости нет, а те которые есть - например полнотекстовые поиски реализованные в Google или Yahoo - тайна за 7ю печатями, там на их разработке люди миллиарды себе сделали....

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

Увы нет... Это всё что я знаю, просто слышал о таком способе, но ни деталей реализации, ни более глубоких принципов работы я не знаю. Скорее всего надо копать где-то в разделах научной литературы по теории баз данных.

пока что интересного нарыл по этой теме, если кому интересно:

http://www.getinfo.ru/article13.html
http://citforum.ru/database/articles/rel_search.shtml
http://citforum.ru/database/articles/search_sys.shtml

попробую переделать алгоритм, о результатах напишу

Итак задачу решил следующим образом:

Таблица: Index (WordHash integer,WordPos integer)
пробегаем по всем записям определяем все уникальные слова длиннее 3-х букв, затем добавляем в таблицу Index хэш (я взял CRC32), этого слова и номер записи, где это слово встречается. Все оказалось гараздо проще.
Использовал библиотеки TextParser c Некоторыми доработками типа избавления HTML от тэгов и т.п.

Итак: построение полного индекса по 500 тыс записям около 10 мин.+построение двух индексов по полям WordHash и WordPos еще 7 мин.
размер индекса равен 80% от исходной таблицы
Количество записей в таблице Index около 24 млн.
Используемая оперативная память менее 1 мб.
Время поиска от 10 мс до 1 сек.

Недостатки:
1) Поиск точных слов т.е. "ИСКАТЬ " в поИСКАТЬ не найдет, хотя думаю сделать при добавлении слова в поиск добавлять и некоторые морфологические формы.
2) Подозреваю, что CRC32 не дает нужной уникальности, а жаль прийдется использовать другую хэш функцию, хотя все равно прийдется делать
обычный поиск в результататах для поиска словосочетаний.
3) Немаленикий размер индекса.

Спасибо всем кто ответил.

Недавно наткнулся на интересный компонент. Rubicon 2.20 Full Sources For Delphi
Rubicon - это поисковый движок, позволющий вам вести поиск текста со скоростью света. Может поможет. Сам честно не пробовал ставить.

А какую функцию использовали? Примерно тоже самое делаю, хеширование происходит очень медленно

Как по Вашему, какую _локальную_ СУБД можно испольовать для этих целей?

Я использую firebird 1.5. В принципе всем доволен.