An eight-dimensional systematic evaluation of optimized search algorithms on modern processors

• Published in: Proceedings of the VLDB Endowment 2018-07, Vol.11 (11), p.1550-1562
• Main Authors: Schulz, Lars-Christian, Broneske, David, Saake, Gunter
• Format: Article
• Language: English
• ISSN: 2150-8097; 2150-8097
• DOI: 10.14778/3236187.3236205

Searching in sorted arrays of keys is a common task with a broad range of applications. Often searching is part of the performance critical sections of a database query or index access, raising the question what kind of search algorithm to choose and how to optimize it to obtain the best possible performance on real-world hardware. This paper strives to answer this question by evaluating a large set of optimized sequential, binary and k-ary search algorithms on a modern processor. In this context, we consider hardware-sensitive optimization strategies as well as algorithmic variations resulting in an eight-dimensional evaluation space. As a result, we give insights on expected interactions between search algorithms and optimizations on modern hardware. In fact, there is no single best optimized algorithm, leading to a set of advices on which variants should be considered first given a particular array size.