Things SQL needs: sargability of monotonic functions
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 BTree index, the keys of the index should be compared to the value being searched for.
Let's consider this sample BTree 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 BTree 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 BTree looks now from the point of view of the expression in the WHERE
clause
Now, we have a perfectly valid BTree: 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 BTree as seen from the expression's side:
The order persists.
This BTree 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 nonunique field.
Finally, let's consider one more expression, a very simple one:
SELECT * FROM mytable WHERE 20  value = 10
and how it sees the BTree:
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 BTree order, while the other ones maintain it.
What is the difference between the two?
For an expression to maintain the BTree 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 nondecreasing), if for allx
andy
such thatx ≤ y
one hasf(x) ≤ f(y)
, sof
preserves the order. Likewise, a function is called monotonically decreasing (also decreasing, or nonincreasing) if, wheneverx ≤ y
, thenf(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 singleargument 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 BTree searches without changing the search order. AUNIQUE
set of values is mapped to aUNIQUE
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 BTree searches without changing the search order. AUNIQUE
set of values may be mapped to a nonunique 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 BTree searches, changing the search order. AUNIQUE
set of values is mapped to aUNIQUE
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 BTree searches, changing the search order. AUNIQUE
set of values is mapped to aUNIQUE
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 piecedefining 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
Piecedefining 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 nonstrict 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 isSTRICTLY MONOTONIC
 A superposition of any number of
STRICTLY MONOTONIC
functions and at least oneMONOTONIC
function isMONOTONIC
(as opposed toSTRICTLY MONOTONIC
)  A superposition of an
INCREASING
and aDECREASING
function isDECREASING
 A superposition of an
INCREASING
and anINCREASING
functions, or that of aDECREASING
function and aDECREASING
function isINCREASING
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 ], [ nonoverarg1 [ ,… ] ])
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 argumentPIECE
. This is the value defined by the piecedefining function. This only makes sense in a functiondefined piecewise monotonynonoverarg
. This is the argument to the function not used in theOVER
clause. This only makes sense for multipleargument 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 provideEXCLUDE
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 BTree 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 EXCLUDEYEAR
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 asEXCLUDE
, 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 RESULTThe 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 EXCLUDEThe 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 ENDThis function defines division operator.
It is monotonic over the first argument. This means that the second argument should be provided as the runtime 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 ofarg2
.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 nonstrict 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  arg1This 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 EXCLUDEMONTH
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
andRESULT
arguments. ThePIECE
argument defines the current year, theRESULT
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)
ENDCosine is piecewise monotonic too. The pieces are defined by the cosine halfwaves. Depending on the piece, it can be increasing or decreasing. The halfwave number is defined by
FLOOR(arg / PI())
. This piecedefining function, being a superposition of increasing functions, is increasing too.On the even halfwaves, the function is decreasing; on the odd halfwaves, it is increasing. In principle, the function monotony is strict, but due to the possible rounding errors, it is marked as nonstrict 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)
ENDSame 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:

If the function is not sargable against the first argument, then just do the full table or index scan.

If the function is sargable against the first argument, check its monotony.

If the function is monotonic over all domain:

If no inversion function is defined, then locate the values in the BTree using the BTree 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.

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 ofcol1
and locate it in the index using BTree search algorithm. 
If the function is monotonic, but not strictly, check the inversion type:

If a scalar inverse expression is defined, then:

Apply the inverse function to
const
and find the key values in the BTree closest to the value ofinverse_expression(const)

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.


If a range inverse expression is defined, then:

Find the beginning and the ending values of the
col1
range that yieldsconst
If the beginning of range is not exact, iterate keys backwards, applying the function to each key found until the function equals toconst
. 
Iterate the keys forward, returning the records found, until the end of the range is reached.

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




If the function is piecewise monotonic:

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.

If the pieces are defined by a function:

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 BTree, 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. 
Within the range defined by these values, apply the steps above, with respect to the monotony of each piece.


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.

Userdefined functions
All examples above were applied to the builtin 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 userdefined functions can be made sargable too.
Here are some suggestions on how to make it:
 To be sargable, a userdefined 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)
 If a function is a superposition of the monotonic functions (with the additional constraints stated above), it should be automatically treated as monotonic.

If a function is declared as monotonic by a user, special algorithms should be used to check its monotony (and hence sargability):

Sargability of a monotonic userdefined function should be a property of indexfunction pair. Function's declared monotony is a necessary but not sufficient condition for sargability.
By default, sargability of indexfunction pair is
unknown
. 
Whenever a query is issued which could be satisfied by using the index to search for the function values, the indexfunction 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 indexfunction pair can be checked.  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.
 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 userdefined function as well, the monotony of the piecedefined function should also be checked in the same routine.
 If the check succeeds, the indexfunction is marked as
sargable
both for the function and its piecedefining function (if any).  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.

If an index is marked as
usable
for any given function, allDML
operations against this index should perform an additional validation for the function monotony: 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.
 If the function is declared as piecewise monotonic with a piece defining function, the latter is checked first.

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.
 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 piecedefining function. Additionally, the values of the arguments which are proven to violate the function's monotony are recorded with the function's metadata.
 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.

For any indexfunction 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.
First, this was an excellent article. Second, I’ll be reviewing what parts of your suggestions I can easily introduce into the Drizzle optimizer.
Finally, I’d just say that perhaps the reason that many RDBMS have yet to implement such optimizations is because in many (all?) cases where a monotonic function might be inlined within the optimizer into a sargable parameter, the SQL statement can be rewritten in such a way as to manually perform the translation.
Simple example would be rewriting this MySQLish SQL SELECT statement (assume an index on t1(date_col)):
SELECT * FROM t1 WHERE TO_DAYS(date_col) > TO_DAYS(NOW()) – 8;
to
SELECT * FROM t1 WHERE date_col > NOW() – INTERVAL 8 DAY;
Cheers, and nice blog! :)
jay
Jay Pipes
20 Feb 10 at 05:51
@Jay: with a function monotonic over all its domain, it’s easy to rewrite the condition.
However, the point of SQL (as we have been told for the decades) is that
, and this proposal is to make this statement more true.Rewriting the conditions, though, may be not easy as it seems. Say,
col1 / y = z
is not the same ascol1 = z * y
(due to the rounding errors). This requires extra handling too.And what about functions that are piecewise monotonic? Like
? This is not so easy to rewrite as a sargable condition.So having these things handled automatically in Drizzle would be very nice :)
Quassnoi
20 Feb 10 at 10:07
Absolutely agree with you Quassnoi :)
Jay Pipes
20 Feb 10 at 19:04
Hi,
Very good write!
I also wrote a bit earlier on monotonic functions: on how to utilize the fact we have a monotonic function, to cover for a missing index:
Monotonic functions, SQL and MySQL
Regards
Shlomi Noach
19 Mar 10 at 14:52
@Shlomi: great minds think alike!
Quassnoi
19 Mar 10 at 15:17