Chapter 9. Parser and Optimizer

The MySQL server receives queries in the SQL format. Once a query is received, it first needs to be parsed, which involves translating it from what is essentially a textual format into a combination of internal binary structures that can be easily manipulated by the optimizer.

In this context, when we say optimizer, we refer to the server module responsible for creating and executing the plan to retrieve the records requested by the query. The optimizer picks the order in which the tables are joined, the method to read the records (e.g., read from an index or scan the table), as well as which keys to use. Its goal is to deliver the query result in the least amount of time possible.

In this chapter, we’ll examine the parser and optimizer in detail.


MySQL’s parser, like many others, consists of two parts: the lexical scanner and the grammar rule module. The lexical scanner breaks the entire query into tokens (elements that are indivisible, such as column names), while the grammar rule module finds a combination of SQL grammar rules that produce this sequence, and executes the code associated with those rules. In the end, a parse tree is produced, which can now be used by the optimizer.

Unlike some parsers, which translate the textual representation of the query into byte code, MySQL’s parser converts it directly into internal interlinked C/C++ structures in the program memory.

For example, imagine the server receives the following query:

 SELECT count(*),state ...

Get Understanding MySQL Internals now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.