Evaluating Learned Indexes for External-Memory Joins
<|reference_start|>Evaluating Learned Indexes for External-Memory Joins: In this paper, we investigate the effectiveness of utilizing CDF-based learned indexes in indexed-nested loop joins for both sorted and unsorted data in external memory. Our experimental study seeks to determine whether the advantages of learned indexes observed in in-memory joins by Sabek and Kraska (VLDB 2023) extend to the external memory context. First, we introduce two optimizations for integrating learned indexes into external-memory joins. Subsequently, we conduct an extensive evaluation, employing hash join, sort join, and indexed-nested loop join with real-world and simulated datasets. Furthermore, we independently assess the learned index-based join across various dimensions, including storage device types, key types, data sorting, parallelism, constrained memory settings, and increasing model error. Our experiments indicate that B-trees and learned indexes exhibit largely similar performance in external-memory joins. Learned indexes offer advantages in terms of smaller index size and faster lookup performance. However, their construction time is approximately $1000\times$ higher. While learned indexes can be significantly smaller ($2\times$-$4\times$) than the internal nodes of a B-tree index, these internal nodes constitute only 0.4 to 1% of the data size and typically fit in main memory in most practical scenarios. Additionally, unlike in the in-memory setting, learned indexes can prioritize faster construction over accuracy (larger error window) without significantly affecting query performance.<|reference_end|>
@article{chesetti2024evaluating,
    title={Evaluating Learned Indexes for External-Memory Joins},
    author={Yuvaraj Chesetti and Prashant Pandey},
    journal={arXiv preprint arXiv:2407.00590},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.00590},
    primaryClass={cs.DB}
}