Page 20 - 《软件学报》2026年第2期
P. 20

刘佳伟 等: LA-tree: 查询感知的自适应学习型多维索引                                                  499


                    (2) 数据集  TPC-H Lineitem  是最常见的  OLAP  基准测试数据, 包含商品交易的事实记录, 其特点是数据记录
                 规模较大、维度值域广, 但维度间相关性较弱.
                    (3) 数据集 DSB Sales 由  Ding  等人  [12] 设计, 是较新的  OLAP  基准测试集合, 包含大量交易记录. 其特点是数据
                 记录规模较大、维度数量高, 因此本文选用该数据集用于评估多维索引在高维数据下的性能表现.


                                           表 1 实验所用的数据集与查询负载统计情况

                      数据集        数据表行数 (M)      数据表维度       查询负载      查询维度             查询谓词范围
                                                             Uniform    1–4       均匀分布, 谓词宽度正态分布
                      Stock           20            7
                                                              Skew      1–4      向极值倾斜, 谓词宽度指数分布
                                                             Uniform    2–5       均匀分布, 谓词宽度正态分布
                   TPC-H Lineitem     3             8
                                                              Skew      2–5      向极值倾斜, 谓词宽度指数分布
                                                             Uniform    2–5       均匀分布, 谓词宽度正态分布
                     DSB Sales        6            34         Skew      2–5      向极值倾斜, 谓词宽度指数分布
                                                              HD        7–33            同Uniform

                    由于多维索引主要关注查询谓词对数据表多维属性范围的同时约束, 部分数据表没有附带查询或附带查询不
                 符合实验场景, 我们用随机模板的方式构造了查询负载. 具体来说, 先随机生成多个模板, 每个模板覆盖数据表的
                 部分属性维度. 之后在生成查询的过程中, 第             1  步随机选择一个模板, 第     2  步服从查询负载设置的查询范围分布随
                 机生成模板包含的每个属性维度上的约束范围, 合起来作为查询谓词. 该方法既符合模板法查询生成的惯例, 又保
                 证了查询的随机性和多样性. 在此基础上, 我们构造了均匀                  (Uniform) 和倾斜  (Skew) 两种谓词范围分布不同的查
                 询负载, 其中, Uniform  查询负载谓词的中点位置、范围宽度关于数据值域均匀分布; Skew                     查询负载谓词的中点
                 位置、范围宽度关于数据值域指数分布. 此外, 针对高维数据集                   DSB Sales 构造了高维   (high-dimensional, HD) 查
                 询负载, 使每条查询谓词约束的属性维度提高              3–15  倍, 更加具有挑战性.
                  6.2   评价指标、对比方法和实验设计
                    (1) 实验  1: 静态场景. 多维索引主要应用场景侧重于优化在线查询性能, 而数据更新不频繁, 且现有工作对更
                 新功能考虑较少. 因此, 我们按照现有工作惯例, 先评测最重要的静态场景中的索引查询性能, 其评测指标如下.
                    ● 在线查询平均用时. 这是首要指标, 即对于测试集每条查询, 计算从调用索引在线查询入口函数到该函数返
                 回包含所有查询范围内数据的指针的数组的用时, 再求平均用时. 进一步地, 我们分析多维索引查询过程中筛选和
                 扫描两个阶段的用时, 但在索引内部函数中反复计时会显著干扰索引性能使测试结果失真, 因而我们通过两个常
                 用且关键的指标间接对比索引在两个阶段分别的用时.
                    ● 在线查询平均扫描比. 计算索引扫描的数据条目数和查询范围内数据条目数的比值, 由于小基数的查询易
                 使该指标突增     (尽管扫描的数据条目数仍然很少), 故计算执行整个查询负载测试集的扫描比而非每个查询平均扫
                 描比. 一般来说, 若该指标较小, 索引扫描查询范围外的条目数较少自然扫描阶段开销较小, 筛选效果较好.
                    ● 在线查询平均访问单元数量. 计算索引平均一条查询筛选出需访问的单元数量. 一般来说, 若该指标较小,
                 说明索引在筛选阶段用时较短, 也即筛选效率较高.
                    ● 索引离线构建用时和索引大小. 作为次要指标, 虽然索引性能以在线查询性能为主要指标, 也应该兼顾合理
                 的离线构建用时和索引大小.
                    ● 基准方法. 分为传统和学习型两类. 传统方法包括              Clustered、KD-tree 和  Octree. 其中, Clustered  是单维索引,
                 仅对查询负载谓词中选择度最低的属性维度建立排序索引, 由一次二分查找直接获得查询结果, 用于模拟数据库系
                                                                                              [2]
                                         [1]
                 统中最常用的聚簇索引. KD-tree 是经典的多维空间划分二叉树, 常用于高效的多维索引使用. Octree 是经典的三
                 维空间划分八叉树, 一般用作空间索引, 我们参考现有工作                 [4,5] 对其的拓展, 令每个节点随机任选数据表的          3  个维度
                                                                                        [3]
                 做三维空间划分, 使其作为多维索引使用. 学习型方法包括                 Qd-tree 和  Tsunami. 其中, Qd-tree 总是在查询边缘对
                 数据做划分, 对查询负载训练集强拟合, 考虑到查询较多, 所有查询边缘全部参与划分使得分片过于细碎, 大幅增加
                 索引占用空间大小同时反而拖累在线查询性能, 我们在每个数据集的每个查询负载上都为                             Qd-tree 分别调优了划分
   15   16   17   18   19   20   21   22   23   24   25