FASTer search from Intel and Oracle

Databases are critical components in everyday computing. The current database market segment is $27 billion (by the technology analysis firm Forrester) and will grow to $32 billion by 2013. Search is one of fundamental operation in database.

We do search every day — basically search for a book in Amazon, and a movie title on Netflix etc. Tree index is often built to facilitate search. Traditional approaches to large database search operations have primarily been memory bound, and thus modern attributes of our multicore CPUs, like core count, on-die caches, SIMD and threads have only had limited performance benefit.

Intel’s Throughput Computing Lab, working in collaboration with Oracle’s Special Projects Group, has come up with an innovative algorithm, Fast Architecture Sensitive Tree search (FAST), for database search operation that delivers more than 5-fold improvement in CPU performance over any previously reported result.

This speedup comes from an architecture-friendly layout of the index tree, and a key compression scheme which together have transformed this traditionally memory-bandwidth bound problem into a compute-bound problem. Our approach eliminates impact of memory latency, and exploits on-die caches, and scales favorably with cores, SIMD width and threads.

Implementation of this approach to Intel’s recently announced, MIC architecture, Knights Ferry platform, delivers highest performance for both small and large tree sizes, over all previously claimed CPU and GPU performance results.

Prestigious database conference, ACM SIGMOD Award Committee has awarded this paper the Best 2010 Paper Award for its contribution to the field. Their citation further notes the ‘complete solution’ aspect of this research:

“This paper is an excellent research contribution that provides an end-to-end system design and associated algorithms and techniques to develop a complete solution that leverages the underlying hardware architecture. Given the modular structure of the overall design, the solution can easily be adapted to future architectures.”