SOSD

SOSD是一个包含8个不同数据集的基准框架，由慕尼黑工业大学创建，用于评估学习型索引结构。每个数据集包含2亿个64位无符号整数，数据来源多样，包括书籍销售、Facebook用户ID、OpenStreetMap位置等。数据集创建过程中，使用了多种算法和技术来模拟和优化数据分布。该数据集主要应用于数据库索引结构的性能评估，旨在通过比较学习型索引与传统索引的性能，推动数据库索引技术的进步。

SOSD is a benchmark framework encompassing 8 distinct datasets, developed by the Technical University of Munich for evaluating learned index structures. Each dataset consists of 200 million 64-bit unsigned integers, sourced from diverse domains including book sales records, Facebook user IDs, OpenStreetMap location data, and others. During the dataset construction phase, various algorithms and techniques were utilized to simulate and optimize the data distributions. This benchmark framework is primarily used for performance evaluation of database index structures, with the goal of advancing database indexing technology by comparing the performance of learned indexes and traditional indexes.

搜集汇总

数据集介绍

构建方式

在数据库索引结构研究领域，SOSD基准测试框架的构建体现了严谨的实证研究范式。其核心在于整合了多样化的真实世界与合成数据集，例如来自亚马逊销售排名、Facebook用户ID以及维基百科编辑时间戳等八个不同领域的数据，每个数据集包含两亿个64位无符号整数键。框架采用C++实现并以开源形式发布，确保了实验的可复现性。构建过程特别注重底层性能，通过精心设计的数据加载与查询验证机制，将每次查找的额外开销控制在极低水平，为公平比较各类索引算法奠定了可靠基础。

特点

SOSD基准测试的显著特点在于其数据集与评估维度的双重多样性。数据集涵盖了从均匀分布、对数正态分布到高度偏斜的真实世界数据等多种累积分布函数形态，这有效检验了索引结构在不同数据特性下的鲁棒性。评估体系不仅关注最终的查找延迟，还深入剖析了缓存缺失、分支预测错误和执行指令数等底层硬件性能指标，为理解算法性能差异提供了多维度的洞察。该框架首次公开提供了高性能的递归模型索引实现，并囊括了从传统B树、自适应基数树到新兴的基于学习的索引等多种基线方法，构成了一个全面的对比平台。

使用方法

研究人员使用SOSD框架时，首先需在其提供的多样化数据集上运行待评估的索引算法。框架支持单线程下的千万次等值查找操作，并自动验证结果的正确性。用户可通过框架比较不同算法在查找延迟、内存开销和构建时间等方面的表现。更重要的是，SOSD集成了性能计数器分析功能，能够自动测量并关联缓存行为、分支预测与指令执行等微观架构事件，从而帮助研究者超越宏观计时，深入理解性能瓶颈的本质。这种使用方法旨在推动索引结构研究从单纯的速度竞赛，转向对算法与硬件交互机理的更深层次探索。

背景与挑战

背景概述

在数据库系统研究领域，随着机器学习技术的蓬勃发展，学者们开始探索将传统数据库组件替换为学习型模型的可能性。SOSD（Search on Sorted Data Benchmark）数据集于2019年由慕尼黑工业大学与麻省理工学院的研究团队联合推出，旨在为学习型索引结构提供一个标准化的评估框架。该数据集的核心研究问题聚焦于验证学习型索引是否能在真实世界数据上超越传统索引结构（如B树）的性能。通过集成多样化的真实与合成数据集，SOSD不仅推动了索引结构研究的实证比较，还为数据库社区的后续创新奠定了坚实基础，显著提升了学习型索引在数据管理领域的可信度与影响力。

当前挑战

SOSD数据集所针对的领域挑战在于解决学习型索引结构在性能评估中的标准化缺失问题。传统索引结构经过数十年优化，其效率已接近极限，而学习型索引虽在理论上具备潜力，但缺乏公开、可复现的基准测试来验证其实际优势。构建过程中的挑战包括数据集的多样性与代表性获取，需涵盖从均匀分布到高度偏斜的真实世界数据（如亚马逊销售排名、Facebook用户ID等），以确保评估的全面性。此外，实现高效且低开销的基准测试框架，并集成高度优化的传统索引基线，对技术实现提出了严峻要求。

常用场景

经典使用场景

在数据库系统与索引结构的研究领域，SOSD数据集作为基准测试框架，其经典使用场景聚焦于评估与比较各类学习型索引与传统索引在内存中搜索排序数据的性能。该数据集通过提供多样化的真实世界与合成数据分布，如亚马逊销售排名、Facebook用户ID及OpenStreetMap位置等，使研究者能够在统一环境下系统性地测试不同索引算法的查找延迟、缓存效率与空间开销，从而为学习型索引的可行性与优化方向提供实证依据。

实际应用

在实际应用层面，SOSD数据集为数据库系统与大数据处理引擎的索引设计与选型提供了关键参考。例如，在需要高效查询排序键值对的在线事务处理或实时分析系统中，开发者可依据SOSD的测试结果，针对特定数据分布选择最优索引策略。学习型索引通过拟合数据分布，能在亚马逊销售数据、维基百科时间戳等真实场景中显著降低查找延迟，同时减少内存占用，这对于云计算环境与边缘计算中资源受限的应用具有重要工程价值。

衍生相关工作

SOSD数据集的推出催生了一系列围绕学习型索引的经典衍生研究。例如，基于该基准测试的扩展工作ALEX提出了可更新的自适应学习型索引，解决了早期学习型索引难以支持动态更新的局限。同时，PGM索引等多标准压缩学习索引也借鉴了SOSD的评估方法，进一步探索了索引在空间效率与查询性能间的权衡。这些工作共同深化了学习型索引在并发访问、多维数据与硬件加速等方向的创新，形成了从理论到实践的完整研究脉络。