Разделы презентаций


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

Содержание

ПланСжатиеМакет данныхРазбиениеВставкаОбновлениеУдалениеТолько вставкаCompressionData LayoutPartitioningInsertUpdateDeleteInsert Only

Слайды и текст этой презентации

Слайд 1Основы технологий хранения баз данных в памяти
Лекция 2

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

Слайд 2План
Сжатие
Макет данных
Разбиение
Вставка
Обновление
Удаление
Только вставка
Compression
Data Layout
Partitioning
Insert
Update
Delete
Insert Only

ПланСжатиеМакет данныхРазбиениеВставкаОбновлениеУдалениеТолько вставкаCompressionData LayoutPartitioningInsertUpdateDeleteInsert Only

Слайд 31. Кодирование словарей
Поскольку память является новым узким местом ("бутылочным горлышком")

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

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

Слайд 4Кодирование словаря создает базу для ряда других методов сжатия, которые

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

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

Слайд 5В данной теме мы обсудим различия между горизонтальным, ориентированным на

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

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

Слайд 61. Сжатие

Методы сжатия

• Тяжелый вес в сравнении методами легкого веса

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

префикс кодирование
• кодирование длин серий
• кластерное кодирование
• разреженное кодирование
• косвенное кодирование
• Для словаря
• сжатие Дельта для строк
• другие типы данных хранятся в отсортированных массивах
1. СжатиеМетоды сжатия• Тяжелый вес в сравнении методами легкого веса• Фокус на легких весовых методах баз данных•

Слайд 7Пример

Пример

Слайд 81. Префикс - кодирование
В реальных базах данных, мы часто сталкиваемся

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

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

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

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

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

Слайд 10Префикс-кодирование:
• используется, если столбец начинается с длинной последовательности одного и

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

а остальные значения в основном уникальны или имеют низкое дублирование.
Пример: колонка стран, таблица отсортирована по численности населения страны.
Префикс-кодирование:• используется, если столбец начинается с длинной последовательности одного и того же значения;• лишь одно преобладающее значение

Слайд 11Дан вектор атрибута столбца стран из таблицы населения мира, который

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

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

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

для хранения всех 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 ГБ
Следующий расчет показывает степень сжатия. Прежде всего, количество бит, необходимых для хранения всех 200 стран рассчитывается как

Слайд 14Таким образом, 1,3 ГБ, то есть 17% пространства в памяти

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

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

Слайд 152. Кодирование длин серий (Run-Length encoded)
Кодирование длин серий представляет собой

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

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

Пример: колонка стран, таблица отсортирована по численности населения страны
2. Кодирование длин серий (Run-Length encoded)Кодирование длин серий представляет собой метод сжатия, который работает лучше всего, если

Слайд 16На рисунке 7.2 приведен пример кодирования длин серий с использованием

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

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

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

Слайд 17Следовательно, размер вектора атрибута может быть значительно уменьшен примерно до

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

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

Если хранить вектор числа вхождений (вариант а), одно поле из 33 бит может быть сэкономлено, но возникнет потеря возможности прямого доступа с двоичным поиском. Потеря прямого доступа приводит к увеличению продолжительности отклика, что нежелательно для управления корпоративными данными.
Следовательно, размер вектора атрибута может быть значительно уменьшен примерно до 1 Кбайт без потери информации:200 * (33

Слайд 19Кластерное кодирование
• вектор атрибутов разбивается на N блоков фиксированного размера

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

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

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

Кластерное кодирование• вектор атрибутов разбивается на N блоков фиксированного размера (обычно 1024)• если кластер содержит только одно

Слайд 20Разреженное кодирование
• Удалить значение V, который появляется чаще всего
Бит вектор

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

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

Разреженное кодирование• Удалить значение V, который появляется чаще всегоБит вектор указывает, из каких позиций V удаляли из

Слайд 21Косвенное кодирование
Последовательность разбивается на N блоков размером S (обычно 1024)

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

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

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

Адрес словаря 7.8 млн
Вектор сжатия: 8 млрд х 8 бит 7.6 Гб ~ 11.8 Гб
Косвенное кодированиеПоследовательность разбивается на N блоков размером S (обычно 1024)• Если блок содержит только несколько различных значений,

Слайд 22Дельта кодирование для словаря
• Для строковых отсортированных значений
• Блок-мудрое сжатие

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

Дельта кодирование для словаря• Для строковых отсортированных значений• Блок-мудрое сжатие (как правило, 16 строк на блок)

Слайд 23Что необходимо иметь в виду, что большинство методов сжатия требуют

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

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

Обратная связь

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

Email: Нажмите что бы посмотреть 

Что такое TheSlide.ru?

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


Для правообладателей

Яндекс.Метрика