New hardware support for compute-intensive database and data stream operations
Divyakant Agrawal, Amr El Abbadi, Nagender Bandi · 2007
High performance database systems require both the software and hardware components of the system to deliver their best possible performance. While years of research by the database community has primarily focused on improving performance by developing better software techniques, relatively little effort has gone into hardware level innovations. Several important database problems such as polygon-related spatial database queries, conditional database joins and one-pass database summarization queries, are still computationally quite expensive to solve. Although several architecture-conscious solutions have been proposed, there is a limit to the performance improvement that can be achieved on current architectures. In this thesis, we take an alternative approach and propose novel hardware-based techniques using off-the-shelf graphics and networking hardware to augment the capabilities of modern database systems. We first develop the dual-threaded framework, which enables the integration of hardware-based techniques into a commercial database. Using modern graphics hardware as a co-processor, we propose a spatial query operator for answering intersection queries over polygon datasets. This operator, built using the dual-threaded framework, complements the existing index structures and optimizations of a spatial database. We next focus on developing faster database algorithms using Terenary Content Addressable Memories (TCAMs), which enable giga-bit rate forwarding at network routers. We propose the CAM-Cache architecture which integrates an off-the-shelf TCAM into the memory hierarchy of a conventional processor through the PCI interface. Using this architecture, we develop a fast sorting algorithm, which also functions as an index structure. We then develop a fast conditional join algorithm which uses the sorting algorithm as a basic component. Finally, we present fast TCAM-based solutions for solving the heavy hitters and heavy distinct hitters problems over data streams. We analyze several popular software solutions for detecting heavy hitters and heavy distinct hitters, discuss their bottlenecks and propose several TCAM-conscious solutions which address these issues. We develop all the TCAM-conscious solutions on a state-of-the-art network processing platform which interfaces with the TCAM over the SRAM bus.