A Dynamic Materialized View Selection in a Cloud-Based Data Warehouse

摘要

数据仓库是在生产环境中提供决策支持的系统。传统的数据仓库管理系统往往通过提高查询性能来进行优化。这种优化一般通过使用缓存、索引以及物化视图而实现，优化过程中也需要选择一套最佳的数据结构(物化视图、索引等)。随着云计算的快速发展，决策支持系统脱颖而出，并成为了一种新的挑战模式，查询优化则成为云环境面临的主要挑战之一。
　　本文的目标是将物化视图的选择引入到基于云计算的架构中去。在基于云的数据仓库中，由于云环境的复杂性以及其按次计费的模式，导致执行物化视图的选择颇具挑战性。因而，在云环境中，物化视图的选择不应基于查询得到的元组数或查询次数而完成，而应该考虑CPU的消耗、带宽的使用率、以及存储空间等。
　　我们可以看到，财政预算有限的用户只能接受一个漫长的查询响应时间，但具有较足的预算的用户可以忽略成本，并要求一个非常快的响应时间。我们可通过构建物化视图来完成这一目标，这里的挑战在于如何选择一组视图并能在云环境中得以物化，以提高查询处理响应时间和降低云计算的成本。有如下三种情况需要考虑：
　　有限的预算：给定一个预先的财务预算，这里的关键在于如何选择正确的数据集视图，并将其在云环境中进行物化以尽量减少查询响应时间。
　　响应时间的限制：在有限的响应时间内，这里的关键是如何选择一组物化视图来减少财务费用。
　　预算和时间之间的权衡：在这种情况下，我们必须对查询响应时间和财务预算之间进行权衡。我们的目标是选择一组视图并将其在云环境中进行物化，并能给出一种最佳方案来解决查询响应时间与财务预算的问题。
　　基于上述问题，本文的主要研究工作如下：
　　首先，文中定义了一种费用模型，该模型适用于云环境下的按需付费模式，并在费用预算限制下，根据CPU的功耗来实现物化视图的多标准优化。
　　其次，本文提出了一种基于费用成本的动态物化视图选择算法，该算法考虑了计算复杂度、存储开销以及转移成本。通过使用前述工作中定义的查询预测，本文提出的算法能动态地选择最佳物化视图。
　　费用模型是视图选择问题中的一个重要问题，在预算有限的情况下，它有助于实现物化视图的多目标优化（CPU利用率，带宽消耗和磁盘分配）。
　　使用物化视图意味着要修改计算成本，因为查询处理可能会利用物化视图，而视图则需要选择和维护。通过使用一组视图来响应查询而产生的计算成本包括处理成本，物化成本和维护成本。
　　处理费用通常由查询负载Q、物化视图集V、租用云实例的配置和查询的频率来产生。查询可能会使用物化视图的内容，而无需重新计算其结果。对视图进行物化需要执行相关的查询，在云环境中，这样的操作是需要付费的，而且还会产生物化成本。如果对源数据集进行了大量的修改，那么物化视图集也需要得到更新。更新或维护成本与更新物化视图的时间和频率是成正比的。
　　存储成本是一个重要的问题，尤其是在基于云的架构中，任何存储的数据需要按存储时间支付。随着云计算存储中的数据可以在多个服务器和多个位置进行跨越，数据的安全性则成为了一个重要问题。因此，使用物化视图来提高查询的性能意味着要在云中存储选定的视图，并支付相应的费用。数据存储成本和数据的大小（初始数据集和物化视图）及存储时间是成正比的。
　　对于数据处理、存储和分发，云计算已经成为一个可行的、主流的解决方案，但大量数据在云中进出及 TB级的数据大小是一个不可逾越的挑战。因此，数据传输的成本无法在我们的成本模型被忽略。
　　数据传输成本或带宽消耗成本取决于输入数据的大小、物化视图的输出数据、物化视图的整个数据集（初始数据集和插入数据）以及CSP的原子转移成本。
　　本文提出的物化视图选择方法是基于PR_Q系统预测的，它能作为一个完整的视图管理体系运作。它能预测下一个查询并为其进行视图的物化。我们的算法对视图选择有两个阶段：启动和在线阶段。
　　在启动阶段，系统通过输入的查询流开始工作，查询流（THQ）的阈值由数据库管理员指定。我们假设大家对查询流都比较了解。对查询流很熟悉的话能使我们为自己的算法作出所需的估算。启动阶段包含有两个连续的步骤：两阶段优化方法（2PO）和背包0/1优化。首先，基于两阶段优化方法，它执行了静态视图选择。两阶段优化方法结合了迭代优化算法（II）和模拟退火优化算法（SA）。
　　在许多改进算法中，该迭代改进算法通过一系列的迭代来优化初始解。通过使用众所周知的爬山算法，该迭代改进是基于局部优化的。该算法开始时，选择一个随机的初始状态。接着它随机选择一些邻值，并对它进行分析。该算法随机执行一系列变动，并且仅接受下坡移动，直到它到达一个局部最小值。
　　找到一个局部最小值后，将会随机生成一个新的状态，该算法将在这一状态不停地执行直到满足停止的条件。
　　模拟退火源于统计力学，模拟退火技术最先用于视图选择问题，该算法模仿固体的退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。与迭代优化算法类似，达到某种概率的话，模拟退火技术将接受上坡移动。该算法的每个步骤中的概率值都会下降，并最终只接受下坡移动。这种技术使得模拟退火技术比迭代改进更加优化。
　　接受上坡移动的原因是，一些局部极小值相互逼近，需要通过少量的上坡移动来分离。如果算法只执行下坡移动，即进行迭代优化，它会停留在第一个访问到的局部最小值。
　　在基于云计算的架构中，视图选择问题实质上是货币成本的优化问题，我们发现有必要在我们的算法中集成一个优化的过程，该过程需要考虑到用户的财务预算（本文算法中的BL变量）。在我们的例子中，我们只考虑到预算有限的情况，即预先给定一个财务预算，关键在于选择一组能在云环境中进行物化的视图，在预算受限制的情况下减少查询响应时间。为解决这一问题，我们选择了一种动态编程方法来引用0/1背包优化。
　　在线阶段是系统的运行时阶段。在这一阶段，系统对预测的视图进行物化，此外，系统能识别出一些没有意义的视图并将其删除。
　　在线视图选择问题可以定义如下：给定一个已经物化的视图集和一个查询负载，接着按照资源受限情况，基于对查询的预测重新选择一组物化视图。
　　未来数据查询工作的预测将使用类似于PR_Q系统预测这一技术，它使用关联规则挖掘和概率推理方法。

目录

封面

声明

DEDICATION

英文摘要

中文摘要

目录

CHAPTER 1. INTRODUCTION

1.1 Background and motivation

1.2 Research question and aims

1.3 Thesis outline

CHAPTER 2. BASIC CONCEPTS AND LITERATURE REVIEW

2.1 Literature review

2.1.1 Review of view selection method

2.1.2 Dynamic selection and Static selection

2.1.3 Materialized view and cloud-based OLAP

2.2 Basic concepts

2.2.1 Data warehouse overview

2.2.2 Cloud computing

2.2.3 Materialized view and Data warehouse

2.2.4 Materialized view into the cloud computing

CHAPTER 3. COST MODEL FOR CLOUD BASED ENVIRONMENT

3.1 Cloud Data management cost model

3.1.1 Data computation cost

3.1.2 Data storage cost

3.1.3 Data transfer cost

3.2 Cost model for materialized view in cloud based data

3.2.1 Materialized view computation cost

3.2.2 Materialized view storage cost

3.2.3 Materialized view transfer cost

CHAPTER 4. MATERIALIZED VIEW SELECTION

4.1 Startup phase

4.1.1 Two phase optimization approach \(2PO\)

4.1.2 Knapsack 0/1 optimization

4.2 Online phase

4.2.1 Query answer

4.2.2 Recurrent pattern extraction

4.2.3 Next query prediction

4.2.4 Example for materialized view selection algorithm

CHAPTER 5. EXPERIMENTAL EVALUATIONS

5.1 Experimentation setup

5.1.1 TCP-H benchmark

5.1.2 Hadoop

5.1.3 MapReduce

5.1.4 Java

5.1.5 HIVE

5.2 Experimentation results

5.2.1 Cost under the period

5.2.2 Total response time under the period

5.2.3 Cost comparison with SA and II

5.2.4 Cost and response time comparison with 2PO

CONCLUSION AND FUTURE WORKS

参考文献

致谢

Appendix A:Published paper list