EXPLAIN EXTENDED

I'm going to write a series of articles about the things SQL needs to work faster and more efficienly.

With these things implemented, most of the tricks I explain in my blog will become redundant and I'll finally have some more time to spend with the family.

Ever wondered why a condition like this:

WHERE TRUNC(mydate) = TRUNC(SYSDATE)

, which searches for the current day's records, is so elegant but so slow?

Of course this is because even if you create an index on mydate, this index cannot be used.

The expression in the left part of the equality is not a mydate. The database engine cannot find a way to use an index to search for it. It is said that this expression is not sargable.

Now, a little explanation about the indexes and sargability. If you are familiar with these, you can skip this chapter. But beware that this chapter is the only one illustrated, so skipping it will make the article too boring to read.

Ahem.

To locate a record in a B-Tree index, the keys of the index should be compared to the value being searched for.

Let's consider this sample B-Tree index:

As you can see, this structure maintains the record order.

Within one page, records are just sorted; the links between the pages obey the sorting order too. A binary search can be used to locate the record on a page; if the search resulted in a pair of adjacent records and the search expression is within the range of these records, then we just follow the link between them. All records behind this link will belong to the range, no matter how deep is the tree.

This works well when we search for the exact field that was indexed.

But what happens when we search for a derived expression?

SELECT  *
FROM    mytable
WHERE   value % 3 = 1

The B-Tree itself of course does not change. But, being casted to the expression we are searching for, the values stored will look like that:

As you can see, there is no order anymore. The records are neither ordered within one page, nor the links follow the order. A 1 we are searching for can appear anywhere in the tree. There is no other way than to traverse the whole tree and compare each record.

It is said that this expression is unsargable: the index can not be used to search for this expression.

But let's consider another example:

SELECT  *
FROM    mytable
WHERE   value + 3 = 10

Here's how the B-Tree looks now from the point of view of the expression in the WHERE clause

Now, we have a perfectly valid B-Tree: everything stays in order and the search algorithms can still be used.

Another example (DIV is the integer division operator):

SELECT  *
FROM    mytable
WHERE   value DIV 3 = 3

Here's the B-Tree as seen from the expression's side:

The order persists.

This B-Tree is a little bit harder to traverse, since the key values are not unique anymore. But the same values of the keys are still contiguous, and the order between the different keys is still maintained.

Is this case, the algorithm should be changed just a little. When a key is found in the database, we should just continue searching to the left until we find the very first occurrence of the key with lower value. Then we continue searching to the right and return all the records with the correct value of the key.

This problem is of course well known and has long since been solved by all database systems: you can create an index on a non-unique field.

Finally, let's consider one more expression, a very simple one:

SELECT  *
FROM    mytable
WHERE   20 - value = 10

and how it sees the B-Tree:

In this case, the order is reversed. But there still is the order. The only difference is that the values are sorted right to left, not left to right, and all traversals should be made according to these new directions.

We see that some expressions break the B-Tree order, while the other ones maintain it.

What is the difference between the two?

For an expression to maintain the B-Tree order, it is necessary and sufficient for this expression to be a monotonic function of the argument being indexed.

Here's the definition of the monotonic function from Wikipedia:

In calculus, a function f defined on a subset of the real numbers with real values is called monotonic (also monotonically increasing, increasing or non-decreasing), if for all x and y such that x ≤ y one has f(x) ≤ f(y), so f preserves the order. Likewise, a function is called monotonically decreasing (also decreasing, or non-increasing) if, whenever x ≤ y, then f(x) ≥ f(y), so it reverses the order.

By definition, the monotonic function preserves (or reverses) the order, but does not break it.

This means that if an index is built over an expression, it also can be used to search over any monotonic function of this expression.

However, most query optimizers do not take this fact into account, while this behavior is relatively easy to implement.

Sample implementation

There will be many new keywords. I will introduce them all at the beginning and explain them later in the article. Also, there will be many fake functions, like NEXT_COLLATION_CHARACTER or EXTRACT(calendar_date), which are absent in the actual engines but their name easily tells their purpose (and it's quite simple to implement them anyway). These functions are used to demonstrate the concept.

A sargable function, as I shown above, needs to expose some monotony:

function(arg1, …) monotony_declaration

Function of two or more arguments can be sargable by some or all of it's arguments:

monotony_declaration := MONOTONIC ( monotony_domain | OVER(arg1) monotony_domain [, …])


When the function is a single-argument function, OVER clause should be omitted.

monotony_domain := (monotony | PIECEWISE piecewise_monotony)


Monotony defines the direction and uniqueness of the function on the given range of the function's domain:

monotony := (STRICTLY INCREASING | INCREASING | STRICTLY DECREASING | DECREASING | UNDEFINED ) [ inversion_clause ]

• If monotony is STRICTLY INCREASING, it can be used for the B-Tree searches without changing the search order. A UNIQUE set of values is mapped to a UNIQUE set of the results of the function. The cardinality of the function over the indexed expression is the same as that of the expression.
• If monotony is INCREASING, it can be used for the B-Tree searches without changing the search order. A UNIQUE set of values may be mapped to a non-unique set of the results, and no assumptions should be made about the uniqueness of the results. The cardinality of the function over the indexed expression may be not the same as that of the expression.
• If monotony is STRICTLY DECREASING, it can be used for the B-Tree searches, changing the search order. A UNIQUE set of values is mapped to a UNIQUE set of the results of the function. The same algorithms that are used for scanning the index in the opposite order should be applied. The cardinality of the function over the indexed expression is the same as that of the expression.
• If monotony is STRICTLY DECREASING, it can be used for the B-Tree searches, changing the search order. A UNIQUE set of values is mapped to a UNIQUE set of the results of the function. The same algorithms that are used for scanning the index in the opposite order should be applied. The cardinality of the function over the indexed expression may be not the same as that of the expression.
• There is one more flavor, UNDEFINED, which states that the function is not monotonic or its monotony should not be relied upon. This has no sense as such, but can be used in the complex constructs we shall discuss below.

If the function is monotonic over the whole domain, then monotony is provided right after the keyword MONOTONIC.

However, a function can be piecewise monotonic. Its domain may consist of several (possibly infinite) number of pieces, with the function being monotonic over each piece but not across them.

Piecewise monotony

piecewise_monotony := PIECEWISE (constant_piece_definition | functional_piece_definition)

The pieces can be defined either by a set of constants or by another monotonic function, in which the pieces are defined by distinct values of the piece-defining function.

constant_piece_definition := WHEN VALUE [STRICTLY] LESS THAN const monotony, [ … ], WHEN VALUE LESS THAN MAXVALUE monotony

Each const should be greater than the previous, and the last clause should be WHEN VALUE THEN MAXVALUE. The const comparison can be declared as strict: this may be important for handling discontinuities.

functional_piece_definition := DEFINED BY piece_defining_function(arg) CASE ( (WHEN expression(PIECE) THEN monotony) [ (…) | ELSE monotony ] ) END

Piece-defining function should itself be a monotonic function (but not a strict monotonic) over all domain of the original function.

The point of having this function is to split the domain into several pieces which themselves are sargable (hence the requirement for non-strict monotony), and then define the monotony within each piece.

The monotony for each piece is defined by SQL's standard CASE WHEN … THEN … ELSE … END control flow construct (which of course returns monotonies instead of values).

Two or more arguments

A function of two or more arguments can be sargable too, as defined by monotony_declaration.

Each OVER clause defines monotony over one of the fuction's arguments.

If an indexed field is used as a corresponding argument to this function and the other arguments are provided as constants or values from the leading table in the join, then the function is sargable.

Superpositions

When dealing with the superposition of functions, some assumptions can be made:

• A superposition of any number of STRICTLY MONOTONIC functions is STRICTLY MONOTONIC
• A superposition of any number of STRICTLY MONOTONIC functions and at least one MONOTONIC function is MONOTONIC (as opposed to STRICTLY MONOTONIC)
• A superposition of an INCREASING and a DECREASING function is DECREASING
• A superposition of an INCREASING and an INCREASING functions, or that of a DECREASING function and a DECREASING function is INCREASING

This only concerns functions monotonic over all domain (that is without PIECEWISE expressions).

Inversions

inversion_clause := INVERSE ( inverse_expression | FROM inverse_expression [ EXACT [ EXCLUDE ] ] TO inverse_expression [ EXACT [ EXCLUDE ] ] )

inverse_expression := sql_expression ([ PIECE ], [ RESULT ], [ non-over-arg1 [ ,… ] ])

Each monotony may be provided with an inversion_clause, which maps the results back to the values of the arguments.

These expressions can accept the following arguments:

• RESULT. This is the result of the function which needs to be mapped back to the value of the argument
• PIECE. This is the value defined by the piece-defining function. This only makes sense in a function-defined piecewise monotony
• non-over-arg. This is the argument to the function not used in the OVER clause. This only makes sense for multiple-argument functions.

Inversion clause may come in two forms: scalar inversion and range inversion.

• A scalar inversion maps the function result to the single value of the argument.

  If the monotony is strict, then the value of the expression is treated as a unique mapping. The decision on whether to return the value or not is made solely on the basis of the inverse result: function is not applied to the values taken from the index for more fine filtering.

  If the monotony is not strict, them the value of the expression is treated as a reference point. Key reads back and forward to this reference point should be made with the function being applied to the result of each key read.

• A range inversion maps the function result back to the range of values that are guaranteed to yield the RESULT, being provided as an argument to the function. The first expression provides the start value of the range, the second expression provides the end value.

  Within the range, the results are returned from the index without any additional checking.

  If any of the range expressions is marked as EXACT, then no values are returned outside the range in the corresponding direction. Otherwise, key reads are made in this direction and the function is applied to the results of the key reads to do the fine checking.

  With EXACT clause, it is also possible to provide EXCLUDE clause. Depending on its presence, the corresponding range will be treated as including or not including the boundary.

The point of allowing inexact inverse functions is to deal with the rounding errors introduced by floating point operations. Even if in theory the function can uniquely map back to a single value or a range of values, in practice, this may be not the case.

The B-Tree search is possible even without providing inverse functions at all. However, if inverse functions are provided, the number of the function evaluations is kept to the minimum: the function is only evaluated for several keys outside of the guaranteed range.

Examples

• EXP(arg FLOAT) MONOTONIC INCREASING INVERSE LN(RESULT)

  Exponent function is increasing over the whole set of natural numbers. Its inverse function is natural logarithm.

  Due to possible rounding errors, this function cannot be declared as strict.

• YEAR(arg DATETIME) MONOTONIC INCREASING
INVERSE
FROM DATE_TRUNC('year', RESULT) EXACT
TO DATE_TRUNC('year', RESULT) + INTERVAL 1 YEAR EXACT EXCLUDE

  YEAR is an increasing function but not a strictly increasing one: two distinct dates can share the same year. That's why we provide two inverse functions: the first one provides the minimal possible date for a given year, the second one provides the maximal possible one. The latter function is marked as EXCLUDE, since the first date of the next year does not belong to the current year's domain piece, but any value strictly less than it (and greater than the year's beginning date) does.

• ABS(arg INT) MONOTONIC PIECEWISE ON
VALUES STRICTLY LESS THAN 0 STRICTLY DECREASING INVERSE -RESULT,
VALUES LESS THAN MAXVALUE STRICTLY INCREASING INVERSE RESULT

  The absolute value function is piecewise monotonic: it is strictly decreasing for the values below zero and strictly increasing for the values of zero and above.

  The inverse functions for each piece are the negation of the result and result itself, accordingly.

• FLOOR(arg FLOAT) MONOTONIC INCREASING
INVERSE
FROM RESULT EXACT
TO RESULT + 1 EXACT EXCLUDE

  The nearest lower integer function is monotonically increasing, almost the same as YEAR described above.

• OPERATOR_DIVISION(arg1 FLOAT, arg2 FLOAT)
MONOTONIC OVER (arg1)
CASE WHEN arg2 > 0 THEN INCREASING INVERSE RESULT * arg2
WHEN arg2 = 0 THEN UNDEFINED
WHEN arg2 < 0 THEN DECREASING INVERSE RESULT * arg2
END

  This function defines division operator.

  It is monotonic over the first argument. This means that the second argument should be provided as the run-time constant for it to be sargable: no field from the table being searched for can be used as a second argument to this function.

  This function is monotonic over the whole domain of arg1, but the monotony depends on the value of arg2.

  In theory, this function is strictly monotonic, but in practice, rounding errors can make the function yield same results for different values of arg1. That's why this function should be declared non-strict and a single inverse expression should be provided.

• OPERATOR_PLUS(arg1 FLOAT, arg2 FLOAT) MONOTONIC
OVER (arg1) STRICTLY INCREASING INVERSE RESULT - arg2,
OVER (arg2) STRICTLY INCREASING INVERSE RESULT - arg1

  This function defines the + operator.

  This is quite simple: the function is strictly increasing over both arguments, and the inverse function is just a subtraction.

• MONTH(arg DATETIME) MONOTONIC PIECEWISE
DEFINED BY DATE_TRUNC('year', arg)
INCREASING
INVERSE
FROM PIECE + INTERVAL RESULT - 1 MONTH EXACT
TO PIECE + INTERVAL RESULT MONTH EXACT EXCLUDE

  MONTH returns the month number within a year.

  This function is piecewise monotonic: within a year, higher dates always return same of higher months. Whenever the year changes, monotony breaks. DATE_TRUNC is monotonic and not strict, and, hence, can be used to define the pieces.

  The reverse functions use both PIECE and RESULT arguments. The PIECE argument defines the current year, the RESULT is used to find the beginning of the current and the next months.

• COS(arg FLOAT) MONOTONIC PIECEWISE
DEFINED BY FLOOR(arg / PI())
CASE PIECE % 2
WHEN 0 THEN DECREASING INVERSE PIECE * PI() + ACOS(RESULT)
ELSE INCREASING INVERSE (PIECE + 1) * PI() - ACOS(RESULT)
END

  Cosine is piecewise monotonic too. The pieces are defined by the cosine half-waves. Depending on the piece, it can be increasing or decreasing. The half-wave number is defined by FLOOR(arg / PI()). This piece-defining function, being a superposition of increasing functions, is increasing too.

  On the even half-waves, the function is decreasing; on the odd half-waves, it is increasing. In principle, the function monotony is strict, but due to the possible rounding errors, it is marked as non-strict and only one inverse function provided.

• SIN(arg FLOAT) MONOTONIC PIECEWISE
DEFINED BY FLOOR(arg / PI() - 0.5)
CASE PIECE % 2
WHEN 0 THEN DECREASING INVERSE PIECE * PI() + ASIN(RESULT)
ELSE INCREASING INVERSE PIECE * PI() - ASIN(RESULT)
END

  Same as cosine above, with a π / 2 shift.

• LEFT(arg VARCHAR, length INT) MONOTONIC
OVER(arg) INCREASING
INVERSE
FROM LEFT(arg, length) EXACT
TO LEFT(arg, length - 1) || NEXT_COLLATION_CHARACTER(SUBSTRING(arg, length, 1)) EXACT EXCLUDE


  Function LEFT takes the leading characters from the string.

  It is sargable over the first argument: in the string is indexed, you can always search for a leading substring. I had to make up the function NEXT_COLLATION_CHARACTER, which would take next possible alphabet character according to the current collation.

  Note that SQL Server and MySQL have traces of such optimization. In both systems, LIKE predicate is sargable if the search string does not contain the leading wildcards.

  If you build a plan for a predicate like column LIKE 'test%', you will see that is will use the index seek in this range:

  column >= 'test' AND column < 'tesU'

  This behavior is exactly like described above.

Search algorithm

To select the values matching this condition:

function(col1 [ , arg2, … ]) = const

, the following procedures should be made:

1. If the function is not sargable against the first argument, then just do the full table or index scan.
2. If the function is sargable against the first argument, check its monotony.
3. If the function is monotonic over all domain:
   1. If no inversion function is defined, then locate the values in the B-Tree using the B-Tree search algorithm and applying the function to each key before the comparison. The monotony direction (increasing or declreasing) should of course be taken into account.
   2. If the function is strictly monotonic and a single inverse function is defined, apply the inverse function to the value of const, find the corresponding value of col1 and locate it in the index using B-Tree search algorithm.
   3. If the function is monotonic, but not strictly, check the inversion type:
      1. If a scalar inverse expression is defined, then:
         1. Apply the inverse function to const and find the key values in the B-Tree closest to the value of inverse_expression(const)
         2. Starting from inverse_expression(const), iterate through the index back and forward, applying function to the each key found until the function exceeds (or falls short of) const, returning the records found.
      2. If a range inverse expression is defined, then:
         1. Find the beginning and the ending values of the col1 range that yields const
            If the beginning of range is not exact, iterate keys backwards, applying the function to each key found until the function equals to const.
         2. Iterate the keys forward, returning the records found, until the end of the range is reached.
         3. If the range end is not exact, then iterate keys beyond the range, applying the function to the keys found, until the function value exceeds or falls short of const
4. If the function is piecewise monotonic:
   1. If the pieces are defined by a set of constants, split the domain into the pieces, then apply the steps above to each piece separately with respect to the monotony of each piece.
   2. If the pieces are defined by a function:
      1. Use loose index scan to build a distinct list of the function's values (each defining a piece). The loose index scan will jump over the B-Tree, starting from the minimal (or maximal) value of the function and recursively searching for the greater (or the lesser value). Each distinct value will reveal the least and the greatest value of the col1 belonging to its piece.
      2. Within the range defined by these values, apply the steps above, with respect to the monotony of each piece.
   3. If for any of the pieces the monotony is UNDEFINED, then just apply the function to every key in the piece's range, filtering the results.

User-defined functions

All examples above were applied to the built-in functions. In fact, they don't need declaration and all clauses above were added only to demonstrate the point.

However, with a little effort, the user-defined functions can be made sargable too.

Here are some suggestions on how to make it:

1. To be sargable, a user-defined function should be strictly deterministic, that is its result should depend on and only on the values of the arguments (specifically, it should not depend on the database state)
2. If a function is a superposition of the monotonic functions (with the additional constraints stated above), it should be automatically treated as monotonic.
3. If a function is declared as monotonic by a user, special algorithms should be used to check its monotony (and hence sargability):
   1. Sargability of a monotonic user-defined function should be a property of index-function pair. Function's declared monotony is a necessary but not sufficient condition for sargability.

      By default, sargability of index-function pair is unknown.

   2. Whenever a query is issued which could be satisfied by using the index to search for the function values, the index-function pair is marked as potentially sargable. This property can be made dynamic: say, 10 or 100 queries should be issued before the sargability of the index-function pair can be checked.
   3. When the query threshold is reached (this means that the certain number of queries which possibly could use the index had been run), the index checking process is initiated.
   4. The database job which is responsible for collecting the index statistics, runs over the index and checks the declared monotony of the function over the given argument: within each piece, higher values of argument should map to higher (or lower, or not higher, or not lower) values of the function. If the function is piecewise monotonic with pieces defined by a user-defined function as well, the monotony of the piece-defined function should also be checked in the same routine.
   5. If the check succeeds, the index-function is marked as sargable both for the function and its piece-defining function (if any).
   6. At the same time, the statistics routine should collect the additional statistics for the function as if it was the index over the function's values.
   7. If an index is marked as usable for any given function, all DML operations against this index should perform an additional validation for the function monotony:
      1. Whenever a new record is inserted into the index, the function should be applied to the values of the key inserted and both of its neighbors. The value of the function over the key inserted should be between (or, depending on the function's monotony, strictly between) the values of the function over the neighboring keys.
      2. If the function is declared as piecewise monotonic with a piece defining function, the latter is checked first.
      3. If any of the neighboring keys belongs to a piece different to that of the key being inserted, that neighboring key will not participate in the check.
   8. A failure to prove the function's monotony invalidates the function's usage in all indexes and also invalidates the sargability of all functions that use it as a piece-defining function. Additionally, the values of the arguments which are proven to violate the function's monotony are recorded with the function's metadata.
   9. Any change to the function's definition invalidates all sargability information linked with this function, as well as linked with the functions that uses it to define the pieces.
   10. For any index-function pair, the validation and statistics collection process can be initiated manually. The database engine should provide means for that.

Points of interest

Function sargability may be used to improve many queries, specifically:

• Searching for dates within a given period (month, date, year) without a need to calculate the ranges manually:

  SELECT  *
  FROM    mytable
  WHERE   EXTRACT(YEAR_MONTH FROM col1) = '201002'
  

• Searching for birthdates and calendar events:

  SELECT  *
  FROM    mytable
  WHERE   EXTRACT(calendar_date FROM mydate) = '0310'
  

• Searching for the substrings:

  SELECT  *
  FROM    mytable
  WHERE   LEFT(value, 10) = 'abcdefghij'
  

• Searching for the COALESCE'd values:

  SELECT  *
  FROM    mytable
  WHERE   COALESCE(value, 'test') = 'test'
  

and many others.

I really hope that this will be added to the major database engines in the nearest future.