{"id":1908,"date":"2010-02-09T09:47:21","date_gmt":"2010-02-09T07:47:21","guid":{"rendered":"http:\/\/code.openark.org\/blog\/?p=1908"},"modified":"2010-02-11T08:52:52","modified_gmt":"2010-02-11T06:52:52","slug":"monotonic-functions-sql-and-mysql","status":"publish","type":"post","link":"https:\/\/code.openark.org\/blog\/mysql\/monotonic-functions-sql-and-mysql","title":{"rendered":"Monotonic functions, SQL and MySQL"},"content":{"rendered":"

In mathematics, a monotonic function<\/strong> (or monotone function<\/strong>) is a function which preserves the given order. [Wikipedia<\/a>]<\/p><\/blockquote>\n

To be more precise, a function f<\/em> is monotonic increasing, if for every x \u2264 y<\/em> it holds that f(x)\u00a0\u2264 f(y)<\/em>. f<\/em> is said to be strictly monotonic increasing is for every x < y<\/em> it holds that f(x) < f(y)<\/em>.<\/p>\n

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

Monotonic functions play an important role in SQL. To discuss monotonic functions in SQL we must first determine what the order<\/em> is, and then, what the function<\/em> is.<\/p>\n

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

\n
CREATE TABLE `log` (\r\n `id<\/strong>` int(11) NOT NULL AUTO_INCREMENT<\/strong>,\r\n `ts<\/strong>` timestamp<\/strong> NOT NULL DEFAULT CURRENT_TIMESTAMP<\/strong>,\r\n `error_level` tinyint(4) DEFAULT NULL,\r\n `subject` varchar(32) DEFAULT NULL,\r\n `description` varchar(255) DEFAULT NULL,\r\n PRIMARY KEY (`id`)\r\n)<\/pre>\n<\/blockquote>\n
In the above log<\/strong> table, log entries are added with id<\/strong> and ts<\/strong> getting automatically evaluated. Assuming no dirty hacks occur, we can expect that ts<\/strong> in monotonic<\/em> by order of id<\/strong>. That is, as id<\/strong> increases, so does ts<\/strong>. Is is possible that we get the same ts<\/strong> for a few rows (it is not unique), but once it increases, it never decreases again.<\/p>\n
Why is this interesting?<\/h4>\n
Because it simplifies common problems.<\/p>\n
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())”<\/strong>, thus using, again, full table scan plus locking all rows (depending on storage engine), we can use other methods:<\/p>\n
For example, it simplifies a search for a given ts<\/strong> value, when no index exists on the ts<\/strong> column. If we were to look for a log entry from ‘2009-02-07 11:58:00’<\/strong> by simple SELECT<\/strong>, we would have to use a full table scan. But, by knowing that ts<\/strong> is monotonic, we can also use binary search<\/a> on id<\/strong>.<\/p>\n