iSearch: seek acceleration through interpolation in smart storage settings

Modern database management systems (DBMS) face significant challenges when executing analytical tasks on exponentially growing datasets, often relying on search operation for key lookup. Traditional optimization methods focus on minimizing execution times in host-based systems. In contrast, smart storage devices enable offloading of query plan execution on-device, presenting opportunities for new optimizations. However, these devices operate under strict computational constraints and necessitate efficient resource management. Prevailing DBMS implementations predominantly employ binary search, because of its performance and robustness. In contrast, interpolation search algorithms yield considerable computational savings in smart storage settings, however they are not always robust. In this paper, we propose a novel adaptive search algorithm iSearch, which combines a configurable number of interpolation search iterations with a fallback to binary search. This hybrid approach ensures robust and predictable runtime performance, regardless of the underlying data distribution. We further demonstrate that commodity consumer devices benefit more from adaptive search approaches than traditional host systems, highlighting the potential for improved performance and efficiency in both contexts.