sware

ПО: индексирование с учетом сортировки

Исходный код для подачи статьи на ICDE 2023: «Индексирование почти отсортированных данных».

О

Репозиторий содержит исходный код для реализаций B+tree и SWARE. В текущей версии кода обе реализации являются универсальными, но файлы приложений, проверяющие эти структуры индексных данных, поддерживают только целочисленный тип данных. Кроме того, файлы приложения используют одно и то же значение как для ключа, так и для значения каждой записи. Будущие расширения кода будут поддерживать более крупные типы данных.

Обе структуры данных требуют выделения пула буферов во время выполнения кода, который можно расширить до необходимого объема, если необходимо полностью выполнить его в памяти. Распределение буферного пула определяется количеством блоков, каждый из которых имеет размер 4 КБ. Например, если вы используете выделение блоков размером 1 МБ, то для древовидной структуры данных вы выделяете 1 М*4 КБ = 4 ГБ памяти.

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

Как бежать

Создание рабочей нагрузки по приему

Используйте генератор данных сортировки из этого репозитория: https://github.com/BU-DiSC/bods для генерации ключей приема (можно указать размер полезной нагрузки = 0, чтобы генерировать только ключи). Как упоминалось выше, файлы приложения используют одно и то же значение как для ключа, так и для значения каждой записи (пара K,V). Запишите путь к созданной рабочей нагрузке.

B+ Дерево

1. скомпилировать с помощью команды «make bplustree»
2. Запустите исполняемый файл в следующем формате:

./ test_base_index < ingestion_workload_path > < output_file_name > < buffer_pool_allocation > < K > < L > < #. queries >

Например, вы можете использовать:

./ test_base_index createdata_1000000 - elems_100000 - K_100000 - L_1seed1632764083 . dat sample . txt 1000000 100000 100000 200000

Здесь мы принимаем рабочую нагрузку из 1 миллиона записей/ключей с K=L=100 000. Мы используем кеш буферного пула для блоков размером 1 млн и выполняем запросы на 200 000 точек. Задержки вывода как для приема, так и для точечных запросов записываются в файл «sample.txt».

Дерево SA B+

1. скомпилировать с помощью команды «make satree»
2. Запустите исполняемый файл в следующем формате:

./ test_satree < ingestion_workload_path > < output_file_name > < buffer_pool_allocation > < K > < L > < #. entries > < swareBuffer allocation > < fill factor % >  < #. queries >

Например, вы можете использовать:

/ test_satree createdata_1000000 - elems_10 - K_10 - L_1seed1632764083 . dat swaresample . txt 1000000 10 10 1000000 10000 95 200000

Здесь мы принимаем рабочую нагрузку из 1 млн записей/ключей с K=L=100 000 (10% от общего числа записей). Мы используем кеш буферного пула для блоков размером 1 млн и выполняем запросы на 200 000 точек. Задержки вывода как для приема, так и для точечных запросов записываются в файл «swaresample.txt». Буфер в памяти будет содержать 10 000 записей (1% от 1М), и мы поддерживаем коэффициент заполнения 95%.