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

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

度 a. 因此, 评分函数兼顾节点维度多样性, 有利于在线查询时的泛化性能.
● 证明优化公式 (7) 是优化公式 (6) 的上界. 先提出 Q-T 分布这一中间概念, 描述一个查询集合 Q 对一个数据
集合 T 不同区域数据的选择度, 也称 Q 在 T 不同区域的热度. 通过比较单个节点维度 a N k 的不同选择对其子节点
Q-T 选择对扫描量的影响.
分布的影响, 定量推导出节点维度
a N k
如图 3, Q N k 在 T N k 上的 Q-T 分布形如一个多维直方图, 每个格子代表 T N k 值域上的一个小区域, 其中的数值代
中查询范围与此区域有交集的查询数量占比, 可以理解为热度, 越高的区域越红. 在这个单独的 Q-T 分布和
表 Q N k
节点维度选择的例子中, a N k 选择 X 比 Y 好, 结合公式 (6) 理解, 较高的子节点 Q-T 分布热力值总和具有两个有利
于全局估计扫描比降低的良好性质. 首先, 任何查询的索引扫描比都不小于 1, 越高的子节点 Q-T 热力和意味着越
多不在查询结果中的数据条目已经被筛选到其他子树中, 被排除候选扫描集, 因此查询负载扫描比之和的上限越
低. 不失一般性地, 我们记考虑的数据表子集查询负载子集分别为 T 和 Q, 记 Q-T 分布为 H(Q,T) 且都把 T 划分为
m 个区域, 记节点维度选择为 a, 优化目标:

∑ ∑

min T (1− H(Q c ,T c ) p ) (8)
a∈A c,p
1⩽c⩽b 1⩽p⩽m
将公式 Q 中展开得到:
(8) 中每条查询从
∑ ∑ ∑

min T (1− H({q},T c ) ) (9)
p
a∈A c,p
1⩽c⩽b 1⩽p⩽m q∈Q c

X
[1,2] [3,4] [5,6] [7,8] [9,10] [11,12] [13,13]
Y
查询负载Q N k 数据表子集T N k
[2,3] 0 0.25 0.25 0.50 0 0 0
q 1 : SELECT* FROM T WHERE
3≤X≤7； [4,5] 0 0.25 0.50 0.75 0.25 0.25 0
id 1 2 3 4 5 6 7 8 9 10 11 12 13
q 2 : SELECT* FROM T WHERE [6,7] 0.25 0.50 0.75 1.00 0.50 0.50 0.25
5≤X≤12 AND 4≤Y≤10;
q 3 : SELECT* FROM T WHERE [8,9] 0.25 0.50 0.75 1.00 0.50 0.50 0.25 X 1 2 3 4 5 6 7 8 9 10 11 12 13
6≤Y≤14; [10,11] 0.25 0.50 0.75 1.00 0.50 0.50 0.25
q 4 : SELECT* FROM T WHERE
7≤X≤8 [12,13] 0.25 0.50 0.50 0.75 0.25 0.25 0.25 Y 14 13 12 11 10 9 8 7 6 5 4 3 2
[14,14] 0.25 0.50 0.50 0.75 0.25 0.25 0.25
按维度X划分 节点N k 上的Q-T分布 按维度Y划分
=X) X Y =Y)
(a N k (a N k
[1,5) [5,9) [9,14) [2,6) [6,10) [10,15)

X X X X X X
[1,2] [3,4] [5,6] [7,8] [9,11] [12,13] [10,11] [12,13] [6,7] [8,9] [1,3] [4,5]
Y Y Y Y Y Y
[11,12] 0.5 1.0 [7,8] 0.75 1.00 [2,4] 0.5 0.5 [2,3] 0 0 [6,7] 1.00 0.75 [10,2] 0.50 0.75
[13,14] 0.5 1.0 [9,10] 0.75 1.00 [5,6] 1.0 1.0 [4,5] 0.333 0.333 [8,9] 1.00 0.75 [13,14] 0.50 0.75
图 3 Q-T 分布及 LA-tree 节点选用不同划分维度对 Q-T 分布的影响

随 m 增大, Q-T 分布精度提升, 直至每个格子精确到仅单个数据条目. 此时我们记 S (q,T) 为一个 0-1 取值的
a
函数, 表示经过节点维度划分, 查询 q 是否需要进一步筛选数据表子集 ( T 值域相交), 公式 (9) 化简为
T q 是否与
∑ ∑ a
min a∈A |T c | S (q,T ), 标准化即推得公式 (7) 的节点维度选择优化比, 进一步可得评分函数 OPRS T,Q,N k (a), 该指
c
1⩽c⩽b q∈Q
b 个数据分位点之间的大小关
标的计算仅需判断查询负载子集中每个查询 q 的不同单维约束范围 [lb q,a ,ub q,a ] 与
系, 无需执行查询, 也无需计算 Q-T 分布.