This page describes a small enhancement to Trafodion: Adding support for a regular expression pattern matching predicate. As the enhancement moves forward, we'll document here what we did, and use it to illuminate lower level design aspects. Note: We did this work on a side branch; none of it has been submitted to the master branch as of this writing.
This particular enhancement is to the Trafodion Compiler and Executor, so design illustrations are limited to those components.
Aside from the fact that pattern matching is a useful feature in its own right, we have two goals for this particular enhancement:
The second point bears a little discussion. The open source development model we use for Trafodion is reviewer-centric: Anyone can contribute changes, but in order for them to be merged into the master thread the changes must pass code review. Humans can review code much more quickly if the set of changes are small and crisp in their functionality. A small set of changes are much more likely to be integrated into the master thread, and much less likely to encounter merge issues along the way. The reader will see as we discuss internal design below that we have put some thought into how this particular feature can be broken up into a series of small changes.
In developing this feature we took the following steps.
The Launchpad Blueprint under which this work is tracked is at https://blueprints.launchpad.net/trafodion/+spec/regular-expression-predicate.
To decide on externals we looked at several possibilities.
Except for SIMILAR, all of the above use regular expression matching that conforms to the POSIX specifications. Since that seems to be the trend in the industry, we decided to go that way too.
Another consideration is the difficulty of a run-time implementation. As described below, we chose the RE2 regular expression engine for our run-time semantics. This implements an extension to the POSIX regular expression syntax, and so determines the precise syntax of regular expressions that we will support.
Based on the discussion above, we chose "REGEXP" as the spelling of our pattern-matching predicate.
The reader who is more interested in Compiler and Executor design rather than the REGEXP predicate itself may skip this section and go directly to Internals.
The syntax consists of two parts: the REGEXP predicate itself and the regular expression used in pattern matching.
Here is the syntax for the REGEXP predicate:
<regular expression matching predicate> ::= <character match value> [ NOT ] REGEXP <regular expression pattern>
Here, <character match value> is a <character value expression> representing the value to be matched. <regular expression pattern> is a <character value expression> representing the regular expression to match the value against. One departure we make from the LIKE predicate is we do not supply an ESCAPE clause. ANSI LIKE by default does not have an escape character; LIKE provides the user the ability to specify an optional escape character of their own choosing as needed. POSIX regular expressions on the other hand uses '\' as an escape character always, and does not provide the user a means to override that choice.
In ANSI SQL, a <character value expression> is any expression that yields a character value. So it could be a literal constant, a column reference, a dynamic parameter, or the result of any sequence of function calls and operators that yield a character value. Since the values of these expressions are not in general known at compile time, many of the error checks are sometimes deferred to run time.
The ANSI SQL syntax rules for LIKE require that all three expressions are "comparable". We will do the same for REGEXP. For our purposes this means that they must be of the same character set.
ANSI SQL supports a notion of collating sequences. One could imagine using a case-insensitive collating sequence with REGEXP, getting case-insensitive pattern matching as a result. However, collating sequence support in general turns out to be complicated. To limit the scope of this work, we'll restrict ourselves to the default collating sequence, and will raise a compile time error if a non-default collating sequence is specified or implied.
We will use the RE2 package unaltered. The syntax of regular expressions supported by RE2 is available on Google's re2 syntax page.
If the value given for the regular expression is invalid, we will raise the following error:
*** ERROR[8442] Invalid regular expression: <message text from RE2>
Here, the <message text from RE2> gives more specifics. For example, '*a' is an invalid regular expression, because the *-operator is a post-fix operator. In this case, the error message returned is:
*** ERROR[8442] Invalid regular expression: no argument for repetition operator: *
If either operand to REGEXP is a null value, the REGEXP predicate will return null. This is similar to the LIKE predicate behavior.
Assuming both operands are not null, and the regular expression specified is valid, the predicate will return true if the value specified matches the regular expression in its entirety, and false otherwise.
In this section, we give an overview of Compiler and Executor internals, and describe how we implement the REGEXP predicate within these internals.
A query in Trafodion passes through several phases:
During compilation, a query is transformed from query text into various intermediate trees then finally into a query plan. As the query is parsed, it is represented as a syntax tree. This tree is then bound to various metadata, then transformed into a tree suitable for optimization. Optimization explores a query plan space by manipulating this tree further, making partial copies of the tree for each explored plan. Finally, the chosen plan is generated. During compilation one set of C++ classes represents the nodes in the query tree. At code generation, the query plan is transformed into a different representation in a different set of C++ classes. We discuss some of these below.
As mentioned, Trafodion query plans consist of C++ objects generated by the Trafodion Compiler. These objects are organized into fragments, each fragment representing a piece of the query plan that runs in a particular process. Since query plans run in several processes, Trafodion must serialize and deserialize these objects so they can be communicated across process boundaries.
At query execution time, the initial phase of processing is called fix-up. During fix-up, the Trafodion Executor acquires any processes it needs and downloads the query plan fragments to each. Once downloaded, the fragment is deserialized, and additional run-time objects are created. Any files that need to be opened are opened.
Execution begins by passing an input row consisting of input parameters to the root node of the query. This row then flows down the tree of relational operators with appropriate transformations along the way. Eventually the inputs reach the leaf nodes of the query. For a SELECT these would be scan nodes. Those nodes in turn read rows that are passed up the tree. Each operator informs its parent operator when it has returned all rows satisfying a given input.
A query ends execution in one of three ways. It may end because all the output rows have been processed. It may end because an error was detected during execution. It may end early because the client has closed the output cursor before consuming all the output rows, or because the query has been cancelled. Since operators execute asynchronously and communicate via queues, error conditions or early close/cancel will cause a cancellation indication to be passed down all or part of the query tree. Eventually, though, all operators quiesce.
Queries can be explicitly cleaned up (for example, by reusing the statement name when preparing a query). If they are not, the query plan remains available in fixed-up state on the chance that the query is re-executed.
Within the Compiler, all SQL expressions are represented by an object in the ExprNode class hierarchy. These can be subdivided into relational expressions (having a value of a relation) and item expressions (having a scalar or row value). This subdivision in turn leads to two sub-trees of the ExprNode hierarchy, the RelExpr and ItemExpr trees respectively.
The REGEXP predicate has a scalar value, so for our purposes here we are most interested in the ItemExpr hierarchy. Given that REGEXP bears many similarities to LIKE, it is worth looking at how LIKE is represented in this hierarchy. The picture below describes it:
The Function class is a specialization of ItemExpr, representing a function call. This might be a built-in function or a user-defined function. Built-in functions in turn are represented by the BuiltinFunction specialization of Function. The CacheableBuiltinFunction class is a further specialization for those functions that are "cacheable" in the sense of the compiler query cache.
Of course, methods that are specific to the LIKE predicate are implemented in the Like class.
The code for Like is spread over several files. Code in the Compiler tends to be arranged by the kind of processing the methods do. So, for example, all the ItemExpr hierarchy methods dealing with type synthesis are together in one file. The table below gives an overview of where some of the common ItemExpr class methods (including the Like representatives) live:
| Method | File | File Description |
|---|---|---|
| bindNode | sql/optimizer/BindItemExpr.cpp | bindNode methods bind column and table references to SQL metadata |
| normalizeForCache | sql/optimizer/ItemCache.cpp | deals with cached query plans |
| constructor, copyTopNode | sql/optimizer/ItemExpr.cpp | all the constructors for ItemExpr classes are here; also copyTopNode, used to duplicate the top node of an ItemExpr tree (sharing the children below it) |
| synthesizeType | sql/optimizer/SynthType.cpp | synthesizeType methods synthesize the type of expressions, based on the node and its children |
In our design research, we found that many methods on the Like class also apply to the REGEXP predicate. Therefore, we propose some refactoring. As part of our implementation, we will create a new class Regexp, in parallel with Like. We will also create a new class, PatternMatchingPredicate, which inherits from CacheableBuiltinFunction, and has Like and Regexp as subclasses. Some of the existing methods of the Like class will be pushed up to PatternMatchingPredicate so we can use them for Regexp as well.
In our implementation approach, we wanted to implement code by pass. That requires an understanding of which pass methods belong to. Some can be guessed simply from the method name ("bindNode" suggests Binder pass, and knowing that the Binder pass does type synthesis suggests that "synthesizeType" is also a Binder pass method). To be more certain, though, we used the following technique to figure out when methods are called:
In the stack trace, we look for the stack frame for the CmpMain::compile method. This is the method that drives the passes. Using gdb, we could look at the CmpMain::compile code. Comments around the code reveal what pass is being invoked.
One thing to note in this exercise is that some methods are called in multiple passes. This happens because the Compiler sometimes rewrites expressions during its processing. When it creates a new parse sub-tree, it must bind it, normalize it, and so on. So, if a portion of the tree is rewritten due to an Optimizer transformation, for example, one can expect to see bind and normalize methods executed on that sub-tree even though CmpMain::compile shows that we are in the Optimizer pass.
Quite often in these rewrites, the new sub-tree will contain pieces of the old parse tree. Binding, normalizing, etc. are recursive processes. This means that sometimes an old parse node will be revisited (say, for binding). For this reason, you will often see logic in these methods that makes them idempotent; for example, the bindNode methods usually check to see if the node has already been bound before proceeding.
The ExprNode class hierarchy is compile-time only. The compiler translates the query tree into a query plan. The main class hierarchies in the query plan are the ex_tcb hierarchy (task control blocks), and the ex_clause hierarchy (scalar expression operators). There is a rough correspondence between RelExpr classes and ex_tcb classes, and also between ItemExpr classes and ex_clause classes.
Unlike RelExpr and ItemExpr, however, ex_tcb and ex_clause do not share a unique base class. (They do both ultimately inherit from NABasicObject, but other hierarchies also inherit from NABasicObject.) The reason is that the query plan implementation of relational operators is quite different from scalar operators. Relational operators implement a data flow architecture, and represent tasks that are executed asynchronously at run-time. Relational operators communicate with each other via queues. Scalar expression operators on the other hand are invoked in a single-threaded manner by an expression evaluation engine. Relational operators are arranged in trees in general, while scalar operators are arranged as sequences within expressions.
The ex_tcb class hierarchy is used to represent compile-time state of relational operators. The query plan is represented as a tree of ex_tcb objects. Each node in the plan is some leaf in this class hierarchy which represents the semantics of a particular operator. At fix-up time, Trafodion creates a parallel hierarchy of ex_tdb objects which contain the run-time state of particular operators. For most operators, there is a one-to-one correspondence between an ex_tcb object and an ex_tdb object. Exceptions are operators that deal with parallelized inter-process communication. For example, the "split bottom" operator combines n partitions of a stream of data from lower level fragments into one stream in the current, parent fragment. There is one ex_tdb object for each of the partitions, but one ex_tcb object for the operator as a whole.
The ex_clause class is the base class for all individual scalar operations. A scalar expression consists of a sequence of objects from the ex_clause hierarchy. Both compile time and run-time state may be stored within an ex_clause object.
For the LIKE predicate, there is a tree of subclasses. ex_like_clause_base is the base class for LIKE. ex_like_clause_char is the specialization that implements LIKE for the ISO88591 and UTF8 character sets. ex_like_clause_double_byte is the specialization that implements LIKE for the UCS2 double-byte character set.
There does not seem to be any advantage in using ex_like_clause_base as a base class for REGEXP also, nor does there seem to be a useful run-time abstraction common to LIKE and REGEXP beyond that already represented by ex_clause. Too, we decided not to do a run-time implementation for double-byte character set values; instead we decided to translate these values to UTF8 in the query plan. We will create a class hierarchy ExRegexpClauseBase that parallels the ex_like_clause_base class, but lacking a double-byte leaf class.
The Compiler and Executor use an optimized memory management scheme. Both create many objects per SQL statement. We sometimes avoid the overhead of calling the destructors on most of these objects by placing them in customized heaps, which we simply throw away en masse.
Some care must be taken in using this scheme. One must be careful to use the same heap when deleting an object as when one created it. For most Compiler and Executor classes, this has been simplified by defining these classes as inheriting from NABasicObject. NABasicObject overloads new and delete, and keeps a pointer to the heap that an object was allocated on. Overloaded delete uses this pointer in order to free the object storage to the proper heap. But much of the time overloaded delete is never called; instead the heap itself is destroyed.
For Executor classes in particular, these heaps might be destroyed at any time without knowledge within the classes themselves.
This implies that any resources outside the heap that are owned by a class must be handled specially. File opens, for example, are tracked by a separate layer of code that is not based on the heap. That code can detect when a query plan has gone away and close files in a lazy fashion as needed.
For another example, if we have a class that does not inherit from NABasicObject, we must be very careful about using such a class from an Executor class to avoid memory and other resource leaks. In our example, we are using a class RE2 from the RE2 package. If we create this object as a stack variable, we are assured it will be destroyed when it goes out of scope. On the other hand, if we wish to create this object on the C++ heap, we must track its creation outside the plan fragment, and have the agent that destroys the plan fragment's heap destroy this object also.
Our implementation will result in some new error checks. Also, in doing the work incrementally from the parser forward, we will want to issue a stub error message at the point where our changes stop. So, here is some general information about error message generation and handling in the Compiler and Executor.
The Compiler and Executor both use class ComDiagsArea to manage error information. The execution model in both is that when an error occurs, information about the error is inserted into ComDiagsArea, and the calling method typically returns. Later processing often checks to see if any errors have been raised before proceeding.
To create an error, one uses the << operator to insert a stream of DgBase objects into a ComDiagsArea object. DgBase is a class hierarchy; the leaf classes define different tokens associated with the error. The first DgBase object in the stream is a DgSqlCode object which gives the (integer) SQL error code associated with the error. The remaining DgBase objects vary depending on what SQL error is raised. For example, an error complaining that a column does not exist in a given table would have a DgColumnName object naming the column, and a DgTableName object naming the table. Below is example code creating an error taken from sql/optimizer/BindItemExpr.cpp:
*CmpCommon::diags() << DgSqlCode(-4002)
<< DgColumnName(nam)
<< DgTableName(getCorrNameObj().getExposedNameAsAnsiString())
<< DgString0(fmtdList)
<< DgString1(bindWA->getDefaultSchema().getSchemaNameAsAnsiString());
bindWA->setErrStatus();
Things to note in this code: The Compiler, being in a single process, typically uses one ComDiagsArea object for all its errors. The CmpCommon class has a static method, diags(), that returns a reference to this object. Another thing to note is the setErrStatus call after the error is created. The object referenced here is the Binder work area. Each pass of the Compiler has a work area object, which serves as a set of "globals" for that pass. The Binder keeps track of whether any errors have been raised in its work area.
In this example, a constant was hard-coded for the SQL error code. The Compiler presently lacks an enumeration for SQL error codes. The Executor on the other hand does have one; you can find it in sql/exp/ExpErrorEnum.h. (In another accident of history, this file is in the exp (expressions) directory, but it includes all Executor errors.)
The ComDiagsArea class definition and the declaration of the << operator are in file sql/export/ComDiagsArea.h. One interesting thing to note about ComDiagsArea is that it inherits from IpcMessageObj. This is because we sometimes pass error information across process boundaries. The DgBase class hierarchy is defined in file sql/common/DgBaseType.h.
SQL errors are usually presented to end users in text form. The code that translates error diagnostics to text form uses a template file found in sql/bin/SqlciErrors.txt. There is a line in this file for each SQL error code. The format of each line is:
<SQL error code> <SQL state> <SQL sub-state> <BEGINNER/ADVANCED> <severity> <reporting mechanism> <message text>
An example is given below:
1009 ZZZZZ 99999 BEGINNER MINOR DBADMIN Column $0~ColumnName does not exist in the specified table.
In the text part of the example, notice the string "$0~ColumnName". The first DgColumnName object inserted into the error stream will have its value substituted for this token.
By convention, ranges of SQL error codes have been dedicated to certain components.
We use the open source RE2 package for run-time semantics. The eval method of our new ExRegexpClauseChar class will create an RE2 object on the stack, pass the regular expression and the value to be matched to it, and handle the results passed back.
RE2 does not support UCS2. Rather than adding such support, it seems simpler to convert UCS2 strings in the query plan to UTF8 strings instead, and use the UTF8 support in RE2.
Here we list the code changes to implement REGEXP.
We actually didn't develop them quite this way. We made some wrong turns along the way as far as design choices, and refactored our work as a result. The interested reader can jump to Wrong Turns to see what we really did.
The first change we did was to add the REGEXP predicate syntax to the parser. In this step we have not created classes to represent REGEXP yet. So we added stub logic to the parser actions to raise an error if REGEXP is specified. Specific changes:
With these changes, the REGEXP predicate is now recognized by Trafodion. We get output like this:
>>select * from temp where b regexp '%xyz%'; *** ERROR[9980] The REGEXP predicate is not yet implemented. *** ERROR[8822] The statement was not prepared.
Study of the Like methods revealed that much of the code there also applies to Regexp. Rather than create Regexp as a peer class and clone the code, we've chosen to refactor the Like class into a parent class, PatternMatchingFunction with a leaf class Like. In the next set of changes, we'll add Regexp as a second leaf class. The methods and data members that look useful for both LIKE and REGEXP are pushed up into the PatternMatchingFunction class, while methods that seem LIKE-specific will remain in the Like class. Specific changes:
We ran the full regression suite after this set of changes to make sure our refactoring didn't break LIKE functionality.
With this set of changes, we add support for static semantic checks for the REGEXP predicate. That is, we do type checking of its operands. It turns out to be convenient to take care of the query caching logic at this time as well. Our stub to raise an error when REGEXP is specified is moved out of the parser and into the code generator.
With these code changes, we can now do negative tests on type checking. For example:
>>create table test1(a integer not null, b date not null) no partition; --- SQL operation complete. >>select * from test1 where a regexp '[x]*'; *** ERROR[4041] Type INTEGER cannot be compared with type CHAR(4). *** ERROR[4050] The operands of the REGEXP predicate must be comparable character data types (that is, of the same character set and collation). *** ERROR[8822] The statement was not prepared. >>select * from test1 where b regexp '[x]*'; *** ERROR[4041] Type DATE cannot be compared with type CHAR(4). *** ERROR[4050] The operands of the REGEXP predicate must be comparable character data types (that is, of the same character set and collation). *** ERROR[8822] The statement was not prepared. >>
The next set of changes will define run-time clause classes for the REGEXP predicate, though we will stub their evaluation routines so that any attempt to execute a REGEXP predicate will result in our friendly -9980 stub error.
Note that we have skipped over the implementation of normalizer and optimizer methods for the moment. We do this because testing these requires the ability to generate a plan, and this can't be done until we can generate the run-time classes. What this means, though, is that we'll get default selectivity for all REGEXP predicates, and we won't get such transformations as the left join-to-inner join transformation when a REGEXP predicate references a null-instantiated column.
We make the following changes:
With these changes, a query using the REGEXP predicate can be compiled. The query will even execute successfully against an empty table or a table containing only null values in the expressions referenced by REGEXP.
When considering how to implement the run-time semantics, we briefly considered implementing our own regular expression engine. For the basic regular expression operators, +, *, ? and |, this is straight-forward. One can find, for example, an algorithm to do this in Aho, Sethi and Ullman's book, "Compilers", on p. 135-141. To make this industrial-strength, though, one needs to add support for wild cards and character classes. A regular expression engine must parse the pattern, and implement matching semantics. Fortunately, there is an open source engine available, RE2, with an appropriate license. This engine is DFA-based (like the Aho, Sethi, Ullman algorithm), and has a small memory footprint. It implements a very rich set of regular expression support, close to the Posix standard. We chose to use this package for our run-time semantics.
This set of changes adds the run-time semantics for single-byte character sets. The double-byte support remains stubbed.
Trafodion supports UCS2 (an encoding of Unicode) as its only double-byte character set. This set of changes adds the run-time semantics for UCS2. Since this is the final bit of code required to have a fully-functional implementation, we also remove the stub error message we added in our very first step.
The RE2 library does not support UCS2-encoded characters. So, to support REGEXP for UCS2, we need to translate the UCS2 strings to UTF8 strings, which RE2 does understand. This will always work because UTF8 is a superset of UCS2.
We have a design choice to make here. We could mimic LIKE, and let REGEXP have two run-time implementations. The double-byte implementation would translate UCS2 strings to UTF8 strings on the fly. Alternatively, we could let the Compiler do the work for us. If we find a REGEXP predicate with UCS2 operands, we do the following transformation: We stick TRANSLATE nodes on top of each operand sub-tree, making them UTF8 strings, and generate a new REGEXP node with these TRANSLATE nodes as children. Now, the rest of compilation and execution deals only with the single-byte variation of REGEXP.
Besides simplifying the run-time implementation, doing this in the compiler has some other benefits: If an operand is constant, the TRANSLATE function may be constant-folded at compile time, so the need to translate it on the fly at run-time is eliminated.
The set of code changes made here include:
The previous set of changes gives us a fully functional implementation of REGEXP. The remaining changes add certain optimizations, inspired by those that Trafodion already implements for LIKE.
The Normalizer pass of the compiler performs heuristic optimizations, that is, optimizations that are thought to be always good. One of these is the left join to inner join transformation. If a query has a predicate on a null-instantiated value that eliminates rows having a null for that value, then the left join query is equivalent to an inner join query. One can simply change the left join to an inner join. This has some run-time benefits: We can eliminate logic dealing with null-instantiation (a path length reduction), and we can enable the Optimizer to consider a richer set of join orders (for example, one can commute the operands of an inner join but not a left join).
The Like class already has a virtual method, Like::predicateEliminatesNullAugmentedRows, that enables this transformation for LIKE. Fortunately for us, the same code works for REGEXP. So, we can simply move this method up into the PatternMatchingFunction class. The specific code changes:
To unit test this change, we can use the showplan utility to see the plan change. For example, before this change we will see a left join in the generated plan for the following query:
>>select * from temp1 left join temp2 on temp1.a = temp2.b +> where temp2.b regexp 'a*[ ]*'; A B A B ---- -------------------- ---- -------------------- aaaa aaaa aaaa aaaa --- 1 row(s) selected. >>showplan select * from temp1 left join temp2 on temp1.a = temp2.b +> where temp2.b regexp 'a*[ ]*'; ... a bunch of output, but ultimately you'll see a join node... Contents of EX_HASHJ [6]: ------------------------- For ComTdb : Class Version = 1, Class Size = 528 InitialQueueSizeDown = 4, InitialQueueSizeUp = 4 queueResizeLimit = 9, queueResizeFactor = 4 queueSizeDown = 2048, queueSizeUp = 2621, numBuffers = 1, bufferSize = 262144 estimatedRowUsed = 100, estimatedRowsAccessed = 0, expressionMode = 0 Flag = 0000000000101001 For ComTdbHashj : hjFlags = 0000000000000010, isSemiJoin = 0, isLeftJoin = 2, isRightJoin = 0 isAntiSemiJoin = 0, isUniqueHashJoin = 0, isNoOverflow = 0, isReuse = 0 bufferedWrites = 0, logDiagnostics = 0, hashBufferSize = 262144 memoryQuotaMB = 1200, numClusters = 4 ...a bunch more output...
After the change, we see an inner join:
Contents of EX_HASHJ [6]: ------------------------- For ComTdb : Class Version = 1, Class Size = 528 InitialQueueSizeDown = 4, InitialQueueSizeUp = 4 queueResizeLimit = 9, queueResizeFactor = 4 queueSizeDown = 2048, queueSizeUp = 3542, numBuffers = 1, bufferSize = 262144 estimatedRowUsed = 100, estimatedRowsAccessed = 0, expressionMode = 0 Flag = 0000000000101001 For ComTdbHashj : hjFlags = 0001000000000000, isSemiJoin = 0, isLeftJoin = 0, isRightJoin = 0 isAntiSemiJoin = 0, isUniqueHashJoin = 1, isNoOverflow = 0, isReuse = 0 bufferedWrites = 0, logDiagnostics = 0, hashBufferSize = 262144 memoryQuotaMB = 1200, numClusters = 4
As of this writing, we have not attempted these changes yet. There are two changes that should be considered.
As of this writing, we have not attempted these changes yet.
We mentioned earlier that our implementation is inefficient: For each row, we build a DFA, even when the regular expression is constant in the query. Almost always, the regular expression will be constant (at least this is the common usage pattern with LIKE), so it pays to consider constructing the DFA just once (per unit of parallelism) and re-using it. This should result in substantial path length reduction for the REGEXP predicate.
To build the DFA just once requires that we create the RE2 object on the heap instead of as a stack variable. This forces us to consider the peculiarities of Executor memory management. The RE2 class (and the objects it creates) use the usual C++ new and delete, and it would be a major effort to change them to use Executor memory management. Instead, we propose to create a new scheme for cleaning up these objects:
When we developed this exercise, we made some wrong design choices along the way. As we learned more, we backtracked and refactored. We thought these were instructive, so here's a list of the wrong turns we made: