Qd-дерево: обучение размещению данных для аналитики больших данных

Сегодня корпорации собирают данные в беспрецедентных и постоянно возрастающих масштабах, что делает всё более важной возможность выполнять запросы к большим наборам данных. Такие технологии, как столбцовая блочная организация данных и сжатие, стали стандартной практикой в большинстве коммерческих систем управления базами данных. Однако задача оптимального распределения записей по блокам данных в хранилище до сих пор остаётся нерешённой. Например, современные системы обычно разбивают данные на группы строк по времени поступления либо выполняют интервальное или хеш-разбиение данных на основе выбранных полей. Однако для заданной рабочей нагрузки такие методы не позволяют оптимизировать важную метрику — количество блоков, к которым обращается запрос. Эта метрика напрямую связана со стоимостью операций ввода-вывода (I/O) и, следовательно, с производительностью большинства аналитических запросов. Кроме того, существующие методы не позволяют использовать дополнительное доступное пространство хранения для дальнейшего снижения этой метрики. В данной статье мы предлагаем новую структуру, называемую деревом маршрутизации запросов и данных (query-data routing tree), или qd-деревом, для решения этой задачи, а также два алгоритма её построения, основанные на жадных методах и глубоком обучении с подкреплением. Эксперименты на эталонных и реальных рабочих нагрузках показывают, что qd-дерево может обеспечивать физическое ускорение более чем на порядок по сравнению с современными схемами блочного хранения и достигать результата, отличающегося менее чем в 2 раза от нижней границы пропуска данных, основанной на селективности, при этом предоставляя полные семантические описания созданных блоков.