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.

JavaScript Object Notation (JSON) gained popularity as a data exchange and storage format. While recent advances on modern CPUs show an improved JSON parsing by using data parallelism with vector instructions, the rigid instruction set and limited pipelining of CPUs prevent parsing performance from reaching the practical limit of memory bandwidth.

FPGA technology has introduced new ways to accelerate database query processing, that often result in higher performance and energy efficiency. This is thanks to the unique architecture of FPGAs using reconfigurable resources to behave like an application-specific integrated circuit upon programming. The limited amount of these resources restricts the number and type of modules that an FPGA can simultaneously support. In this paper, we propose "morphing sort-merge": a set of run-time configurable FPGA modules that achieves resource efficiency by reusing the FPGA's resources to support different pipeline-breaking database operators, namely sort, aggregation, and equi-join. The proposed modules use dynamic optimization mechanisms that adapt the implementation to the distribution of data at run-time, thus resulting in higher performance. Our benchmarks show that morphing sort-merge reaches an average speedup of 5x compared to MonetDB.

Re-Pair is a compression algorithm well-suited for applications that require random accesses to compressed data, but has not found widespread use in the data management community due to its prohibitively high compression times. As Re-Pair is a computationally expensive algorithm and FPGAs are becoming more and more common to accelerate such problems in data centers, we devise an FPGA system that performs Re-Pair compression. The system is implemented in OpenCL, aside from a hash table and sorting component realized in RTL for more control over the synthesized hardware. Our experiments demonstrate that an Intel Arria® 10 GX FPGA with our system compresses an order of magnitude faster than a highly-optimized CPU version of Re-Pair. We discuss further optimization opportunities and argue that our system can scale to being deployed on a more resourceful FPGA for even better performance.

As a result of recent improvements in FPGA technology, their benefits for highly efficient data processing pipelines are becoming more and more apparent. However, traditional RTL methods for programming FPGAs require knowledge of digital design and hardware description languages. OpenCL™ provides software developers with a C-based platform for implementing their applications without deep knowledge of digital design. In this paper, we conduct a comparative analysis of OpenCL and RTL-based implementations of a novel heapsort with merging sorted runs. In particular, we quantitatively compare their performance, FPGA resource utilization, and development effort. Our results show that while requiring comparable development effort, RTL implementations of critical primitives used in the algorithm achieve 4X better performance while using half as much the FPGA resources.

An efficient compression of integer vectors is critical in dictionary-encoded column stores like SAP HANA to keep more data in the limited and precious main memory. Past research focused on lightweight compression techniques that trade low latency of data accesses for lower compression ratios. Consequently, only few columns in a wide table benefit from light-weight and effective compression schemes like run-length encoding, prefix compression or sparse encoding. Besides bit-packing, other columns remained uncompressed, which clearly misses opportunities for a better compression ratio for many columns. Furthermore, the main executor for compression was the CPU as compression involves heavy data transfer. Especially when used with co-processors, the data transfer overhead wipes out performance gains from co-processor usage.