近似查询处理的资源分配优化

# 近似查询处理的资源分配优化 ## 1 引言 在查询处理中，资源分配的优化至关重要。尤其是在资源受限的情况下，如何合理分配资源以达到最佳的查询质量是一个关键问题。本文将介绍一种近似查询处理的资源分配优化算法，该算法可以在资源受限的条件下，为查询提供尽可能好的结果质量。 ## 2 理论基础 ### 2.1 引理 2 设 $C$ 为关键路径，$T$ 为可分配的资源量。对于每个 $op \in op(C)$，质量函数是线性的，即 $q(op)(t) = q(op) + s(op)t$，其中 $t$ 在质量函数的限制范围内。根据最优资源分配过程，存在 $op(C^+) \subseteq op(C)$ 使得：$t_p > 0$ 当且仅当 $p \in op(C^+)$；并且 \[ t_{op} = \max\left\{ \frac{T}{n} + \frac{1}{n} \sum_{p \in op(C^+)} \frac{q(p)}{s(p)} - \frac{q(op)}{s(op)}, 0 \right\} \] 其中 $op \in op(C)$，$n = |op(C^+)|$。 ### 2.2 引理 3 设 $C$ 为关键子树，$l, r \in op(C)$ 是具有线性质量函数的兄弟子树的两个根节点，即 $Q(l)(t) = Q(l) + S(l)t$ 和 $Q(r)(t) = Q(r) + S(r)t$，其中 $t$ 在质量函数的范围内，$T \in Time$ 是在这两个兄弟节点之间分配的资源量。根据最优资源分配过程，$T_l = \frac{S(r)}{S(l) + S(r)}T$ 和 $T_r = \frac{S(l)}{S(l) + S(r)}T$。 ## 3 资源分配算法 ### 3.1 算法和数据结构 该算法用于在固定查询执行计划上进行最优资源分配。具体步骤如下： 1. 首先，使用传统的优化技术构建一个不考虑资源量的查询计划。 2. 然后，将资源分配算法应用于该计划。 需要注意的是，这个计划不一定是全局最优的，但对于任何固定的树，该方法可以提供局部最优的计划。 根据前面的引理，可以有效地在两种类型的计划结构中分配资源： - 从根到叶的单路径（垂直路径）。 - 单个父节点的叶兄弟节点之间。 为了利用这些引理，需要从查询执行计划的某些部分构建虚拟超节点，然后在超节点内应用适当的引理。 虚拟超节点的构建规则如下： - 如果关键计划包含兄弟叶（超）节点，将这些兄弟节点收缩为一个超节点，该超节点成为父节点的单个子节点。 - 从叶到分裂点的任何路径收缩为一个垂直超节点，该超节点成为分裂点的叶子节点。 如果计划至少包含两个节点，上述两个步骤中至少有一个是适用的。当整个计划收缩为一个单一的超节点时，过程停止，因为根节点不能有兄弟节点，所以这个超节点总是垂直的。 超节点的质量函数构建如下： - 原始树节点的质量函数由相应操作的成本模型提供。 - 超节点的质量函数在创建超节点时构建。 由于引理要求每个操作（节点）的质量是分配资源的线性函数，但超节点的质量不一定能总是表示为线性函数，因此用线性近似代替，这使得算法成为近似算法（除了少数特殊情况）。水平（兄弟）超节点的质量函数根据引理 3 是线性的，而垂直节点的质量函数通常不是线性的，需要用线性近似来代替，并且在参数值的特定范围内有效。 超节点的范围构建方式应确保相应的资源量可以始终分配给该超节点的子节点，而不违反超节点内的约束。 整体资源分配控制流程的伪代码如下： ```plaintext Input: Query tree P, resource for allocation T. Output: For all operations op ∈ op(P) allocated amount of resources t_op. Initialization(P, T) while T > 0 &!isMaxQualityReached(P) do QualityEstimation(P) C = CriticalSubtreeConstruction(P) H = HypergraphConstruction(C) ResourceAllocation(H, T) end while ``` 算法概述如下： - 初始化阶段：为 $P$ 中的每个操作分配等于最小所需的资源，并调整质量函数以接受增量。如果最小资源的总和超过 $T$，则算法失败，因为使用可用资源无法执行该计划。 - 初始分配最小所需资源后，剩余的资源以增量形式分配。增量需要满足以下约束： - 任何节点的线性段边界不被超过。 - 关键子查询的质量不应超过其非关键兄弟查询的质量。 - 增量分配重复进行，直到所有可用资源耗尽或达到查询的最大可能质量。 - 对于每个增量步骤，重新计算关键子树和超节点结构，然后递归地将分配过程应用于所有超节点，在每个超节点内使用适当的引理进行分配。 可以证明，该算法在查询评估计划的节点数量上具有多项式复杂度。 ### 3.2 水平超节点 根据引理 3，分配给水平超节点的