Proving that 1=2, is Oracle Wrong to Short-Circuit an Execution Plan?

25 12 2009

December 25, 2009

Earlier this month I wrote a blog article that showed how Oracle behaves when the WHERE clause includes the predicate 1=2.  But is the shortcut implemented by Oracle wrong?  Will 1=2 never happen?

I attended a college course that covered just mathematical proofs (the name of the class escapes me at the moment – Discrete Mathematics?).  The mathematics professor for that course proved that 1=2.  That proof follows (I attempted to align the equal sign to make the proof easier to read):

Assumption: Let a = b
1.  a^2               = a^2
2.  a^2               = b^2
3.  a^2               = b * b
4.  a^2               = a * b
5.  a^2 - b^2         = a * b - b^2
6.  (a + b) * (a - b) = b * (a - b)
7.  a + b             = b
8.  b + b             = b
9.  2b                = b
10. 2 = 1

 

Mathematical Explanation of the Above Steps:
1.  Truth Statement
2.  Substitution
3.  Factor
4.  Substitution
5.  Subtract b^2 from Both Sides of the Equation
6.  Factor
7.  Divide Both Sides of the Equation by (a - b)
8.  Substitution
9.  Simplification
10. Divide Both Sides of the Equation by b

I think that there is a lesson in the above that may be applied to the understanding of Oracle databases.  Let me ponder the lesson while you review the Faulty Quotes series of blog articles.

A couple references for mathematical proofs follow – how might the techniques of mathematical proofs be applied to understanding the logic built into Oracle Database?http://www.eiu.edu/~mathcs/mat2345/index/Webview/Slides/handout-Week02-2×3.pdf
http://www.math.harvard.edu/archive/23b_spring_05/proofs.pdf
http://en.wikibooks.org/wiki/Category:Mathematical_Proof
http://wapedia.mobi/en/Inductive_proof


Actions

Information

5 responses

25 12 2009
Maxim

Well, the lesson might be, that Oracle ( like you from step 7 onwards ;-) ) consider two infinities equal to each other:

SQL> select dummy from dual where 2f/0f=3f/0f;

D

X

I think btw, it could be interesting as well to show, how Oracle produce “wrong” results in queries like
select dummy from dual where 3*(1/3) = 1;
seems to be well known fact about numbers precision, but people tend to forget about it again and again …
Best regards

Maxim

25 12 2009
Charles Hooper

Maxim, thanks for the comments.

I wonder if there is a deeper lesson in the proof that may be applied to Oracle databases, keeping in mind the description of mathematical proofs provided by the paper on the math.harvard.edu website. Mathematical type proofs are quite helpful for describing Oracle behavior, as long as the person preparing the proof does not ignore simple rules. Maybe the lesson is even deeper yet?

Incidentally, those are interesting queries and results. Here is what a portion of a 10053 trace file has to say about the first query:

******************************************
----- Current SQL Statement for this session (sql_id=15x9pv81bs0hs) -----
select dummy from dual where 2f/0f=3f/0f
*******************************************
...
FPD: Considering simple filter push in query block SEL$1 (#0)
BINARY_FLOAT_INFINITY=BINARY_FLOAT_INFINITY
try to generate transitive predicate from check constraints for query block SEL$1 (#0)
finally: BINARY_FLOAT_INFINITY=BINARY_FLOAT_INFINITY
...
Final query after transformations:******* UNPARSED QUERY IS *******
SELECT "DUAL"."DUMMY" "DUMMY" FROM "SYS"."DUAL" "DUAL" WHERE BINARY_FLOAT_INFINITY=BINARY_FLOAT_INFINITY
...
============
Plan Table
============
-------------------------------------+-----------------------------------+
| Id  | Operation          | Name    | Rows  | Bytes | Cost  | Time      |
-------------------------------------+-----------------------------------+
| 0   | SELECT STATEMENT   |         |       |       |     2 |           |
| 1   |  TABLE ACCESS FULL | DUAL    |     1 |     2 |     2 |  00:00:01 |
-------------------------------------+-----------------------------------+
Predicate Information:
----------------------
Content of other_xml column
...

Here is the partial 10053 trace file output for the second query:

******************************************
----- Current SQL Statement for this session (sql_id=3xzpa61x251bn) -----
select dummy from dual where 3*(1/3) = 1
*******************************************
...
FPD: Considering simple filter push in query block SEL$1 (#0)
.9999999999999999999999999999999999999999=1
try to generate transitive predicate from check constraints for query block SEL$1 (#0)
finally: .9999999999999999999999999999999999999999=1
...
Final query after transformations:******* UNPARSED QUERY IS *******
SELECT "DUAL"."DUMMY" "DUMMY" FROM "SYS"."DUAL" "DUAL" WHERE .9999999999999999999999999999999999999999=1
...
============
Plan Table
============
--------------------------------------+-----------------------------------+
| Id  | Operation           | Name    | Rows  | Bytes | Cost  | Time      |
--------------------------------------+-----------------------------------+
| 0   | SELECT STATEMENT    |         |       |       |     1 |           |
| 1   |  FILTER             |         |       |       |       |           |
| 2   |   TABLE ACCESS FULL | DUAL    |     1 |     2 |     2 |  00:00:01 |
--------------------------------------+-----------------------------------+
Predicate Information:
----------------------
1 - filter(NULL IS NOT NULL)
Content of other_xml column
...

Notice in the above that the query optimizer has completely eliminated the WHERE clause in the first query based on the output of the “Predicate Information” section of the plan. Note also how Oracle transformed the query that was submitted.

The second query produced the same type of plan that I showed in this blog entry. Note that Oracle also transformed the second SQL statement.

This raises the question, are these just bugs in the query optimizer?

2 01 2010
Charles Hooper

I did not want to spoil the fun for everyone else – Maxim is correct regarding the proof.

If a=b then (a-b)=0, so in step 7 the proof is essentially dividing by 0. I remember the first time I saw the proof – I paused at step 6, trying to make certain that the change on the left side of the equation [a^2 - b^2 to (a + b) * (a - b)] was permitted/legal – that the two were equivalent. After verifying that the professor did not pull a fast one at that step, I moved on to the next step, competely losing sight of the assumption at the start of the proof that a=b. So, it was not a basic algebra equation that brought down the proof, but something more basic – dividing by 0 is not permitted (as the divisor approaches 0, the equation result grows infinitely large, as pointed out by Maxim).

22 06 2011
Troy

The only reason No. 6 is true is because of the fact that a==b or (a-b)==0; we cannot divide both sides by (a-b) or 0 to get No. 7.
x*0==y*0 does not prove x==y.

22 06 2011
Charles Hooper

Troy,

Yes, exactly. That was also the point that Maxim made with his clever statement, “consider two infinities equal to each other” – in other words, divide by 0 and you obtain infinity.

I believe that Maxim stated it as such to give people a little more time to think about the problem and how it might be a larger statement related to Oracle. I don’t think that we ever reached the part of the larger statement about Oracle Database. Maybe something like the following:
* If you break the commonly accepted rules, you could see impossible results.
* A vertical 8 and a horizontal 8 (the symbol for infinity) are not the same thing – using information out of context could lead to significant problems.
* Even though a 0 and an empty set symbol ( Ø ) look similar, the two have very different meanings. I believe that someone tried to use this logic to prove that Oracle supports multiple block sizes for performance because it supports the KEEP and RECYCLE pools. :-)
* If you set out to prove something, make certain that you are proving what you think that you are proving.

Any other ideas about the larger meaning in the context of Oracle Database?

Leave a Reply

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




Follow

Get every new post delivered to your Inbox.

Join 141 other followers

%d bloggers like this: