（计算机应用技术专业论文）一种分页查询优化方法的研究与实现.pdf

摘要 一种分页查询优化方法的研究与实现 摘要 分页是每个w e b 应用程序都要面对的一个问题。对于小型的应 用，可以采取一些很粗糙的做法，比如对于每次请求都从数据源直接 提取数据，这样做简单易行，不失为一个较好的解决方案；对于规模 较大的应用程序，每个页面都牵扯到大量的数据库访问，数据库的分 页查询效率成为提高数据库访问性能的重要问题。 本文是对目前广泛应用的多种查询优化算法和多种分页的显示 方法进行研究。在查询优化方面利用查询优化器对s q l 语句优化原 理进行分析，文中主要是对当前使用最频繁的多连接查询语句进行研 究。另一方面则是讨论了各种分页方法的优缺点，从而指出了可扩展 的分页方法的一些基本思想以及接口描述。然后以一特征实例讨论了 w e b 数据库数据记录分页显示的程序设计方法，并结合采购招标系统 当中订单分页查询问题给出了相关文件的部分程序源代码。结果表 明，该方法能够达到显示逻辑和业务逻辑的分离、代码的重用、与具 体数据库无关等优点。 另外，文中所讨论的分页技术已应用于笔者开发的实际应用系统 当中。经测试，该方案能够体现了较好的系统性能。如在对5 万条 数据库记录进行查询分页时，平均响应时间最短。并且该分页查询技 术方案与具体数据库相关性小、通用性好、执行效率较高。在健壮性、 北京化t 犬学硕 ：学位论义 安全性、稳定性和移植性上相对其他方法都有良好的改进。 关键词：分页，w e b 应用，查询优化，优化器，数据库 a b s t r a c t as t u d ya n di m p l e m e n t a t i o no fp a g i n 垤i o n q u e r yo p t i m i z a t i o n a b s t r a c t p a g ei sap r o b l e mf o re a c hw e ba p p l i c a t i o nt of a c e f o rs m a l l - s c a l e a p p l i c a t i o n s ，s o m ev e r yr o u g ha p p r o a c h e sc a nb et a k e n ，f o re x a m p l ei ti s s i m p l ea n d ab e t t e rs o l u t i o nt oe x t r a c tt h ed a t af r o md a t as o u r c ed i r e c t l y f o re a c hr e q u e s t ；w h i l ef o rl a r g e r - s c a l eo n e s ，al a r g en u m b e ro fd a t a b a s e a c c e s sa r ei n v o l v e di ne a c hp a g e ，t h ep a g i n gq u e r ye f f i c i e n c yo fd a t a b a s e h a sb e c o m ea ni m p o r t a n ti s s u et o i m p r o v ep e r f o r m a n c eo fd a t a b a s e a c c e s s t h i sa r t i c l eh a sr e s e a r c ho nm u l t i p l eq u e r yo p t i m i z e da l g o r i t h m s w h i c ha r ew i d e l yu s e da n dd i s p l a ym e t h o d so fv a r i o u sp a g e t h e o p t i m i z e dp r i n c i p l eo fs q l s t a t e m e n t si sa n a l i z e dt h r o u g ho p t i m i z e ri n q u e r yo p t i m i z a t i o n ，m u l t i - j o i nq u e r ym o s tf r e q u e n t l yu s e da tp r e s e n ti s m a i n l ys t u d i e d i nt h et e x t o nt h e o t h e rh a n d ，t h ea d v a n t a g e sa n d d i s a d v a n t a g e so fv a r i o u sp a g i n gm e t h o d s a r ed i s c u s s e dt op o i n to u ts o m e b a s i ci d e a sa n di n t e r f a c i a ld e s c r i p t i o n so f e x t e n d e dp a g i n gm e t h o d s t h e n t h ep r o g r a m m i n g so fd a t ar e c o r dd i s p l a y e dp a g e l yi nw e bd a t a b a s ea r e d i s c u s s e dt h r o u g hac h a r a c t e r i s t i ce x a m p l e ，a n ds o u r c ec o d e so fs o m e p r o c e d u r e s a leg i v e nc o m b i n i n gw i t hp a g i n g q u e r i e s o fo r d e r si n p r o c u r e m e n ta n dt e n d e rs y s t e m t h er e s u l t ss h o wt h a t t h i sm e t h o dc a n i i i 北京化丁人学硕：i j 学位论文 a c h i e v et h em e r i t sw i t ht h es e p a r a t i o no fd i s p l a yl o g i ca n db u s i n e s s l o g i c ，r e u s eo fc o d e s ，a n dn o t h i n gt od ow i t ht h es p e c i f i cd a t a b a s e i na d d i t i o n ，t h ep a g i n gt e c h n o l o g yd i s c u s s e di nt h ea r t i c l eh a sb e e n a p p l i e d t ot h e p r a c t i c a la p p l i c a t i o n a ls y s t e m sd e v e l o p e db y t h e a u t h o r a f t e r t e s t i n g ，t h ep r o g r a m c a nr e f l e c tab e t t e r s y s t e m p e r f o r m a n c e f o re x a m p l et h ea v e r a g er e s p o n s et i m ei ss h o r t e s tw h e nt h e p a g eq u e r yi sc a r r i e do u ta m o n g5 0 ，0 0 0r e c o r d si nt h ed a t a b a s e a n di th a s s m a l l e rr e l e v a n c ew i t ht h es p e c i f i cd a t a b a s e ，g o o dc o m m o n ，a n de f f i c i e n t i m p l e m e n t a t i o n ，w i t hb e t t e ri m p r o v ei nr o b u s t n e s s ，s e c u r i t y , s t a b i l i t ya n d p o r t a b i l i t yr e l a t i n gt oo t h e rw a y s k e y w o r d s ：p a g i n a t i o n ，w e ba p p l i c a t i o n ，q u e r yo p t i m i z a t i o n ， o p t i m i z e r , d a t a b a s e i v 北京化工大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本 论文不含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 作者签名：玉兰阻 日期：五呼乙包卫一 关于论文使用授权的说明 学位论文口者完全了解北京化工大学有关保留和使用学位论文 的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属北 京化工大学。学校有权保留并向国家有关部门或机构送交论文的复印 件和磁盘，允许学位论文被查阅和借阅；学校可以公布学位论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存、汇编 学位论文。 非保密论文注释：本学位论文不属于保密范围，适用本授权书。 作者签名： 至至盏池 日期：一丝2 ：占：2 导师签名： 吞圭辜 e la n ： 导师签名：孕牡 ： 第一章绪论 第一章绪论 7 1 1 论文研究的目的及意义 数据和信息在当今社会活动中越来越显示出其重要性，已经成为人类发展的 一种极为重要的资源。数据库是集中、统一保存和管理某一领域内所有信息的集 合，是管理信息系统的核心【l 】。目前，几乎所有的应用查询都要和数据库打交道， 通过查询数据库以获得需要的结果。随着现代数据库规模的不断扩大以致到以十 亿字节( g b ) 计量，对能够处理如此巨大的数据信息系统的需求也随之而来，从而， 找到一种高效的信息提取方法对于使研发过程更有效地进行是十分必要的【引。数 据库应用系统的性能受多方面的限制，如操作系统、数据库管理系统以及前端开 发工具等都有很大的影响。从大多数数据库应用系统的实例来看，查询操作在各 种数据操作中占的比重最大。查询的效率是数据库系统的重要指标，高效的查询 能够极大地提高系统的性能。因此，提高查询效率的有效手段一查询优化就显得 尤为重要了p j 。 随着互联网的飞速发展，基于w e b 的各类应用系统愈来愈多，良好的的系 统软件能够应用十几年，甚至几十年，数据库系统的数据往往超过了千万条，可 谓是海型4 1 。那么，如何实现快速地从这些超大容量的数据库中提取数据( 查 询) 、分析、统计以及提取数据后进行数据分页已成为系统管理员和数据库管理 员亟待解决的难题p j 。 一个系统的优劣很大程度上取决于数据的查询速度。而“查询优化”和“分 页算法”两者又是决定数据库系统查询速度的关键。本文从分析影响分页查询速 度的关键因素入手，结合优化器对s o l 语句的优化原理和分页方法，并通过理论 推倒和实验结果的分析，提出分页查询优化设计的方法，将该方法应用实际的系 统当中取得了良好的效果。 1 2 查询优化技术概述 1 2 1 查询优化的基本概念 所谓查询优化，就是在查询执行引擎生成一个执行策略的过程中，尽量使查 询的总开销和总时间达到最小【6 川。 实际系统对查洵优化的具体实现不同，但一般来说，可以归纳为四个步骤： ( 1 ) 将查询转换成某种内部表示，通常是语法树。 北京化t 人学硕。l ：学位论义 ( 2 ) 根据一定的等价变换规则把语法树换成优化( 标准) 形式。 ( 3 ) 选择底层的操作算法。对于语法树中的每一个操作需要根据存取路径、 数据的存储分布、存储数据的聚簇等信息来选择具体的执行算法。 ( 4 ) 生成查询计划。查询计划是由一系列内部操作组成的，这些内部操作按 照一定的次序构成查询的一个执行方案，通常这样的执行方案有很多个，需要 对每个执行计划计算代价，从中选择代价最小的一爪【引。 其过程如图l 一1 所示： 图卜l 查询优化的处理过程 f i g 1 - 1q u e r yo p t i m i z a t i o np r o c e s s 查询计划是用户所提交的s q l 语句的集合，执行计划是经过优化处理之后所 产生的语句集合。d b m s 处理查询计划的过程是这样的，在做完查询语句的词法、 语法检查数据库查询优化技术研究及其应用之后，将语句提交给d b m s 的查询优 化器，优化器做完代数优化和存取路径的优化之后，由预编译模块对语句进行处 理并生成执行计划，然后在合适的时间提交给系统处理执行，最后将执行结果返 回给用户【9 】。在实际的数据库产品( 如o r a c l e ，s y b a s e 等) 的高版本中都是采用基于 代价的优化方法，这种优化能根据从系统字典表中所得到的信息来估计不同的查 询计划的代价，然后选择一个较优的执行计划。许多程序员认为查询优化是数据 库管理系统( d b m s ) 的任务，与程序员所编写的s q l 语句关系不大，这是错误的。 一个好的查询执行计划往往可以使程序性能提高数十倍。查询优化器的主要 任务是控制和加快查询执行和数据传输的过程。然而，查询优化一直是个复杂的 问题，理想的、全面的查询优化几乎是不可能的，许多专家和学者在这一领域曾 做出过不少的研究和探讨，但总的说来，不尽人意，往往只能达到局部目标的查 询优化效果，甚至有些理论并不适用【1 0 1 。 虽然现在的数据库产品在查询优化方面已经做得越来越好，但由用户提交的 s q l 语句是系统优化的基础，很难设想一个原本糟糕的查询计划经过系统的优化 之后会变得高效，因此用户所写语句的优劣至关重要。由于s q l 语言是面向结果 而不是面向过程的查询语言，所以一般支持s q l 语言的大型关系型数据库都需要 2 第一章绪论 使用一个基于成本的优化器，为即时查询提供一个最佳的执行策略。对于优化器， 输入是一条查询语句，输出是一个执行策略。这个执行策略是执行这个查询所需 要的一系列步骤。数据库的反应速度经常就体现在这一个优化算法上。不同的查 询策略和查询步骤可使服务器的反应不同，因此采用适当的查询策略可使系统性 能大大提高。优化器的优化是基于用户对所查询表的内容和其他一些与服务器有 关的因素，如c a c h e 大小、c a c h e 策略、i 0 大小掣。1 引。硬盘访问是成本最高的 操作，因此对用户来讲，使优化器对字段索引进行操作是优化查询的关键。s o l 查询语句都可以有很多种执行策略，优化器将估计出全部的执行方法中所需时间 最少的也就是所谓成本最低的一种方法。最为重要的选择就是使用什么索引和采 用何种的连接手段，而所有优化的进行都是基于用户所使用的查询语句中w h e r e 子句。 查询优化既是数据库系统实现的关键技术又是关系系统的优点所在，它减轻 了用户选择存取路径的负担，用户只要提出“干什么 ，不必指出“怎么干。 1 2 2 查询优化技术 数据库的查询优化从总体上分为物理层和逻辑层两大部分，涉及数据库的物 理设计、逻辑设计、体系结构设计以及数据库管理系统的设计几个方面【1 3 1 。数据 库物理设计是试图建立高效的存储结构和有效的物理存储布局，这需要涉及到文 件组织形式、存储映射算法、存储介质等方面，是提高数据库查询效率的基础。 逻辑设计方面，规范化理论和模式分解理论为关系数据库逻辑设计提供了坚实的 理论基础和有效的手段，依据规范化和模式分解理论进行设计，可以很大程度上 消除数据冗余，避免一定的更新异常，增进了数据库的完整性，从而提高了数据 库的可维护性和可靠性。 当前对查询优化的研究性要分为两个方面，一是外部优化，即着眼于利用现 有的优化器最大限度地挖掘软、硬件的潜力，提高查询效率，它针对影响查询的 多种因素，涵盖了从系统分析、设计到实现的各个阶段。其中包括数据的存储与 组织、s q l 语句的优化、前端开发工具的使用技巧及后台数据库的参数调整等。 另一方面的研究则是内部优化，是对查询优化器( q u e r yo p t i m i z e r ) 的工作机理进 行研究。当前数据库查询优化策略多种多样，就内部优化来讲，就有基于规则的、 基于代价的、基于语义的多种优化方法【1 4 1 。 3 北京化丁人学顾1 j ! 学位论义 1 3w e b 分页技术概述 1 3 1w e b 应用的体系结构 随着w w w 的迅速发展，w e b 技术与数据库技术的联系也越来越紧密。如何 从数据库中高效地获取大量数据并在浏览器中进行显示成为w e b 应用开发中必 须面对的问题。基于：1 ) 小块数据便于在浏览器上显示，不需要用户滚屏浏览，避 免漏掉一些重要的信息；2 ) 在网络上传输小块数据，可以减少网络流量，提高网 页的响应速度这两个理由，目前解决大数据量获取并在w e b 页面上显示的最常用 的解决方法是采用分页技术【1 5 。1 6 】。目前的多种分页技术各有不同的优缺点，适用 于不同的场合。 通常，一个典型的应用程序可分解为四个组成部分：1 ) 界面表示逻辑一与用 户进行交互的应用代码，主要是各种图形用户界面；2 ) 业务处理逻辑一使用输入 数据来完成业务处理和规则的应用代码，与具体的应用有关；3 ) 数据处理逻辑 ( d a t a b a s em a n a g e m e n ts y s t e m ，d b m s ) 一访问数据库的应用代码，例如建立数据 库连接，编写s o l 语句等；4 ) 数据库管理系统一d b m s 不属于应用程序本身，主要 完成实际数据的存取处理。 早期的应用程序属于单机程序，上述四个组成部分运行在一台计算机上，从 数据库中获取数据的性能主要取决于d b m s 的执行效率。随着网络技术的发展，软 件体系结构逐渐从单机模式向客户端服务器模式( c s ) 的方向发展。在c s 模式 中，客户端主要负责实现界面表示逻辑、业务处理逻辑和数据处理逻辑，而数据库 服务器负责存取处理数据，并以存储过程的形式实现部分业务处理逻辑。在c s 模式中，获取数据的性能除d b m s 的执行效率外，还需要考虑网络传输数据的效 率，但由于c s 模式的应用程序主要运行在高速的局域网内，所以网络性能的影响 力很刀、【1 7 】。 随着w w w 的发展，以浏览器为客户端的b s 模式开始成为应用程序开发的 主流。b s 模式一般应用在i n t e i t t e t 的环境中，网络带宽有限，负载比较大，获取数据 的性能主要取决于网络传输数据的效率，而且b s 模式可能涉及到多台机器之间 的数据传输效率问题( 因为w e b 应用系统可能会分布在3 台或更多的计算机上) 。 w e b 应用程序主要分为3 个部分：客户层、功能层和数据层，如下图所示【l 引。 4 第一章绪论 图1 - 2w e b 应用程序体系结构 f i g 1 - 2w e ba p p l i c a t i o na r c h i t e c t u r e 客户层实现界面表示逻辑，主要是浏览器；功能层实现业务处理逻辑和数据 处理逻辑，主要是w e b 服务器和应用服务器；而数据层主要是指数据库服务器。b s 模式三个层次的划分只是逻辑上的概念，具体实现时物理结构上的差异可能会很 大【19 1 。 1 3 2w e b 应用的分页性能模型 在单机应用程序中，获取数据的性能主要取决于数据库的查询代价一局部 代价，包括i o 代价和c p u 代价，可以通过优化s q l 语句等手段提高效率【2 0 1 。但在网 络环境中，除上述局部代价外，获取数据的性能还取决于网络传输数据的能力，尤 其在远程通信网络中，各站点之间的数据传输速度比单机情况下内存与磁盘间的 数据传输率要慢许多，因此，在远程网络坏境中，提高获取数据的性能，主要靠减 少传输的次数和数据量【2 l l 。w e b 应用程序主要应用于远程网络环境中，结厶w e b 应 用体系结构的特点可以得出以下分页性能模型。 定义l 查询代价。d b m s 处理s q l 语句并返回查询结果的时间称之为查询代 价，记为t l 。t l 与s q l 语句是否优化、d b m s 的执行效率及数据库内表的数据容 量等因素有关。 定义2 通信代价。一次网络传输的通信代价可用下式表示： t c ( x ) = c o + c i 宰x 其中：x 为数据的传输量，通常以b i t 为单位计算：c o 为两站点间通信初始化 一次所花费的时间，它由通信系统确定，近似一个常数，以s 为单位；g 为传输率， 单位是s b i t ，即单位数据传输的时间，与具体的网络类型有关。 定义3 分页代价。从提出查询请求到显示第一页数据所需要的时间称为分 页代价t w 。可用下式表示： t w = t c o ( x o ) + z r c l ( 五) + t l ( x o x i ) 其中托表示从数据层传输到功能层的数据量，t c o 表示从数据层传输到功 能层的通信代价；五表示从功能层传输到客户层的数据量，tc i 表示从功能层 到客户层的通信代价。 定义4 页间切换代价。从一个页面切换到另一个页面所需要的时间称为页 5 北京化t 人学顾i j 学位论文 间切换代价，用t f 表示。万大小与具体的分页技术有很大关系 2 2 】。 定义5 存储费用。服务器所需要的内存数量称为存储费用m ( x ) 。可用下 式表示： m ( x ) = m o ( ) + m ，( x 。) x o 五 其中k 表示功能层从数据层接收的数据量，m 。表示功能层所在的主机所 耗费的内存数；五表示客户层从功能层接收的数据量，m 。表示客户层所在的主 机所耗费的内存数。 定义6w e b 应用的分页性能模型。对w e b 应用中分页技术进行性能分析的模 型，包括邢，t f 和m ( x ) 三部分。其中邢和t f 是主要的性能指标，而m ( x ) 主 要对分页性能具有制约的作用。 1 3 3m v c 设计模式下j s p 分页技术概述 m v c 是8 0 年代s m a l l t a l k 8 0 中出现的一种软件设计模式，是最著名的程 序设计模式之一。所谓m v c 程序设计模式，是指模型( m o d e l ) 、视图( v i e w ) 和控 制器( c o n t r o l l e r ) 相分离的设计方案【2 3 2 4 1 。模型只提供纯粹功能性的公开接口和 参数，让系统其他部分能通过这些公开接口得到或修改模型的内部状态参数。视 图决定模型以什么样的方式显示给用户，一个模型可以对应多个视图，那么对于 视图来说，模型就是可重用的代码。控制器是和视图联合使用的。用户在与视图 发生交互的时候，是通过控制器来操纵模型，从而向模型传递数据，更新模型的状 态。s u n 公司j s p 技术体系的m v c 程序设计模式如图1 - 3 所示。 传统的开发j s p 动态网站的程序设计模式是将所有服务器端应用逻辑代码 全写在j s p 程序或s e r v l e t 程序中，难于维护。而用m v c 程序设计模式开发j s p 分 页程序将功能模块和显示模块有效分离，从而改善了分页显示程序的可维护性。 图1 - 3j s p 技术体系中的m v c 程序设计模式 f i g 1 3m v cd e s i g np a t t e r ni nt o c h n o l o g ya r c h i t e c t u r e j s p 分页技术是针对用户查询大批量数据时，基于j s p 动态网页技术的 w e b 站点将数据分批传送至客户端浏览器显示所采用的技术。常用的技术方案 有：( 1 ) 用户每次查询都直接将满足查询条件的数据全部取出，存放在服务器端的 6 第一章绪论 结果集对象中，再用控制游标位置和限制查询范围的方法来达到分页显示目的， 这种方案只适用于小型、用户量少和信息量少的网站。在用户量大和信息量大 的情况下，大批量数据频繁取出，每次查询都要建立与数据服务器的连接，与之通 讯、登录验证等无疑会大大地消耗服务器的内存和c p u 资源【z 引。( 2 ) 用户在第一 次查询时就将所有满足查询条件的数据全部取出，并将这些数据保存在一个作用 于会话的结果集对象中( 将这个结果集对象捆绑在一个s e s s i o n 会话变量中) ，给 用户在与网站整个会话阶段的页面请求提供数据源，控制游标位置并限制查询范 围以获取当前页所需数据【2 6 1 。这种方案稍优于前一种方案，用户后续页面请求不 再与数据库服务器交互，但仍消耗服务器内存。基于以上两种技术方案的分析， 采用某些数据库服务器支持( 如o r a c l e ) 的l i m i t 查询条件或用户第一次页面请求 时读取少量特征数据放在一个作用于会话的结果集对象中( 如信息i d 关键字，针 对不支持l i m i t 查询条件的数据服务器，如s q ls e r v e r ) 来限制查询范围，以达到 分页目的，这不失为一种较好的分页显示技术方案。用户每次页面请求时根据 l i m i t 查询条件或少量特征数据确定当前页数据查询范围，访问数据库获取当前 页所需的少量数据，访问完毕后及时断开数据库连接以释放内存和c p u 资源，使 服务器能快速响应其他用户请求，从而克服了前面两种分页方案的不足【2 心列。 1 4 查询优化和分页技术的发展前景 1 4 1 查询优化技术展望 查询优化工作是一个系统的琐碎的过程，但却又是决定系统是否成功的关键 所在，所以无论作为一个系统开发者还是一个数据库d b a ，数据库优化都是一个 无法回避的工作。数据库的优化包括很多种，如数据库环境、服务器配置、网络 设置以及数据库实例和对象的调整，但是越来越多的研究者发现，s q l 的调整才 是所有优化的重中之重。经过2 0 多年的努力，很多专家、学者都做了大量的研究 工作，提出了很多优秀的解决方案，提出了很多相应的算法。 ( 1 ) 数据库统计概貌的管理。统计概貌信息在生成执行计划过程中，起着非 常重要的作用。传统地，数据库是在假设每个属性都是独立的基础上建立统计概 貌的，优化器用这些统计概貌信息来生成执行计划。通常，这些方法会产生大量 的估算错误，而且直接导致最终执行计划效率的低下。如何选用有价值的统计信 息，如何排除无用的统计信息，如何使统计信息的维护费用达到最小，都是统计 概貌管理所关心的而且急需解决的问题。成功地建立一个“最有益”的统计概貌 集合，对查询优化具有重要的意义。 ( 2 ) s o l 的查询重写。自从八十年代提出在查询优化过程中采用查询重写这一 7 北京化- t 人学硕：l ：学位论文 新技术后，查询优化的研究范围进一步得到推广。同时查询重写是查询优化器的 重要组成部分，它将一个查询表示根据一定的规则，转换为另一个效率更高或更 易于优化的查洵表达式。如何发现更多而有效的重写规则，也是当前查询优化研 究的主要研究内容。 ( 3 ) 查询优化算法。对于优化算法的研究仍然是查询优化研究的一个难点和 重点。在关系数据库中，最难处理和优化的一个逻辑操作符是连接( j o i n ) ，由于 多个关系连接时可以有很多不同的次序，因此对应于查讯的执行计划的数目会随 着该查询包含的关系个数呈指数级增长，当关系个数很多时，将导致搜索空问极 度膨胀，传统的数据采用的大多是s y s t e mr 的空间搜索算法或其变形算法，这 一般都是近乎于穷举的搜索算法。在决策支持系统中，查询所涉及到的关系数目 通常都很大，这将使得这类搜索算法毫无用处。现在越来越多成熟的优化算法被 引入到查询优化中来处理连接关系较多时的优化问题，爬山算法、模拟退火算法、 遗传算法，都在一定程度上提高了查询优化的性能。 ( 4 ) 分布式查询优化。现代数据库应用的发展，使得高性能的并行机或分布 式系统逐步取代传统的大型机进行大型数据库的管理和事务处理，但与此不适应 的是，传统的查询优化技术并没有考虑到并行性，从而不能最大限度地发挥并行 机或分布式系统的能力。因此，当前的查询优化也将并行查询的优化作为研究重 点，并行查询中主要考虑以下三个问题： 1 专家模型的评估。由于查询将会是并行执行的，因此我们应该有一个新的专 家模型来评估一个并行执行计划的执行代价。 2 计划空间搜索算法的改进。并行执行计划的引入将大大增加执行计划的计划 空间，因此，也应该有一些适应于并行系统的搜索算法。 3 并行执行计划的表示。并行执行计划的表示在一定程度上也决定了执行计划 的执行步骤。 1 4 2 分页技术的展望 随着信息技术的高速发展，计算机、数据库和网络已成为信息系统的三大支 柱，w e b 应用系统显示出了其强大的优势。而在许多w e b 应用系统中都需要对数 据库中的数据进行查询，并将得到的数据以适当的方式显示出来。随着数据库中 信息量的增大，当查询条件较为宽松时，将会出现大量符合条件的数据。如果简 单地将数据一次性全部显示出来，不仅会降低页面的响应效率，而且也不方便用 户的浏览【2 9 。3 0 1 。这时，就需要采取分页的显示方式。因此，对数据进行分页显示 是十分必要的。 与此同时，随着各种应用系统的普及与使用，用户对系统性能的要求也越 8 第一章绪论 来越高，如何最大限度地提高系统的性能已经成为一个迫切需要解决的问题。目 前，查询分页技术已成为一种对数据库数据操作的常用技术，分页的目的就是 为了使查询方便、页面清晰，方便用户的浏览，如果响应效率很低，就与其目的 背道而驰。因此，如何实现一种高性能的查询分页技术就成为一个值得研究的问 题。 对数据库查询结果进行分页显示的实现方式主要有两种：一种是先将数据库 中所有符合查询条件的记录一次性保存下来，然后通过设置每页要显示的记录 数，确定要显示记录的起始点和终止点来实现分页显示。第二种是根据客户的请 求，每次分别从符合查询条件的记录中将规定数目的记录数读取并显示出来【3 。 如果数据库的数据相对较少，同时使用查询功能的人数也不是很多时，两种方 法的执行效率基本相同。此时，第一种方法实现起来就比较简单。但是当数据库 中的数据很多时，第一种方法的执行效率将明显低于第二种方法。它每次查询时 都要将所有符合条件的记录存放在服务器内存中，然后再进行分页显示，如果 同时又有许多用户在使用查询功能时，应用程序的执行效率将受很大影响。 1 5 论文的研究内容及组织结构 本论文各章的内容如下： 第一章简述了论文研究的目的和意义，分别介绍查询优化与分页技术的概 念，并根据文献综述查询优化和分页技术在国内外的发展前景。 第二章是基于查询优化技术理论基础，针对多连接查询优化算法的搜索策 略。 第三章是基于j s p 的分页技术，先简要介绍了几种传统的分页算法，通过 分析性能比较发现它们存在着一些优缺点，尽而提出一种可扩展的分页方法，详 细阐述了该方法的设计原理和设计流程。 第四章将分页查询技术应用到采购招标系统当中，介绍了一个基于采购招 标系统订单预览分页查询的具体设计。 第五章通过实验对分页查询优化技术进行了分析，并与传统的方法进行了 比较。 9 第一二章基于多连接的奁询优化算法 第二章基于多连接的查询优化算法 2 1 优化器概述 对于用户向d b m s 提出的查询请求q ，查询优化器的目标就是选择最有效的 查询执行计划q e p ( q u e r ye x e c u t i o np l a n ) ，以存取相关数据和回答查询。假定s 是适合查询q 的所有策略的集合，s 中的每一个元素s 都有一个相关联的代价 c ( s ) ，查询优化算法的目标都是找到s o s ，满足 c ( s o ) = m i n c 0 )s o s 实际上，查询优化的最终目的就是提高查询效率，缩短查询请求的响应时间。 花费大量的时间在优化上以找到一个最佳的q e p ，使得优化时间与最佳的q e p 的 执行时间之和非常大，也就是响应时间非常长的做法是并不明智的，因此，在q e p 空间很大的情况下，优化目标并不是找到一个最佳的查询执行计划，而是找到一 个相对较好的查询执行计划，使得“优化时间+ 找到的d e p 的执行时间”最小即可。 2 1 1 优化器优化原理 一个查询往往有很多个查询执行计划d e p ，这是因为一个查询请求对应着大 量的等价关系代数表达式，并且一个关系代数表达式可由大量的查询执行计划来 实现，如图所示，图中用椭圆示意一个查询请求q 所对应的等价关系代数表达式 集合和q e p 集合的大小关系，随着q 中包含的关系数的增加和查询执行引擎提供 的物理操作的增加，这两个集合成指数级增长。查询优化器从中找出一个好的 o e p 的问题可以看作是一个n p 问题，查询优化器面对巨大的搜索空间，必须根 据一定的原理来完成查询的优化。 查 询 请 求 q 图2 - 1 高级查询的转换过程 f i g 2 1c o n v e r s i o np r o c e s so fa d v a n c e ds e a r c h 北京化- t 人学硕 ：学位论文 当前优化领域内所采用的查询优化器的基本原理大致分为三类： 1 穷尽精确优化方法 查询优化器的转换过程分为两个部分：一个是逻辑转换部分，它的任务是对 于一个语法树，根据关系代数等价变换规则，得到所有的等价的关系代数表达式； 另一个是物理转换部分，它的任务是对于每一个关系代数表达式，根据存储路径、 连接次序和连接方法等，找出所有可能的查询执行计划。查询优化器根据代价估 计函数，估计每一个查询执行计划的代价，并从中找出代价最小的o e p 。 很显然，这种方法的优化代价是非常大的，因为两个转换部分包含着大量转 换，并且对所有o e p 估计代价都需要大量的时间，且这种时间复杂性随着查询中 包含的关系个数的增加而成指数级增长。 2 两段优化方法 根据查询优化器的“较短的优化时问内找到较好的查询执行计划”的原则， 还可以将查询优化问题分成这样两个阶段：一个是逻辑优化阶段，任务是从等价 的关系代数表达式中找出几个具有最小代价的关系代数表达式；另一个是物理优 化阶段，任务是将逻辑优化得到的几个关系代数表达式转化为对应的所有查询执 行计划，并从中找出最小代价的o e p 。 查 询 请 求 q 逻辑优化阶段物理优化阶段 图2 - 2 两段查询优化的过程 f 蟾2 - 2t w o - s t a g ep r o c e s so fq u e r yo p t i m i z a t i o n 3 启发式算法 启发式优化建立在两段优化的基础上，不同的是，在逻辑优化部分加入了启 发式规则( 所谓的启发式规则是指用户根据需要自定义的一些规则) 和若干代数 表达式的等价变换规则。对语法树的操作次序和组合做了一些变化和调整，期望 得到的关系代数表达式的代价较小，虽然得到的关系代数表达式不一定是所有等 价表达式中执行时间最小的，但逻辑优化的时间一定比两段优化方法的逻辑优化 的时间要少。由此看出，启发式优化方法的本质是牺牲最优换取优化时间的减少， 以期达到“优化时间+ 找到的o e p 的执行时间 最小的目标。 1 2 第二章基于多连接的查询优化算法 2 2 多连接查询优化 在关系数据库中，s p j ( s e l e c t p r o j e c t j o i n ) 查询是使用的最为频繁的一种查询。 对s p j 查询除了采用代数定律等价变换的方法外，广泛认同的规则有：将s e l e c t 操作尽早的执行以及尽早的执行p r o j e c t 操作。在对s p j 查询进行选择和投影下推 的处理后，s p j 的查询的优化问题就可归结为多元连接查询的优化。最早涉及多 连接查询优化的关系数据库有s y s t e mr 和i n g r e s ，由于连接操作是数据库查询 时最为昂贵的操作，同时随着数据库的不断扩大和查询的日益复杂，要使得提高 多连接查询( 所涉及的关系数大于1 0 ) 的响应速度成为亟待解决的问题。 2 2 1 多连接查询优化问题的图论描述 查询优化器所处理的多连接查询可以用树结构表示，也可以由查询线图表 征，查询线图g = ( y ，e ) 。其中，v 是表征关系的结点集，e 是表征两个关系相连 接的边集。对应多连接查询树的j o i n 树，则中间结点表示j o i n 操作，边表示数 据流向。查询线图的结果实际可以定义为： 。，： 朋( r l x 砌) ，其中， p 1 ，p n ) 是用来标识边的。查询线图如图 所示 图2 _ 3 查询线图 f i g 2 - 3p i c t u r eo fi n q u i r el i n e 查询线图与前面提到过的查询执行计划( q e p ) 的不同点在于：d e p 即强调的 每个操作符的输入，和它是如何评估的；而线图强调的是关系的收集和谓词的连 接，并不涉及次序的问题。然而查询线图与d e p 是相互联系的。一般情况下，给 定一个查询线图可以计算出有效的d e p 的数目，当然这并非易事，因为查询线图 的拓扑结构往往很复杂，但当查询线图有一个规则结构的时候，有效查询计划就 可以被容易的计算出来了。一般是由完全连通图和一个线型图入手解决的。 2 2 2 影响多连接查询优化的因素 影响多连接查询优化效率的因素有很多，主要有： 1 j o i n 树对应的查询线图的拓扑结构( 与代数空间相关) ： 1 3 北京化丁人学硕：i ：学位论文 2 操作的算法即连接和存取的方法( 与路径选择空间相关) ： 3 找到最佳d e p 的搜索算法。 2 3 组合优化问题 多连接查询优化问题实际上是一个组合优化问题。所谓的组合最优化 ( c o m b i n a t o r i a lo p t i m i z a t i o n ) 是通过对数学方法的研究去寻找离散事件最优编排、 分组、次序或筛选等，是运筹学( o p e r a t i o n sr e s e a r c h ) 中的一个经典且重要的分支， 所研究的问题涉及信息技术、经济管理、工业工程、交通运输、通信网络等诸多 领域。关于组合优化问题的研究，特别是求解复杂组合优化问题方法的探索已经 成为众多学科关注的焦点，这不仅在于其内在的复杂性问题有着重要的理论价 值，也在于其在现实生活中的很多方面有着广泛的应用，尤其是对于冲完全问题， 它们都有着非常精确的数学描述和复杂性度量，而且在理论上存在精确解。但是 即使是使用当今最快速的计算机，我们仍无法求得其具有中小规模问题的最优 解，这无疑将成为科学发展的一个巨大挑战。 典型的组合优化问题有o _ l 背包问题、t s p 问题、装箱问题等n p h a r d 问题。 在数据库领域随着数据库中存储的数据量的不断增长以及对数据库的操作从事 务型转换到事务型和分析型操作并存，组合优化问题就显得愈发重要了。 2 3 1 组合优化问题概述 组合优化问题可用的数学模型描述为 r a i nf ( x ) s t g ( x ) 0 ， x d ， 其中，厂( 功为目标函数，g ( x ) 为约束函数，x 为决策变量，d 表示有限个点组成 的集合。一个组合最优化问题可用三参数( 口e ，) 表示，其中d 表示决策变量的 定义域，表示可行解区域f = 扛l 石d ，g ( 功0 ) ，f 中的任何一个问题元素， 成为该问题的可行解f ( x ) 目标函数。满足f ( x + ) = m i n f ( x ) l x f ) 的可行解，成 为该问题的最优解。组合最优化的特点是可行解集合为有限点集，由直观可知， 只要将d 中有限个点逐一判别是否满足g ( x ) 的约束和比较目标值的大小，该问题 的最优解一定存在和可以得到。 下面介绍两个经典的组合优化问题。 1 o 1 背包问题( k n a p s a c kp r o b l e m ) 1 4 第二章基于多连接的查询优化算法 设有一个容积为b 的背包，n 个体积分别为qo = l ，2 ，n ) ，价值分别是 c f ( f = l ，2 ，3 ，z ) 的物品，如何以最大的价值装包? 这个问题成为o 一1 背包问题， 用数学模型表示为： m a x m a x q 耳z c i x i f = l 砒q 而s 6 一l ， 毛 o ，1 ) ，i = 1 ，2 ，刀 ( 1 2 ) ( 1 3 ) 其中目标( 1 1 ) 欲使包内所装物品的价值最大，( 1 2 ) 为包的能力限制，( 1 3 ) 表示 五为二进制变量，x t = 1 表示装第一个物品，五= o 表示不装。此时，d = 0 ，1 ， f 为d 中满足( 1 2 ) 的可行解集。f 为目标函数。 2 旅行商问题( t s p , t r a v e l i n gs a l e s m a np r o b l e m ) 一个商人要到1 1 个城市推销商品，每两个城市i 和j 之间的距离为或，如何选 择一条道路使得商人每个城市走一遍后回到起点且所走路径最短。该问题很类似 于查询优化问题中的代价评估。t s p 问