Многоиндексной выборкой, иначе называемой шаговой или зиг-загом, называется
выборки идентификаторов записей по нескольким индексным структурам одновременно.
Также часто встречается название zig-zag ordered scan.
Принципиальным моментом является слово ordered, или упорядочение искомых
идентификаторов. Применяется для выборки из двух или более индексов.
Индексные структуры отображают значение атрибута на набор идентификаторов. При этом набор идентификаторов может быть упорядочен в каком-либо упорядочении. Если порядок сортировки в нескольких индексах одинаков, то к ним может быть применена многоиндексная выборка.
При такой выборке алгоритм выбирает по какому-то критерию один из индексов, например первый попавшийся и получает идентификатор записи. После чего идет по списку индексов и сверяет есть ли в них соответствующая запись с соответствующими этим индексам значениями атрибутов. Если во всех заданных индексах такая запись есть, то она считается найденной. Если по какому-то из индексов запись не найдена, то по этому индексу выполняется сдвиг в наборе идентификаторов и этот индекс считается начальным, все повторяется. Если на каком-то шаге идентификатор стал пуст, то выборка закончена.
Приведенный алгоритм является одним из вариантов алгоритма соединения сортированных списков, называемый merge join или sort merge join, и может объединять, вообще говоря, произвольное число индексных структур.
Условно представим схему выборки. Положим, что нужно найти серую кошку. При этом располагаем двумя индексами - по цвету и по виду.
Поскольку идентификатор не пуст, не прекращаем поиск и проверяем существование отображения следующего индекса (это индекс по цвету). Такая запись есть, и других индексов для проверки нет, поэтому идентификатор считается удовлетворяющим заданным условиям и отмечается каким-либо способом как найденный.
С этого же индекса (или с любого другого) выполняем сдвиг на следующий идентификатор. Сдвинувшись по индексу по цвету на следующий идентификатор после 4, получаем пустой идентификатор, следовательно поиск закончен.
В найденный набор идентификаторов таким образом должен попасть только один идентификатор id = 4.
Обобщенная функция многоиндексной выборки может выглядеть например таким образом:
Приведем примеры получения данных в соглашениях из первого примера:
Одновременно с тем в большинстве случаев многоиндексная выборка намного предпочтительнее использования только одного индекса и фильтрации значений по остальным атрибутам. В определенной степени это утверждение опирается на наиболее распространенные статистики применяемых данных. Соотношение эффективности различных методов поиска по нескольким индексам, безусловно, зависит от состояния данных.
Многоиндексную выборку можно применять также при смешанных индексах - одновременно использовать древовидные, составные и битовые индексы. Условием их совместности является одинаковость упорядочения искомых идентификаторов. В случае применения индексов разного вида соответственно следует изменить алгоритм выборки, чтобы он обращался к соответствующим операциям получения следующего идентификатора и для проверки существования идентификатора в индексных структурах. Вышеприведенные коды использовали простые индексы и соответственно использовали функции $o() и $d().
Замечание относительно одинаковости упорядочения важно также в отношении применения баз данных с различными соглашениями о сравнении символов (character collation), а также для тех MUMPS систем, в которых сортировка локальных переменных может отличаться от сортировки глобалов в случае если производится выборка из индексов или промежуточных индексных структур, расположенных в смешанном виде хранения - и в локальных и в глобальных переменных одновременно.
Подробнее о книге "MUMPS СУБД"
Индексные структуры отображают значение атрибута на набор идентификаторов. При этом набор идентификаторов может быть упорядочен в каком-либо упорядочении. Если порядок сортировки в нескольких индексах одинаков, то к ним может быть применена многоиндексная выборка.
При такой выборке алгоритм выбирает по какому-то критерию один из индексов, например первый попавшийся и получает идентификатор записи. После чего идет по списку индексов и сверяет есть ли в них соответствующая запись с соответствующими этим индексам значениями атрибутов. Если во всех заданных индексах такая запись есть, то она считается найденной. Если по какому-то из индексов запись не найдена, то по этому индексу выполняется сдвиг в наборе идентификаторов и этот индекс считается начальным, все повторяется. Если на каком-то шаге идентификатор стал пуст, то выборка закончена.
Приведенный алгоритм является одним из вариантов алгоритма соединения сортированных списков, называемый merge join или sort merge join, и может объединять, вообще говоря, произвольное число индексных структур.
Условно представим схему выборки. Положим, что нужно найти серую кошку. При этом располагаем двумя индексами - по цвету и по виду.
^Index("color","белый",1)=""
^Index("color","белый",2)=""
^Index("color","серый",3)=""
^Index("color","серый",4)=""
^Index("type","кошка",1)=""
^Index("type","кошка",4)=""
^Index("type","кошка",5)=""
^Index("type","собака",2)=""
В качестве начального условия выбираем индекс по цвету и позиционируемся на
первое значение идентификаторов 3. Получаем в переменную id = 3. Переходим к
индексу по виду и проверяем есть ли такой идентификатор в отображении значения
"кошка". Такого нет. Делаем текущим индекс по виду и выполняем выборку
следующего идентификатора по виду относительно текущего значения id, id
принимает значение 4.
Поскольку идентификатор не пуст, не прекращаем поиск и проверяем существование отображения следующего индекса (это индекс по цвету). Такая запись есть, и других индексов для проверки нет, поэтому идентификатор считается удовлетворяющим заданным условиям и отмечается каким-либо способом как найденный.
С этого же индекса (или с любого другого) выполняем сдвиг на следующий идентификатор. Сдвинувшись по индексу по цвету на следующий идентификатор после 4, получаем пустой идентификатор, следовательно поиск закончен.
В найденный набор идентификаторов таким образом должен попасть только один идентификатор id = 4.
Обобщенная функция многоиндексной выборки может выглядеть например таким образом:
AND(ret,names...)
n id,i,j,place
; идем по всем и запоминаем. контекст выборки - в переменных
; 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 ; по всем есть, значит подходит
Здесь символом » обозначен перенос строки, которого в реальном коде не должно
быть. В функции AND используется передача переменного числа параметров. То же
самое можно организовать и на стандартном М:
ANDv(ret,names) g AND+1Но при этом следует самостоятельно сформировать набор индексов. Приведенные функции используют соглашения что в передаваемых переменных передаются имена и функции должны использовать косвенность. Это соглашение позволяет составить функцию выборки по индексам в достаточно общей форме.
Приведем примеры получения данных в соглашениях из первого примера:
SelectFigureColor(Figure,Color)
n res
d AND($na(res),$na(^Index("Figure",Figure)), »
$na(^Index("Color",Color)))
s res="" f s res=$o(res(res)) q:res="" d
. w res,!
q
Здесь формируется набор имен, куда следует вренуть результат и имена индексных
записей. Тот же вариант без использования переменного числа аргументов:
SelectFigureColor(Figure,Color)
n res,ind
s ind(1)=$na(^Index("Figure",Figure))
s ind(2)=$na(^Index("Color",Color))
s ind=2 ; два индекса
d ANDv($na(res),.ind)
s res="" f s res=$o(res(res)) q:res="" d
. w res,!
q
Многоиндексная выборка по своему характеру не является наиболее оптимальной по
числу выполняемых с глобалами действий, поскольку часть шагов выполняется
впустую. Количество лишних операций, или операций не приведших к получению
искомого идентификатора, сильно зависит от состояния используемых индексов.
Вполне возможны ситуации, когда при большом количестве данных по обеим индексам
в искомое множество попадает очень малое число идентификаторов, но в этом случае
многоиндексная выборка тем не менее предпримет попытки прохода по неинтересующим
идентификаторам в том числе.
Одновременно с тем в большинстве случаев многоиндексная выборка намного предпочтительнее использования только одного индекса и фильтрации значений по остальным атрибутам. В определенной степени это утверждение опирается на наиболее распространенные статистики применяемых данных. Соотношение эффективности различных методов поиска по нескольким индексам, безусловно, зависит от состояния данных.
Многоиндексную выборку можно применять также при смешанных индексах - одновременно использовать древовидные, составные и битовые индексы. Условием их совместности является одинаковость упорядочения искомых идентификаторов. В случае применения индексов разного вида соответственно следует изменить алгоритм выборки, чтобы он обращался к соответствующим операциям получения следующего идентификатора и для проверки существования идентификатора в индексных структурах. Вышеприведенные коды использовали простые индексы и соответственно использовали функции $o() и $d().
Замечание относительно одинаковости упорядочения важно также в отношении применения баз данных с различными соглашениями о сравнении символов (character collation), а также для тех MUMPS систем, в которых сортировка локальных переменных может отличаться от сортировки глобалов в случае если производится выборка из индексов или промежуточных индексных структур, расположенных в смешанном виде хранения - и в локальных и в глобальных переменных одновременно.
Подробнее о книге "MUMPS СУБД"
Комментариев нет:
Отправить комментарий