Формат выполнения

Vector — это формат контейнера, используемый для хранения данных в памяти во время выполнения. DataChunk — это коллекция векторов, используемая, например, для представления списка столбцов в операторе PhysicalProjection.

Поток данных

DuckDB использует векторизованную модель выполнения запросов. Все операторы в DuckDB оптимизированы для работы с векторами фиксированного размера.

Этот фиксированный размер обычно упоминается в коде как STANDARD_VECTOR_SIZE. По умолчанию STANDARD_VECTOR_SIZE составляет 2048 кортежей.

Формат векторов

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

Плоские векторы

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

Векторы констант

Векторы констант физически хранятся как одно постоянное значение.

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

SELECT lst || 'duckdb'
FROM range(1000) tbl(lst);

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

Векторы констант также генерируются хранилищем при декомпрессии из константного сжатия.

Векторы словарей

Векторы словарей физически хранятся как дочерний вектор и вектор выбора, содержащий индексы в дочернем векторе.

Векторы словарей генерируются хранилищем при декомпрессии из словаря

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

Векторы последовательностей

Векторы последовательностей физически хранятся как смещение и значение приращения.

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

Единый формат векторов

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

Вместо этого, когда вам нужно использовать вектор независимо от типа, можно использовать UnifiedVectorFormat. Этот формат по сути представляет собой общий вид содержимого Vector. Каждый тип Vector может преобразовываться в этот формат.

Сложные типы

Векторы строк

Для эффективного хранения строк мы используем наш string_t класс.

struct string_t {
    union {
        struct {
            uint32_t length;
            char prefix[4];
            char *ptr;
        } pointer;
        struct {
            uint32_t length;
            char inlined[12];
        } inlined;
    } value;
};

Короткие строки (<= 12 bytes) встроены в структуру, а более длинные строки хранятся с указателем на данные в дополнительном буфере строк. Длина используется во всех функциях, чтобы избежать вызова strlen и постоянной проверки на null-указатели. Префикс используется для сравнений, как быстрый способ отсечения (когда префикс не совпадает, мы знаем, что строки не равны, и нам не нужно проверять указатели).

Векторы списков

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

struct list_entry_t {
    idx_t offset;
    idx_t length;
};

Смещение относится к начальной строке в дочернем векторе, длина отслеживает размер списка этой строки.

Векторы списков могут храниться рекурсивно. Для вложенных векторов списков дочерний элемент вектора списка — снова вектор списка.

Например, рассмотрим это имитационное представление вектора типа BIGINT[][]:

{
   "type": "list",
   "data": "list_entry_t",
   "child": {
      "type": "list",
      "data": "list_entry_t",
      "child": {
         "type": "bigint",
         "data": "int64_t"
      }
   }
}

Векторы структур

Векторы структур хранят список дочерних векторов. Количество и типы дочерних векторов определяются схемой структуры.

Векторы словарей

Внутри векторы словарей хранятся как LIST[STRUCT(key KEY_TYPE, value VALUE_TYPE)].

Векторы объединений

Внутри UNION используется та же структура, что и в STRUCT. Первый «дочерний» элемент всегда занят вектором тегов UNION, который регистрирует для каждой строки, какие из типов UNION применяются к этой строке.