16 Parsing Engine SQL What Core Stages Should the Parsing Process Include Below #
As we know, the entire SQL parsing engine can be divided into three stages (as shown in the diagram below). In the previous lesson, we mainly introduced the first stage of the SQL parsing engine in ShardingSphere. Today, I will continue from where we left off and explain the remaining two stages in the SQL parsing process in ShardingSphere.
The Three Stages of the SQL Parsing Engine #
In the first stage of the SQL parsing engine, we explained in detail the process of generating the SQL abstract syntax tree in ShardingSphere and introduced the SQLStatementRule rule class. Today, we will use this rule class to analyze how to extract SQL segments and how to fill in the SQL statements.
1. Second Stage: Extracting SQL Segments #
To understand SQLStatementRule, we need to introduce the ParseRuleRegistry class. From the name, it is a rule registry that stores various parsing rule information. The core variables in the ParseRuleRegistry class include the following three Loader classes:
private final ExtractorRuleDefinitionEntityLoader extractorRuleLoader = new ExtractorRuleDefinitionEntityLoader();
private final FillerRuleDefinitionEntityLoader fillerRuleLoader = new FillerRuleDefinitionEntityLoader();
private final SQLStatementRuleDefinitionEntityLoader statementRuleLoader = new SQLStatementRuleDefinitionEntityLoader();
From the names, we can see that these three Loader classes respectively handle the loading of the SQLStatementRule, ExtractorRule, and FillerRule rule definitions.
Let’s start with SQLStatementRule, and their definitions are in the sql-statement-rule-definition.xml configuration file. We will use MySQL as an example, and this configuration file is located in the META-INF/parsing-rule-definition/mysql directory of the shardingsphere-sql-parser-mysql project. We extract a part of the configuration information from this file for demonstration:
<sql-statement-rule-definition>
<sql-statement-rule context="select" sql-statement-class="org.apache.shardingsphere.sql.parser.sql.statement.dml.SelectStatement" extractor-rule-refs="tableReferences, columns, selectItems, where, predicate, groupBy, orderBy, limit, subqueryPredicate, lock" />
<sql-statement-rule context="insert" sql-statement-class="org.apache.shardingsphere.sql.parser.sql.statement.dml.InsertStatement" extractor-rule-refs="table, columns, insertColumns, insertValues, setAssignments, onDuplicateKeyColumns" />
<sql-statement-rule context="update" sql-statement-class="org.apache.shardingsphere.sql.parser.sql.statement.dml.UpdateStatement" extractor-rule-refs="tableReferences, columns, setAssignments, where, predicate" />
<sql-statement-rule context="delete" sql-statement-class="org.apache.shardingsphere.sql.parser.sql.statement.dml.DeleteStatement" extractor-rule-refs="tables, columns, where, predicate" />
…
</sql-statement-rule-definition>
Based on the ParseRuleRegistry class, the process of obtaining and processing rules involves a large number of entity objects and the definition of JAXB utility classes used to parse XML configuration files. Although there is a lot of content, it is not complicated. The relationship between the core classes is shown in the following diagram:
ParseRuleRegistry Class Hierarchy Diagram
After obtaining the rules, for each SQL of a specific database type, there will be an SQLStatementRule object. We notice that each SQLStatementRule defines a “context” and an “sql-statement-class”.
The “context” here is actually the ParserRuleContext generated by SQL parsing in the SQL abstract syntax tree SQLAST. It includes various StatementContext such as CreateTableContext and SelectContext. For each context, there is a dedicated SQLStatement object corresponding to it. So what does this SQLStatement look like? Let’s take a look:
public interface SQLStatement {
// Get the number of parameters
int getParametersCount();
// Get all SQLSegments
Collection<SQLSegment> getAllSQLSegments();
// Get an SQLSegment by type
<T extends SQLSegment> Optional<T> findSQLSegment(Class<T> sqlSegmentType);
// Get a collection of SQLSegments by type
<T extends SQLSegment> Collection<T> findSQLSegments(Class<T> sqlSegmentType);
}
As you can see, the SQLStatement, which is the final product of the parsing engine, actually encapsulates the operations of obtaining the SQL segment objects SQLSegment. Obviously, for each ParserRuleContext, we ultimately build an SQLStatement object containing a group of SQLSegments. The construction process of these SQLSegments is the so-called extraction of SQLSegments. We can see the references to the various extraction rule objects ExtractorRule in the SQLStatementRule in the configuration file.
ShardingSphere provides a large number of built-in common SQLSegments, including query select items (SelectItems), table information (Table), sorting information (OrderBy), grouping information (GroupBy), and pagination information (Limit), etc. These common SQLSegments have corresponding SQLSegmentExtractors, which can be directly used in the SQLStatementRule.
On the other hand, considering the differences in SQL dialects, ShardingSphere also provides definitions of SQLSegment extractors for various databases. Taking MySQL as an example, there is an extractor-rule-definition.xml configuration file in the META-INF/parsing-rule-definition/mysql directory of its code project, specifically used to define various SQLSegmentExtractors for MySQL. Part of the definition is shown below. As a middleware suitable for multiple databases, this is one of ShardingSphere’s mechanisms for dealing with SQL dialects.
<extractor-rule-definition>
<extractor-rule id="addColumnDefinition" extractor-class="org.apache.shardingsphere.sql.parser.core.extractor.ddl.MySQLAddColumnDefinitionExtractor" />
<extractor-rule id="modifyColumnDefinition" extractor-class="org.apache.shardingsphere.sql.parser.core.extractor.ddl.MySQLModifyColumnDefinitionExtractor" />
…
</extractor-rule-definition>
Now, let’s assume we have the following SQL statement:
SELECT task_id, task_name FROM health_task WHERE user_id = 'user1' AND record_id = 2
Through parsing, we obtained the abstract syntax tree (AST) shown below:
Abstract Syntax Tree diagram
We found that for some nodes in the AST (such as SELECT, FROM, and WHERE), there are no child nodes. However, for nodes like FIELDS, TABLES, and CONDITIONS, they themselves are tree structures. Obviously, the extraction rules for these two types of nodes should be different.
Therefore, ShardingSphere provides two SQLSegmentExtractors: OptionalSQLSegmentExtractor for single nodes, and CollectionSQLSegmentExtractor for tree-like nodes. Due to space constraints, let’s take TableExtractor as an example to demonstrate the process of extracting TableSegments. The implementation of TableExtractor is as follows:
public final class TableExtractor implements OptionalSQLSegmentExtractor {
@Override
public Optional<TableSegment> extract(final ParserRuleContext ancestorNode, final Map<ParserRuleContext, Integer> parameterMarkerIndexes) {
// Get the TableName node from the context
Optional<ParserRuleContext> tableNameNode = ExtractorUtils.findFirstChildNode(ancestorNode, RuleName.TABLE_NAME);
if (!tableNameNode.isPresent()) {
return Optional.absent();
}
// Create a TableSegment based on the TableName node
TableSegment result = getTableSegment(tableNameNode.get());
// Set the alias of the table
setAlias(tableNameNode.get(), result);
return Optional.of(result);
}
private TableSegment getTableSegment(final ParserRuleContext tableNode) {
// Get the Name node from the context
ParserRuleContext nameNode = ExtractorUtils.getFirstChildNode(tableNode, RuleName.NAME);
// Create a TableSegment based on the Name node
TableSegment result = new TableSegment(nameNode.getStart().getStartIndex(), nameNode.getStop().getStopIndex(), nameNode.getText());
// Get the Owner node of the table from the context, if any, and set the Owner
Optional<ParserRuleContext> ownerNode = ExtractorUtils.findFirstChildNodeNoneRecursive(tableNode, RuleName.OWNER);
if (ownerNode.isPresent()) {
result.setOwner(new SchemaSegment(ownerNode.get().getStart().getStartIndex(), ownerNode.get().getStop().getStopIndex(), ownerNode.get().getText()));
}
return result;
}
private void setAlias(final ParserRuleContext tableNameNode, final TableSegment tableSegment) {
// Get the Alias node from the context, if any, and set the alias
Optional<ParserRuleContext> aliasNode = ExtractorUtils.findFirstChildNode(tableNameNode.getParent(), RuleName.ALIAS);
if (aliasNode.isPresent()) {
tableSegment.setAlias(aliasNode.get().getText());
}
}
}
Obviously, the Table node in the syntax tree is a single node, so TableExtractor extends OptionalSQLSegmentExtractor. For TableExtractor, the entire parsing process is to get various nodes related to table definition from the ParserRuleContext and then construct a TableSegment object based on the start and stop positions of the node, as well as its content. TableSegment implements SQLSegment, and its core variables are also clearly defined as follows:
public final class TableSegment implements SQLSegment, TableAvailable, OwnerAvailable<SchemaSegment>, AliasAvailable {
private final int startIndex;
private final int stopIndex;
private final String name;
private final QuoteCharacter quoteCharacter;
private SchemaSegment owner;
private String alias;
…
}
Now, based on the understanding of the extractors and the extraction operations described above, let’s take a look at the implementation of the SQL segment extraction engine, SQLSegmentsExtractorEngine:
public final class SQLSegmentsExtractorEngine {
// Used to extract SQL segments from the SQLAST syntax tree
public Collection<SQLSegment> extract(final SQLAST ast) {
Collection<SQLSegment> result = new LinkedList<>();
// Traverse the extractors and extract the corresponding SQLSegments from the Context, such as TableSegment
for (SQLSegmentExtractor each : ast.getSqlStatementRule().getExtractors()) {
// Single node scenario, directly extract the content under the single node
if (each instanceof OptionalSQLSegmentExtractor) {
Optional<? extends SQLSegment> sqlSegment = ((OptionalSQLSegmentExtractor) each).extract(ast.getParserRuleContext(), ast.getParameterMarkerIndexes());
if (sqlSegment.isPresent()) {
result.add(sqlSegment.get());
}
...
// Scene of tree node, traverse and extract all child nodes under the node//
} else if (each instanceof CollectionSQLSegmentExtractor) {
result.addAll(((CollectionSQLSegmentExtractor) each)
.extract(ast.getParserRuleContext(), ast.getParameterMarkerIndexes()));
}
}
return result;
}
}
Obviously, the role of SQLSegmentsExtractorEngine is to traverse the extractors configured in SQLStatementRule for a specific SQL statement, extract the corresponding type of SQL segment from the context, and finally store them in a collection object and return.
Phase 3: Fill in SQL statements #
After completing the extraction of all SQL segments, we come to the last phase of the parsing engine, which is filling in the SQL statement. The filling process is the process of injecting specific SQL segments into the SQL statement using the segment filler SQLSegmentFiller. From the definition of SQLSegmentFiller interface, we can see the relationship between the three components - SQLSegmentFiller, SQLSegment, and SQLStatement:
public interface SQLSegmentFiller<T extends SQLSegment> {
void fill(T sqlSegment, SQLStatement sqlStatement);
}
Then the question is, how do we correctly understand the processing relationship between SQLSegmentFiller, SQLSegment, and SQLStatement? First, we find the corresponding SQLSegmentFiller based on a certain SQL segment. This relationship is also maintained in a configuration file called filler-rule-definition.xml in ShardingSphere. Here is a partial example of the configuration:
<filler-rule-definition>
<filler-rule sql-segment-class="org.apache.shardingsphere.sql.parser.sql.segment.generic.TableSegment"
filler-class="org.apache.shardingsphere.sql.parser.core.filler.impl.TableFiller" />
<filler-rule sql-segment-class="org.apache.shardingsphere.sql.parser.sql.segment.generic.SchemaSegment"
filler-class="org.apache.shardingsphere.sql.parser.core.filler.impl.dal.SchemaFiller" />
...
</filler-rule-definition>
Obviously, this configuration file stores the mapping relationship between SQLSegment and SQLSegmentFiller. For different SQL dialects, they can also maintain their own filler-rule-definition.xml files.
Let’s take the TableFiller for TableSegment as an example to analyze a specific implementation of SQLSegmentFiller. The TableFiller class is shown below:
public final class TableFiller implements SQLSegmentFiller<TableSegment> {
@Override
public void fill(final TableSegment sqlSegment, final SQLStatement sqlStatement) {
if (sqlStatement instanceof TableSegmentAvailable) {
((TableSegmentAvailable) sqlStatement).setTable(sqlSegment);
} else if (sqlStatement instanceof TableSegmentsAvailable) {
((TableSegmentsAvailable) sqlStatement).getTables().add(sqlSegment);
}
}
}
This code uses a callback mechanism to complete the object injection. In ShardingSphere, callback is a very common mechanism. In essence, the callback solves the problem of circular dependency caused by the mutual invocation between classes. The implementation strategy of the callback usually adopts the following class layer structure:
Callback mechanism diagram
The interfaces TableSegmentAvailable and TableSegmentsAvailable that TableFiller depends on are similar to the Callback interface in the diagram above. The specific SQLStatement is the implementation class of Callback, and TableFiller is the caller of the Callback. Taking TableFiller as an example, we can see that if the corresponding SQLStatement implements either of these two interfaces, we can inject the corresponding TableSegment through TableFiller, thereby completing the filling of the SQL segment.
Taking TableSegmentAvailable interface as an example, it has a group of implementation classes as shown in the following diagram:
Implementation classes of TableSegmentAvailable
Taking the CreateTableStatement as an example, it implements both TableSegmentAvailable and IndexSegmentsAvailable callback interfaces, so it can operate on both the TableSegment and IndexSegment SQL segments. The implementation of CreateTableStatement class is shown below:
public final class CreateTableStatement extends DDLStatement
implements TableSegmentAvailable, IndexSegmentsAvailable {
private TableSegment table;
private final Collection<ColumnDefinitionSegment> columnDefinitions = new LinkedList<>();
private final Collection<IndexSegment> indexes = new LinkedList<>();
}
So far, we have explained the cooperation relationship between the various classes related to the filling operation through an example. The class diagram below shows the overall structure of this cooperation relationship.
Class diagram of SQLStatement hierarchy
With the foundation provided by the diagram above, understanding the SQLStatementFillerEngine for filling becomes relatively simple. Here is the implementation of the SQLStatementFillerEngine class:
public final class SQLStatementFillerEngine {
private final ParseRuleRegistry parseRuleRegistry;
private final String databaseTypeName;
@SuppressWarnings("unchecked")
@SneakyThrows
public SQLStatement fill(final Collection<SQLSegment> sqlSegments, final int parameterMarkerCount, final SQLStatementRule rule) {
//Get the SQLStatement instance, such as CreateTableStatement, from SQLStatementRule
SQLStatement result = rule.getSqlStatementClass().newInstance();
//Validate the legality of the SQLStatement using assertions
Preconditions.checkArgument(result instanceof AbstractSQLStatement, "%s must extends AbstractSQLStatement", result.getClass().getName());
//Set the parameter count
((AbstractSQLStatement) result).setParametersCount(parameterMarkerCount);
//Add all SQLSegments to the SQLStatement
result.getAllSQLSegments().addAll(sqlSegments);
//Fill the corresponding type of SQLSegment
for (SQLSegment each : sqlSegments) {
//Find the corresponding SQLSegmentFiller based on the database type and SQLSegment, and fill the SQLSegment for the SQLStatement
//For example, find the TableFiller through TableSegment, and then fill the TableSegment for CreateTableStatement
Optional<SQLSegmentFiller> filler = parseRuleRegistry.findSQLSegmentFiller(databaseTypeName, each.getClass());
if (filler.isPresent()) {
//Use SQLSegmentFiller to fill the SQLSegment in the SQLStatement
filler.get().fill(each, result);
}
}
return result;
}
}
We have added comments to the core code of SQLStatementFillerEngine. Note that here, based on the database type and the type of SQLSegment, we obtain the corresponding SQLSegmentFiller from the ParseRuleRegistry and complete the filling operation on the SQLStatement.
So far, we have completed the introduction of the three stages of the SQL parsing engine in ShardingSphere. We have obtained the target SQLStatement, providing a foundation for subsequent routing and other operations.
From Source Code Analysis to Daily Development #
Through the study of the framework source code, on one hand, we can better understand the implementation principles behind the core features of the framework; on the other hand, we can absorb the design ideas and implementation methods of these excellent frameworks to better guide our daily development work. In this article, we also summarized a set of design and implementation techniques.
1. Application of Design Patterns #
In this article, we mainly discussed the application scenarios of two design patterns: factory pattern and facade pattern.
The application of the factory pattern is relatively simple and direct. For example, the SQLParseEngineFactory factory class is used to create SQLParseEngine, and the SQLParserFactory factory class is used to create SQLParser.
Compared to the factory pattern, facade classes are usually more difficult to recognize and grasp. Therefore, we also spent a certain amount of space introducing the facade class SQLParseKernel in the SQL parsing engine and the delegation relationship between it and SQLParseEngine.
2. Implementation of Caching #
Caching is widely used in ShardingSphere, and there are various ways to implement it. In this article, we encountered two ways to implement caching.
The first way is to use the ConcurrentHashMap class to store instances of SQLParseEngine, which is relatively simple to use.
The other way is to build an SQLParseResultCache based on the Cache class in the Guava framework to store SQLStatement objects. The initialization method of the Cache class in Guava is shown below, and we can operate on the cache using methods such as put and getIfPresent:
Cache<String, SQLStatement> cache = CacheBuilder.newBuilder().softValues().initialCapacity(2000).maximumSize(65535).build();
3. Two-tier Configuration Management Mechanism #
In ShardingSphere, the definitions of various extraction rules and filling rules are placed in XML configuration files and adopt a two-tier configuration management mechanism. The design idea behind this two-tier management mechanism is that while the system provides default implementations of various common rules, it can also integrate customized rules from various SQL dialects, forming a rule management system with high flexibility and extensibility.
4. Callback Mechanism #
The so-called callback is essentially a bidirectional calling mode, which means that the callee will also call the caller while being called. In terms of implementation, we can extract a business interface as a Callback interface, and then let the specific business objects implement this interface. In this way, when external objects depend on this business scenario, they only need to depend on this Callback interface without caring about the specific implementation class of this interface.
This is a common way to eliminate circular dependencies between business objects and external objects in software design and implementation processes. ShardingSphere extensively uses this implementation method to ensure code maintainability, which is worth learning.
Summary #
As the first core component of the ShardingSphere sharding engine, the purpose of the parsing engine is to generate the SQLStatement target object. The entire parsing engine is divided into three stages: generating the SQL Abstract Syntax Tree, extracting SQL segments, and using these segments to fill the SQL statement. This article provides a detailed discussion of the overall structure of the parsing engine and these three stages.
Finally, I have a question for you: briefly introduce the input and output of each stage of SQL parsing in ShardingSphere. I welcome your discussion in the comments, and I will comment on each answer.
Now that we have obtained the SQLStatement, we are ready to perform the SQL routing operation, which will be covered in the next lesson.