Перейти к основному содержимому

Использование Bitmap для точного Count Distinct

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

Битовые карты являются полезным инструментом для вычисления количества уникальных значений в массиве. Этот метод занимает меньше места для хранения и может ускорить вычисления по сравнению с традиционным Count Distinct. Предположим, есть массив A с диапазоном значений [0, n). Используя битовую карту размером (n+7)/8 байт, можно вычислить количество уникальных элементов в массиве. Для этого нужно инициализировать все биты как 0, установить значения элементов в качестве индексов битов, а затем установить все биты в 1. Количество единиц в битовой карте равно количеству уникальных элементов в массиве.

Традиционный Count Distinct​

Selena использует архитектуру MPP, которая может сохранять детальные данные при использовании Count Distinct. Однако функция Count Distinct требует множественных перемешиваний данных во время обработки запросов, что потребляет больше ресурсов и приводит к линейному снижению производительности по мере увеличения объема данных.

Следующий сценарий вычисляет UV на основе детальных данных в таблице (dt, page, user_id).

dtpageuser_id
20191206game101
20191206shopping102
20191206game101
20191206shopping101
20191206game101
20191206shopping101

Selena вычисляет данные согласно следующей схеме. Сначала группирует данные по столбцам page и user_id, а затем подсчитывает обработанный результат.

alter

  • Примечание: На рисунке показана схема вычисления 6 строк данных на двух узлах BE.

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

Подсчет uv с группировкой по page:

select page, count(distinct user_id) as uv from table group by page;

|  page   |   uv  |
| :---: | :---: |
|   game  |  1   |
|   shopping  |   2  |

Преимущества Count Distinct с Bitmap​

Вы можете получить следующие преимущества от битовых карт по сравнению с COUNT(DISTINCT expr):

  • Меньше места для хранения: Если использовать bitmap для вычисления количества уникальных значений для данных INT32, требуемое место для хранения составляет только 1/32 от COUNT(DISTINCT expr). Selena использует сжатые roaring bitmaps для выполнения вычислений, что еще больше сокращает использование места для хранения по сравнению с традиционными битовыми картами.
  • Более быстрые вычисления: Битовые карты используют побитовые операции, что приводит к более быстрым вычислениям по сравнению с COUNT(DISTINCT expr). В Selena вычисление количества уникальных значений может обрабатываться параллельно, что приводит к дальнейшему улучшению производительности запросов.

Для реализации Roaring Bitmap см. конкретную статью и реализацию.

Примечания по использованию​

  • И bitmap индексирование, и bitmap Count Distinct используют технику bitmap. Однако цель их введения и проблемы, которые они решают, совершенно разные. Первое используется для фильтрации перечисляемых столбцов с низкой кардинальностью, а второе используется для вычисления количества уникальных элементов в столбцах значений строки данных.
  • Selena 2.3 и более поздние версии поддерживают определение столбца значений как BITMAP независимо от типов таблиц (Aggregate table, Duplicate Key table, Primary Key table или Unique Key table). Однако sort key таблицы не может быть типа BITMAP.
  • При создании таблицы можно определить столбец значений как BITMAP, а агрегатную функцию как BITMAP_UNION.
  • Roaring bitmaps можно использовать только для вычисления количества уникальных значений для данных следующих типов: TINYINT, SMALLINT, INT и BIGINT. Для данных других типов необходимо построить глобальные словари.

Count Distinct с Bitmap​

Рассмотрим пример вычисления UV страниц.

  1. Создайте Aggregate table со столбцом BITMAP visit_users, который использует агрегатную функцию BITMAP_UNION.

    CREATE TABLE `page_uv` (
      `page_id` INT NOT NULL COMMENT 'page ID',
      `visit_date` datetime NOT NULL COMMENT 'access time',
      `visit_users` BITMAP BITMAP_UNION NOT NULL COMMENT 'user ID'
    ) ENGINE=OLAP
    AGGREGATE KEY(`page_id`, `visit_date`)
    DISTRIBUTED BY HASH(`page_id`)
    PROPERTIES (
      "replication_num" = "3",
      "storage_format" = "DEFAULT"
    );

  2. Загрузите данные в эту таблицу.

    Используйте INSERT INTO для загрузки данных:

    INSERT INTO page_uv VALUES
    (1, '2020-06-23 01:30:30', to_bitmap(13)),
    (1, '2020-06-23 01:30:30', to_bitmap(23)),
    (1, '2020-06-23 01:30:30', to_bitmap(33)),
    (1, '2020-06-23 02:30:30', to_bitmap(13)),
    (2, '2020-06-23 01:30:30', to_bitmap(23));

    После загрузки данных:

    • В строке page_id = 1, visit_date = '2020-06-23 01:30:30' поле visit_users содержит три элемента bitmap (13, 23, 33).
    • В строке page_id = 1, visit_date = '2020-06-23 02:30:30' поле visit_users содержит один элемент bitmap (13).
    • В строке page_id = 2, visit_date = '2020-06-23 01:30:30' поле visit_users содержит один элемент bitmap (23).

    Загрузка данных из локального файла:

    echo -e '1,2020-06-23 01:30:30,130\n1,2020-06-23 01:30:30,230\n1,2020-06-23 01:30:30,120\n1,2020-06-23 02:30:30,133\n2,2020-06-23 01:30:30,234' > tmp.csv | 
    curl --location-trusted -u <username>:<password> -H "label:label_1600960288798" \
        -H "column_separator:," \
        -H "columns:page_id,visit_date,visit_users, visit_users=to_bitmap(visit_users)" -T tmp.csv \
        http://StarRocks_be0:8040/api/db0/page_uv/_stream_load

  3. Вычислите UV страниц.

    SELECT page_id, count(distinct visit_users) FROM page_uv GROUP BY page_id;
    +-----------+------------------------------+
    |  page_id  | count(DISTINCT `visit_users`)|
    +-----------+------------------------------+
    |         1 |                            3 |
    |         2 |                            1 |
    +-----------+------------------------------+
    2 row in set (0.00 sec)

Global Dictionary​

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

Global Dictionary на основе Hive таблицы​

Глобальный словарь в этой схеме сам является Hive таблицей, которая имеет два столбца: один для исходных значений и один для закодированных Int значений. Шаги для генерации глобального словаря следующие:

  1. Дедуплицировать столбцы словаря фактовой таблицы для генерации временной таблицы
  2. Выполнить левое соединение временной таблицы и глобального словаря, добавить новое значение во временную таблицу.
  3. Закодировать новое значение и вставить его в глобальный словарь.
  4. Выполнить левое соединение фактовой таблицы и обновленного глобального словаря, заменить элементы словаря на ID.

Таким образом, глобальный словарь может быть обновлен, а столбцы значений в фактовой таблице могут быть заменены с использованием Spark или MR. По сравнению с глобальным словарем на основе дерева trie, этот подход может быть распределенным, и глобальный словарь может быть переиспользован.

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

Построение глобального словаря на основе дерева trie​

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

Построив глобальный словарь и преобразовав другие типы данных в целочисленные данные, можно использовать Bitmap для выполнения точного анализа Count Distinct нецелочисленных столбцов данных.