自适应处理的近似查询技术解析

# 自适应处理的近似查询技术解析 ## 1. 处理算法的近似策略 在处理存储数据集时，为了应对高维数据（常见于数据仓库、多媒体和空间领域），提出了几种近似算法。这些算法可分为以下两种近似策略： ### 1.1 搜索空间缩减技术 该技术并非在整个数据空间中搜索解决方案，而是通过某种方式限制搜索空间，从而降低处理的计算成本，但可能会影响结果的准确性。通常，搜索空间缩减技术是通过修改现有精确计算算法的某些步骤，引入较弱的条件（如弱化剪枝条件）来实现的。例如，在空间数据的 kNN 选择和连接操作中，由于在高维空间中效率较低，人们提出了各种此类技术，通过使用特定的剪枝条件和停止标准来减少搜索空间，从而修改传统的 kNN 算法。即使 top - k 运算符本身可被视为一种面向数据质量（QoD）的近似方法，也可以使用搜索空间缩减方法以近似方式执行，以提高性能。在这些情况下，近似答案会关联一个概率度量，指出它们与精确的 top - k 答案的差距。 ### 1.2 启发式搜索技术 启发式搜索技术可能无法找到最佳解决方案，但总能在合理时间内找到一个不错的解决方案。常见的启发式方法包括局部搜索、模拟退火或遗传算法等。这些方法已应用于空间连接以及 kNN 选择和连接操作。 ## 2. 自适应查询处理概述 自适应查询处理（AdQP）是指根据查询评估过程中从环境获得的反馈来改变查询的执行方式。传统的先规划后执行的查询处理方法被以下两种方式所取代： - 完全摒弃查询计划的概念，如基于路由的方法，每个数据项可以通过组成查询的运算符以自己的方式（路由）参与最终结果的生成。 - 动态优化过程，通过两步解决方案对查询进行即时重新优化。第一步，优化器根据运行时收集的系统统计信息动态选择一个新的等效查询计划；第二步，系统需要从当前运行的查询计划迁移到第一步中确定的计划（动态计划迁移）。迁移策略必须确保在计划转换期间和之后系统产生的结果不会改变，即结果既不缺失也不包含重复项。这两种方法都可以看作是适应性度量 - 分析 - 规划 - 执行循环的实例，只是适应频率不同。在基于路由的方法中，适应是基于每个元组进行的。 查询计划可能包含无状态和有状态的运算符。无状态运算符无需维护中间数据或其他辅助状态信息即可生成完整且正确的结果；而有状态运算符在执行的中间点会存储已处理的数据（或从中提取的辅助信息），以便生成完整且正确的结果。在处理数据流查询时，只能采用流水线计划，并且实现连接和聚合的运算符需要是有状态的。需要注意减少连续查询积累的状态。 现有的自适应查询处理方法可以根据不同维度进行分类： - 适应循环的频率。 - 基于计划、基于路由或专门针对连续查询。 - 所应用操作的属性。 部分方法会引入近似处理，从而影响数据质量（QoD）；而另一些方法处理近似运算符（如 top - k），但其适应目标是服务质量（QoS）。 以下是一些代表性的自适应查询处理技术，按照适应主题和目标进行了总结： | 主题 | 目标 | 方法 | | --- | --- | --- | | 查询计划 | 数据特征 | [17, 67, 87, 86] | | 元组路由 | 数据特征 | [25]（事后计划） | | 元组路由 | 数据特征和到达率 | [11]（事后计划） | | 查询计划 | 数据到达率和顺序 | [65] | | 查询计划 | 数据特征和到达率 | [18, 102] | | 查询计划 | 处理环境 | [58] | | 运算符调度 | 数据到达率 | [13] | | 负载削减 | 数据到达率 | [15, 116] | | 远程过滤器安装 | 数据特征和到达率 | [20, 94] | | 负载均衡 | 机器能力和实际工作负载分布 | [1, 52, 102] | | 子查询共享 | 工作负载、数据和系统条件 | [34, 84, 93] | ## 3. 自适应查询计划调整 ### 3.1 应对成本估计错误 AdQP 技术面临的一个基本问题是如何自适应地应对错误的成本估计，这些错误估计会导致选择非最优的查询计划。对于存储数据，这可能是由于谓词选择性估计不准确，而运行时监控可以修正这些估计，以反映优化器成本模型未考虑的列之间的相关性。对于流数据，数据特征不可用且不可靠。运行时选择性可以提供更准确和完整的成本信息，从而实现适当的数据路由或创建反映这些信息的修订查询计划。因此，适应的主题是执行计划或处理技术，适应目标是最小化查询处理时间。 ### 3.2 分布式环境下的适应 在分布式环境中，除了成本估计错误外，还有其他因素会影响查询处理的效率。例如，当在一个节点进行处理，但数据从不同节点收集时，处理需要适应网络带宽和从其他节点接收数据的速率。在这种情况下，适应目标除了最小化查询完成时间外，还包括结果生产的连续性（结果生产速率、尽早产生第一个结果）。动态适应可以使系统对网络 I/O 延迟和流量速率的变化做出反应。 ### 3.3 流数据查询处理的适应 在流数据查询处理中，数据特征和数据到达率都是变化且不可预测的。连续查询计划的成本取决于当前的流条件（如数据分布、到达率）和系统条件（如查询负载、内存可用性）。这些条件在长时间运行的连续查询的生命周期内可能会发生显著变化，通常的目标是最大化查询吞吐量。 ### 3.4 不同的查询计划调整方法 #### 3.4.1 基于路由的方法 - **Eddies**：根据查询执行过程中收集和监控的操作成本和选择性，动态确定数据通过运算符的路由顺序。这是一种基于每个元组的适应方式，不考虑查询计划的概念，而是将查询处理视为元组通过运算符的路由过程，通过改变元组的路由顺序来实现计划的更改。E