In mathematics, a monotonic function (or monotone function) is a function which preserves the given order. [Wikipedia]

To be more precise, a function f is monotonic increasing, if for every x ≤ y it holds that f(x) ≤ f(y). f is said to be strictly monotonic increasing is for every x < y it holds that f(x) < f(y).

So, if we follow values in some order, we say that f is monotonic increasing if f‘s value never decreases (it either increases or stays the same), and we say that f is strictly increasing if f‘s value is always changes “upwards”.

Monotonic functions play an important role in SQL. To discuss monotonic functions in SQL we must first determine what the order is, and then, what the function is.

Well, they both change according to our point of view. Let’s look at some examples. Take a look at the following table:

CREATE TABLE `log` (
 `id` int(11) NOT NULL AUTO_INCREMENT,
 `ts` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP,
 `error_level` tinyint(4) DEFAULT NULL,
 `subject` varchar(32) DEFAULT NULL,
 `description` varchar(255) DEFAULT NULL,
 PRIMARY KEY (`id`)
)

In the above log table, log entries are added with id and ts getting automatically evaluated. Assuming no dirty hacks occur, we can expect that ts in monotonic by order of id. That is, as id increases, so does ts. Is is possible that we get the same ts for a few rows (it is not unique), but once it increases, it never decreases again.

Why is this interesting?

Because it simplifies common problems.

For example, it simplifies a search for a given ts value, when no index exists on the ts column. If we were to look for a log entry from ‘2009-02-07 11:58:00’ by simple SELECT, we would have to use a full table scan. But, by knowing that ts is monotonic, we can also use binary search on id.

As another example, it simplifies the task of purging all rows up to last midnight. Instead of issuing “DELETE FROM log WHERE ts < DATE(NOW())”, thus using, again, full table scan plus locking all rows (depending on storage engine), we can use other methods:

• We can detect the id for the first row which holds the condition using binary search, then “DELETE FROM log WHERE id < ###”
• Or we can slowly work our way in ascending id order, issuing something like “DELETE FROM log WHERE ts < DATE(NOW()) ORDER BY id ASC LIMIT 1000”, and stop once the ROW_COUNT() is less than 1000. We know we need not advance any further, without needing to compute anything. We thus block less, while retaining correctness of our operation.

Monotonic functions in MySQL

When we iterate InnoDB tables (as in full table scan), we know that rows are iterated in ascending PRIMARY KEY order [¹]. So the PRIMARY KEY dictates the order by which monotonic functions are evaluated.

With MyISAM, rows are iterated according to internal storage order. It has nothing to do with PRIMARY KEYs (though depending on concurrent_insert this can be somewhat controlled). It also has nothing to do with chronological order. Newer rows may capture space held by older rows.

But MyISAM allows for ALTER TABLE … ORDER BY … syntax, which allows us to do a one-time sort of the table. Assuming no writes shortly thereafter, a full table scan will iterate the rows according to specified order.

Monotonic functions and indexes

A column which is indexed dictates a monotonic function by index order.

Wait. Isn’t that obvious? Of course: if we index a column, then the index sorts by that column, and the column is ascending by the index order which is,… itself.

I call that trivial, but it does interest us: because, while mathematically there may be nothing significant here, we do care about this order when we have index scans. So, if we can force an index scan on our query, then we can anticipate the order by which rows are processed; we now have some order by which to evaluate monotonic functions.

OK, maybe I made it sound more complicated than it really is. Monotonic functions work well when the order by which they are monotonic is some indexed column(s). The AUTO_INCREMENT PRIMARY KEY we saw in the log example above, is perhaps the most trivial case.

While MySQL does not support function indexes, if the function we consider is monotonic, we still benefit from adding an index on the raw column.

Other examples of monotonic functions

So, where else can we find them? Timestamp columns are probably the most common (this post holds true until time travel to the past is introduced).

But also summaries: like a reporting table which lists down some ever-ascending value (the number of books ever sold in our store; trip mileage; hop counter; etc.).

I’ve seen many cases (though difficult to illustrate in this scope) when foreign key values are in ascending order. A very brief example is a 1-1 relation between two denormalized tables, where the tables ids do not necessarily have to match, but is always ascending).

And Baron’s wishlist for SQL can also benefit from monotonic functions.

Conclusion

When a monotonic function is present, it brings an added value to our schema and query design. It allows for less indexing; quicker operations. Look for these. I’ve only discussed increasing functions. Indeed, MySQL’s indexes are always increasing (they cannot be defined in decreasing order), but query simplifications work just as well for monotonic decreasing functions.

[¹] I’ve actually seen a different behavior on temporary InnoDB tables and on compressed InnoDB Plugin tables; I’ll write on this on another occasion.

I wish to present an SQL solution for checking if two strings are permutations of the same text.

About permutations

So, if ‘lolhe’ is a permutation of ‘hello’, then ‘hello’ is a permutation of ‘lolhe’, as well; and both are permutations of ‘elloh’. The REVERSE() of a text is an example of permutation. Mathematically, string permutation is an equivalence relation, and divides all strings to equivalence classes.

Use cases

• We may be interested in permutations when a user chooses a password. We may disallow a password which is identical to the login name; but we may also disallow upper-lower-case-only transformations of the text. We may still disallow a permutation of the text.
• On a slightly different scale, the two queries: SELECT * FROM City WHERE id IN (5, 21, 13) and SELECT * FROM City WHERE id IN (13, 5, 21) are identical. Here, the permutation is not with string characters, but with string tokens. While the solution discussed is targeted at string characters, it can be easily converted to work with string tokens.

Checking for permutation

The solution I’m suggesting checks for permutation between 2 strings by permuting both to a third, normal form. The two string are permutations of each other if both have the same normal form.

What exactly is a normal form? Well, anything you like, really, as long as it’s deterministic and works the same for all elements in the equivalence class (mathematically speaking, this was a really bad definition, I know).

Enough of mathematical notions: on the practical side, I’ll normalize ‘CAB’ to ‘ABC’, and ‘DOG’ to ‘DGO’. Can you see what normalization means here? I’m merely rearranging the characters in alphabetical order. This rearrangement is in itself a permutation of the string (hence, one last mathematical statement, it can be seen as a representative of the equivalence class).

So, to see if two strings are permutations of each other, we rearrange both in alphabetical order, and see if we got the same text. ‘hello’ and ‘lolhe’ both normalize to ‘ehllo’, hence are permutations.

Normalizing the text

Down to business: how do we normalize a text using SQL? Well, once again, string walking and string unwalking to the rescue. The trick is to break the string apart (to distinct characters), then re-combine the characters, but instead of in original order, do that in ascending order.

Breaking of the word ‘hello’ is as follows:

SELECT
 SUBSTRING(s, value+1, 1) AS c
FROM
 tinyint_asc, (SELECT 'hello' AS s) sel1
WHERE
 value < char_length(s);

Recombining it in ascending character order is as follows:

SELECT GROUP_CONCAT(c ORDER BY c SEPARATOR '') AS normalized FROM
 (
 SELECT
   SUBSTRING(s, value+1, 1) AS c
 FROM
   tinyint_asc, (SELECT 'hello' AS s) sel1
 WHERE
   value < char_length(s)
 ) walked_string_select;
+------------+
| normalized |
+------------+
| ehllo      |
+------------+
1 row in set (0.00 sec)

We can write a stored function to do that more conveniently (and, while at it, also normalize character case):

DELIMITER $$

DROP FUNCTION IF EXISTS `normalize_text`$$
CREATE FUNCTION `normalize_text` (input_text VARCHAR(255) CHARSET utf8) RETURNS VARCHAR(255) CHARSET utf8
DETERMINISTIC
READS SQL DATA
BEGIN
 SELECT GROUP_CONCAT(c ORDER BY c SEPARATOR '') INTO @normalized FROM
 (
 SELECT
   SUBSTRING(s, value+1, 1) AS c
 FROM
   tinyint_asc, (SELECT input_text AS s) sel1
 WHERE
   value < char_length(s)
 ) walked_string_select;
 RETURN LOWER(@normalized);
END$$

DELIMITER ;

And use like this:

mysql> SELECT normalize_text('Smith');
+-------------------------+
| normalize_text('Smith') |
+-------------------------+
| himst                   |
+-------------------------+
1 row in set (0.00 sec)

mysql> SELECT normalize_text('Smith') = normalize_text('Thims');
+---------------------------------------------------+
| normalize_text('Smith') = normalize_text('Thims') |
+---------------------------------------------------+
|                                                 1 |
+---------------------------------------------------+
1 row in set (0.00 sec)

mysql> SELECT normalize_text('Smith') = normalize_text('Sniff');
+---------------------------------------------------+
| normalize_text('Smith') = normalize_text('Sniff') |
+---------------------------------------------------+
|                                                 0 |
+---------------------------------------------------+
1 row in set (0.00 sec)

To compare tokenized strings (like ‘21,5,13’ vs. ‘5,13,21’), we can use the SUBSTRING_INDEX() function to break the string apart, instead of SUBSTRING().