一、逻辑查询处理
SQL语言不同于其他编程语言，最明显的不同体现在处理代码的顺序上。在大多数编程语言中，代码按编码顺序被处理。但在SQL语言中，第一个被处理的子句总是FROM子句。下面显示了逻辑查询处理的顺序以及步骤的序号。
|
1 2 3 4 5 6 7 8 9 10 |
(8) SELECT (9) DISTINCT <select_list> (1) FROM <left_table> (3) <join_type> JOIN <right_table> (2) ON <join_condition> (4) WHERE <where_condition> (5) GROUP BY <group_by_list> (6) WITH {CUBE|ROLLUP} (7) HAVING <having_condition> (10) ORDER BY <order_by_list> (11) LIMIT <limit_number> |
可以看到一共有11个步骤，最先执行的是FROM操作，最后执行的是LIMIT操作。每个操作都会产生一张虚拟表，该虚拟表作为一个处理的输入。这些虚拟表对用户是透明的，只有最后一步生成的虚拟表才会返回给用户。如果没有在查询中指定某一子句，则将跳过相应的步骤。
接下来我们来具体分析查询处理的各个阶段：
1）FROM
第一步需要对FROM子句中的左表<left_table>和右表<right_table>执行笛卡尔积，也称为交叉联接（CROSS JOIN），产生虚拟表VT1。如果FROM子句前的表中包含a行数据，FROM子句后的表中包含b行数据，那么虚拟表VT1中将包含a*b行数据。
2）ON
应用ON过滤器，对虚拟表VT1应用ON刷选，只有那些符合<join_condition>的行才被插入虚拟表VT2中。SELECT查询一共有3个过滤器，分别是ON、WHERE、HAVING；ON是最先执行的过滤过程。
对于大多数的编程语言而言，逻辑表达式的值只有两种：TRUE 和 FALSE。但是在关系型数据库中起逻辑表达式的作用并非只有两种，还有一种称为三值逻辑的表达式。这是因为在数据库中对NULL值的比较与大多数编程语言不同。在 C 语言中，NULL == NULL的返回的值是1，即相等，而在关系数据库中，NULL的比较则完全不是这么回事。例如：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
mysql> select 1 = NULL; +----------+ | 1 = NULL | +----------+ | NULL | +----------+ 1 row in set (0.00 sec) mysql> select NULL = NULL; +-------------+ | NULL = NULL | +-------------+ | NULL | +-------------+ 1 row in set (0.00 sec) mysql> select NULL <=> NULL; +---------------+ | NULL <=> NULL | +---------------+ | 1 | +---------------+ 1 row in set (0.00 sec) |
第一个 NULL 值的比较返回的是 NULL 而不是0；第二个 NULL 值的比较返回的仍然是 NULL，而不是 1；第三个 使用安全比较时 NULL 值才为1。对于比较返回值为 NULL 的情况，用户应该将其视为UNKNOWN，即表示未知的。因为在某些情况下，NULL 返回值可能代表1，即NULL等于NULL，而有时NULL值返回值可能代表0。
对于在ON过滤条件下的NULL值比较，此时的比较结果为UNKNOWN，却被视为FALSE来进行处理，即两个NULL并不相同。但是在下面两种情况下认为两个NULL值的比较是相等的：
- GROUP BY子句把所有NULL值分到同一组。
- ORDER BY子句把所有NULL值排列在一起。
3）JOIN
如果指定了OUTER JOIN（如LEFT OUTER JOIN、RIGHT OUTER JOIN），那么就会产生外部行，会把保留表（如LEFT OUTER JOIN时左表为保留表）中未匹配的行作为外部行添加到虚拟表VT2中，非保留表中的数据被赋予了NULL值，然后产生了虚拟表VT3。如果FROM子句包含两个以上表，则对上一个连接生成的结果表VT3和下一个表重复执行此步骤1至步骤3，直到处理完所有的表为止。
4）WHERE
对虚拟表VT3应用WHERE过滤条件，只有符合<where_condition>的记录才被插入虚拟表VT4中。
在当前应用WHERE过滤器时，有两种过滤是不被允许的：
- 由于数据还没有分组，因此现在还不能在WHERE过滤器中使用where_condition=MIN(col)这类对统计的过滤。
- 由于没有进行列的选取操作，因此在SELECT中使用列的别名也是不被允许的，如SELECT city as c FROM t WHERE c=’ShangHai’是不被允许的。
5）GROUP BY
根据GROUP BY子句中的列，对VT4中的记录进行分组操作，产生VT5。前面也说了GROUP BY阶段，数据库认为两个NULL值是相等的，因此会将NULL值分到同一组中。
6）CUBE|ROLLUP
如果指定了ROLLUP选项，那么将创建一个额外的记录添加到虚拟表VT5的最后，并生成虚拟表VT6。对于CUBE选项，MySQL数据库虽然支持该关键字的解析，但是并未实现该功能。若执行带有CUBE选项的SQL语句，可能会得到错误。
7）HAVING
这是最后一个过滤器了，HAVING是对分组条件进行过滤的筛选器。对虚拟表VT6应用HAVING过滤器，只有符合<having_condition>的记录才被插入虚拟表VT7中。
8）SELECT
第二次执行SELECT操作，选择指定的列，插入到虚拟表VT8中。虽然SELECT是查询中最先指定的部分，但是直到步骤8才真正去处理。
9）DISTINCT
去除重复数据，产生虚拟表VT9。如果在查询中指定了DISTINCT语句，则会创建一张内存临时表（如果内存放不下就放到磁盘）。这张内存临时表的表结构和上一张一样，不同的是对进行DISTINCT操作的列增加了一个唯一索引，以此来去除重复数据。
10）ORDER BY
将虚拟表VT9中的记录按照<order_by_list>进行排序操作，产生虚拟表VT10。使用ORDER BY时，除了使用ORDER BY id这种形式，也可以使用ORDER BY 1这种使用列中序列号的形式（不推荐使用）。
大多数DBA和开发人员都错误地认为在选取表中的数据时，记录会按照表中主键的大小顺序地取出，即结果像进行了ORDER BY一样。导致这个经典错误的原因主要是没有理解什么是真正的关系数据库。下面简单介绍一下关系数据库的起源。
1970年，IBM公司的研究员、有“关系数据库之父”之称的E.F.Codd博士在刊物《Communication of the ACM》上发表了题为“A Relational Model of Data for Large Shared Data banks（大型共享数据库的关系模型）”的论文，文中首次提出了“数据库的关系模型”的概念，奠定了关系模型的理论基础。后来Codd又陆续发表多篇文章，论述了范式理论和衡量关系系统的12条准则，用数学理论奠定了关系数据库的基础。IBM的Ray Boyce和Don Chamberlin将Codd关系数据库的12条准则的数学定义以简单的关键字语法表现出来，里程碑式地提出了SQL语言。由于关系模型的相关书籍简单明了、具有坚实的数学理论基础，因此一经推出就受到了学术界和产业界的高度重视和广泛响应，并很快成为数据库市场的主流。20世纪80年代以来，计算机厂商推出的数据库管理系统几乎都支持关系模型，数据库领域当前的研究工作都以关系模型为基础。
关系数据库是在数学的基础上发展起来的，关系对应数学中集合的概念。数据库中常见的查询操作其实对应的是集合的某些运算：选择、投影、联接、并、差、交、除。最终的结果虽然是以一张二维表的方式呈现在用户面前，但是从数据库内部来看是一系列的集合操作。因此，对于表中的记录，用户需要以集合的思想来理解。表中的数据是集合中的元素，而集合是无须的。因此对于没有ORDER BY子句的SQL语句，其解析结果应为：从集合中选择期望的子集合。这表明结果并不一定要有序。
就算是使用InnoDB存储引擎（索引组织表），没有ORDER BY的查询也不一定是有序的，如下测试：
|
1 2 3 4 5 6 7 8 9 |
CREATE TABLE user( id int primary key, name varchar(30), unique key(name) ) engine = innodb; insert into user select 1,'c'; insert into user select 2,'b'; insert into user select 3,'a'; |
我们来正常查询一下：
|
1 2 3 4 5 6 7 8 9 |
mysql> select * from user; +----+------+ | id | name | +----+------+ | 3 | a | | 2 | b | | 1 | c | +----+------+ 3 rows in set (0.00 sec) |
表user上有主键id，对于没有ORDER BY子句进行查询的操作，“出人意料”地按照主键降序排序结果。由此可见，即使采用的是InnoDB存储引擎表，对于没有使用ORDER BY子句的选择查询，其结果永远不会是按照主键顺序进行排序的。因为没有ORDER BY子句的查询只代表从集合中查询数据，而集合是没有顺序概念的。
因此要牢记，不要为表中的行假定任何特定的顺序。就是说，在实际使用环境中，如果确实需要有序输出行记录，则必须使用ORDER BY子句。当然，排序需要成本，可以通过变量来查看数据库的排序操作。示例如下：
|
1 2 3 4 5 6 7 8 9 10 |
mysql> show status like '%Sort%'; +-------------------+-------+ | Variable_name | Value | +-------------------+-------+ | Sort_merge_passes | 0 | | Sort_range | 0 | | Sort_rows | 7 | | Sort_scan | 1 | +-------------------+-------+ 4 rows in set (0.06 sec) |
其中Sort_scan为1，Sort_rows为7，表示进行了一次排序扫描操作，工排序了7条数据。在实际的生成环境中，需要观察这些变量，判断是否可以通过添加索引来避免额外的排序开销。
11）LIMIT
取出指定行的记录，产生虚拟表VT11，并返回给查询用户。对于没有应用ORDER BY的LIMIT子句，结果同样可能是无须的，因此LIMIT子句通常和ORDER BY子句一起使用。
MySQL数据库的LIMIT支持如下形式的选择：LIMIT n,m
表示从第n条记录开始选择m条记录，而最多都是用来解决Web中经典的分页问题。对于小规模的数据，这并不会有太大的问题。对于大规模数据的应用来说，LIMIT n,m的效率是十分低的。因此每次都需要对数据进行选取。如果只是选取前5条记录，则非常轻松和容易；但是对100万条记录，选取从第80万行记录开始的5条记录，则还需要扫描记录到这个位置。因此，对于数据量非常庞大的分页问题，在应用层建立一定的缓存机制是十分有必要的。
二、物理查询处理
前面介绍了逻辑查询处理，并且描述了执行查询应该得到什么样的结果。但是数据库也许并不会安全按照逻辑查询处理的方式来进行查询。在MySQL数据库层有Parser和Optimizer两个组件。Parser的工作就是分析SQL语句，而Optimizer的工作就是对这个SQL语句进行优化，选择一条最优的路径来选取数据，但是必须保证物理查询处理的最终结果和逻辑查询处理是相等的。
如果表上建有索引，那么优化器就会判断SQL语句是否可以利用该索引来进行优化。如果没有可以利用的索引，可能整个SQL语句的执行代价非常大。比如有如下表结构：
|
1 2 |
CREATE TABLE x (a int) ENGINE = INNODB; CREATE TABLE y (a int) ENGINE = INNODB; |
表x有10万条数据，表y有18万条数据。现在表x和表y上都没有索引，因此最终SQL解析器解析的执行结果为逻辑处理的步骤，也就是按照上面分析的，总共经过11个步骤来进行数据的查询。最先根据笛卡尔积生成一张虚拟表VT1，表x有10万行数据，表y有18万行数据，这意味着进行笛卡尔积后产生的虚拟表VT1总共有180亿行的数据，速度可想而知。180亿数据的产生，即便是在内存中产生这么多次的数据，也需要话费很长时间。然而，如果这时对表y添加一个主键值，再执行这条SQL语句，速度就可能会变得异常快了。原因很简单，就是在添加索引后避免了笛卡尔表的产生，因此大幅度缩短了语句运行的时间。
添加索引是非常有技巧的一项工作，正确地利用索引的特性能显著提高SQL语句运行的效率。但是一味地添加很多索引反而会导致数据库运行得很慢。物理查询会根据索引来进行优化，这也是MySQL数据库优化器的一项重要工作。
<摘录>
InnoDB存储引擎
<延伸>
