MariaDB and MySQL’s optimizer does not recognize tautologies and contradictions

In logic, a tautology is an expression which is always TRUE, no matter what values are assigned to variables (col = col). The opposite of tautologies are contradictions: a contradiction is an expression which is always FALSE (col col).

I wondered if MariaDB’s optimizer recognizes tautologies and contradictions, so I played with some stupid queries. The procedure I used to verify the tautologies is simple:

EXPLAIN EXTENDED <query>;
SHOW WARNINGS;

As you probably know, if you execute SHOW WARNINGS after EXPLAIN EXTENDED, it returns the query internally rewritten by MariaDB. This way, it’s easy to verify if a tautology/contradiction has been recognized: WHERE <tautology> should be replaced with: WHERE 1, while WHERE <contradiction> should be replaced with: WHERE 0. Just to be sure, I check if EXPLAIN says we are going to have a full table scan… just to verify a tautology.

It turns out that the optimizer recognize very few tautologies. For example:

<const_value>
<const_expression>
col = col
col != col
NOT NOT col = col
(col = val) AND (col  val)

(col = val) OR NOT (col = val)

Tuatologies and contradictions that are NOT recognized: (some of them are partly optimized, however)

col IN (col, ...)
col IN (val1, val2) = col NOT IN (val1, val2)
col IN (val1, val2) = (col = val1 OR col = val2))
(col > val) AND (col < val)
(col = val) = (val = col)
(col AND val) = (val AND col) // etc
(col = val) AND NOT (col = val)
(col = val) OR (col <> val)
(col IS NULL) OR (col IS NOT NULL)
(col = val) XOR NOT (col = val)
(col = val1) = (col = val1) AND (col = val2)

I could have tried more tautologies/contadictions, but if these one are not recognized, I can reasonably say that more complex ones are not recognized.

Please, note that I didn't try these in any other DBMS. So I am NOT saying that other software projects has a superior optimizer. Probably they have not. However, I find these results quite amazing. It is probably rare for a DBMS to meet one of these tautologies in a query. But, I guess that sometimes it happens… and it's really hard for a user to guess that col IN (col, ...) is not properly optimized.

UPDATE
Henrik Ingo commented this post on Facebook, and I wish to share his thoughts with everyone:
It’s easy for us app developers to think that a RDBMS contains some form of AI or general purpose logic engine that will solve our “obvious” where clauses. I’ve had similar surprises, but in real world cases, too. It’s good for app developers to understand that the optimizations that exist in a RDBMS are there only because someone actually spent lot of time implementing them.
http://openlife.cc/blogs/2012/september/hand-holding-postgresql-simple-query

Advertisements

5 thoughts on “MariaDB and MySQL’s optimizer does not recognize tautologies and contradictions

  1. Do you have any real-world examples where detecting these tautologies would provide a real benefit? I’ve been working with optimizer complaints for years and don’t recall anybody complaining.
    Detecting tautologies can be *expensive*. For example, the “3-satisfability problem” is essentially detection of tautology.

    Why would an application submit SQL queries with tautologies? I would argue that most of SQL queries are real data-searching queries, and have no tautologies. The only way an application may submit a tautology is when it is dynamically building SQL from lots of pieces, and ends up building a tautology without realizing. I’d like to see some real world examples, then.

    • I’m not really complaining about this. I just found a query which contained a tautology (of the type: (col = val) OR (col val)) but it was a mistake. I noticed that the tautology was detected. So, as I wrote, I ran some queries because I was curios. I was surprised, because I thought the optimizer would dectected tautologies. That’s all.
      Of course if you think this is useless (or too expensive), you must be right.

      • I’ll be happy to add detection/elimination of any particular kind of tautologies, as long as there’s some evidence that it will bring benefits. At the moment, there’s no evidence. There are things where MySQL/MariaDB optimizers cause pain for the users, but tautology detection is not in the list.

  2. (col = val) OR NOT (col = val) is actually handled:

    MariaDB [test]> explain select * from ten where a=3 and not (a =3);
    +——+————-+——-+——+—————+——+———+——+——+——————+
    | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
    +——+————-+——-+——+—————+——+———+——+——+——————+
    | 1 | SIMPLE | NULL | NULL | NULL | NULL | NULL | NULL | NULL | Impossible WHERE |
    +——+————-+——-+——+—————+——+———+——+——+——————+

Leave a comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s