关系型数据库进阶之查询优化
在前面几篇文章中,我们已经介绍了总体构架,客户端管理和查询管理。在查询管理中,有一个很重要的部分我们没有介绍,那就是查询优化,这也是本文所要介绍的内容。 所有的现代数据库都是基于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是最简单的一种情况...