Хотя таблицы фактов часто имеют более 100 столбцов, типичный запрос хранилища данных одновременно обращается только к 4-5 из них (запросы «SELECT *» редко нужны для аналитики). Возьмем запрос в примере 3-1: он обращается к большому количеству строк (каждый случай покупки фруктов или конфет в течение 2013 календарного года), но ему нужно обратиться только к трём столбцам таблицы fact_sales: date_key, product_sk и quantity. Запрос игнорирует все остальные столбцы.

В большинстве OLTP баз данных хранение данных осуществляется в виде строк: все значения из одной строки таблицы хранятся рядом друг с другом. Базы данных документов устроены аналогичным образом: весь документ обычно хранится как одна непрерывная последовательность байт. Это можно увидеть в примере с CSV на рисунке 3-1.

Для обработки запроса, похожего на Пример 3-1, вам нужны индексы на fact_sales.date_key и/или fact_sales.product_sk, которые указывают механизму хранения, где найти все продажи за определенную дату или для определенного продукта. Но тогда ориентированному на строки механизму хранения всё равно нужно загрузить все эти строки (каждая из которых состоит из более чем 100 атрибутов) с диска в память, разобрать их и отфильтровать те, которые не соответствуют требуемым условиям. Это может занять много времени.

Идея хранения, ориентированного на столбцы, проста: не храните все значения из одной строки вместе, а храните все значения из каждого столбца вместе. Если каждый столбец хранится в отдельном файле, запрос должен читать и разбирать только те столбцы, которые используются в запросе, что может сэкономить много работы. Этот принцип показан на рисунке 3-10.

Ориентированная на столбцы схема хранения основана на том, что каждый файл столбцов содержит строки в одном и том же порядке. Таким образом, если вам нужно собрать всю строку, вы можете взять 23-ю запись из каждого отдельного файла столбцов и собрать их вместе, чтобы сформировать 23-ю строку таблицы.

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

Посмотрите на последовательности значений для каждого столбца на рисунке 3-10: они часто выглядят повторяющимися, что является хорошим поводом для сжатия. В зависимости от данных в столбце можно использовать различные методы сжатия. Одним из методов, который особенно эффективен для хранилищ данных, является растровое кодирование, показанное на рисунке 3-11.

Часто количество различных значений в столбце невелико по сравнению с количеством строк (например, у розничной компании могут быть миллиарды операций по продаже, но только 100 000 различных товаров). Теперь мы можем взять столбец с n различными значениями и превратить его в n отдельных битовых карт: по одной битовой карте для каждого отдельного значения, с одним битом для каждой строки. Бит равен 1, если в строке есть это значение, и 0, если нет.

Если n очень мало (например, столбец страны может иметь около 200 различных значений), эти битовые карты можно хранить с одним битом в строке. Но если n больше, то в большинстве битовых карт будет много нулей (мы говорим, что они разреженные). В этом случае битовые карты могут быть дополнительно последовательно закодированы, как показано в нижней части рисунка 3-11. Это делает кодирование столбца очень компактным.

Подобные растровые индексы очень хорошо подходят для запросов, которые часто встречаются в хранилище данных. Например:

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

Для запросов к хранилищу данных, которые должны сканировать миллионы строк, большим узким местом является пропускная способность передачи данных с диска в память. Однако это не единственное узкое место. Разработчики аналитических баз данных также беспокоятся об эффективном использовании полосы пропускания из основной памяти в кэш процессора, избежании ошибок предсказания ветвлений и пузырей в конвейере обработки инструкций процессора, а также об использовании инструкций типа SIMD (single-instruction-multi-data — одиночный поток команд, множественный поток данных) в современных процессорах.

Помимо сокращения объёма данных, которые необходимо загружать с диска, ориентированные на столбцы схемы хранения также позволяют эффективно использовать циклы процессора. Например, механизм запросов может взять кусок сжатых данных столбцов, который легко помещается в кэше L1 процессора, и просмотреть его в жестком цикле (то есть без вызовов функций). Процессор может выполнить такой цикл гораздо быстрее, чем код, требующий большого количества вызовов функций и условий для каждой обрабатываемой записи. Сжатие столбцов позволяет поместить больше строк из столбца в тот же объем кэша L1. Операторы, такие как побитовые AND и OF, описанные ранее, могут быть разработаны для обработки таких кусков сжатых столбцов напрямую. Эта техника известна как векторная обработка.

Для хранилища столбцов не всегда важно, в каком порядке хранятся строки. Проще всего хранить их в том порядке, в котором они были вставлены, поскольку тогда вставка новой строки означает просто добавление ее к каждому из файлов столбцов. Однако мы можем указать порядок, как мы это делали ранее с SSTables, и использовать его в качестве механизма индексирования.

Обратите внимание, что нет смысла сортировать каждый столбец независимо, потому что тогда мы уже не будем знать, какие элементы в столбцах принадлежат одной и той же строке. Мы можем восстановить строку только потому, что знаем, что k-й элемент в одном столбце принадлежит к той же строке, что и k-й элемент в другом столбце.

Скорее, данные нужно сортировать по целой строке за раз, несмотря на то, что они хранятся по столбцам. Администратор базы данных может выбрать
столбцы, по которым следует сортировать таблицу, используя свои знания о распространенных запросах. Например, если в запросах часто используются диапазоны дат, например, последний месяц, то, возможно, имеет смысл сделать date_key первым ключом сортировки. Тогда оптимизатор запросов сможет сканировать только строки за последний месяц, что будет намного быстрее, чем сканирование всех строк.

Второй столбец может определять порядок сортировки всех строк, которые имеют одинаковое значение в первом столбце. Например, если date_key является первым ключом сортировки на рисунке 3-10, то имеет смысл сделать product_sk вторым ключом сортировки, чтобы все продажи одного и того же продукта в один и тот же день были сгруппированы в хранилище. Это поможет запросам, которым нужно сгруппировать или отфильтровать продажи по продуктам в определенном диапазоне дат.

Еще одно преимущество сортированного порядка заключается в том, что он может помочь в сжатии столбцов. Если в столбце первичной сортировки не так много отдельных значений, то после сортировки в нем будут длинные последовательности, где одно и то же значение повторяется много раз подряд. Простое кодирование по длине строки, похожее на то, что мы использовали для растровых изображений на рисунке 3-11, может сжать этот столбец до нескольких килобайт — даже если таблица содержит миллиарды строк.

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

Отличное развитие этой идеи было представлено в C-Store и использовано в коммерческом хранилище данных Vertica. Разные запросы получают пользу от разных порядков сортировки, так почему бы не хранить одни и те же данные, отсортированные несколькими разными способами? Данные в любом случае необходимо реплицировать на несколько машин, чтобы не потерять их в случае сбоя одной машины. С тем же успехом можно хранить избыточные данные, отсортированные разными способами, чтобы при обработке запроса можно было использовать ту версию, которая лучше всего соответствует шаблону запроса.

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

Эти оптимизации имеют смысл в хранилищах данных, поскольку значительная часть нагрузки состоит из больших запросов на чтение, выполняемых аналитиками. Хранение, ориентированное на столбцы, сжатие и сортировка помогают сделать эти запросы на чтение быстрее. Однако их недостатком является усложнение процесса записи.

Обновление на месте, как в B-деревьях, невозможно при использовании сжатых столбцов. Если бы вы захотели вставить строку в середину отсортированной таблицы, вам, скорее всего, пришлось бы переписать все файлы столбцов. Поскольку строки идентифицируются по их положению в столбце, при вставке необходимо последовательно обновить все столбцы.

К счастью, мы уже видели хорошее решение ранее в этой главе: LSM-деревья. Все записи сначала поступают в резидентное хранилище, где они добавляются в отсортированную структуру и подготавливаются для записи на диск. Не имеет значения, ориентировано ли резидентное хранилище на строки или на столбцы. Когда накапливается достаточное количество записей, они объединяются с файлами столбцов на диске и записываются в новые файлы в массовом порядке. По сути, это то, что делает Vertica.

Запросы должны проверить как данные столбцов на диске, так и последние записи в памяти, и объединить их. Однако оптимизатор запросов скрывает это различие от пользователя. С точки зрения аналитика, данные, которые были изменены вставками, обновлениями или удалениями, немедленно отражаются в последующих запросах.

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

Ещё один аспект хранилищ данных, о котором стоит кратко упомянуть — это материализованные агрегаты. Как обсуждалось ранее, запросы к хранилищам данных часто включают агрегатную функцию, такую как COUNT, SUM, AVG, MIN или MAX в SQL. Если одни и те же агрегаты используются во многих разных запросах, то каждый раз перебирать исходные данные может быть ресурсозатратно. Почему бы не кэшировать некоторые подсчеты или суммы, которые наиболее часто используются в запросах?

Одним из способов создания такого кэша является материализованное представление. В реляционной модели данных оно часто определяется как стандартное (виртуальное) представление: объект типа таблицы, содержимое которого является результатами некоторого запроса. Разница в том, что материализованное представление — это реальная копия результатов запроса, записанная на диск, в то время как виртуальное представление — это просто ярлык для записи запросов. Когда вы читаете из виртуального представления, механизм SQL расширяет его до базового запроса представления на лету, а затем обрабатывает расширенный запрос.

Когда базовые данные изменяются, материализованное представление необходимо обновить, поскольку оно является денормализованной копией данных. База данных может сделать это автоматически, но такие обновления делают запись более ресурсозатратной, поэтому материализованные представления не часто используются в базах данных OLTP. В хранилищах данных с высокой нагрузкой на чтение они могут иметь больше смысла (действительно ли они улучшают производительность чтения, зависит от конкретного случая).

Частным случаем материализованного представления является куб данных или OLAP-куб. Он представляет собой сетку агрегатов, сгруппированных по различным измерениям. На рисунке 3-12 показан пример.

Представьте сейчас, что каждый факт имеет внешние ключи только к двум таблицам измерений — на рисунке 3-12 это дата и продукт. Теперь вы можете нарисовать двумерную таблицу, где даты расположены вдоль одной оси, а продукты — вдоль другой. Каждая ячейка содержит агрегированный результат (например, SUM) атрибута (например, net_price) всех фактов с данной комбинацией даты и продукта. Затем вы можете применить тот же агрегат к каждой строке или столбцу и получить сводку, уменьшенную на одно измерение (продажи по продуктам с учетом даты или продажи по дате независимо от продукта).

В целом, факты часто имеют более двух измерений. На рисунке 3-9 имеется пять измерений: дата, продукт, магазин, акция и клиент. Намного сложнее представить, как будет выглядеть пятимерный гиперкуб, но принцип остается тем же: каждая ячейка содержит продажи для определенной комбинации —дата — продукт — магазин — промо-акция — клиент. Затем эти значения можно многократно суммировать по каждому из измерений.

Преимущество материализованного куба данных заключается в том, что определённые запросы становятся очень быстрыми, поскольку они фактически уже предварительно вычислены. Например, если вы хотите узнать узнать общий объём продаж по магазину за вчерашний день, достаточно посмотреть итоговые значения по соответствующему измерению — не нужно сканировать миллионы строк.

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

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

На высоком уровне мы увидели, что системы хранения данных делятся на две обширные категории: оптимизированные для обработки транзакций (OLTP) и оптимизированные для аналитики (OLAP). Модели доступа в этих случаях использования сильно различаются:

Что касается OLTP, то здесь мы увидели системы хранения данных двух
основных типов:

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

Завершая рассмотрение OLTP, мы провели краткий экскурс по более сложным структурам индексирования и базам данных, оптимизированным для хранения всех данных в памяти.

Затем мы отвлеклись от внутреннего устройства систем хранения и рассмотрели высокоуровневую архитектуру типичного хранилища данных. Эта история показала, почему аналитические рабочие нагрузки так отличаются от OLTP: когда ваши запросы требуют последовательного сканирования большого количества строк, индексы гораздо менее актуальны. Вместо этого становится важным кодировать данные очень компактно, чтобы минимизировать объем данных, которые запрос должен прочитать с диска. Мы обсудили, как ориентированное на столбцы хранение помогает достичь этой цели.

Если вы — разработчик приложений — вооружены этими знаниями о внутреннем устройстве систем хранения данных, вы сможете лучше понять, какой инструмент лучше всего подходит для вашего конкретного приложения. Если вам нужно изменить параметры настройки базы данных, это понимание позволит вам представить, какой эффект может оказать большее или меньшее значение.

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