面向绿色数据中心的能耗有效查询优化技术

邢宝平 吕梦圆 金培权,2 黄国锐 岳丽华,2

1(中国科学技术大学计算机科学与技术学院 合肥 230027)2(中国科学院电磁空间信息重点实验室 合肥 230027)3(中国人民解放军31002部队 北京 100081)

自哥本哈根大会之后，建设低碳社会已经成为全球共识.面向可持续发展的低成本、低能耗的新型计算系统、模型和应用的研究，或称为绿色计算，已成为未来信息技术领域面临的重大挑战[1].在当前以数据为中心的计算模式下，研究节能的低能耗数据库系统不仅具有显著的应用价值和社会意义，同时对于推动数据库领域的发展也具有重要的科学意义.

低能耗数据库系统的主要目标是实现数据库系统的低能耗，同时兼顾性能.传统的数据库系统通常以高性能为目标进行设计，没有充分考虑数据存储与操作时的能耗有效性(energy efficiency).所谓能耗有效性[2]，通常指使用更少的电能来提供相同的服务，例如缓冲区管理、查询执行等.由于能耗在现有大型数据管理系统(通常是数据中心)中的费用比例逐年升高(目前大约占总能耗的16%左右)[3]，不仅给企业带来了沉重的经济负担，产生的碳排放也会带来一系列的社会问题和国际影响.因此，研究能耗有效的数据库系统，降低数据管理的能耗，已经成为政府、企业和学术界普遍关心的焦点问题之一[4-7].

数据中心的能耗总体上受到2个方面的因素影响：第1是单个服务器节点的能耗；第2是由于分布式环境带来的能耗代价，例如网络通信、任务调度、分布式执行等带来的能耗开销.本文主要针对单个服务器节点的能耗问题.传统的数据库服务器以性能为导向，各模块实现时并没有考虑到能耗因素.作为数据库系统核心模块的查询优化器目前均基于性能(即时间代价的估计)来进行执行计划的选择.已有研究表明[8]，现有查询优化器选中的执行计划通常是性能最优，但并不是能耗性能比最优的.但已有工作[8]仅考查了有限的物理操作符的能耗，而且物理操作符的能耗采用了经验性估计方法，存在较大的误差(例如，没有剔除统计量装载等能耗代价).此外，也没有在查询处理器中提供灵活的能耗和性能折中的方案.

本文提出了一种能耗有效的数据库查询优化新方法.该方法通过在执行计划生成过程中对时间代价进行预测的同时，引入计划执行的能耗代价，进而做出更好的计划选择策略.同时，由于不同的应用对性能和能耗有着不同的要求，因此我们的方法也允许用户在性能和能耗之间进行灵活选择.总体而言，本文的主要工作和贡献可总结为3点：

1) 提出了一个基于操作符的执行计划功耗模型.我们结合数据库应用层信息和操作系统层信息，基于回归分析方法构建了操作符功耗模型，进而给出了整个执行计划的功耗模型.

3) 构建了数据库系统能耗测试平台，在开源数据库PostgreSQL上实现了能耗有效的查询优化器，并基于TPC-H和TPC-C基准测试进行了大量实验.结果表明，我们所提出的功耗预测模型比已有方法准确度更高.同时，提出的性能退化度因子为数据库系统提供了性能和能耗之间的灵活折中方案，可以实现比原始PostgreSQL更高的能耗有效性.

1 相关工作

1.1 能耗有效的数据库查询处理技术

设计一个能耗有效的数据库管理系统(database management systems, DBMS)，需要保证在性能退化较少的情况下大大降低系统的能耗，同时又不影响系统的扩展性和可靠性.文献[7]提出了考虑延迟的能耗有效查询(query energy-efficiency with delays, QED)算法，通过队列缓存一段时间内接收到的查询请求，达到阈值后通过查询聚合，提取请求中的公共部分.这一显式延迟的方案更适用于多用户场景，如处理搜索引擎的服务器集群.对于单节点数据库系统，反而会使得性能急剧下滑.另一种方式，可以在查询优化器设计时加入能耗因素的考量.这需要在DBMS设计时建立2个模型：1)能耗模型，将它加入查询优化器中，从而能够在评估每个查询计划的代价时考虑到能耗因素；2)总代价模型，结合新加的能耗和性能模型，得出每个查询计划的总代价，从而选择最优的查询计划.

因此，对查询优化的改进，重点就在于建立良好的能耗模型和总代价模型.为此，需要了解系统硬件层面的性能和操作特性，以及能耗与性能间的联系[9].文献[8]利用PostgreSQL中性能模型，通过使用待定系数法，调节参数后建立了能耗模型.尽管该方法通过数学方法确定了系数，但模型的操作符的能耗代价基于经验性估计，与实际代价差异较大(在本文的实验中误差达25%)，因此该能耗模型的合理性有待商榷.

1.2 数据库系统的资源预测模型

在数据库系统中，估计SQL查询的资源消耗是关乎系统性能方面至关重要的工作.查询优化器中内建的代价模型为给定查询提供了基势估计.这一方面有很多的工作，包括基于采样的方法[10-11]、基于直方图的方法[12]等.

近来的工作都在探讨使用基于机器学习的方法[13-17].文献[13]通过使用混合模型(plan-template models, operator-level models)，来预测查询执行时间.但该模型使用的输入特征都是来自于数据库内部数据，没有考虑系统层的影响.文献[15]中研究了在并发环境下如何预测查询的执行时间，使用了多元线性回归模型来捕捉查询间相互作用.文献[16]则是基于一种特殊的循环神经网络——长短期记忆(long-short term memory)，能够预测一个特定的查询计划的执行时间区间.文献[17]在单站点数据库服务器上构建了资源单位统一的能耗预测模型，采用多元线性回归模型拟合模型的重要参数。

文献[8]表明，现有查询优化的代价估计选中的执行计划通常是性能最优，但并不是能耗性能比最优的.文献[8]保留原有的性能模型，初步探索了能耗有效的查询优化研究.依然存在2个问题：

1) 实验中整机功耗的测量使用的是万用表，不仅数据误差大，而且无法具体查看不同操作下各模块的功耗.

2) 使用的功耗模型基于的是标量函数，无法准确地描述系统的功耗代价.在动态环境下，该功耗模型的预测结果较差.

2 能耗有效的查询优化框架

不同于已有的基于执行时间预测建模的研究，本文集中于预测查询执行过程中的平均功耗(average power).之所以这样选择，主要考虑了2个方面：

1) 如果我们直接预测能耗，将会是一个十分复杂的问题. 而查询操作的能耗可以通过查询执行时间、执行平均功耗计算得到.由于这2个环节相互之间较为独立，因此通过这种方式可以避免模型估计误差的传递，并将1个复杂问题分解成2个较简单的问题，便于问题的讨论和实现.

2) 数据中心中功耗一直被看作是最重要的优化目标之一.当系统运行在低功耗状态时，冷却系统的耗能也随着大大降低.

因此，本文实现了能耗有效的查询优化器.首先需要建立功耗预测模型，在此基础上，将其融入到现有的查询计划的代价计算模型中，最终选取能耗有效性更好的查询计划.

2.1 总体方案

Fig. 1 Design of energy efficient query optimizer图1 能耗有效查询优化器的设计

性能模型通过以时间为度量单位的时间模型(time model, TM)表示，用于估计不同查询计划的执行时间.而能耗模型(energy model, EM)是以焦耳(J)为度量单位，用于估计不同查询计划执行的电能消耗大小.功耗模型(power model, PM)是以瓦特(W)为度量单位，用于估计不同查询计划执行中系统功耗大小.PM与TM之间相对独立，但是由于已有的TM无法给定查询计划的实际执行时间，因此在实际使用时并不能简单地通过“能耗=功耗时间”来度量，而是需要定义合理的参数或值来调节功耗和时间的权重，才能创建更合理的EM.

基于查询优化器的工作原理和流程，图1给出了本文的能耗有效查询优化器的设计思路，它主要包含2个方面的内容：

1) 功耗代价的计算

功耗代价用于预测给定执行计划在实际运行中的平均功耗.具体可分为3个步骤完成：

第1步. 确定训练数据集中数据格式和采集方案.对于每类物理操作符，确定在其执行过程中需要记录哪些数据，再设计相应的数据格式和运行负载.在负载运行过程中进行数据采集.

第2步. 建立操作符层功耗模型.基于第1步采集的数据，提取特征数据，利用回归分析，建立操作符层功耗模型.

第3步. 建立执行计划的功耗模型.基于第2步建立的操作符层功耗模型，通过单个物理操作符的功耗预测来计算整个执行计划的平均功耗.

2) 计划间代价比较及执行计划选择

功耗模型建立后，对于每个查询的执行计划都会得到2个代价值：估计执行时间T以及预测执行的平均功耗P.而后将其融入到已有的代价计算架构中，选择能耗有效性最好的查询计划.

2.2 数据采集方案

已有研究发现，不同操作符之间有着不同的功耗[7-8]. 即使在CPU使用率相同的情况下，功耗差异最大可达60%.因此对于单个数据库物理操作的执行功耗，不仅要考虑CPU和内存的使用情况[18-19]，还需要考虑数据库的运行状态.最终，要收集的数据由3部分数据组成：系统当前运行状态的表征数据、操作符执行时可能读取的页面数目等数据和执行的功耗数据.在建立的功耗模型中，将系统和数据库内部的表征数据作为输入来预测功耗.

图2显示了我们所设计的数据采集平台架构，主要由2个模块构成：

1) 内部监控器(internal monitor).在能够提供数据库服务的测试机上实现内部数据采集.在PostgreSQL中，通过explain analyze+SQL查询语句的查询执行方法的方式，能够输出结果的同时输出代价计算值和相关估计参数值.通过修改explain analyze的代码，可以提取数据库参数.通过修改查询执行中的代码，在对应的物理执行计划执行前，查询系统运行状态(CPU使用率等).组织后得到内部采集数据，格式为(操作符类型标识，数据库参数，系统参数，开始时间，结束时间).以顺序扫描操作符的执行为例，采集的数据格式为(seq_scan，读写页面数目，处理元组数目，CPU使用率，开始时间t1，结束时间t2).

2) 外部监控器(external monitor).用于监控测试机部件的实时功耗，采集的功耗数据格式为(采集时间，CPU功耗，磁盘功耗，整机功耗). External monitor通过我们自行设计的数据库系统能耗测试平台来实现.在3.2节中将具体介绍该平台的实现架构.

Fig. 2 Data acquisition platform and data format design图2 数据采集平台及采集数据格式设计

对于系统信息，可以收集的信息有：CPU使用率、内存使用率、系统热设计功耗(thermal design power, TDP)值. 其中，系统TDP值是系统运行功耗上限，是常量值.CPU使用率和内存使用率可以实时获取.具体地，在Linux系统中，可以通过读取文件procstatprocmeminfo中内容来分别确定当前CPU的使用率和内存使用率.stat文件中包含了所有CPU活动的信息，该文件中所有值都是从系统启动开始累积到当前时刻.执行catprocstat后显示内容如表1所示：

Table 1 CPU Running Information表1 CPU运行信息

通过选择2个时刻t1，t2，分别读取文件的内容，经过计算得到这段时间内的CPU使用率，即

CPU使用率=100%×

(1)

内存使用率需要从meminfo文件中提取2个数据，分别是当前内存的使用量(cmem)以及内存总量(umem)，计算公式为

(2)

对于数据库信息，表2和表3通过分类方式列出了在数据库系统内部可以取得的参数及相应含义.

Table 2 Common Features of All Physical Operators表2 所有物理操作符的共同特征

Table 3 Features of Specific Operators表3 基于特定操作符的特征

在PostgreSQL中具体实现时，需要修改内核中的costsize.c，createplan.c，explain.c，plannodes.h，relation.h等文件.通过修改plannodes.h和relation.h中对于结构体plan，path的定义添加相应数据类型的字段来记录信息.已知在PostgreSQL数据库中可以通过(explain+SQL查询)的方式来显示给定SQL查询的执行计划树.explain enalyze会显示带有代价的执行计划树且执行查询.因此通过修改程序中explain执行操作的源码，借由系统中本身自有的查询执行树的解析程序来完成记录信息的输出保存.具体的修改主要集中在PostgreSQL的srcackendcommands目录下explain.c文件中的explain_outNode函数上.

数据采集工作需要有相应的负载，在查询负载运行过程中进行数据的收集.由于TPC-H基准测试中的查询都是复杂查询，其执行树由一系列物理操作符组合而成，因此在实际数据采集中会遇到2个问题：1)尽管能耗测试平台(external monitor)能够实时监控测试机的运行功耗.但是由于复杂查询下物理操作符执行时序的不确定性，很难确定每个物理操作的执行时段，进而去确定它的运行功耗.2)对于单个操作符，系统信息采集时误差大.这是由于短时间内频繁地读取procstat，procmeminfo文件造成的.

为此，我们提出了一套简单负载设计原则，通过合理有效地使用简单查询负载来达到数据收集的目的，同时保证收集数据能够较好地反映物理操作符的真实功耗情况.在设计运行负载时，我们使单个查询尽可能涉及较少的物理操作符、不同查询间尽可能不存在操作符交集、整个负载要尽可能地包括所有类型的物理操作符.最终，设计的运行负载为

SELECT*FROMR;

(Scan)

SELECT*FROMRORDER BYR.a;

(Sort)

SELECT*FROMRWHERER.A

(Select)

SELECT COUNT(*) FROMR;

(Aggregate)

SELECT*FROMR，S;

(Product)

SELECT*FROMR，SWHERER.a=S.a;

(Join)

利用TPC-H基准测试方法，我们将上述查询实现为TPC-H中扩展的查询模板.

2.3 执行计划的功耗模型

基于采集的训练数据集，我们采用回归分析的方法来建立操作符层功耗模型.对于单个物理操作符，为了能够得到预测功耗模型，我们使用2个特征数据：1)在DBMS内部，采集到的物理操作符执行时可能处理的元组数目T、读取页面数目N、选择度σ等信息；2)当前系统的CPU使用率C.单个操作符的预测功耗P定义为

P=F(T,N,σ,C).

(3)

然后，对F用训练数据集进行回归分析.考虑到实际使用中计算复杂度问题，我们使用迭代线性回归的训练方法，以总误差率值f(训练数据误差率err的累加，误差率err的定义为

(4)

作为目标函数，回归过程为

步骤1. 根据初始输入特征T，N，σ，C和训练集中功耗W，线性回归得到F1，并计算总误差率值f1.

步骤2. 选取单个特征进行简单变换(如T→T2)作为新特征，再次进行线性回归，得到F2和f2.

步骤3. 比较f1，f2，若f2f1，且无新特征，则算法停止.

实现时使用了GSL(GNU scientific library)工具. GSL是开源的CC++统计学习工具库，能够方便地完成对于多维数据的回归学习.

下一步，由得到的单个物理操作的预测功耗来估计查询执行的平均功耗.任意一个查询Q可以看成是由一系列物理操作符O组成的执行计划树.每个合法的执行计划树都是由一组物理操作符有序执行的结果.在传统代价估计中，TQ为执行计划的时间估计，tO为操作符的时间估计，如式(5)所示.已有研究并没有特别强调PQ如何计算，为此我们自然地认为PQ也是如此计算.

(5)

然而，时间累加代表总时间，功耗的累加并不具有实际意义.本文通过对每个操作符的功耗进行加权累加，而不是直接的叠加方式，最终得到整个执行计划的平均功耗(即查询的功耗)，即：

(6)

(7)

其中，Tmp是中间变量，用来计算每个操作符的时间、功耗乘积.

2.4 总的代价模型

通过2.3节的功耗模型，对于每个执行计划最终可以得到2个值：1)估计执行时间T，无单位，并不与真实执行时间量级上有关.但是在传统数据库系统中能够很好地指导最优计划的选取.2)预测执行平均功耗P(单位W).

在最终合理的计划集中，能耗有效的优化器要选取的执行计划与传统优化器中选择的执行计划就代价估计而言，常常要选取的计划在功耗上有优势，但是在性能上有所退化.为此，我们定义了总代价模型：

Cost=PαT1-α.

(8)

假设现有2个执行计划：Plan1和Plan2，并假设Plan2的功耗低于Plan1，我们可以计算出当两者代价相等时Plan2的性能T*，具体过程为

Plan1:已知平均功耗P以及执行时间T；

Plan2:已知平均功耗为np(0

通过上述推导过程，我们发现不同的执行计划的功耗和性能之间存在着可计算的相关性.换句话说，如果查询优化器最终选中比Plan1功耗低的Plan2，参数α决定了Plan2的性能退化率，即由T退化为T*.

因此，我们将α定义为性能退化度调节因子.假设Plan2在功耗上有20%的收益(n=0.8)，通过外部的α值设置，可以控制能耗有效的查询优化器在选择Plan2所允许的最大的性能退化程度(相比传统查询计划选择策略).比如：α=0.2时，T*=1.06T，允许的性能最大退化度为6%.因此，在实际系统中，我们可以通过设置合适的α值，有效地控制查询计划选择时的性能与功耗之间的折中.α=0表示不允许性能退化；α=1表示允许性能可以无限退化，达到功耗最低.表4给出了不同退化因子下的性能退化度.

Table 4 Degenerated Factor α(n=0.8)表4 退化因子α(设n=0.8)

3 实验结果

3.1 实验设置

实验的软件环境为PostgreSQL 8.3.3和Ubuntu 12.04(内核 3.5.0).硬件设置以及相应的功耗参数如表5所示.测试负载使用了TPC-H和TPC-C.

Table 5 Experimental Environment and Parameter Settings表5 实验环境和功耗参数设置

3.2 能耗测试平台

系统运行时，测试平台能够实时对计算部件和存储部件的各路供电线路进行电流和电压采样，并将采样所得的模拟信号经过模电转换器件转换后传输给数据处理系统进行数据的处理和保存.

图3给出了系统架构设计.系统由硬件和软件2部分构成，其中软件部分由2个部分构成：

1) 运行在测试机上的各类测试负载；

2) 运行在数据分析机上的数据收集和分析软件.

硬件部分由5部分构成：

1) 能耗测试设备；

2) 计算机1(作为测试机，提供数据库服务)；

3) 计算机2(数据采集和分析)；

5) 机箱电源.

Fig. 3 Energy consumption testing platform architecture图3 能耗测试平台架构

3.3 TPC-H基准测试结果与分析

1) 预测精度

我们分别在2种不同系统环境下进行了TPC-H基准测试.在基准测试生成的10 GB数据集上，分别运行TPC-H测试查询语句，利用能耗测试平台统计并计算查询执行的平均功耗，进而计算模型精度.

我们测试了静态运行环境和竞争运行环境下的性能.静态运行环境是指系统上只运行数据库服务.由于测试查询依次单个执行，相当于独占系统.竞争运行环境中则存在其他的应用程序，不是数据库服务器独占系统资源，在实验中我们通过运行Web服务程序来模拟.测试结果如图4和图5所示:

Fig. 4 Accuracy of power consumption prediction of TPC-H in static environment图4 TPC-H在静态环境下功耗预测的精度

Fig. 5 Accuracy of power consumption prediction of TPC-H in competitive environment图5 TPC-H在竞争环境下功耗预测的精度

在静态运行环境下，本文模型比文献[8]中的功耗模型预测精度更高.文献[8]中普遍存在预测过高的问题.在竞争运行环境下，由于考虑了当前系统运行状态，因此能够对运行功耗进行更精度的估计.

2) 额外代价

本文模型在查询优化阶段获取数据库信息的同时，还要获取当前系统运行信息.对计算得到的代价，还需要进行加权累加，在查询运行时带来了额外代价.为此，我们通过实验来评测查询优化器的额外代价.实验分别对比了1 GB和10 GB数据集下，未加入能耗代价的PostgreSQL和添加了能耗代价模型的PostgreSQL的性能和能耗表现.实验中设置α=0，以保证2个数据库选择相同执行计划.

设t1为原始的PostgreSQL的查询执行时间，t2为增加能耗代价模型后的查询执行时间，我们将额外代价定义为t2-t1.图6和图7显示了TPC-H查询的实验对比结果，其中Y轴为(t2-t1)t1的比值，代表了增加能耗优化后带来的额外时间代价比例.

在1 GB的数据量能耗有效的查询优化带来的额外代价较高，说明这一机制在小数据量或者简单查询下额外代价大.主要原因是此类查询本身的执行时间短，生成的候选计划空间小，花费较长时间用于能耗有效的查询优化，反而得不偿失.但是，在10 GB数据集上，额外代价相对较小，平均每个查询所增加的额外时间为3.78%.

Fig. 6 Additional cost of a single query on the 1 GB data set图6 1 GB数据集上单个查询的额外代价

Fig. 7 Additional cost of a single query on the 10 GB data set图7 10 GB数据集上单个查询的额外代价

3) 能耗有效查询优化的总体性能

表6给出了不同α参数下TPC-H总体查询性能(1 GB数据量)的测试结果.随着α的增大，时间性能变差，同时负载执行的平均功耗是降低的，符合我们的预期.通过表6可以看出，α能够有效地调节查询优化器在性能和功耗之间的均衡.如果设置较大的α值，意味着总是偏向选择功耗低的执行计划，则会导致查询执行的时间性能下降.在实验中我们发现，α取值在(0，0.3]，可以取得较好的能耗有效性.

Table 6 Effect of α on the Overall Query Performance表6 α对总体查询性能的影响

3.4 TPC-C基准测试结果与分析

TPC-C是联机事务处理的基准测试，在本实验中我们使用它来测试所提出的能耗有效查询优化策略对联机事务处理的性能表现.在实验中我们将能耗有效性定义为

实验中使用了1 GB数据库，模拟开启了10个终端，并运行10 000个OLTP事务.图8和图9分别给出了执行时间和平均功耗的实验结果.图10的能效结果显示能耗有效的查询优化器能够有效提高能效比.结合TPC-H中总体测试结果我们可以得出结论：能耗有效的查询优化器，通过添加对功耗代价的考量能够起到能耗优化的目的，但是不能单纯以功耗优化为目的做出忽略性能的计划选择.

Fig. 8 Execution time of under different α values图8 不同α值下测试的执行时间

Fig. 9 Average power consumption under different α values图9 不同α值下测试执行过程中的平均功耗

Fig. 10 Energy efficiency ratio under different α values图10 不同α值下测试执行的能效比

4 结束语

本文着眼于在查询优化器中引入能耗代价，提出了基于回归分析的操作符功耗预测方法.此外，通过引入性能退化调节因子，提出了兼顾能耗和性能的查询代价模型，并最终在PostgreSQL上实现了能耗有效的查询优化器.基于TPC-H和TPC-C的实验结果也表明了能耗有效查询优化技术的可行性、有效性以及实用性.

由于目前的关系型数据库系统普遍采用了基于代价的查询优化器，因此本文的研究成果理论上也同样适用其他类型的关系型数据库系统.在本文的实验中，我们主要基于开源的PostgreSQL开展了性能和能耗方面的测试.目前其他的商用DBMS如Oracle,Microsoft SQL Server,MySQL等均采用了与PostgreSQL类似的基于代价的查询优化技术，因此本文的结果具有一定的普适性，理论上可以推广到其他关系型数据库中.

在未来工作中，我们首先将研究连接、聚集等复杂查询操作符的功耗代价估计方法，并提出针对复杂查询的能耗有效查询优化方法.其次，由于目前数据中心往往以服务器集群的形式部署，因此数据中心的能耗一方面受到每个服务器节点的影响，也受到集群中的分布式调度、数据迁移等问题的影响，在未来工作中，我们将针对数据中心中的分布式查询处理、任务调度等问题研究能耗有效的解决方案.