数据库系统中的查询技术探讨毕业论文.docx

毕业设计(论文)题 目 名 称 数据库系统中的查询技术探讨院 （系） 专 业 班 级 学 生 姓 名 指 导 老 师 辅 导 老 师 时 间 目录毕业设计任务书 i开题报告 iii指导教师审查意见 ix 评阅教师评语 x答辩会议记录 xi摘要 xii1 前言12 选题背景22.1 课题的背景及来源22.2 研究的目的和意义22.3 国内外发展现状和趋势与研究的主攻方向33 查询优化概述33.1 查询优化的基本概念33.2 关系查询语言43.3 查询优化目标53.4 查询处理流程64 数据库查询优化技术74.1 分布式查询优化7 4.1.1 分布式查询优化需要考虑的问题7 4.1.2 分布式查询优化过程8 4.1.3 分布式查询优化的目标94.2 查询优化技术104.3 实例分析125 总结156 参考文献 157 致谢 16中文摘要 数据库系统中的查询技术探讨学 生 ： 学院指导老师 ： 学院【摘要】 数据库技术是通过研究数据库的结构、存储、设计管理以及应用的基本理论和实现方法，并利用这些理论来实现对数据库中的数据进行处理、分析和理解的技术。即：数据库技术是研究、管理和应用数据库的一门软件科学。查询优化技术是数据库管理系统设计和实现所采用的一项重要技术，也是影响数据库系统性能的一个重要因素，当前所有商用数据库都成功采用了这项技术。关系数据库系统和非过程化的sql语言能够取得巨大成功，主要得益于查询优化技术的发展。对于一个复杂的查询，寻找一个优化的执行策略是数据库系统开发成功的关键所在，此项研究目前在数据库领域仍属于np问题。在查询执行的过程中，低效的sql查询语句,概貌信息的匮乏、连接顺序的错误选择都是直接导致查询低效的原因。 【关键词】：数据库技术；查询优化技术；sql语言；低效1外文摘要query technology of database systemsstudent: mathematicstutor : mathematics【summary】database technology is the basic theory and implementation methods through research database structure, storage, design, management, and application, and use these theories to achieve the data in the database for processing, analysis and understanding of the technology. namely: database technology is a software science research, management, and database applications.query optimization technology is an important technology database management system design and implementation used is also an important factor in database system performance, all current commercial databases have successfully adopted this technology. relational database systems and non-procedural sql language can achieve great success, mainly due to the development of query optimization techniques. in the query execution process, inefficient sql queries, overview lack of information, the connection sequence of wrong choices are a direct result of the query of inefficiency. keywords：database technology; query optimization technology; sql language; inefficient.xiii前言 数据库系统中的查询技术探讨1、前言1.1 数据库的产生和发展以前，当人们需要了解大量复杂的资源信息时，都只有通过相关的书籍或者光盘，磁盘等等进行查找，这通常需要耗费大量的人力和时间，效率尤为低下。而随着网络技术与数据库技术日益结合的成熟性，使得这一问题得到了很好的解决，人们仅需在家里的电脑上动动手指，就能快捷的得到各种所需要的信息，这大大满足了广大人民的需求。数据库技术产生于20世纪60年代末70年代初，其主要目的是有效地管理和存取大量的数据资源.数据库技术主要研究如何存储，使用和管理数据. 数年来，数据库技术和计算机网络技术的发展相互渗透，相互促进，已成为当今计算机领域发展迅速，应用广泛的两大领域.数据库技术不仅应用于事务处理，并且进一步应用到情报检索，人工智能，专家系统，计算机辅助设计等领域。1.2数据库技术概述数据库技术是通过研究数据库的结构、存储、设计、管理以及应用的基本理论和实现方法，并利用这些理论来实现对数据库中的数据进行处理、分析和理解的技术。即：数据库技术是研究、管理和应用数据库的一门软件科学。数据库技术研究和管理的对象是数据，所以数据库技术所涉及的具体内容主要包括：通过对数据的统一组织和管理，按照指定的结构建立相应的数据库和数据仓库；利用数据库管理系统和数据挖掘系统设计出能够实现对数据库中的数据进行添加、修改、删除、处理、分析、理解、报表和打印等多种功能的数据管理和数据挖掘应用系统；并利用应用管理系统最终实现对数据的处理、分析和理解。第 1 页 共 16页2、选题背景2.1课题类型及来源课题类型：设计类课题来源：其 他2.2研究的目的和意义 现如今很多地方都离不开数据库，而查询操作在各种数据库操作中（如增、删、改、查）所占据的比重最大，通过查询数据库就可以有效的得到想要的数据。但是，现实中许多数据库开发人员。许多程序员认为查询优化是数据库管理系统(dbms)的任务，与程序员所编写的sql语句关系不大。在利用一些前端数据库开发工具开发数据库应用程序时只注重用户界面的华丽，并不注重查询效率，导致所开发出来的应用系统中查询时间长，响应速度慢，甚至查询结果不够准确等，系统工作效率低下，资源浪费严重，这是错误的，一个好的查询执行计划往往可以使程序性能提高数十倍。究其原因，一是硬件设备（如cpu、磁盘）的存取速度跟不上，内存容量不够大；另一方面是数据查询方法不适当，抑或是没有对数据查询技术进行优化。举例来说，如果数据的量积累到一定程度，比如一个银行的账户数据库表信息积累到上百万甚至上千条记录，全表扫描一次往往需要几十分钟，甚至有几个小时。如果采用比全表扫描更好的查询策略和技术，往往可以使查询时间降为几分钟或是更短，由此可以看到查询优化技术的重要性和必要性。所以，对数据库查询技术的优化研究就变得尤为重要。这对工作效率有极大的影响，这也是本人选择此题目的理由。第 23 页 共16页选题背景2.3国内外发展现状和发展趋势与研究的主攻方向从20 世纪60 年代末期开始到如今，数据库技术已经发展了40 多年，已经经历了三代演变，目前已经发展成为一个庞大的数据库家族，而且关系数据库取得了巨大的成功，关系数据库以其查询语言的非过程化，数据模型和用户视图的简明性，以及较高的数据独立性等特点，已经被广泛使用，在数据库领域中占有重要的地位。我国的数据库(主要是中文数据库)建设起步于70年代中后期,经过几十年的发展，我国的数据库技术进步很大，在商用数据库管理系统（dbms）中也出现了像openbase、secbase等自主版权的数据库管理系统。数据库查询技术也随着数据库的发展而进步着。但是，由于使用高级查询语言和存在费时低效的多关系连接操作使得数据库的响应速度较慢，让众多用户无法忍受。查询响应速度已经成为数据库的重要指标和主要发展瓶颈，特别是对于大型数据库而言，这一点尤为突出。为了实现快速查询，除了在数据库的物理设计、关系规范化等方面进行改进外，一个关键措施就是提供最优的查询路径决策能力，提高查询响应速度。本文就是通过此方面的探讨和研究，力争使secbase数据库的查询优化技术得到进一步提高。3、 查询优化概述3.1查询优化的基本概念所谓查询优化，就是在查询执行引擎生成一个执行策略的过中，尽量使查询的总开销和总时间达到最小。实际系统对查询优化的具体实现不同，但一般来说，可以归纳为四个步骤：（1）将查询转换成某种内部表示，通常是语法树。 （2）根据一定的等价变换规则把语法树换成优化(标准)形式。 (3) 选择底层的操作算法。对于语法树中的每一个操作需要根据存取路径、数据的存储分布、存储数据的聚簇等信息来选择具体的执行算法。 （4）生成查询计划。查询计划是由一系列内部操作组成的，这些内部操作按照一定的次序构成查询的一个执行方案，通常这样的执行方案有很多个，需要对每个执行计划计算代价，从中选择代价最小的一个。其过程如下图1所示: 图1 查询优化处理过程 3.2关系查询语言数据库的查询主要是通过查询语言来完成的，关系查询语言通常分为过程性的和描述性的。关系数据模型可以为数据库提供一个数据无关的接口，关系数据库语言是关系演算，进行数据查询时，只需对要查询的数据进行简单的描述，而无须说明如何获取这查询优化概述些数据。关系代数是关系模型中最为著名的过程性查询语言，是关系操纵语言的一种传统表达方式，它是用对关系的运算来表达查询的，关系代数的运算按运算符的不同可分为传统的集合运算和专门的关系运算。传统的集合运算是二目运算，包括并、差、交、广义笛卡尔积四种运算。专门的关系运算包括选择、投影、连接、除等。关系数据库中用得最广泛的描述性语言就是sql查询语句，其本质就相当于数据操纵语言dml。使用sql语言进行数据库查询，用户可以方便快捷的获取数据，但是使用这种语言，同样也需要对搜索、存取操作以及数据传输过程进行必要的说明，因此相应的查询优化技术的研究也在不断进行中。sql语言的一般格式如下：select columnlist from tablelist where conditionlist其中，columnlist是要返回的查询结果的属性列表，tablelist是查询所涉及到的所有关系，conditionlist是条件表达式，条件表达式中的谓词可以将查询作为其操纵数。 3.3查询优化目标查询优化的目标是：用最少的代价，最短的时间取得最理想的结果。基于用最少的代价的目标是，使查询执行所使用的系统资源总和尽量地少，从而降低系统开销，整个系统的开销可以从单个系统资源的开销表达式中推出；基于最短的查询时间优化的目标是尽量走最短最有效的路径，从而减少查询的响应时间。3.4查询处理流程 查询处理过程如下图2所示：图2 查询处理步骤 基本步骤包括： 1. 语法分析与翻译； 2. 优化； 3. 执行。 查询处理开始之前系统必须将查询语句翻译成系统内部的表示形式。翻译过程类似与编译器语法分析器的工作。在翻译过程中要对用户的查询进行语法检查，并构造该查询语句的语法分析树表示，进而翻译成关系代数表达式。优化器利用数据字典中的统计信息对关系代数表达式进行代价评估，从而产生出最优的执行计划。执行引数据库查询优化技术擎再为每一个关系操作或操作组实现一系列物理操作。4 数据库查询优化技术4.1分布式查询优化41.1分布式查询优化要考虑的问题分布式数据库存在于网络环境中，由于数据的分布性，一次查询所操纵的对象可能分布于不同的网络节点中，由此带来的开销和执行速度就会不一样，优化所要考虑的因素就更为复杂。分布式数据库环境中的查询优化要考虑以下两个关键的问题：(1)数据和信息均要通过通信线路进行传输，存在延迟的问题将减慢整个查询执行过程。(2)网络中多处理器的存在提供了并行处理和传输的机会，应充分利用可以加快查询相应的速度。在分布式数据库系统中，还影响到物理查询计划设计的复杂性和可选方案。在选择物理查询计划时必须考虑的问题包括:(1)如果某个所需的关系r有多个副本，那么应该从哪个副本中获得r的值。(2)当在两个关系r和s上实施某个操作时，若有多个可选方案时，我们应该选择哪个。为了简化查询的执行，有五条应用于等价变换的一般准则：(1)使用选择和投影的幂等来为每个操作数关系产生相应的选择和投影。 (2)把算符树中的选择和投影运算尽可能向下推移。 (3)把选择运算向下推到算符树的树叶处，然后对它们使用限定关系代数；如果结果的限定语是永假式，则用空关系来代替此次选择的结果。 (4)利用限定关系代数来求结合的操作数的限定语之值；如果结合结果的限定语是永假式，则用空关系来代替此子树，包括此结合及它的操作数在内。 (5)为了分布出现在全局查询中的结合，必须把并集向上推，超过我们要分布的结合的范围。 4.1.2 分布式查询优化过程 分布式查询优化已经开展了很多年，从各种应用角度，所有的工作都可以归分为两种基本的方法： (1) 通过减少分布式查询中数据传输的数量来降低传输的费用。 (2) 用并行技术来降低反应时间。下图3体现了分布式查询处理的各个阶段，这个查询从用户输入sql语句开始，然后由解析器翻译，并进行优化，使之成为一个可以执行的查询计划，行资源生成器执行这个计划，最后得出查询的结果。 图3 分布式查询优化处理过程下面给出处理过程中的每一步的完成的功能：(1)解析器。在这个阶段，查询语句被解析成查询的内部表示，以便后面的各阶段的处理。(2)基于规则的优化器。又可以称为查询重写器。根据规则删除语句的一些冗余的信息，简化表达式、子查询和视图。语句在这一步，进行了简单的优化。在分布式数据库系统中，查询重写器还能够选出那些要参与查询操作的数据库表。 (3)基于代价的查询优化器。负责主要的优化工作，根据数据库的统计概貌信息，选择执行查询语句中涉及到的操作运算的次序，如何为每个操作分配内存。在分布式数据库中，这一步还必须能够选择每个操作的执行站点。为了完成这一系列的选择，查询优化器会枚举出所有可能的执行计划，根据每个查询计划的代价估计，选择最优执行计划。 (4)字典表。数据库的统计描述，它保存了数据库的模型信息，如表定义、视图、用户自定义类型和函数、约束等。基于代价的查询优化器在生成执行计划时，将其作为进行定量分析的参考。它通常包含元组的数目、属性的大小和对于不同属性的不同值的数目。在分布式数据库系统中，还通常包括关系的站点信息。 (5)执行计划。一个执行计划描述一个查询请求是如何具体地被执行，几乎所有的数据库系统都用同样的方法来表达查询计划语法树。树的叶节点是每个需要操作的关系；树的中间节点就是查询计划中的每次操作的操作符，每个操作符代表一个特定的操作(如选择、投影、连接等)。在分布式数据库中，还要考虑同一关系表的不同的分段。图14给出一种不同站点之间的查询处理过程。(6)全局信息表。全局信息表储存了分布式站点用于解析、重写和优化各阶段所需的所有信息。保存了数据库分布信息、全局分段和重构规则和表的物理存储位置。在集中式数据库中，字典表可以提供查询优化所需的信息，而在分布式数据库系统，这样一个全局信息表是必不可少的。 (7)行资源生成器。根据最终确定的执行计划，访问数据库获得查询结果返回给用户。分布式数据库中，还要考虑同一关系表的不同的分段。4.1.3 分布式查询优化的目标 分布式数据库系统中，虽然数据存在分布透明性，但是我们在查询处理中仍然要考虑站点间传输数据的通信费用，所以相对于集中式数据库来说，它的总代价除了考虑cpu代价和fo代价之外，还应考虑数据在网络上的传输代价，即：总代价=cpu代价+io代价+通信代价。在分布式数据库中，则还必须考虑数据的传输量。然而，在传输的费用和本地io的费用之间哪个更为重要没有统一的看法。本文认为只考虑传输方面的要求是很合理的，因为：(1)传输要求对于系统是公平的，一般来说它们在站点之间传送的数据量的函数是一致的。(2)一个分布式查询的优化可以分成为两个独立的问题：站点之阃访问策略的分布；每个站点处的本地访问策略，这可使用集中式数据库的传统方法。各个问题是按上述次序来解决的，因为前者比后者更重要。4.2 查询优化技术以及实例分析虽然现在的数据库产品在查询优化方面已经做得越来越好，但由用户提交sql语句是系统优化的基础，因此用户所写语句的优劣很重要，下面先介绍几个改善用户查询计划的方法：1）合理使用索引索引是数据库中重要的数据结构，它的根本目的就是为了提高查询效率。现在大多数的数据库产品都采用ibm最先提出的isam索引结构。索引的使用要恰到好处，其使用原则如下： 在经常进行连接，但是没有指定为外键的列上建立索引，而不经常连接的字段则由优化器自动生成索引。 在频繁进行排序或分组（即进行groupby或orderby操作）的列上建立索引。 在条件表达式中经常用到的不同值较多的列上建立索引，在不同值少的列上不需要。比如在 “性别”列上只有“男”与“女”两个不同值，如果建立索引不但不会提高查询效率，反而会严重降低更新速度。 如果待排序的列有多个，可以在这些列上建立复合索引。 使用系统工具。如informix数据库有一个tbcheck工具，可以在可疑的索引上进行检查。在一些数据库服务器上，索引可能失效或者因为频繁操作而使得读取效率降低，如果一个使用索引的查询不明不白地慢下来，可以试着用tbcheck工具检查索引的完整性，必要时进行修复。另外，当数据库表更新大量数据后，删除并重建索引可以提高查询速度。 2）避免或简化排序应当简化或避免对大型表进行重复的排序。当能够利用索引自动以适当的次序产生输出时，优化器就避免了排序的步骤。以下是一些影响因素：索引中不包括一个或几个待排序的列；groupby或orderby子句中列的次序与索引的次序不一样；排序的列来自不同的表。3）消除对大型表行数据的顺序存取在嵌套查询中，对表的顺序存取对查询效率可能产生致命的影响。比如采用顺序存取策略，一个嵌套3层的查询，如果每层都查询1000行，那么这个查询就要查询10亿行数据。避免这种情况的主要方法就是对连接的列进行索引。例如，两个表：学生表（学号、姓名、年龄）和选课表（学号、课程号、成绩）。如果两个表要做连接，就要在“学号”这个连接字段上建立索引。4）避免相关子查询一个列的标签同时在主查询和where子句的查询中出现，那么很可能当主查询中的列值改变之后，子查询必须重新查询一次。查询嵌套层次越多，效率越低，因此应当尽量避免子查询。如果子查询不可避免，那么要在子查询中过滤掉尽可能多的行。 5）避免困难的正规表达式matches和like关键字支持通配符匹配，技术上叫正规表达式。但这种匹配特别耗费时间。 6）使用临时表加速查询把表的一个子集进行排序并创建临时表，有时能加速查询。它有助于避免多重排序操作，而且在其他方面还能简化优化器的工作。7）用排序来取代非顺序存取非顺序磁盘存取是最慢的操作，表现在磁盘存取臂的来回移动。sql语句隐藏了这一情况，使得我们在写应用程序时很容易写出要求存取大量非顺序页的查询。4.3 实例分析下面我们举一个制造公司的例子来说明如何进行查询优化。制造公司数据库中包括3个表，模式如下所示：part表零件号（part_num）零件描述（part_desc）其他列（othercolumn）102，032seageat30gdisk500，049novel10mnetworkcardvendor表厂商号（vendor_num）厂商名（vendor_name）其他列（othercolumn）910，257seageatcorp 523，045ibmcorp parven表零件号（part_num）厂商号（vendor_num）零数量（part_amount）102，032910，2573，450，000234，423321，0014，000，000下面的查询将在这些表上定期运行，并产生关于所有零件数量的报表： selectpart_desc，vendor_name，part_amount frompart，vendor，parven wherepart.part_num=parven.part_num andparven.vendor_num=vendor.vendor_num orderbypart.part_num 如果不建立索引，上述查询代码的开销将十分巨大。为此，我们在零件号和厂商号上建立索引。索引的建立避免了在嵌套中反复扫描。关于表与索引的统计信息如下：表(table)行尺寸(rowsize)行数量（rowcount）每页行数量（rows/pages）数据页数量（datapages）part15010,00025400vendor1501,0002540parven1315,00030050索引（indexes）键尺寸(keysize)每页键数量（keys/page)页面数量(leafpages）part450020vendor45002parven825060结果分析通过查看系统表可以看到，在part_num上和vendor_num上有簇索引，因此索引是按照物理顺序存放的。parven表没有特定的存放次序。这些表的大小说明从缓冲页中非顺序存取的成功率很小。此语句的优化查询规划是：首先从part中顺序读取400页，然后再对parven表非顺序存取1万次，每次2页（一个索引页、一个数据页），总计2万个磁盘页，最后对vendor表非顺序存取1.5万次, 合3万个磁盘页。可以看出在这个索引好的连接上花费的磁盘存取为5.04万次。实际上，我们可以通过使用临时表分3个步骤来提高查询效率： 1从parven表中按vendor_num的次序读数据：selectpart_num，vendor_num，pricefromparvenorderbyvendor_numintotemppv_by_vn这个语句顺序读parven（50页），写一个临时表（50页），并排序。假定排序的开销为200页，总共是300页。2把临时表和vendor表连接，把结果输出到一个临时表，并按part_num排序:selectpv_by_vn，vendor.vendor_numfrompv_by_vn，vendorwherepv_by_vn.vendor_num=vendor.vendor_numorderbypv_by_vn.part_numintotmppvvn_by_pndroptablepv_by_vn这个查询读取pv_by_vn(50页)，它通过索引存取vendor表1.5万次，但由于按vendor_num次序排列，实际上只是通过索引顺序地读vendor表（402=42页），输出的表每页约95行，共160页。写并存取这些页引发5160=800次的读写，索引共读写892页。3把输出和part连接得到最后的结果：selectpvvn_by_pn.，part.part_descfrompvvn_by_pn，partwherepvvn_by_pn