[科普中国]-优化技术

优化技术是指通过一定的方法或策略使系统或程序有关性能提高。优化技术的好处主要可以从以下几个方面来体现：内存利用更加合理；运行时间更短；读取数据的数据更快；准确率更高等。不管是从软件角度还硬件角度进行优化工作，优化技术的基础是数据流分析和控制流分析。

数据流分析是一项编译时使用的技术，它能从程序代码中收集程序的语义信息，并通过代数的方法在编译时确定变量的定义和使用。通过数据流分析，可以不必实际运行程序就能够发现程序运行时的行为，这样可以帮助大家理解程序。数据流分析被用于解决编译优化、程序验证、调试、测试、并行、向量化和片行编程环境等问题1。

数据流分析试图获得程序中每一点的特定信息。通常，在基本块(basic blocks)的界限内就可以获得这些信息，因为很容易计算基本块中的信息。在前向流分析(forward flow analysis)中，一个块的结束状态是这个块起始状态的一个函数。函数由块内的语句的影响信息组成。一个块的开始状态是它的前驱的结束状态的函数。这就产生了一系列的数据流方程：

对于每一个块b：

在这里， 是块b的转移函数。它作用于入口状态 ，并产生出口状态 。连接运算符join将块b的前驱节点 的出口状态联合起来，产生入口状态b。在求解这一系列方程之后，块的入口和出口状态可以被用来获得程序在块内的属性。每条语句的转移函数可以被分别的用于获得在一个基本块内的某一点的信息。每一个特定类型的数据流分析都有它自己的特定的转移函数和连接运算符。一些数据流问题需要后向数据流分析。和前向数据流分析类型，除了转移函数是使用出口状态来产生入口状态，而连接运算符作用于后继节点的入口状态以产生出口状态。(在前向流分析中的)入口点起着重要的作用：因为它没有前驱节点，它的入口信息在分析开始时是明确的。比如，可以确定的局部变量的值的集合此时为空。如果控制流图并不包含循环(在程序中显性的或隐性的循环)，只需直接求解数据流方程即可。此时可以对控制流图的基本块进行拓扑排序；按照排序后的结果依次计算，则每个块的入口状态都可以在块起始处计算，因为此时块的所有前驱节点都已经计算过了，所以它们的出口状态是可以获得的。如果控制流图包含循环，那么就需要一个更高级的算法。

控制流分析（Control flow analysis）简称CFA，是一种确认程式控制流程的静态代码分析技术。控制流程会以控制流图来表示。对于函数编程语言及面向对象程式设计，CFA都是指计算控制流程的算法。

对于像是Scheme之类有高阶函数的编程语言，不一定可以会程式中直接看出函数呼叫的目标，例如以下的程式片段

(lambda (f) (f x))

根据上述程式无法确认程序f是指什么，此情形下的控制流分析需考虑何时会执行此程式码，及当时的传入值。抽象释义、约束补偿及型别系统都可以用来进行控制流分析。

关系数据库的物理结构、查询优化器和执行引擎是影响数据库查询性能的主要因素。数据库物理结构的改变虽然不会影响应用的查询结果，但会影响数据库性能。早期的关系数据库主要用于联机事务处理,数据规模较小，通常进行查询语句和执行引擎的优化，物理结构设计的重要性没有充分得到体现。数据库的物理结构是整个数据库存储的基础，主要在设计阶段确定而且具有持久性，也就是说,物理结构一旦确定，不会经常变化。一般在以下情况下会发生物理结构的优化推荐：

数据被移植到一个新的存储系统；

数据库的应用模式有了较大的变动,主要指的是元数据的变化；

数据库的工作负荷(workload)有很大的变动,主要指的是查询语句的使用变化；

数据库性能明显降低。

数据库物理结构优化是指为数据库系统的数据推荐合适的物理存储位置或存储结构，以及为查询推荐合适的存取路径，进而改进整个系统的性能。在数据仓库还没有发展起来之前，物理结构优化的早期产品一般只考虑索引这一种物理结构的优化。但是，随着互联网等技术的发展，数据仓库技术的广泛应用，为了进一步提高系统的性能，数据库系统逐渐提供了对其他物理结构种类的支持，除了传统的索引之外，还有物化视图、无共享分区和多维聚集等。

索引(index)是数据库系统中用于提高检索查询速度的数据组织，一般情况下可以显著提升数据库系统检索查询的性能，也可以快速检索特定数据和范围数据以及提升数据值唯一性等。通常在索引的选择过程中，除了选择最好的单一属性索引之外，还需要逐渐考虑附加索引，以确定是否有更好的选择方案。有些情况下，虽然创建新的索引提升了查询效率，但却严重降低了更新性能。因此，当判断一个新的索引是否可用时，通常要考虑查询和更新的性能组合。索引设计过程中需要考虑的关键问题包括：(1) 增加一个索引是否会对检索有益；(2) 使

用什么类型的索引；(3) 索引需要包括哪些属性的组合；(4) 考虑索引对存储空间的需求;(5) 在表更新时，索引是否还是有益的.综合考虑上面的几个因素，当一个索引的收益大于其开销时，就应当创建并使用该索引，其中的收益和开销都依赖于响应时间和吞吐量。当一个已用索引的性能变得较差时,需要选择优化新的设计方案。索引优化是物理结构优化领域最早开始研究的问题。因此，关于 ISP 的算法有很多。 以下有两种方法:一种是基于背包子问题和基于拉格朗日分解的启发式算法，这种方法适合应用在大规模 ISP问题上；另一种方法是基于线性规划的分支界限法，这种方法通过预处理过程降低候选索引集的大小来提高索引

的选择效率。在 ISP 问题上，以上方法都存在效率低下和优化质量不高的问题，比如启发式算法在索引方案产生之前,由于候选索引各自收益或者价值的相互作用，导致其最后得到的不一定是最好的优化方案.更重要的是，自动优化技术大都依赖于如果假设分析接口，实现对某个查询的索引集合的收益的精确评价，如果工作负荷集比较大，再加上针对每个查询的巨大的解决方案集合，整个优化过程就会依赖于大量的如果假设调用,显著增加了优化推荐过程的代价或成本。为了进一步解决效率问题，提出了一种截然不同的优化方法。利用 60 多年前在线性规划领域的研究成果来解决ISP 问题，证明了基于快速如果假设分析的索引优化问题等价于简洁的二进制整数规划(BIP)问题。BIP 的引出，使优化过程只需进行少量的如果假设调用，利用线性规划现有的方法高效地解决了索引的选择优化问题。基于线性规划的方法解决物理结构优化问题近几年才开始广泛研究和应用2。

物化视图(materialized view)是用于保存在基表上进行连接或聚集等耗时较多的操作结果的一种数据库对象。物化视图存储基于原始数据表的检索数据，这样在执行查询时就可以直接访问物化视图,避免重复进行耗时的操作，从而加快得到结果的速度。

利用物化视图能够显著改善磁盘 I/O 和检索查询性能，主要来源于以下4方面因素：(1) 利用专用磁盘生成视图,避免 I/O 资源的竞争；(2) 物化视图可能会比基表小很多，这为每次询的磁盘 I/O 性能带来很大的收益；(3) 降低多表之间的连接成本，减少计算量；(4) 对于经常访问的查询来说,收益倍增.物化视图对应用透明，增加和删除物化视图不会影响应用程序中 SQL 语句的正确性和有效性。物化视图的缺点是需要占用存储空间，当基表发生变化时，物化视图也应刷新。同步更新问题严重降低了物化视图的使用性能，因此在设计和使用时必须考虑更新性能。