Избыток данных в мире открыл множество возможностей для изучения и анализа поведения людей по всему миру. Для большинства анализов требуется, по крайней мере, несколько дней данных, если не больше, что приводит к необходимости быстрого запрашиваемого механизма хранения. Базы данных OLAP существуют только для этой цели, то есть для облегчения запросов к огромным объемам данных с минимальными задержками.

Чтобы минимизировать задержку, все базы данных имеют индексы, созданные на основе данных. Индекс, как правило, представляет собой древовидную структуру, такую ​​как B-tree, R-Tree и т. Д., Которая на основе некоторого фиксированного ключа напрямую предоставит вам строку или блок, содержащий данные, вместо того, чтобы сканировать все строки.

Уникальная проблема с базами данных OLAP заключается в том, что запросы могут выполняться сразу по нескольким столбцам, например. запрос для получения общего количества заказов по пользователям, дате и городу. Технически вы можете создавать индексы и по нескольким измерениям, но вам придется делать предположения о том, каким шаблонам запросов будет следовать пользователь. Вы также должны предположить, какой объем данных будет содержать каждый столбец, чтобы принять эффективное решение об индексировании.

Что, если бы сама база данных адаптировала свой индекс в соответствии с введенными данными? Усвоенные многомерные индексы - это попытка решить эту конкретную проблему. В этом блоге мы рассмотрим один из этих алгоритмов.

Наводнение

Алгоритм Flood был разработан для индексов в памяти. Его также можно изменить для использования в базах данных OLTP. За Flood стоят две ключевые идеи:

  1. Используйте образец рабочей нагрузки фильтра запроса, чтобы определить, как часто используются определенные измерения, какие из них используются вместе, а какие более избирательны, чем другие. Основываясь на этой информации, настройте весь макет для оптимизации производительности.
  2. Используйте эмпирические модели CDF для сглаживания многомерных искаженных данных в однородное пространство.

Предположим, необходимо создать индекс для d-мерных данных. В таких данных нет естественного порядка сортировки. Итак, алгоритм сначала выбирает измерение, которое будет использоваться для сортировки. Затем алгоритм создает размерную сетку d-1, в которой каждое измерение разделено на столбцы с равным интервалом. Каждая ячейка в такой сетке содержит несколько точек данных.

Чтобы обеспечить равномерное распределение точек данных, они нормализуются с использованием минимального и максимального значений конкретного измерения. Последнее измерение используется для сортировки данных в каждой ячейке.

Запрос

Запрос обычно состоит из k измерений, где k ‹d. Поскольку запрос уже содержит диапазон значений для каждого измерения, которое необходимо запросить, мы можем просто выбрать все ячейки, которые лежат в этом диапазоне, а также ячейки, которые частично перекрываются. Этот шаг известен как проекция.

Для ячеек, которые частично перекрываются, мы можем использовать тот факт, что данные в них отсортированы, и выбрать соответствующие данные с помощью двоичного поиска. Это возможно только при наличии измерения сортировки как части запроса. Этот шаг известен как «Уточнение».

Когда у нас есть все данные, мы можем дополнительно их уточнить, чтобы проверить, есть ли какие-либо данные вне диапазона, а затем вернуть результат пользователю. Этот шаг известен как сканирование.

Оптимизация макета

Основная сила FLOOD заключается в его способности оптимизировать структуру данных для минимизации задержки запроса. Чтобы минимизировать задержку, вам сначала понадобится прокси для определения производительности запроса. Алгоритм для достижения этой цели использует настраиваемую функцию стоимости. Функция стоимости состоит из трех частей:

  • wpNc, где wp - среднее время выполнения уточнения ячейки, а Nc - общее количество ячеек в сетке.
  • wrNc, где wr - среднее время выполнения уточнения ячейки, а Nc - общее количество ячеек в сетке.
  • wsNs, где ws - среднее время выполнения каждого сканирования, а Ns - общее количество просканированных точек данных.

Затем модель времени запроса может быть рассчитана как -

wpNc + wrNc + wsNs

Следующим шагом является вычисление весов wp, wr и ws. Для этого Flood использует простую модель, которая принимает такие характеристики, как общее количество ячеек, среднее значение, медиана и хвостовой квантиль размеров фильтруемых ячеек, количество измерений и т. Д. Flood только один раз тренирует весовую модель и использует ее повторно. это для нескольких макетов данных.

Последним шагом является оптимизация макета, который состоит из работы с размерами для измерения сортировки и количеством столбцов в каждом измерении.

На каждой итерации алгоритм выбирает одно из измерений d в качестве измерения сортировки. Остальные размеры используются для создания размерной сетки d-1. Затем он запускает алгоритм градиентного спуска, чтобы определить количество столбцов, которое минимизирует время запроса.

Flood перенастраивает структуру данных для каждой новой рабочей нагрузки. Поскольку администратор БД не может сгенерировать наиболее вероятные запросы для использования в качестве входных данных для модели, Flood сам генерирует запросы для обучения, рандомизируя одни измерения для группировки, другие - для фильтрации и оставляя остальные. Группировка по агрегатным функциям также рандомизирована.

Заключение

Алгоритм Flood знаменует собой важную веху на пути самообучения индексов. Это очень практично и может использоваться в реальной базе данных, как показано в документе. Однако Flood по-прежнему страдает недостатками, которые необходимо исправить, чтобы сделать его полностью универсальным алгоритмом. Некоторые из этих недостатков -

  • Он не поддерживает вставку новых данных. В случае поступления новых данных необходимо заново подогнать весь набор данных. Текущая версия предназначена для использования только для рабочих нагрузок только для чтения.
  • Он однопоточный и не может поддерживать параллелизм в текущей реализации.
  • Хотя Flood повторно настраивается на новую рабочую нагрузку, он все еще пытается определить, когда рабочая нагрузка изменилась настолько, чтобы можно было запустить операцию перенастройки.

В конце концов, я надеюсь, что эти проблемы будут исправлены в будущем, и базы данных OLAP в конечном итоге станут, по крайней мере, на порядок быстрее, как показано в документе.

Вы можете использовать следующие ссылки, чтобы узнать больше о полученных структурах данных и индексах: