Индексация для поиска по шаблону представляет собой одну из наиболее интересных
и занятных задач-головоломок. Общая формулировка задачи такова: построить индекс
со структурой и алгоритм поиска так, чтобы поиск по шаблону значения атрибута
выполнялся наиболее быстро.
Прямым применением традиционных индексных структур такая задча в общем случае не решается. Обычные индексы могут быть использованы только если шаблон значения атрибута начинается на какие-то символы. Если начало шаблона определено, то мы можем спозиционироваться в индексе на это начало и дальше пройти перебором значений до тех пор пока начальная часть значений в индексе не перестанет соответствовать шаблону.
Конечно, во-первых, в общем случае это условие не выполняется и, во-вторых, перебор индексированных значений по начальной части поиска может пройтись по десяткам мегабайт диска. Для малых баз данных перебор обычно не критичен, но для больших реальных инсталляций такой подход существенно увеличивает число операций с глобалами и может прокачать через кеш множество бесполезных блоков базы данных.
Более того, можно сказать, что для малых баз данных и сама индексация скорее может быть вредной. Если данных в базе данных мало, то намного эффективнее выполнять просто переборы по кешу, если сами данные помещаются в памяти, чем регулярно обращаться к индексным структурам, которые вымывают кеш и усложняют логику работы. Индексация для поиска по шаблону по самой постановке вопроса и по степени его привередливости традиционно относится к реально большим базам данных, где построение индексов соответствующих выполняемой задаче действительно дает преимущество.
В качестве одного из вариантов индексации для поиска по шаблону может быть использован принцип максимального отсечения неподходящих вариантов. Для этого индексируемое значение разбивается на последовательности в 1, 2, 3 и т.д. символов. Например, строка
Для построения индекса по шаблону используются служебные функции разбиения слова и шаблона на части:
Для построения индекса используется набор функций добавления и удаления индексных записей:
Соответственно может быть модифицировано и применение алгоритма поиска $$ANDnext() с тем, чтобы он выполнял проход сначала по самым длинным фрагментам.
Кроме того, каждый разработчик видит проблему по-своему, и у каждого могут быть свои варианты, как построить индексацию для поиска по шаблону, чтобы она выполнялась максимально быстро. Вполне возможно, что разработчик может использовать специфику разрабатываемой системы и / или особенности индексируемых данных.
Интересно отметить, что у поиска по шаблону может быть найдена масса вариаций. В одном из проектов, разработанных на MUMPS с прямым программированием индексных структур и нестандартными выборками из индексов было применено решение, содержащее разбиение значения атрибута на фрагменты и построение индексов по фрагментам. Далее, при вводе искомой строки она также разбивалась на фрагменты. Поиск выполнялся по начальным частям полученных фрагментов и нечувствительно к регистру. Можно было ввести одну - две буквы из начала каждого из необходимых фрагментов и система автоматически и весьма быстро находила в огромном массиве те записи, в которых присутствовали фрагменты начинающиеся на те же символы.
Такой поиск решал проблему поиска по названиям или именам, когда одно название или полное имя может включать много слов, но затруднительно набрать в точности то же самое, что было введено при записи данных в базу. В частности, название
Скорость поиска по описанным алгоритмам такова, что поиск первых 10 - 20 строк может выполняться интерактивно, при очередном вводе символа в строке поиска.
Подробнее о книге "MUMPS СУБД"
Прямым применением традиционных индексных структур такая задча в общем случае не решается. Обычные индексы могут быть использованы только если шаблон значения атрибута начинается на какие-то символы. Если начало шаблона определено, то мы можем спозиционироваться в индексе на это начало и дальше пройти перебором значений до тех пор пока начальная часть значений в индексе не перестанет соответствовать шаблону.
Конечно, во-первых, в общем случае это условие не выполняется и, во-вторых, перебор индексированных значений по начальной части поиска может пройтись по десяткам мегабайт диска. Для малых баз данных перебор обычно не критичен, но для больших реальных инсталляций такой подход существенно увеличивает число операций с глобалами и может прокачать через кеш множество бесполезных блоков базы данных.
Более того, можно сказать, что для малых баз данных и сама индексация скорее может быть вредной. Если данных в базе данных мало, то намного эффективнее выполнять просто переборы по кешу, если сами данные помещаются в памяти, чем регулярно обращаться к индексным структурам, которые вымывают кеш и усложняют логику работы. Индексация для поиска по шаблону по самой постановке вопроса и по степени его привередливости традиционно относится к реально большим базам данных, где построение индексов соответствующих выполняемой задаче действительно дает преимущество.
В качестве одного из вариантов индексации для поиска по шаблону может быть использован принцип максимального отсечения неподходящих вариантов. Для этого индексируемое значение разбивается на последовательности в 1, 2, 3 и т.д. символов. Например, строка
abcdразбивается на подстроки
a b c d ab bc cd abc bcdПри задании шаблона поиска шаблон трансформируется также в последовательность подстрок, которые он содержит, например шаблон
ab*dразбивается на подстроки
a b d abПосле этого производится поиск аналогичный многоиндексной выборке, как если бы у искомой записи было несколько атрибутов, с применением алгоритма zig-zag. Основной задачей такого подхода является пропуск заведомо неиспользуемых подстрок и отсечение как можно большего числа неподходящих записей.
Для построения индекса по шаблону используются служебные функции разбиения слова и шаблона на части:
DEPTHS() q 3 ; use 1,...,3 symbols MAKEPARTS(str,parts) ; use as parts all symbols n depth=$$DEPTHS(),d,pos,i,substr f i=1:1:depth d . f pos=1:1:$l(str)-i+1 d . . s substr=$e(str,pos,pos+i-1) s:substr'="" parts(substr)="" q MAKEPATPARTS(str,parts) ; use as parts only symbols between * and ? q:str="" n i f i=1:1:$l(str,"*") d MAKEPATPARTS2($p(str,"*",i),.parts) q MAKEPATPARTS2(str,parts) q:str="" n i f i=1:1:$l(str,"?") d MAKEPATPARTS3($p(str,"?",i),.parts) q MAKEPATPARTS3(str,parts) q:str="" n depth=$$DEPTHS(),d,pos,i,substr,start=$l(str) i $l(str)>=depth s start=depth f i=1:1:depth d . f pos=1:1:$l(str)-i+1 d . . s substr=$e(str,pos,pos+i-1) s:substr'="" parts(substr)="" q PAT(mask) ; make MUMPS pattern based on the LIKE's template n quote,i,ret,char s quote=0,ret="" f i=1:1:$l(mask) d . s char=$e(mask,i) s:char="""" char=char_char . i "*?"'[char s ret=ret_$s(quote:char,1:"1"""_char),quote=1 q . i quote s ret=ret_"""" . s ret=ret_$s(char="*":".E",1:"1E") . s quote=0 i quote s ret=ret_"""" q:$q ret qСтруктурно пример использует набор слов и индексов в виде:
^LIKEDATA(id)=word ^LIKEIND(part,id)=""Здесь id - идентификатор слова, word - значение слова, part - часть слова.
Для построения индекса используется набор функций добавления и удаления индексных записей:
ADDWORD(word) n id=$i(^LIKEDATA) s ^LIKEDATA(id)=word n parts d MAKEPARTS(word,.parts) n part="" f s part=$o(parts(part)) q:part="" d . s ^LIKEIND(part,id)="" q DELWORD(id) n word=$g(^LIKEDATA(id)),parts d MAKEPARTS(word,.parts) n part="" f s part=$o(parts(part)) q:part="" d . k ^LIKEIND(part,id) k ^LIKEDATA(id) q REINDEX k ^LIKEIND n i="" f s i=$o(^LIKEDATA(i)) q:i="" d . n parts d MAKEPARTS(^LIKEDATA(i),.parts) . n part="" f s part=$o(parts(part)) q:part="" d . . s ^LIKEIND(part,i)="" qПример использует контрольный набор данных:
INIT ; clear and recreate all data k ^LIKEDATA,^LIKEIND n word f word="abc def","def ghj","rty iop","789 hjk","abdefghj" d . d ADDWORD(word) qДля выборки по шаблону используется алгоритм многоиндексной выборки адаптированный с использованием нескольких индексов по разным атрибутам к использованию одного индекса по нескольким фрагментам:
LIKESELECT(mask,ids) n pat=$$PAT(mask),parts,inames,part,id ; make template parts d MAKEPATPARTS(mask,.parts) ; make index names s part="" f s part=$o(parts(part)) q:part="" d . s inames($i(inames))=$na(^LIKEIND(part)) ; call index search k ids d AND($na(ids),.inames) ; use filter to remove unneed s id="" f s id=$o(ids(id)) q:id="" d . i ^LIKEDATA(id)'?@pat k ids(id) q AND(ret,names) ; make zig-zag ordered selection n id,i,j,place s id="" f s i=1,id=$$ANDnext() q:id="" s @ret@(id)="" q ANDnext() ANDrep s id=$o(@names(i)@(id)) q:id="" "" f j=i+1:1:i+names-1 s place=((j-1)#names)+1 >> i '$d(@names(place)@(id)) s i=place g ANDrep q idПоскольку при поиске по индексу находятся записи, подходящие по индексу, но не подходящие по шаблону, применяется дополнительная фильтрация по шаблону
s id="" f s id=$o(ids(id)) q:id="" d . i ^LIKEDATA(id)'?@pat k ids(id)И, наконец, контрольный тест для запуска:
test ; n ids,like f like="* *","*ef","*hj?" d . k ids . d LIKESELECT(like,.ids) . d dump q dump w "like template=""",like,"""",! n id="" f s id=$o(ids(id)) q:id="" d . w "found id=",id,", string=""",^LIKEDATA(id),"""",! qПри необходимости разработчик может вставить трассировку выполнения или счетчики операций и, последовательно совершенствуя алгоритм, добиться большей оптимизации, например выполнять поиск по индексу не в индексной сортировке, а использовать сначала отсечение по фрагментам максимальной длины, например построить структуру
^LIKEDATA(id)=word ^LIKEIND(len,part,id)=""Здесь id - идентификатор слова, word - значение слова, part - фрагмент слова, len - длина фрагмента.
Соответственно может быть модифицировано и применение алгоритма поиска $$ANDnext() с тем, чтобы он выполнял проход сначала по самым длинным фрагментам.
Кроме того, каждый разработчик видит проблему по-своему, и у каждого могут быть свои варианты, как построить индексацию для поиска по шаблону, чтобы она выполнялась максимально быстро. Вполне возможно, что разработчик может использовать специфику разрабатываемой системы и / или особенности индексируемых данных.
Интересно отметить, что у поиска по шаблону может быть найдена масса вариаций. В одном из проектов, разработанных на MUMPS с прямым программированием индексных структур и нестандартными выборками из индексов было применено решение, содержащее разбиение значения атрибута на фрагменты и построение индексов по фрагментам. Далее, при вводе искомой строки она также разбивалась на фрагменты. Поиск выполнялся по начальным частям полученных фрагментов и нечувствительно к регистру. Можно было ввести одну - две буквы из начала каждого из необходимых фрагментов и система автоматически и весьма быстро находила в огромном массиве те записи, в которых присутствовали фрагменты начинающиеся на те же символы.
Такой поиск решал проблему поиска по названиям или именам, когда одно название или полное имя может включать много слов, но затруднительно набрать в точности то же самое, что было введено при записи данных в базу. В частности, название
ООО "Белый Медведь"может быть введено в базу данных в разном виде, но логически эти названия эквивалентны для пользователя:
ООО "Белый Медведь" ООО Фирма "Белый Медведь" Белый Медведь, ООО ООО БЕЛЫЙ МЕДВЕДЬПосле разбиения на отдельные слова и приведения к общему регистру в индексах системы использовались значения
OOO БЕЛЫЙ МЕДВЕДЬРазумеется, что при применении такого механизма поиска, когда пользователь мог просто ввести в строке поиска
бе месистема оперативно отыскивала также и необходимое ему название ООО "Белый Медведь", и, возможно, еще пару подходящих под такой же шаблон.
Скорость поиска по описанным алгоритмам такова, что поиск первых 10 - 20 строк может выполняться интерактивно, при очередном вводе символа в строке поиска.
Подробнее о книге "MUMPS СУБД"
Комментариев нет:
Отправить комментарий