Пусть у нас есть большая таблица ну пусть с 1 млрд записей в виде произвольных строк
мы хотим искать по ней произвольным regex запросами
есть какойто способ разбиения ее как хештаблицу или какойто способ индексирования чтобы ускорить поиск?
Я изъездил эту страну вдоль и поперек, общался с умнейшими людьми и я могу вам ручаться в том, что обработка данных является лишь причудой, мода на которую продержится не более года. (с) Эксперт, авторитет и профессионал из 1957 г.
Re: Индексирование/хеширование при поиске по regex
Здравствуйте, Barbar1an, Вы писали:
B>Пусть у нас есть большая таблица ну пусть с 1 млрд записей в виде произвольных строк B>мы хотим искать по ней произвольным regex запросами
В общем случае нет.
B>есть какойто способ разбиения ее как хештаблицу или какойто способ индексирования чтобы ускорить поиск?
Проанализировать типовые запросы и для них пытаться строить индексы и распараллеливать запросы.
Re: Индексирование/хеширование при поиске по regex
Здравствуйте, Barbar1an, Вы писали:
B>Пусть у нас есть большая таблица ну пусть с 1 млрд записей в виде произвольных строк B>мы хотим искать по ней произвольным regex запросами B>есть какойто способ разбиения ее как хештаблицу или какойто способ индексирования чтобы ускорить поиск?
пересмотреть задачу в сторону Full-text search.
Re: Индексирование/хеширование при поиске по regex
Здравствуйте, Barbar1an, Вы писали:
B>Пусть у нас есть большая таблица ну пусть с 1 млрд записей в виде произвольных строк B>мы хотим искать по ней произвольным regex запросами
А запросы у тебя снаружи приходят?
Ты в курсе, что стоимость компиляции regex-а в худшем случае экспоненциальная, причем и по процессору и по памяти? Я б не стал внешие regex-ы в свою машину впускать...
Re[2]: Индексирование/хеширование при поиске по regex
Здравствуйте, Pzz, Вы писали:
Pzz>Здравствуйте, Barbar1an, Вы писали:
B>>Пусть у нас есть большая таблица ну пусть с 1 млрд записей в виде произвольных строк B>>мы хотим искать по ней произвольным regex запросами
Pzz>А запросы у тебя снаружи приходят?
Pzz>Ты в курсе, что стоимость компиляции regex-а в худшем случае экспоненциальная, причем и по процессору и по памяти? Я б не стал внешие regex-ы в свою машину впускать...
вообще да, внешние, но нет проблемы обрубать выполнение по превышению лимитов
Я изъездил эту страну вдоль и поперек, общался с умнейшими людьми и я могу вам ручаться в том, что обработка данных является лишь причудой, мода на которую продержится не более года. (с) Эксперт, авторитет и профессионал из 1957 г.
Re: Индексирование/хеширование при поиске по regex
Здравствуйте, Barbar1an, Вы писали:
B>Пусть у нас есть большая таблица ну пусть с 1 млрд записей в виде произвольных строк B>мы хотим искать по ней произвольным regex запросами B>есть какойто способ разбиения ее как хештаблицу или какойто способ индексирования чтобы ускорить поиск?
0. Оптимизация для произвольных регекс-запросов — это сизифов труд. Какой бы способ вы ни выбрали, всегда найдётся патологический регексп, который его "обходит", сводя задачу обратно к полному просмотру.
Исходя из этого, вырисовываются два направления размышлений:
1. Отказ от регекспов. Точно ли пользователям нужна вся разрушительная мощь регекспов, или их устроит чуть менее выразительный язык запросов?
2. Отказ от произвольности регекспов. Для некоторых частных случаев можно срезать углы; тогда у нас задача распадается на две:
2.1. Придумать собственно способ срезать углы, и
2.2. Придумать способ определить для заданного регекспа, позволяет ли он срезать углы (и запретить выполнять его в противном случае).
Например, можно попытаться быстро отмести те строки, которые точно не заматчат наш регексп.
Допустим, вот такой регекс /\bfoo\ba* заматчит только строки, в которых есть слово foo. Так что можно воспользоваться полнотекстовым индексом, чтобы быстро отбросить строки, где слова foo нет.
Этот индекс может быть построен на n-граммах, либо на словах, либо на том и другом.
То есть при получении регекспа мы
а. Определяем, есть ли в нём какие-то фрагменты, которые обязательно должны (или обязательно не должны) содержаться в строке. Если их нет, или они нам не нравятся (слишком короткие), то мы блокируем дальнейшее выполнение.
б. Оцениваем количество строк, которые нужно просмотреть, с учётом найденных фрагментов. Если их слишком много — опять блокируем дальнейшее выполнение.
в. Строим список строк-кандидатов, которые нужно просмотреть, и просматриваем их нашим регекспом.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re: Индексирование/хеширование при поиске по regex
B>Пусть у нас есть большая таблица ну пусть с 1 млрд записей в виде произвольных строк B>мы хотим искать по ней произвольным regex запросами
B>есть какойто способ разбиения ее как хештаблицу или какойто способ индексирования чтобы ускорить поиск?
Elasticsearch или Solr индексы практически для этого и делали.
Re: Индексирование/хеширование при поиске по regex
