KeRRaS: Sort-Based Database Query Processing on Wide Tables Using FPGAs
Research output: Contribution to book/Conference proceedings/Anthology/Report › Conference contribution › Contributed › peer-review
Contributors
Abstract
Sorting is an important operation in database query processing. Complex pipeline-breaking operators (e.g., aggregation and equi-join) become single-pass algorithms on sorted tables. Therefore, sort-based query processing is a popular method for FPGA-based database system acceleration. However, most accelerators have a limit on the table width or the number of columns they can sort. This limit is often set by the width of the data path or the amount of BRAM present on the FPGA. In this paper we propose KeRRaS, an abstract sorting algorithm that enables existing sort-based query processors to support arbitrarily wide tables while offering scalability, preserving modularity, and having low resource overhead. Moreover, we present an implementation of KeRRaS based on morphing sort-merge, a resource-efficient FPGA-based query accelerator. The implementation behaves similarly to morphing sort-merge on narrow tables, and scales well as the number of key columns increases.
Details
| Original language | English |
|---|---|
| Title of host publication | Proceedings of the 19th International Workshop on Data Management on New Hardware, DaMoN 2023 |
| Pages | 1-9 |
| Number of pages | 9 |
| ISBN (electronic) | 9781450395076 |
| Publication status | Published - 18 Jun 2023 |
| Peer-reviewed | Yes |
External IDs
| Scopus | 85163778078 |
|---|---|
| Mendeley | 13955595-1d04-3527-9b30-04aeeb7c16ce |
Keywords
Research priority areas of TU Dresden
DFG Classification of Subject Areas according to Review Boards
Subject groups, research areas, subject areas according to Destatis
ASJC Scopus subject areas
Keywords
- database system, large key, FPGA, sorting, wide table