Page 9 - 《软件学报》2026年第2期

488 软件学报 2026 年第 37 卷第 2 期

本文第 1 节给出问题定义, 介绍多维查询与学习型索引的基本概念. 第 2 节描述 LA-tree 的索引结构与整体
算法框架. 第 3 节提出多层次查询感知的数据划分方法. 第 4 节提出基于学习模型的高效在线筛选方法. 第 5 节进
一步探讨自适应增量更新机制, 以应对动态场景下的数据和查询负载变化. 在第 6 节中, 我们通过多种数据集和查
询负载的实验, 评估了 LA-tree 在静态与动态环境下的性能表现. 第 7 节回顾相关研究工作. 最后, 第 8 节对全文
进行总结.

1 问题定义

本文针对多维结构化数据上的范围/等值查询, 研究高效多维索引的构建与查询处理问题. 本节将介绍所需的
基本概念, 并给出问题的形式化定义.
● 多维数据: 根据多维数据模型 [7,8] 定义多维数据, 数据表包含多行多列 (属性), 每行代表一条数据记录, 对应
一个多维空间内的点; 每列代表一个属性, 对应多维空间的一个维度. 例如, TPC-H 交易订单数据表 Lineitem 以价
T
格、货量、折扣等多个维度描述交易数据. 形式化地, 考虑一个 n 行 d 列的数据表 , 包含 n 条数据记录 T =
⟨ ⟩
{t 1 ,t 2 ,...,t n }, 以及 d 个维度 A = {a 1 ,a 2 ,...,a d }, 每条记录可以表示为一个 d 维向量 t l = v t l ,a 1 ,v t l ,a 2 ,...,v t l ,a d , 而对数据
[ ]
a j
表 T 取单独一维度 a j 投影, 即为一大小为 n 的数组 T = v t 1 ,a j ,v t 2 ,a j ,...,v t n ,a j .
● 多维查询: 在多维数据的基础上定义多维查询. 用户经常从多个角度同时查询多维数据, 例如, 对于 TPC-H
交易订单事实数据表 Lineitem, 筛选出同时满足价格小于等于 2 000 000、货量大于等于 10、折扣小于等于 5 的订
单, 即是一条典型的多维查询, “SELECT * FROM LINEITEM T WHERE L_EXTENDEDPRICE<=2000000 AND
L_QUANTITY>=10 AND L_DISCOUNT<=5;”. 本文聚焦多维数据上的范围查询, 也可很自然地推广至等值查询.
形式化地, 定义多维查询, 一条同时包含多个范围约束谓词 (涵盖点查询) 的 SQL 查询形如:
SELECT * FROM T WHERE P 1 AND P 2 AND ... AND P p ;
其中, 每个范围约束谓词 P x 作用在某个维度 (如 a j ) 上: lb x ⩽ a j ⩽ ub x . SQL 查询的谓词也可以拓展到含 OR 逻辑
连词的情形, 可以被转化为析取范式加以处理. 本文遵循多维索引研究的惯例, 为更好突出多维属性范围查询, 针
对谓词仅包含 AND 逻辑连词的查询展开讨论. 注意到多条范围约束可能作用在同一维度上, 显然可以合并这些

谓词, 最终将多维属性范围查询描述为多维数据 T 对应的有限多维空间中的一个超立方体范围: ]∧
q : [lb q,a 1 ,ub q,a 1
], 其中每个范围 ] 的两端也可以闭区间或开区间. 特别地, 若查询 q 在某维
[lb q,a 2 ,ub q,a 2 ]∧...∧[lb q,a d ,ub q,a d [lb q,a j ,ub q,a j
a j
a j
度 a j 上没有任何约束条件, 则相应范围约束等价于该维度值域范围 [min{T },max{T }].
{ }
● 查询负载: 在查询定义的基础上, 定义查询负载 Q = q 1 ,q 2 ,...,q |Q| 为查询的集合. 通常, 一个查询负载 Q 中
的查询并非完全随机的, 而是具有一定的分布特征, 比如每条查询谓词的维度组合服从一定的分布, 以及每条查询
对应超立方体的位置和大小服从一定的分布.
● 问题定义: 最后给出多维索引功能, 即检索查询结果的形式化定义. 在数据 T 上在线查询 q, 索引 I T (q) 返回
查询范围内的所有数据条目行号集合, 即:

{ }
,t i ∈ T,∀a j ∈ A (1)
I T (q) = i | lb q,a j ⩽ v t i ,a j ⩽ ub q,a j
利用多维索引进行查询处理时, 一般包括两个基本的步骤.
● 步骤 1: 筛选. 根据查询谓词约束, 过滤掉不相关的数据, 留下可能满足查询条件的候选扫描集.
● 步骤 2: 扫描. 将候选扫描集中的每一条数据与查询谓词进行对比, 得出最终的查询结果.
′ ′′
这里, 不妨将索引的筛选和扫描步骤输出的结果分别表示为两个单独的集合 I (q) 和 I (q), 得到:
T T
{ }
′
T
I (q) = i | v t i ,a j ∈ R q ,t i ∈ T,∀a j ∈ A (2)
其中, R q 是索引根据查询 q 的谓词范围筛选出的一个更粗略的空间范围, 保证 q ⊆ R q . 结合公式 (1) 和公式 (2) 得
{ }

′′ ′ I (q) 越小, 索引扫
′
到 ,i ∈ I (q),∀a j ∈ A , 其中 R q 包含 q 越紧, 候选扫描集大小
T
I T (q) = I (q) = i | lb q,a j ⩽ v t i ,a j ⩽ ub q,a j T T
描耗时越少, 也即索引筛选效果越好. 这里我们引出度量索引筛选效果的一个重要指标: 扫描比 ScanRatio(I T (q)),
即候选扫描集大小相对最终查询结果集大小的比值. 具体计算如下: