Поиск по критериям - tsafin/tarantool GitHub Wiki

Задача:

Есть пространство из N кортежей. Объявлен индекс по некоторому количеству K полей, то есть заданы K пар {field_no, field_type}, где field_no различны. Обозначим F - множество этих field_no.

Индекс должен осуществлять поиск кортежей по подмножеству значений полей объявления индекса, то есть в запросе заданы условия поиска - R пар {field_no, value}, где field_no различны и ∈ F. Обозначим множество field_no запроса как FR. Поиск должен находить кортежи, у которых каждое поле field_no равно соответствующему value из параметра запроса.

Ожидаемое применение - поиск первых limit кортежей из всех кортежей пространства, удовлетворяющих условиям поиска и отсортированных по значению(ям) какого(их)-то поля(ей).

Вариант решения 1, условно назовем его блюм-дерево.

Задается хэш-функция H(a, b, c) и натуральное число h.

Каждому кортежу сопоставляется слово W из B бит, в котором установлены все биты (H(i, f, v) % B), где i = 1..h, f ∈ F, v - это значение поля f в кортеже; остальные биты - нулевые. Листовые узлы дерева содержат до M кортежей, и хранят свое слово W, равное побитовое ИЛИ всех слов W кортежей листа. Узлы ветвления содержат до M дочерних узлов, и хранят свое слово W, равное побитовое ИЛИ всех слов W детей. Все листовые узлы имеют один уровень, дерево всегда сбалансировано. Нахождение кортежей в дереве выбирается таким образом, чтобы минимизировать суммарное количество установленных бит в словах W всех узлов.

Для поиска вычисляется слово W запроса, у которого установлены все биты (H(i, f, v) % B), где i = 1..h, f ∈ FR, v - это значение поля f в запросе; остальные биты - нулевые. Интересующие кортежи могут находится только в поддеревьях с корнем в узле, слово W которого имеет установленными все биты слова W запроса. Для поиска надо обходить узлы дерева начиная с корня, пропуская те узлы, у которых не установлен хотя бы один нужный бит.

Вставка. При вставке в поддерево с корнем в определенном узле необходимо установить в этом узле все биты слова W кортежа. Поэтому при вставке надо рекурсивно вставлять кортеж в такое из поддеревьев, чтобы увеличение суммарного количества установленных бит было минимальным. Если у узла становится M + 1 детей (или кортежей - у листовых узлов), узел надо расщепить: выбрать среди слов W детей двух наиболее непохожих, таким образом получив двух лидеров каждый со своим словом W; остальных детей последовательно причислить к одному из двух лидеров, дополняя его слово W, выбирая его (лидера) таким образом, чтобы приращение количества установленных бит было минимальным; также надо следить чтобы одна из получившихся групп не стала более чем в два раза больше второй. Получившиеся группы будут новыми узлами дерева и их надо добавить в родителя взамен расщепляемого.

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

Дополнительную сложность представляет выборка результата в соответствие с критерием сортировки, возможно это удастся сделать по аналогии с поиском knn в R-tree.

Вариант решения 2, условно назовем его GIN.

Создается K Б-деревьев, по одному на каждое field_no из F, в каждое укладываются все N кортежей, упорядоченных по: [соответствующее field_no поле]<дополнительные поля сортировки результата>[указатель на кортеж]. Дополнительные поля сортировки результата одинаковы во всех деревьях.

Для поиска выбираются R соответствующих field_no деревьев и в них выбираются диапазоны соответствующих значений value. Диапазоны упорядочены по одинаковому критерию; надо найти кортежи, присутствущие во всех диапазонах, в порядке того же критерия. Выборка кортежей происходит следующими итерациями до тех по пока хотя бы один из диапазонов не станет пустым:

1)среди начал диапазонов выбирается минимальное и максимальное (здесь и далее - в смысле критерия <дополнительные поля сортировки результата>[указатель на кортеж]). Если они совпадают - то кортеж во всех началах диапазонов одинаковый и относится к результату; записываем его в результат, все начала диапазонов передвигаем на следующую позицию, итерация закончена.

2)начало диапазона с минимальным кортежем передвигаем на позицию, бОльшую или равную максимальным кортежем. Делать это нужно не более чем log2(N) переходами к следующей позиции, после чего осуществляется поиск в соответствующем дереве по ключу [соответствующий value]<дополнительные поля сортировки результата максимального кортежа>[указатель на максимальных кортеж] с условием больше-либо-равно. Нужный кортеж пока не найден, итерация закончена.

Добавление/удаление кортежей в индекс - это просто добавление/удаление кортежей во все K деревьев.