Основы технологий хранения баз данных в памяти

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

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

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

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

строки макете, и макете столбчатой планировки.  Введем такие понятия, как

сжатие и разбиение. Основываясь на этом, получим пояснение внутренних шагов, выполняемых в базе данных для выполнения фундаментальных реляционных операций вставки, обновления и удаления. Как вывод, поясним фундаментальное отличие базы данных «в памяти» SanssouciDB от большинства других баз данных: вставка только подход.  Следуя данной концепции, мы обходим несколько ошибок, касающиеся реляционной целостности и дополнительно получаем основу для создания меньшего зазора для функций, требующих времени

Фокус на легких весовых методах баз данных
• Для вектора атрибута
•

префикс кодирование
• кодирование длин серий
• кластерное кодирование
• разреженное кодирование
• косвенное кодирование
• Для словаря
• сжатие Дельта для строк
• другие типы данных хранятся в отсортированных массивах

с тем,  что столбец содержит одно доминирующее значение, а остальные

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

явном виде каждый раз, когда оно встречается. Это достигается за

счет сохранения количества вхождений преобладающего значения и наличия одного экземпляра самого значения в векторе атрибута. Таким образом, вектор атрибут префикс кодирования содержит следующую информацию:
• число вхождений преобладающего значения
• valueID преобладающего значения из словаря
• valueIDs остальных значений.

того же значения;
• лишь одно преобладающее значение имеется в столбце,

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

отсортирован по численности населения стран в порядке убывания. Таким образом,

1,4 млрд граждан Китая перечислены вначале, затем граждане Индии и так далее. ValueID для Китая, который принял значение 37 в словаре (см. 7.1а), хранится 1,4 миллиарда раз в начале вектора атрибута в несжатом формате. В сжатом формате valueID 37 будет записано только один раз, а затем остальные valueIDs для других стран, как и в несжатом. Число вхождений ‘’1,4 миллиарда'' для Китая будет храниться в явном виде. Рисунок 7.1b представляет примеры несжатых и сжатых векторов атрибутов.

для хранения всех 200 стран рассчитывается как log2(200), что дает

8 бит.
Без сжатия вектор атрибут сохраняет 8 бит для каждого valueID 8 миллиардов раз:
8 миллиардов * 8 бит ~ 8 миллиардов байт ~ 7,45 ГБ
Если применить к столбцу стран префикс-кодирование, valueID для Китая сохраняется только один раз в 8 битах вместо 1,4 миллиарда раз по 8 бит. Дополнительное 31-битовое поле добавляется для хранения количества вхождений :
log2 (1,4 млрд) = 31 бит
Следовательно, вместо того, чтобы хранить 1,4 миллиарда раз 8 бит, только 31 бит + 8 бит = 39 бит действительно необходимы. Полное пространство для хранения сжатого вектора атрибутов теперь:
(8 млрд - 1,4 млрд) * 8 бит + 31 бит + 8 бит ~ 6,15 ГБ

экономится. Еще одно преимущество кодирования префикс - это прямой доступ

с вычислением номера строки. Например, чтобы найти всех мужчин - граждан Китая, система управления базой данных может определить, что только последовательности с номерами строк от 1 до 1,4 млрд следует рассматривать, а затем отфильтровать по гендерному значения.
Несмотря на то, что мы видим, что мы сократили необходимый объем оперативной памяти, очевидно, что мы по-прежнему храним много избыточной информации для всех других стран.
Поэтому рассмотрим метод кодирования длин серий (Run-Length Encoding).

метод сжатия, который работает лучше всего, если вектор атрибута состоит

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

Пример: колонка стран, таблица отсортирована по численности населения страны

стартовой позиции в виде смещения. Сохранение начальной позиции ускоряет доступ.

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

Применительно к нашему примеру столбца стран отсортированного по населению, вместо того, чтобы хранить все 8 миллиардов значений (7,45 ГБ), мы сохраняем два вектора:
• один со всеми различными значениями: 200 раз по 8 бит
• другой со стартовой позицией: 200 раз по 33 бит (33 бита необходимы для хранения смещения по 8 млрд (log2(8 млрд) = 33 бит). Дополнительное 33-битовое поле в конце этого вектора хранит число вхождений для последнего значения (последней страны).

1 Кбайт без потери информации:
200 * (33 бит + 8

бит ) + 33 бит ~ 1 KB

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

(обычно 1024)
• если кластер содержит только одно значение, оно заменено

единственным возникновения этого значения
• бит вектор длины N указывает, какие кластеры были заменены одним значением

Пример: колонка город таблицы, отсортированной по странам, городам
Размер кластера: 1024 элементов  7.8 млн блоков
В худшем случае предположение: 1 несжатый блок на город
Несжатые блоки: 1 млн х 1024 х 20 бит 2 441 Мб
Сжатые блоки: (7.8 – 1) млн х 20 бит + 16 Мб
Бит вектор: 7.8 млн х 1 бит + 1 Мб ~ 2.4 Гб
Вычисление позиции с помощью бит вектора/

указывает, из каких позиций V удаляли из исходной последовательности
Пример: 2-я

национальность, колонка независит от порядка сортировки таблицы
Предположение: 99% людей не имеют 2-й национальности
Бит вектор 8 млрд х 1 бит 954 Мб
Вектор атрибут разреженного кодирования
8 млн х 7 бит +67 Мб
Значение + 7 бит ~1Гб

Если блок содержит только несколько различных значений, используется дополнительный словарь

для кодирования значений в этом блоке
• Дополнительно: ссылки на новые словари + блоки, которые имеют словарь

Пример: колонка Fname, таблица отсортировано по странам
Предположение: каждый набор 1024 человек в той же стране в среднем содержит 200 различных имен
Словари: (200 х 23 бит + 64 бита) х #block 4.2 Гб

Адрес словаря 7.8 млн
Вектор сжатия: 8 млрд х 8 бит 7.6 Гб ~ 11.8 Гб

(как правило, 16 строк на блок)

отсортированных наборов для задействования всего своего потенциала, но таблицы базы

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