Blog about Database, Cloud Computing and Life
前篇介绍了MySQL存储索引信息的基本数据结构。本篇将延续下去，介绍MySQL如何找到可以使用的索引，以及期间需要使用的主要数据结构。
谁适合阅读: 本文不打算从High Level来介绍MySQL索引及其使用，相反是从MySQL源码对应的数据结构开始介绍。如果你了解MySQL索引的基本原理，还打算继续从源码的角度解决一些索引使用的问题，那么你适合参考本文，否则，打住，真的很枯燥:(。在可见的未来，作者还将介绍Range优化相关的数据结构等。
本文介绍MySQL如何发现WHERE条件中的等值表达式，并通过分析这些等值表达式，找到可以使用的索引。在这个过程中，MySQL将递归的访问所有WHERE条件"谓词"，并将等值表达式都存储到KEY_FIELD对象的数组中。
然后遍历该KEY_FIELD数组，并同时对比所有索引列，找到哪些字段是在索引列中出现，这些字段则可能可以使用索引，MySQL将所有这些字段都存储在对象KEYUSE数组中。
最后，对KEYUSE进行处理，包括排序、删除无法使用的索引列。这时KEYUSE数组就是所有可以使用REF的索引列了。[......]
很枯燥的，配首背景音乐吧：
本文将尝试介绍MySQL索引存储相关的数据结构。程序=数据结构+算法，了解数据结构，然后就可以进一步了解MySQL源码中如何使用索引，如何选择自己的执行计划。
MySQL使用TABLE对象来描述一个数据表，那么数据表的索引是如何描述，索引的统计信息又是如何存储的呢? 例如我们有如下数据表：
CREATE TABLE `users` ( `id` int(11) NOT NULL, `nick` varchar(32) DEFAULT NULL, `reg_date` datetime DEFAULT NULL, PRIMARY KEY (`id`), KEY `IND_NICK` (`nick`), KEY `IND_REGDATE` (`reg_date`) )
该表有索引，PRIMARY KEY、IND_NICK、IND_REGDATE，我们来看看MySQL内部是如何存储这三个索引，以及如何使用这些索引的统计信息的。下图，描述了存储一个数据表索引的主要结构：
[......]
前篇介绍了MySQL如何从SQL语句转换成一个内部对象。本文是前篇的延续，将更加详细的介绍WHERE语句对应的Item对象。
(建议阅读：The Item Class@MySQL Internals Manual，忽略本小结)
MySQL Internals Manual较为详细的介绍了Item对象。Item对象经常被称作"thingamabob"（ A thingamabob is a noun used to describe items that either you can't remember the name of or that don't actually exist.）。Item是一个类，每一个Item实例都：(1)代表一个SQL语句里的对象;(2)有取值;(3)有数据类型指针。
下面列出的的SQL相关的对象都是一个Item对象，或者继承至Item：(1)一段字符; (2)数据表的某列; (3)一个局部或全局变量; (4)一个存储过程的变量; (5) 一个用户参数; (6)一个函数/存储过程(这包括运算符+、||、=、like等) 。例如下面的SQL语句：[......]
自从有了微薄后博客就写得少了，上一篇博客已经是6月份写的了... 从写第一篇关于MySQL源码的文章之后也已经过了很久，继续上路。
优化器是关系数据库的一个重要而有特色的部分，优化器的理论和实践也多半也都很复杂，本系列文章希望通过解析MySQL优化器，来用好MySQL,扬其长，避其短。顺便也一窥关系数据库优化器的实现思路。文章将重点介绍重要的数据结构和数据结构之间的关系，而不是侧重于代码（"Bad programmers worry about the code. Good programmers worry about data structures and their relationships."）。
本文解决了什么问题：希望通过这些文章能够帮你更加顺畅的理解MySQL优化器的行为；在你阅读MySQL源代码之前了解更多的背后思路。
本文不解决什么问题：教你如何读懂源代码；
这个系列很长,大概按这样的思路进行下去: 基本的数据结构、语法解析、JOIN的主要算法、JOIN顺序和单表访问。数据结构(以及他们的关系)和算法流程总是相互穿插介绍。
建议阅读：参考文献中的文章和书籍，都建议在阅读本文之前阅读。
MySQL语法解析封装在函数MYSQLparser中完成。跟其他的语法解析器一样，它包含两个模块：词法分析(Lexical scanner)和语法规则(Grammar rule module)。词法分析将整个SQL语句打碎成一个个单词(Token)，而语法规则模块则根据MySQL定义的语法规则生成对应的数据结构，并存储在对象THD->LEX结构当中。最后优化器，根据这里的数据，生成执行计划，再调用存储引擎接口执行。
词法分析和语法规则模块有两个较成熟的开源工具Flex和Bison分别用来解决这两个问题。MySQL处于性能和灵活考虑，选择了自己完成词法解析部分，语法规则部分使用Bison。词法解析和Bison沟通的核心函数是由词法解析器提供的函数接口yylex()，在Bison中，必要的时候调用yylex()获得词法解析的数据，完成自己的语法解析。Bison的入口时yyparse()，在MySQL中是，MYSQLParse。
如果对词法分析和语法规则模块感到陌生，建议阅读参考文献[4][5][6]先注1，否则很难理解整个架构，或者至少会有很强的断层感。而且，根据Bison的Action追踪MySQL数据的存储结构是很有效的。[......]
在MySQL服务器出现短暂(5~30秒)的性能波动的时候，一般的性能监控工具都很难抓住故障现场，也就很难收集对应较细粒度的诊断信息。另外，如果这种波动出现的频率很低，例如几天才一次，我们也很难人为的抓住现场，收集数据。这正是pt-stalk所解决的问题。
pt-stalk是Percona-Toolkit的一部分(其前身是Aspersa的一部分)。安装Percona-Toolkit后，可以通过man pt-stalk了解如何使用该工具，本文的介绍是man pt-stalk的一个子集，强烈建议直接阅读man pt-stalk。额外的，本文将提供pt-stalk示例命令可供参考。
上面的命令表示，让pt-stalk后台运行(--daemonize)，并监视SHOW GLOBAL STATUS中的Threads_connected状态值，如果该值超过2500，则触发收集主机和MySQL的性能、状态信息。pt-stalk会每隔一秒检查一次状态值，如果连续5次满足触发条件，则开始收集。
--collect-tcpdump表示除了收集基本信息外，还将额外使用tcpdump收集当时的网络包，类似的还可以使用--collect-gdb等。
[......]
今天发现Percona Release的Percona-Server-5-5-18-23-0已经完成了Group Commit工作，而且是用最优雅的方式（移植了MariaDB的实现，而不是workaround），心里难掩激动。
这篇文章接前篇继续介绍一下问题的背景：什么是Group Commit，现在的官方版本Group Commit做到了什么程度？
MySQL/InnoDB在做事务的时候使用的日志先行（Write-ahead logging）的方式保证事务的快速和持久，所以每次事务完成都要求日志必须持久化到磁盘，在Linux上对应的操作就是“write and fsync”，write速度是很快的，一般对应的写Page Cache，而fsync则要求文件系统把对应文件的哦Page Cache必须持久化到磁盘上，而对于传统磁盘一次写操作大约需要1~3ms（不说BBU），这意味着对于传统磁盘1秒钟最多最多做333～1000个事务，这是不理想的，对硬件的利用率（吞吐量）也是非常低。
所以，这里就有了Group操作的概念，即当好几个线程都要fsync同一个日志文件时，我们将这些fsync合并到一次来做。简单举例：我们让系统每2ms做一次fsync，这样如果这2ms内有100个线程都需要做fsync，那就赚到了，原本100个fsync都独立来做那耗时会非常多的。
你肯定会说，难道这不是很简单的想法吗？是的，这就是原本是很简单、也很自然的想法。
但对MySQL来说却变成了一种奢求（看看这个Bug讨论）。
MySQL是不是太弱了，这么简单的事情都搞不定？不是的。
MySQL从开源到现在，成功的一个非常重要的原因，就是MySQL的插件式架构。如果MySQL只是MyISAM估计不会有现在的流行程度，插件式的架构让诸如Heikki Tuuri有了发挥空间，在InnoDB和MySQL一起时，MySQL才能算是一个真正的DBMS。再到后来，有Infobright、 FEDERATED、PBXT等等。
插件式的架构给MySQL带来了活力，做出牺牲便是在上层(MySQL)和下层(存储引擎)交互时带来的额外消耗，有时甚至上层和下层需要做一些重复工作。无法做Group Commit就是这其中的牺牲之一。
[......]
