精华推荐：加速SQL查询的特征函数法

1. 查询问题的挑战

关系数据库的查询优化始终是一个重要而实际的问题，在那些以查询为主的应用系统中，这几乎是一个成败攸关的问题。但迄今为止，关于这个问题的讨论中所提出的种种解决方案大致可分为两大类，即利用硬件体系结构上的优势及DBMS对并行处理的支持能力的一类方案及完全由应用设计来处理的方案。在本文作者以前所发表的文章中曾推荐过利用临时中介表和表更新方法和快查询处理的策略。在同一篇文章中，我们也曾提到有可能利用程序变换支持查询优化的想法。所有这些建议和想法都属于应用设计类的处理办法，这些方法从某种意义上说有一定的一般性。但是，实际应用不断地提出这样或那样难而“怪”的问题，这些问题极富挑战性，用常规方法往往要以很昂贵的系统资源为代价才有望解决。

本文的目的是向读者介绍一种由E.Birger等人首先提出的方法，即加速查询处理的特征函数法。这个方法适用于大多数SQL的数据库系统，如果这类系统还包括为数不多的几个（最少为2个）内部函数，如abs（）及sign（）等，则这个方法就是直接可用的了。在E．Birger等人关于这个方法的研究报告中，曾给出很多极有难度而又很典型的查询要求及其求解办法，其中包括分技条件查询、求行内量的边界值、求直方图、表转置、求中位值、有序集的等段截分以及去边界值问题等。这些问题的共性是，若用常规方法求解，系统无论在存储开销上还是处理开销上都很大，而某些问题（如中值）的求解还相当难。本文将重述这些有趣的查询问题及其解决方案。同时，我们还将讨论“特征函数”作为一种使能技术的其他一些应用可能。

2．特征函数及其表示

特征函数是来自点集拓扑学的一个纯数学概念，集合S的特征函数定义如下：

　　1 若x? S
　　d s(x)= （0）
　　0 若x? S

在这里，任意元素x是否属于集合S，决定函数取不同的值。同时，这里也隐含了一个前提，即任何元素的集合S为范围的归属是完全确定的，不存在元素x的归属不明的情况。显而易见，特征函数是一种识别（或判定）装置。正是这一特性，使它能够成为数据库查询中选择准则的一种等价（和更有效的）替换成分。因此，我们说特征函数是加速查询的实施技术。

为了更直接地针对数据库查询问题，我们将特征函数的一般形式变换成如下的“数据库版本”：

　　1 若a=ture
　　d (a)= （1）
　　0 若a=false

原文转自：http://www.ltesting.net