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

[clevel]

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

Предистория.
Понадобилось мне написать "умный поиск"- с учетом морфологии русского языка, плюс возможность искать по текстам, учитывая отступы слов от начала страницы, других слов.
Та вот, пошел я искать в инете, может чего до меня придумали, набрел на один сайт, не буду делать ему рекламы, там есть сырцы на пхп и перле, сделанные для решения моей задачи.
Но! словарь для морфологии сделан на основе хеша и НЕ ПОЗВОЛЯЕТ без перекомпиляции добавлять новые слова.
почитав литературы, сделал свой словарь, используя мускул.
Таблица вида id(mediumint unique autoincriment), content (char20, primary key), parent(mediumint indexkey), где сконвертил все первичные и производные словоформы. все замечательно - можно добавлять новые слова без проблем...
однако встала делема - 60 мегов словарь (дата+индексы).
Начал общаться с челом, которого сырцы нашел, он говорит, что полный словарь у него занимает пять мегов и поиск идет у него быстрее за счет того, что скрипт у него меньше "шуршит" по диску (fseek,read меньше)...
я ему привел пример того, что у меня индексы, и, соответственно, выборок - минимальное количество...
Я ему ссылки с мана, что вот мол, дескать так и так, мускул все грамотно делает, в ответ - усмешки.
Вопрос:
при вышеуказанной структуре и ИНДЕКСАХ будет ли минимальное "шуршание по диску" при запросах:
1.select id,parent from table where content='словщ'
2.select content from table where parent=10000
Интересует теоретическое подкрепление...
Сам читаю доку про бинарные деревья, красно-черные, хеши.... вроде все быстро работает, но хочется ему нос утереть... помогите, плз...

 

[AnToXa]

1. сильно зависит от настроек mysql
может так случиться, что он будет искать вообще в памяти

но с другой стороны в mysql индексирование сделано для общего случая и некие хитрые индексы могут быстрее в данном случае...

вопрос: у тебя в базе лежит дерево словоформ?
тогда для скорости выборок имхо надо юзать nested sets aproach... ведь добавления редки.

Сам читаю доку про бинарные деревья, красно-черные, хеши.... вроде все быстро работает

ну разве что для самообразования

но хочется ему нос утереть... помогите, плз...

оно того стоит? no offence! just curiuos!

 

[clevel]

nested sets aproach

а что это? не нашел по ману...
в базе лежат полные слова - первичные и производные словоформы...

оно того стоит? no offence! just curiuos!

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

 

[AnToXa]

а что это? не нашел по ману...
в базе лежат полные слова - первичные и производные словоформы...

см. http://sdm.viptop.ru/articles/sqltrees.html
также поищи у суида на http://e-taller.net/dev/
классик для управления этим делом в mysql

если не найдешь - поищу, тот, что я писАл

в споре рождается истина...

попытаемся родить

 

[clevel]

почитал первую статью, смотрел ссылку на директорию суида...
описывается работа с таблицей, где есть многоуровневая зависмость начальник-подчиненный, у меня несколько другая ситуация - всего два уровня - первоформа слова (например, 1,стул,0) и производная форма(2,стула,1; 3,столу,1).
дерево я не храню, поэтому все проще...
думается, что если переходить на дерево (32 буквы русского алфавита в первом уровне, от них 32 буквы для каждого на первый уровень), а потом ссылки на возможные варианты с болше, меньше, равно - так это у того чела уже в сырцах реализовано, правда для хранения используется не БД, а бинарные файлы...
все бы хорошо, да при такой структуре нельзя без перекомпиляции словаря новые слова вставлять... что не есть хорошо... а так бы я согласился с этим - и размер меньше словаря....
может кто уже с подобной ситуация сталкивался? в какую сторону глядеть? смотрю сейчас стремминг, что-то он меня не воодушевляет... а хранить все первичные слова и их словоформы - места жалко, так как для каждого языка по млн. записей надо...

 

[AnToXa]

если 2 уровня - то тогда имхо как ты делаешь - это имхо правильно.

второе.

если у него индексы по буквам, то, для каждого конкретного слова время поиска - константа, у mysql - логарифмическое время (если mysql использует стандартные индексы для слов)

зависит сильно от настроек тачки, железа и проч.
надо бенчить.

 

[clevel]

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

 

[AnToXa]

может быть хранить на втором уровне только окончания слов?

т.е. приставку с корнем оставлять на верхнем уровне, а на второй вынести суффикс+окончание?

места будет гораздо меньше занимать

 

[clevel]

может быть хранить на втором уровне только окончания слов?

т.е. приставку с корнем оставлять на верхнем уровне, а на второй вынести суффикс+окончание?

места будет гораздо меньше занимать

в том та вся и фича:
запрос select id,parent from table where content='слово' ищет первоформу ЛЮБОГО СЛОВА (первоформы и производного слова), для этого, в основном, и сделан словарь... если хранить окончания, как мне найти первоформу по производному слову....
если вычленять основу слова до поиска , то это - стемминг, что не очень мне понравилось - много левых слов и много ненужного кодинга...

 

[ForJest]

.select id,parent from table where content='словщ'
2.select content from table where parent=10000

SELECT content FROM table t1, table t2 WHERE t1.content='слово' AND (t1.parent=t2.parent OR t1.id=t2.parent)

 

[clevel]

SELECT content FROM table t1, table t2 WHERE t1.content='слово' AND (t1.parent=t2.parent OR t1.id=t2.parent)

попробуем..

 

[Silent]

> в ответ - усмешки

Вовсе не хотел я ни над кем смеяться. Наоборот, если ты предоставишь мне данные, что на таком сайте с таким числом документов на такой машине на таком запросе, который возвращает столько-то документов время поиска такое-то, я буду сильно признателен. Но пока я только от всех слышу, что если сделать на MySQL, будет быстрее. Почему быстрее? Ну как, это ведь база, там ИНДЕКСЫ... Сам я с MySQL почти не работал, как его оптимально настроить не знаю, и если знающий человек сделает и сообщит результаты, буду только рад.

Теперь по существу: вчера немного поигрался, сформировал список всех словоформ (1700000 штук, общий объем 25 Мб) и загнал их в хеш-таблицу (на основе бинарных файлов) в виде "словоформа -> начальная форма". Получились те же 60 Мб. Скорость доступа тестировал следующим образом: брал небольшой файлик (120 кб), разбивал на слова и в цикле искал в хеш-таблице. Результаты получились достаточно интересные. На первом проходе получил 100-200 запросов в секунду (столько же было и у тебя), причем все время диск работал не переставая. А на второй раз - 5000 запросов в секунду. Видимо на этот раз все нужные части хеша были закешированы где-то в оперативной памяти и обращений к диску было гораздо меньше. Если же сначала прочесть весь хеш в память и затем работать с ним через "substr", тогда скорость работы - 10000 запросов в секунду (это все на Перле). Таким образом получаем, что если есть таблица с 1000000 строк, то скорость доступа получается примерно 100 запросов в секунду (если данные лежат на диске), причем эта скорость мало зависит от того, как реализован индекс (хеш или дерево) и на каком языке все это написано. Основное время расходуется на шуршание диском. Если же данные расположены в оперативной памяти, скорость возрастает в десятки раз (для MySQL может быть и больше, все таки это не Перл). Поэтому я и отнесся так критически к индексам MySQL. Не потому, что они плохие, просто в этой задаче есть другой важный фактор - скорость доступа к жесткому диску. Если базе выделить много памяти, тогда все будет иначе, но на каком бюджетном хостинге одному сайту выделят 60 мег оперативки? А если использовать более сложный алгоритм, но который позволяет уменьшить размер данных, то даже скриптовые языки могут оказаться быстрее неэффективного алгоритма, реализованного на Си.

В дальнейшем эти же проблемы ожидаются и для поиска. Большинство поисковых движков на основе MySQL делаются в виде таблицы со строками "wordID -> docID". Если число документов несколько тысяч, все будет прекрасно. Но если речь идет о десятках тысяч, то опять мы упремся в ограничения, накладываемые жестким диском. И решить их можно (для данной структуры) только выделив больше памяти. А другой подход опять таки может оказаться более эффективным. И я не говорю, что этот подход плохой. У него есть много преимуществ (в основном простота разработки). Но есть и ограничения, котрые желательно знать заранее.

P.S. И я все равно не могу понять, почему ты не хочешь выделить морфологический анализ в отдельную задачу. Тогда тебя не будет волновать, как он устроен, и всегда можно будет заменить один анализатор другим.

 

[clevel]

P.S. И я все равно не могу понять, почему ты не хочешь выделить морфологический анализ в отдельную задачу. Тогда тебя не будет волновать, как он устроен, и всегда можно будет заменить один анализатор другим.

отвечаю:
изначально у меня все данные хранятся не в текстовых файлах, а в таблице, поле longtext. Для поиска я создал fulltext index, и спокойно кодил себе дальше... Но тут один из моих клиентов попробовал поискать на своем сайте, и не найдя то, что искал, выкатил мне притензию - мол, дескать, так и так, не работает поиск...
И выяснилось, что поиск точных совпадений - вещь неблагодарная, нужен поиск, независимый от морфологической формы слова. После этого я и начал искать в данном направлении. Посмотрел топики на этом форуме по поводу поиска, поднабрал идей насчет поиска слова с учетом позиции на странице, и решился все это реализовать...
в чем не понравился твой алгоритм: у тебя создается список всех слов в файл-индеск, который встречается на странице. А мне, по причине скорости, хочется хранить все это в мускуле, и не слова, а номера первоформ этих слов. Соответственно. при индексации мы эти слова заменяем номерами, и при поиске тоже самое...
вот и все.
насчет шуршания по диску... мускул это делает только в том случае, если это не храниться в индексе. Я приводил мою структуру, на диск для считывания даты он обращается только два раза - первый раз найти из индекса необходимое слово, второй раз - по данному слову из индекса найти номер этого слова из таблица.
По поводу скорости - на хостинге у меня ищет слова за две тысчных секунды... это раз, во вторых, если речь идет не о полной переиндексации (она всего раз происходит, и не несколько мегов изначально), то скорость поиска первоформ для нескольких сот страниц не является основопологающей, тем более что в памяти я храня все ранее найденные слова...

 

[Silent]

Отвечаю

Выделяем морфологию в отдельную подзадачу, с поиском никак не связанную. Единственное, что требуется от морфологии - выдать начальную форму слова для любой словоформы. Как это достигается, нас не интересует. Это может быть отдельная таблица в базе (как у тебя сделано сейчас) или библиотека на Си или еще что-нибудь. Теперь, при индексации мы берем слова из текста и отдаем их морфоанализатору, получаем норьмальную форму (на самом деле формы, потому как их может быть несколько). Затем создаем другую таблицу в базе с соответствием "нормальная форма -> ID". Далее все как у тебя. Нужна дополнительная таблица, но зато морфология отделена от поиска и в любой момент ее безболезненно можно заменить.

Насчет шуршания по диску. По твоему два обращения к диску на запрос - это мало? Какова средняя скорость доступа к современным дискам? Порядка 10 мс (на самом деле наверное побольше)? В итоге, в самом идеальном случае ты получишь НЕ БОЛЕЕ 50 запросов в секунду. А если учесть, что для такого большого индекса (1000000 элементов) нужно несколько считываний, то получим всего лишь десяток запросов в секунду. Немного помогает то, что данные, прочитанные с диска, кешируются, поэтому ты получил 100 запросов в секунду, а не 10. Это ведь арифметика, тут даже высшее образование не нужно.

 

[Silent]

> По поводу скорости - на хостинге у меня ищет слова за две тысчных секунды

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

 

[clevel]

Так в чем проблема, если скорость устраивает?

размер словаря под русский язык только - 60 мегов...

 

[Silent]

Ну это можно побороть только кардинальным изменением алгоритма.

 

[ForJest]

Что-то в идее Silent есть все же. Как идея. Реализовать умный алгоритм и хранить индекс в памяти. А умный алгоритм для того чтобы индекс был поменьше размером. В конце концов мускул предназначен для решения более широкого круга задач. Если написать по сути туже БД, только узкоспециализированную то вполне может быть что поиск будет быстрее.

 

[jeka!]

Вот я тут всё перечитал, заинтересовало, может дадите ссылочки на свои сайты/проекты где можно об этом подробнее узнать?
У меня тоже есть одна задача которую я хочу решить, это поиск совпадений.
В общем есть некая БД текстовая размером 50 мегов и миллионом строк, и она будет расти.
Я её использую для хранения уникальных значений.
Так вот, поиск по ней у меня занимает от нескольких долей секунд до, в случае если ничего не найдено 4 секунд.
Длинна каждой записи не более 200 символов в среднем 50.
для поиска использую построчное сравнение функцией preg_match.
БД mysql не использую, по тому что думаю что дудет лишний расход ресурсов, ведь мускул тоже потребляет.
Но с другой стороны, по прочтению всего вышесказанного, уже думаю что надо использовать мускул.
В общем что можете посоветовать?
Любые варианты или статьи на русском, буду признателен.

 

[jeka!]

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

Наоборот смотря на каком хостинге, во первых, все русырсы делятся на все сайты на той машине, а это уже замедление.
Во вторых, днем ресурсов совсем не хватает.
Я писал скрипт галлереи фото, в общем у меня на домашнем компе p533 диск 5400 оборотов 255 оперативки, процесс создания 3500 страниц занимал в 3 раза меньше времени, чем на хостинге Валуехост в ночное время.
А днём сервер загибался, и накрывались все процессы вобще.
Замучу на той машине находится судя по почтовым аккаунтам около 100 сайтов или может немного больше.
Так что смотря где...