Заметки в этой статье действительно задержались на долгое время ==, но я не читал ее слишком внимательно, я просматривал ее несколько раз~
бумажный адрес ⬇️
The Case For Learned Index Structures
Introduction
Когда нам нужно запросить часть данных в базе данных, индекс данных в базе данных — это ответ, который нам нужен, и важность базы данных для нас очевидна.
В существующей структуре индекса дерево B+, несомненно, лучше всего подходит для запроса диапазона, хеш-таблица больше всего подходит для запроса kv, а фильтр Блума больше используется для запроса того, существует ли ключ в определенном наборе данных, но они структура индекса в основном основана на наихудшем случае данных, а чтение и запись оптимизированы относительно равномерно.Здесь автор приводит крайний пример для иллюстрации.Например,наш набор данных 1-100M,то если мы используем дерево B+ на на этот раз это на самом деле не самое разумное, потому что само значение ключа может быть использовано в качестве смещения.Если используется дерево B +, временная сложность O (1), несомненно, станет O (logn), и из-за к существованию индекса, памяти. Пространство также переходит от O (1) к O (n). другими словами,Когда мы поймем распределение данных, мы сможем оптимизировать индекс базы данных.
Основываясь на этой идее, в данной работе автор считает, что структуру индекса также можно рассматривать как модель, поскольку они также «предсказывают» положение заданного ключа, и в то же время исследуют B+-дерево и фильтрацию Блума в процесс ключ индекса базы данных → значение Степень, в которой эти традиционные структуры индекса могут быть заменены обученными сетевыми моделями.
В этом документе в основном обсуждается тип только для чтения, но также обсуждается, как расширить сценарий базы данных с большим количеством операций записи и меньшим количеством операций чтения.Что касается некоторых других операций в базе данных, таких как объединение и т. д., это будет будущей работой. , Направление выходит за рамки этой статьи.
Range Index
Для интервального запроса автор считает, что это сама модель.Когда значение ключа дается для прогнозирования положения индекса ключа, дерево B+ может быть заменено деревом регрессии, а размер страницы в дереве B+ эквивалентен максимальная и минимальная ошибка в модели ML. Но есть некоторые проблемы, когда мы хотим заменить дерево B+ моделью ML,
- Накладные расходы очень малы при вставке дерева B+ или поиске в памяти.
- Деревья B+ могут сопоставлять ключи дискретным дискам или страницам памяти.
- Если модель не является монотонно возрастающей, когда ключ не существует в наборе, модель может вернуть позицию, которая не находится в пределах максимальной и минимальной ошибок.
Однако для интервального поиска использование модели вместо дерева B+ по-прежнему будет иметь много преимуществ.Здесь автор приводит пример, похожий на введение, чтобы проиллюстрировать, что при использовании модели ML вместо дерева B+ сложность операции поиска будет от O(logn ) становится постоянной сложностью.Таким образом, основная проблема здесь заключается в том, как сбалансировать сложность модели с ее точностью.
Модель Range Index абстрагируется как CDF.
Когда индекс рассматривается как модель, в качестве входных данных используется ключ, а в качестве результата прогнозирования используется позиция записи, соответствующей ключу.Для точечного запроса порядок записей не имеет значения, но для интервальный запрос, данные должны быть для того, чтобы быть эффективными, чтобы найти соответствующие записи. В этом случае мы наблюдаем очень интересное явление, прогнозируя приблизительную кумулятивную функцию распределения (CDF) положения ключа в заданном упорядоченном массиве, мы можем смоделировать CDF данных, чтобы предсказать положение данных,
где p — оценка позиции, а F(Key) — предполагаемая CDF, используемая для оценки вероятности того, что x ≤ ключ, т. е.
, N — количество ключей. Есть несколько интересных выводов, сделанных при просмотре нового набора данных.
- Дерево B изучает распределение данных, строя дерево регрессии, а модель линейной регрессии может изучать распределение данных, минимизируя дисперсию линейного уравнения.
- Изучая дистрибутивы CDF, мы можем извлечь пользу из исследований последних лет.
- Изучение CDF играет ключевую роль в оптимизации других типов индексных структур и алгоритмов, которые будут рассмотрены далее в этой статье.
Затем автор попытался использовать временные метки в 200 млн записей журнала веб-сервиса в качестве набора данных для обучения модели.Двухслойная полносвязная нейронная сеть шириной 32 использует ReLU в качестве функции активации, временная метка в качестве входных данных, позиция в качестве метки, использование обучения модели TensorFlow с Python занимает около 80 000 наносекунд для обучения модели, а запрос почти не занимает времени, В отличие от B-дерева требуется всего около 300 наносекунд, чтобы найти те же данные, разница в два порядков, а поиск по всему ключевому пространству происходит примерно в 2-3 раза быстрее, что может быть вызвано следующими причинами,
- TensorFlow лучше подходит для больших моделей, особенно с использованием Python в качестве внешнего интерфейса.
- Для точности последней мили, хотя общее распределение данных выглядит близким к CDF и является очень гладким, при увеличении масштаба распределения данных в определенной точке мы обнаружим, что распределение данных очень неравномерно, поэтому как решить проблему? проблема точности последней мили очень важна
- В классической задаче машинного обучения конечной целью является уменьшение средней ошибки, но когда мы ищем индекс, мы надеемся получить наилучший прогноз и, в конечном счете, надеемся найти истинное положение ключа.
- Дерево B+ очень эффективно, потому что все узлы и индексы верхнего уровня находятся в кеше, но другие модели не могут воспользоваться преимуществами эффективности кеша.Например, если мы используем нейронную сеть, нам нужно использовать все веса для предсказания конечного результата.Если веса в памяти Стоимость будет выше
The RM Index
Чтобы решить проблему точности последней мили моделей ML, заменяющих деревья B +, в статье предлагается LIF и рекурсивное индексирование моделей, в основном с использованием простых полносвязных нейронных сетей.
The Learning Index Framework
LIF можно рассматривать как систему синтеза индексов.При наличии спецификации индекса LIF может генерировать различные конфигурации индексов, оптимизировать и автоматически тестировать, а также может изучать простые модели на лету или полагаться на TensorFlow для получения сложных моделей, но не использовать TensorFlow. , Прогнозы, и при наличии модели, обученной с помощью TensorFlow, LIF может автоматически извлекать веса и генерировать забавные индексные структуры на основе спецификаций. TensorFlow с использованием XLA может поддерживать компиляцию кода, но в основном используется для больших моделей, в отличие от LIF, ориентированного на небольшие модели, поэтому необходимо уменьшить много ненужных накладных расходов на управление большими моделями. , в настоящее время простая модель с вычислением LIF может быть выполнена всего за 30 наносекунд.
Эта часть содержимого в основном используется для решения проблемы временных затрат на переобучение модели при изменении распределения данных.
The Recursive Model Index
Для решения проблемы точности последней мили в статье предлагается модель рекурсивной регрессии. Трудно уменьшить ошибку со 100 млн до сотен порядков, используя одну модель, но очень легко уменьшить ошибку со 100 млн до 10 тыс. Использование модели для замены первых двух слоев B-дерева дает прирост точности 100 * 100 = 10000, опять же, уменьшить ошибку с 1000 до 100 легко, потому что модели нужно сосредоточиться только на подмножестве данных.
Поэтому в статье предлагается модель рекурсивной регрессии, как показано на рисунке.
Ключ в каждом слое используется в качестве входных данных, и на его основе выбирается другая модель, пока последний слой не предскажет окончательную позицию индекса.
Преимущество этой модели структуры состоит в том, что,
- Легко узнать общее распределение данных
- Разделите все пространство на более мелкие подинтервалы, каждый из которых подобен B-дереву или дереву решений, что упрощает решение проблемы точности последней мили.
- Нет необходимости искать между разными слоями.Например, выход y модели 1.1 является смещением, которое может быть непосредственно использовано для выбора модели следующего слоя.
Еще одним преимуществом рекурсивного индексирования модели является возможность использовать смесь моделей, таких как верхний слой, вероятно, нейронная сеть, использующая ReLU, является лучшей, потому что она может изучать большой диапазон сложных распределений данных, но нижняя модель может использовать простая модель линейной регрессии, потому что накладные расходы времени и пространства относительно меньше, и в то же время, если распределение данных сложно изучить, мы можем даже установить порог и использовать традиционное B-дерево на финальном этапе.
Строки 4-10 реализуют обучение на основе вершинной модели и сохраняют ключ в пределах диапазона; строки 11-14 решают, использовать ли B-дерево вместо модели в соответствии с порогом.
стратегия поиска
В статье предложены три стратегии поиска:
- Модельный бинарный поиск: стратегия поиска по умолчанию, аналогичная традиционному бинарному поиску, разница в том, что начальная промежуточная точка устанавливается в результате предсказания модели.
- Предвзятый поиск: модифицированный на основе бинарного поиска, новая средняя точка устанавливается на основе стандартного отклонения σ модели последнего слоя, например, когда ключ больше, чем средний узел, средний = min(middle+σ, (middle +право)/2 )
- Предвзятый четвертичный поиск: поиск трех точек одновременно, pos-σ, pos, pos+σ, требует, чтобы ЦП параллельно получал несколько адресов данных из основной памяти.
в заключении
используемый набор данных
- Web log
- Map
- синтетический набор данных
Использование обучения модели в целом дает более чем на порядок сокращение времени запроса и пространства для хранения по сравнению с B-деревом, но применимый набор данных относительно ограничен.Например, при использовании набора данных временных меток веб-журнала для обучения, Из-за неравномерного распределения временных меток большинство вышеупомянутых плохих случаев опираются на B-деревья.Стратегия поиска более эффективна для веб-журналов, но для других наборов данных стратегия поиска малоэффективна.
Point Index
Для точечных запросов хеш-функция заменяется моделью.Основным здесь является не хранение, а уменьшение коллизий хэшей и уменьшение пространства для хранения ключей. Используйте модель для замены хеш-функции. Содержание обучения не имеет ничего общего с самим ключом и значением, а только изучает распределение CDF, потому что точечный запрос не может гарантировать, что ключ монотонно возрастает. Если нельзя гарантировать, что монотонно возрастает, то распределение самого ключа не соответствует распределению CDF. , когда обучающая CDF достаточно хороша, различение будет гарантировано, так что размер ключа M используется для расширения значения этого hash, чтобы гарантировать отсутствие коллизий.
Но если возникает коллизия, метод обработки такой же, как и у хеш-функции, с использованием связанного списка для ее обработки.
в заключении
После замены хеш-функции моделью время запроса не сокращается, но пространство под ключами эффективно уменьшается, что улучшает использование пространства.
Existence Index
Для определения того, существует ли ключ в наборе данных, текущий сценарий заключается в использовании фильтра Блума, но фильтр Блума имеет определенную долю ложных срабатываний.Если вы хотите повысить точность и уменьшить частоту ложных срабатываний, необходимо увеличить растровое изображение. Для хэш-функции мы ожидаем, что f(x) вызовет как можно меньше конфликтов с различными ключами, но для фильтра Блума мы ожидаем, что существующие ключи и несуществующие ключи будут находиться в своих собственных f(x). Чем больше внутренних конфликтов тем лучше, чтобы большее количество ключей могло быть представлено меньшим растровым изображением, мы хотим использовать модель ML вместо фильтра Блума, мы ожидаем, что будет обеспечен определенный ложный положительный результат и 0 ложных отрицательных результатов. В статье представлены два метода обучения фильтров Блума:
Думайте о фильтрах Блума как о проблеме классификации
Нам нужно обучить такую нейронную сеть, чтобы функция логарифмических потерь была минимальной. Чтобы удовлетворить условию, что ложный отрицательный результат равен 0, мы создаем фильтр Блума переполнения и изучаем модель в соответствии с порогом.Когда выходной результат больше или равен порогу, мы думаем, что ключ существует в наборе , а когда оно меньше порога, то переходим к проверке фильтра Блума переполнения.
Проще говоря, это означает разделить существующий ключ и несуществующий ключ на два набора данных, а затем объединить их в один набор для обучения, чтобы минимизировать функцию потери журнала.
Изучение фильтров Блума с использованием хэшей моделей
Рассмотрение фильтра Блума как проблемы классификации противоречит самой хеш-функции в фильтре Блума, поскольку ни один интервал не имеет ненулевого FNR, мы можем использовать f (x) для отображения в битовый массив m, диапазон отображения f ( x) равно [0,1], поэтому мы можем предположить, что d выглядит следующим образом, роль состоит в дискретизации пространства,
Таким образом, мы можем использовать d(f(x)) в качестве хэш-функции, которая может отображать существующий ключ в старший бит бита и отображать несуществующий ключ в младший бит бита.
f(x) ∈ [0,1], когда ключа не существует, f(x) ближе к 0, в противном случае ближе к 1, поэтому ключ в основном распределен в старшей позиции, а не- ключ в основном распределяется в нижнем положении.
в заключении
Использование пространства действительно улучшилось, и чем выше точность модели, тем меньше памяти она занимает, но сравнительных данных, подтверждающих это, нет.