Equality propagation optimization

You are viewing an old version of this article. View the current version here.

Basic idea

Consider a query with a WHERE clause:

WHERE col1=col2 AND ...

the WHERE clause will compute to true only if col1=col2. This means that in the rest of the WHERE clause occurrences of col1 can be substituted with col2 (with some limitations which are discussed in the next section). This allows the optimizer to infer additional restrictions.

For example:

WHERE col1=col2 AND col1=123

allows to infer a new equality: col2=123

WHERE col1=col2 AND col1 < 10 

allows to infer that col2<10.

Identity and comparison substitution

There are some limitations to where one can do the substitution, though.

The first and obvious example is the string datatype and collations. Most commonly-used collations in SQL are "case-insensitive", that is 'A'='a'. Also, collations have a "PAD SPACE" attribute, which means that comparison ignores the spaces at the end of the value, 'a'='a '.

Now, consider a query:

INSERT INTO t1 (col1, col2) VALUES ('ab', 'ab   ');
SELECT * FROM t1 WHERE col1=col2 AND LENGTH(col1)=2

Here, col1=col2, the values are "equal". At the same time LENGTH(col1)=2, while LENGTH(col2)=4, which means one can't perform the substiution for the argument of LENGTH(...).

It's not only collations. There are similar phenomena when equality compares columns of different datatypes. The exact criteria of when thy happen are rather convoluted.

The take-away is: sometimes, X=Y does not mean that one can replace any reference to X with Y. What one CAN do is still replace the occurrence in the comparisons <, >, >=, <=, etc.

This is how we get two kinds of substitution:

  • Identity substitution: X=Y, and any occurrence of X can be replaced with Y.
  • Comparison substitution: X=Y, and an occurrence of X in a comparison (X<Z) can be replaced with Y (Y<Z).

Comments

Comments loading...
Content reproduced on this site is the property of its respective owners, and this content is not reviewed in advance by MariaDB. The views, information and opinions expressed by this content do not necessarily represent those of MariaDB or any other party.