KeRRaS: Sort-Based Database Query Processing on Wide Tables Using FPGAs

Research output: Contribution to book/Conference proceedings/Anthology/ReportConference contributionContributedpeer-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 languageEnglish
Title of host publicationProceedings of the 19th International Workshop on Data Management on New Hardware, DaMoN 2023
Pages1-9
Number of pages9
ISBN (electronic)9781450395076
Publication statusPublished - 18 Jun 2023
Peer-reviewedYes

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

Keywords

  • database system, large key, FPGA, sorting, wide table