数据库内核基础

浏览数：35 / 时间：2015年06月12日

本文简单介绍了数据库通用的内核基础以及和分布式的一些类比

(1)经常使用数据库的疑问

经常使用数据库，有一个疑问，假如在数据库中输入select * from table，那么数据库如何把这条语句识别成可执行状态？

(2)数据库内部解析主要步骤

SQL---->Parser

客户端输入一条SQL字符串后，例如select,create等语句，首先会进入Parser模块，对于Parser模块，用户输入的是一条字符串，经过Parser模块会解析成数据库能够识别的状态，它会申请结构体或者一个内存空间把字符串给存起来。

例如select * from tb1。Parser模块会把这条SQL拆分成select、*、from、tb1，然后分别存入相应的内存空间中。

目前主要的Parser主要有两个框架，分别是Yacc和Lex。

2.Parser--->Analyzer

经过Parser模块的初步解析后转换成语句，还要经过Analyzer进一步解析，例如tb1有哪些属性，tb1是分区表还是非分区表，是视图还是物化视图。这些解析都会在Analyzer模块中进行。如果Parser是语法解析器，那么Analyzer模块就是语义解析器。

3.Analyzer--->Query

经过了Analyzer模块后，会进入Query模块，Query模块会把Analyzer模块解析后的表达式或者表或者视图定义转化成内部可以识别的初步的树结构，但这只是一个初步的树还没有形成二叉树等复杂结构。

4.Query--->Optimizer

Optimizer即所谓的优化器。在数据库中输入一条语句为什么会走索引扫描，为什么两张表做join的时候为什么会走hashjoin，这些都会Optimizer中决定。优化器会决定表的连接方式比如走索引还是顺序扫描；如果是索引是走普通索引还是别的方式，是仅仅访问索引还是要访问物理表；而且优化器还会决定表的连接顺序，n张表做连接是MergeJoin、嵌套循环连接还是hash连接。优化器决定这些连接的算法有两种，动态规划算法和遗传算法。一般10张表以下的都是动态规划算法，10张表以上的基本上是遗传算法。计划生成后如果表还有分区表的话需不需要根据表的连接条件对分区进行裁剪。

5.Optimizer--->Plan

Optimizer输入的是Plan，Plan就是一个计划树，这个树是二叉的形式。

(3)一些看法

可以看到从SQL到Parser到Analyzer到Optimizer生成Plan对比Hive也是生成计划交给MapReduce来执行，因此数据库的原理都是通用的。

(4)疑问又来了，得到Plan之后呢？

执行流程如下：

得到计划后会交给执行器，首先执行器会进行初始化操作(Open),申请内存如给tc1+tc2这个表达式赋予一下函数，是用哪个函数来计算，根据tc1,tc2是int还是float分别选择不同的函数进行计算。然后交给Next，Next会向下层去要数据。数据库首先会向Access去取数据，Access里面本身是没有数据的，他会向底层存储去取数据(Storage)，Storage是一个模块，但细分过后会分为sBuffer和sSF/OS,sBuffer代表一个内存块，sSF代表缓存管理文件。整个过程就是Next会向Access要一条元祖,Access没有,它会向Storage去申请，但本身Storage也没有，于是会找Buffer，Buffer会向内存中申请一段内存，然后把Buffer传入SF,SF通知文件系统打开文件，文件系统会文件通过二级制的形式拷贝到Buffer中。Buffer中的文件可能很多，但每次Access只拿8K的数据，Access经过一些计算就会把8K中的一条元祖取出交给Next，此时Next拿到元祖会计算，如果满足的话返回给用户，如果不满足会循环去取，直到取完后进入Close退出。

(5)执行器总结以及和分布式的类比

通过类比分析Executor和Access属于计算模块，而Storage输入文件存储模块，这些可以和Hadoop相类比。