Tagged: 查询优化

0

关系型数据库进阶之查询优化二

在前面的文章中我们介绍了查询优化的基础,着重介绍的两个表的JOIN的优化。本文就来看看我们在实际中更常见到的多表JOIN的优化。 现在我们来假设有五个表进行join,我们需要从不同的表中得到一个人的不同信息,比如地址,mail,mobiles等等,简单的QUERY如下所示: 作为查询优化器需要找到最佳的查询数据的方法,这里有两个问题: 每一个join需要使用什么类型的JOIN?我们有三种可能的JOIN (Hash Join,merge  Join, Nested Join) 先做哪个JOIN再做哪个JOIN? 下面这个是一个简单的示意图,有四个表,三个JOIN的情况,显然五个表的情况会更加复杂。 好的,那我们该怎么做呢? 1)暴力解法 遍历所有的可能性,然后找到最佳的方法。在上面的例子中,每一种join有三个可能(HASH, MERGE, NESTED),对于给定顺序的JOIN就有3^4中可能,而JOIN的顺序也是不定的,四个JOIN其实有(2*4)!/(4+1)!种可能的排序,这样一来,这个五个表的JOIN有 3^4*(2*4)!/(4+1)!种可能。 也就意味着,有27216中可能的计划。假如说merge join有0,1,2 B+ tree index,那么这种可能性就变成210000种了。而这还只是一个简单的JOIN。 2)只试验一些计划,然后选择其中最好的 因为可能性太多了,那么我们随机选择其中一些,然后计算他们的cost,选择其中最好的。 3)应用一些规则,来减少可能的计划 这里通常有两种规则: 使用一些简单的逻辑规则去除一些没有用的可能性,只是说这种去除不是很多。比如“nested loop join的inner relation必须是最小的数据集“ 使用一些有侵略性的规则来减少可能性。比如“假如一个relation很小,那么使用nested loop而不使用merge join和hash join”...

0

关系型数据库进阶之查询优化

在前面几篇文章中,我们已经介绍了总体构架,客户端管理和查询管理。在查询管理中,有一个很重要的部分我们没有介绍,那就是查询优化,这也是本文所要介绍的内容。 所有的现代数据库都是基于cost进行优化的(Cost Based Optimization, CBO)。总体的思想就是看每一个操作的cost是多少,然后找出一个cost最小的路径来执行这些操作并获取结果。 本文会首先以最常的三种join为例来进行介绍,看看哪怕是简单的join,它背后的优化是如何进行工作的。在这些例子中,我们关注时间复杂度,这个其实和真实的数据库优化器的计算是有所不同的,它真实会关注CPU消耗,磁盘I/O消耗以及内存的需求。时间复杂度和CPU消耗其实是差不多的,我们这种懒人就直接使用时间复杂度来进行分析了。当然有时候我们还需要考虑磁盘的I/O消耗,因为很多时候真正的瓶颈就是在于磁盘I/O而不是CPU的使用率。 JOIN的操作 我们会来看三个最常见的join操作,merger Join, Hash Join以及Nested Loop Join。在正式开始之前,我们来引入两个名词,outer relation和inner relation,很简单outer relation就是join左边的数据集,inner relation就是join右边的数据集。比如A JOIN B, 我们把A称之为outer relation而B称之为inner relation。并且假设outer relation有N个元素,inner relation有M个元素。我们可以很容易知道A JOIN B和B JOIN A其实是不太相同的。 Nested loop join Nested loop join是最简单的一种情况...