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. Intel claims that their 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.