Home > Oracle, SQL > Which Query is Better?—Part III (No EXPLAIN PLAN To Rule Them All)

Which Query is Better?—Part III (No EXPLAIN PLAN To Rule Them All)


In 1988, a SQL researcher named Fabian Pascal wrote an article for Database Programming and Design in which he quoted Chris Date as saying:

SQL is an extremely redundant language. By this I mean that all but the most trivial of problems can be expressed in SQL in a variety of different ways. Of course, the differences would not be important if all formulations worked equally well but that is unlikely. As a result, users are forced to spend time and effort trying to find the “best” formulation (that is, the version that performs best)—which is exactly one of the things the relational model was trying to avoid in the first place.

Pascal then went on to test seven equivalent queries with five different database engines. Only one out of the five database engines came anywhere near to acing the test; it appeared to use the same execution plan for six of the queries but did not support the seventh query. The other engines used a range of query plans with different execution times. Pascal then predicted that:

Eventually, all SQL DBMSs, for competitive reasons, will have to equalize the performance of redundant SQL expressions and to document their execution plans. Forcing users to maximize performance through query formulation is not only unproductive, but simply a lost cause, especially if there is no guidance from the system. The more users understand the relational model and its productivity intentions, the more they will demand equalized performance and documented execution plans from vendors, instead of doggedly attempting to undertake unnecessary and futile burdens.

Let’s find out if Pascal’s twenty-year old prediction of equalized performance came true. First, let’s create tables similar to those that Pascal used. We need a table called Personnel containing employee details and a table called Payroll containing salary payments. The Payroll table is linked to the Personnel table by the Employee ID. The tests were conducted using Oracle Database 11g Enterprise Edition Release 11.2.0.1.0 on 32-bit Windows Windows XP Professional Version 2002 Service Pack 3.

CREATE TABLE personnel
(
  empid CHAR(9) NOT NULL,
  lname CHAR(15) NOT NULL,
  fname CHAR(12) NOT NULL,
  address CHAR(20) NOT NULL,
  city CHAR(20) NOT NULL,
  state CHAR(2) NOT NULL,
  ZIP CHAR(5) NOT NULL
);

CREATE TABLE payroll
(
  empid CHAR(9) NOT NULL,
  bonus INTEGER NOT NULL,
  salary INTEGER NOT NULL
);

INSERT INTO personnel
SELECT
  TO_CHAR(LEVEL, '09999') AS empid,
  DBMS_RANDOM.STRING('U', 15) AS lname,
  DBMS_RANDOM.STRING('U', 12) AS fname,
  '500 ORACLE PARKWAY' AS address,
  'REDWOOD SHORES' AS city,
  'CA' AS state,
  '94065' AS zip
FROM
  dual
CONNECT BY LEVEL <= 9900;

INSERT INTO payroll(empid, bonus, salary)
SELECT
  empid,
  0 as bonus,
  99170 + 10000 * CEIL(DBMS_RANDOM.VALUE * 10) AS salary
FROM
  personnel;

CREATE UNIQUE INDEX personnel_pk ON personnel(empid);
CREATE UNIQUE INDEX payroll_pk ON payroll(empid);

ALTER TABLE personnel ADD CONSTRAINT personnel_pk PRIMARY KEY (empid);
ALTER TABLE payroll ADD CONSTRAINT payroll_pk PRIMARY KEY (empid);
ALTER TABLE payroll ADD CONSTRAINT payroll_fk1 FOREIGN KEY (empid) REFERENCES personnel(empid);

EXEC DBMS_STATS.GATHER_TABLE_STATS(ownname=>'HR', tabname=>'PERSONNEL');
EXEC DBMS_STATS.GATHER_TABLE_STATS(ownname=>'HR', tabname=>'PAYROLL');

Observe that we gathered optimizer statistics for the newly created tables although they are not strictly necessary for the tests that follow. A database engine can generate query plans even in the absence of statistics and should generate the same plan for all semantically equivalent queries whether or not statistics are available.

The SQL exercise is to list the employees who were paid $199,170. Here are five different ways in which a programmer might formulate the required query, three of which are from Pascal’s article. Focus on the plan hash values in the query plans below. We see that Oracle uses four different query plans, meaning that Pascal’s prediction of equalized performance for equivalent queries is yet to be fulfilled.

The first formulation uses an unnecessary join when only a semi-join is strictly necessary. However, in this particular case, a semi-join is equivalent to a join because the Payroll table is linked to the Personnel table by the Employee ID. Oracle uses a HASH JOIN in the EXPLAIN PLAN.

SELECT lname
FROM personnel, payroll
WHERE personnel.empid = payroll.empid
AND salary = 199170;

SQL_ID  45974660xtuxv, child number 0
-------------------------------------
SELECT lname FROM personnel, payroll WHERE personnel.empid =
payroll.empid AND salary = 199170

Plan hash value: 2476600843

--------------------------------------------------------------------------------------------------------------------------
| Id  | Operation          | Name      | Starts | E-Rows |E-Bytes| Cost (%CPU)| E-Time   | A-Rows |   A-Time   | Buffers |
--------------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |           |      1 |        |       |    80 (100)|          |   1004 |00:00:00.10 |     295 |
|*  1 |  HASH JOIN         |           |      1 |    990 | 40590 |    80   (2)| 00:00:01 |   1004 |00:00:00.10 |     295 |
|*  2 |   TABLE ACCESS FULL| PAYROLL   |      1 |    990 | 14850 |    11   (0)| 00:00:01 |   1004 |00:00:00.01 |      38 |
|   3 |   TABLE ACCESS FULL| PERSONNEL |      1 |   9900 |   251K|    68   (0)| 00:00:01 |   9900 |00:00:00.02 |     257 |
--------------------------------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   1 - access("PERSONNEL"."EMPID"="PAYROLL"."EMPID")
   2 - filter("SALARY"=199170)

The second formulation implements a semi-join using an uncorrelated subquery. Oracle neatly converts this into a join and once again uses a HASH JOIN in the EXPLAIN PLAN. The query plan is identical to the previous one.

SELECT lname
FROM personnel
WHERE empid IN (SELECT empid
FROM payroll
WHERE salary = 199170);

SQL_ID  7n392100shvq0, child number 0
-------------------------------------
SELECT lname FROM personnel WHERE empid IN (SELECT empid FROM payroll
WHERE salary = 199170)

Plan hash value: 2476600843

--------------------------------------------------------------------------------------------------------------------------
| Id  | Operation          | Name      | Starts | E-Rows |E-Bytes| Cost (%CPU)| E-Time   | A-Rows |   A-Time   | Buffers |
--------------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |           |      1 |        |       |    80 (100)|          |   1004 |00:00:00.11 |     295 |
|*  1 |  HASH JOIN         |           |      1 |    990 | 40590 |    80   (2)| 00:00:01 |   1004 |00:00:00.11 |     295 |
|*  2 |   TABLE ACCESS FULL| PAYROLL   |      1 |    990 | 14850 |    11   (0)| 00:00:01 |   1004 |00:00:00.01 |      38 |
|   3 |   TABLE ACCESS FULL| PERSONNEL |      1 |   9900 |   251K|    68   (0)| 00:00:01 |   9900 |00:00:00.02 |     257 |
--------------------------------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   1 - access("EMPID"="EMPID")
   2 - filter("SALARY"=199170)

The third formulation implements a semi-join using a correlated subquery. This time Oracle declines to convert it into a regular join.

SELECT lname
FROM personnel
WHERE EXISTS (SELECT *
  FROM payroll
  WHERE personnel.empid = payroll.empid
  AND salary = 199170);

SQL_ID  g6b8pdygq8vnd, child number 0
-------------------------------------
SELECT lname FROM personnel WHERE EXISTS (SELECT *   FROM payroll
WHERE personnel.empid = payroll.empid   AND salary = 199170)

Plan hash value: 1844477241

----------------------------------------------------------------------------------------------------------------------------
| Id  | Operation            | Name      | Starts | E-Rows |E-Bytes| Cost (%CPU)| E-Time   | A-Rows |   A-Time   | Buffers |
----------------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT     |           |      1 |        |       |    80 (100)|          |   1004 |00:00:00.10 |     295 |
|*  1 |  HASH JOIN RIGHT SEMI|           |      1 |      1 |    41 |    80   (2)| 00:00:01 |   1004 |00:00:00.10 |     295 |
|*  2 |   TABLE ACCESS FULL  | PAYROLL   |      1 |    990 | 14850 |    11   (0)| 00:00:01 |   1004 |00:00:00.01 |      38 |
|   3 |   TABLE ACCESS FULL  | PERSONNEL |      1 |   9900 |   251K|    68   (0)| 00:00:01 |   9900 |00:00:00.02 |     257 |
----------------------------------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   1 - access("PERSONNEL"."EMPID"="PAYROLL"."EMPID")
   2 - filter("SALARY"=199170)

The fourth formulation uses a scalar subquery in the WHERE clause. Oracle uses a different query plan.

SELECT lname
FROM personnel
WHERE (SELECT salary FROM payroll WHERE personnel.empid = payroll.empid) = 199170;

SQL_ID  23t064626ggwk, child number 0
-------------------------------------
SELECT lname FROM personnel WHERE (SELECT salary FROM payroll WHERE
personnel.empid = payroll.empid) = 199170

Plan hash value: 1680572657

-------------------------------------------------------------------------------------------------------------------------------------
| Id  | Operation                    | Name       | Starts | E-Rows |E-Bytes| Cost (%CPU)| E-Time   | A-Rows |   A-Time   | Buffers |
-------------------------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT             |            |      1 |        |       | 11134 (100)|          |   1004 |00:00:00.34 |   10786 |
|*  1 |  FILTER                      |            |      1 |        |       |            |          |   1004 |00:00:00.34 |   10786 |
|   2 |   TABLE ACCESS FULL          | PERSONNEL  |      1 |   9900 |   251K|    68   (0)| 00:00:01 |   9900 |00:00:00.03 |     257 |
|   3 |   TABLE ACCESS BY INDEX ROWID| PAYROLL    |   9900 |      1 |    15 |     2   (0)| 00:00:01 |   9900 |00:00:00.22 |   10529 |
|*  4 |    INDEX UNIQUE SCAN         | PAYROLL_PK |   9900 |      1 |       |     1   (0)| 00:00:01 |   9900 |00:00:00.08 |     629 |
-------------------------------------------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   1 - filter(=199170)
   4 - access("PAYROLL"."EMPID"=:B1)

The fifth formulation uses a scalar subquery in the SELECT clause. Oracle uses yet another query plan.

SELECT (SELECT lname FROM personnel WHERE personnel.empid = payroll.empid)
FROM payroll
WHERE salary = 199170;

SQL_ID  4njn8zu6dj0v8, child number 0
-------------------------------------
SELECT (SELECT lname FROM personnel WHERE personnel.empid =
payroll.empid) FROM payroll WHERE salary = 199170

Plan hash value: 1891291052

--------------------------------------------------------------------------------------------------------------------------------------
| Id  | Operation                   | Name         | Starts | E-Rows |E-Bytes| Cost (%CPU)| E-Time   | A-Rows |   A-Time   | Buffers |
--------------------------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT            |              |      1 |        |       |    11 (100)|          |   1004 |00:00:00.01 |     105 |
|   1 |  TABLE ACCESS BY INDEX ROWID| PERSONNEL    |   1004 |      1 |    26 |     2   (0)| 00:00:01 |   1004 |00:00:00.02 |    1602 |
|*  2 |   INDEX UNIQUE SCAN         | PERSONNEL_PK |   1004 |      1 |       |     1   (0)| 00:00:01 |   1004 |00:00:00.01 |     598 |
|*  3 |  TABLE ACCESS FULL          | PAYROLL      |      1 |    990 | 14850 |    11   (0)| 00:00:01 |   1004 |00:00:00.01 |     105 |
--------------------------------------------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   2 - access("PERSONNEL"."EMPID"=:B1)
   3 - filter("SALARY"=199170)

Christopher Charles laments the need to tune SQL manually in a well-written piece titled My Brilliant Career Tuning SQL. Why was Ingres able to beat the other database engines achieve equalized performance in 1988? Because, back in 1988, Ingres internally converted SQL queries into a QUEL representation. As Pascal explains, “QUEL was a different relational data language, one property of which was lack of sub-queries, meaning that however you expressed a query in SQL, it would map to only one QUEL execution (Chris Date designed the mapping), hence the ease of optimization and consistency.”

P.S. When I submitted a paper containing some of the above material to an Oracle conference, the reviewer took offence and responded:

I was disappointed that you quoted Fabian Pascal’s example of “8 [sic] Semantically Equivalent Queries” asking whether they would all result in the same execution plan. Being involved in this kind of optimization, I can tell you that the answer depends upon which version of the DBMS you are using. Until quite recently, we frequently used inline queries but the Optimizer is significantly smarter in version 10g R2 and some complex SQL refactoring became unnecessary.

Which Query is Better?—Part I
Which Query is Better?—Part II

Categories: Oracle, SQL
  1. December 8, 2010 at 3:38 pm

    “Why was Ingres able to beat the other database engines in 1988”
    I’m not convinced about the word ‘beat’ here. Yes, it achieved Pascal’s goal of consistency but it wasn’t the fastest to execute the query. Given that there is an inevitable runtime cost in transforming/optimizing a query, and (just as importantly) the chance of bugs will increase with the complexity of those algorithms, consistent plans for different queries isn’t necessarily the desired goal of Oracle/IBM/Microsoft.

  2. Iggy Fernandez
    December 8, 2010 at 4:15 pm

    Correct. Ingres was not the fastest on three out of six counts and did not support the seventh query.

  3. December 9, 2010 at 10:38 pm

    I found also a HASH JOIN RIGHT ANTI plan. Without this post I would have never written such query.

  4. December 31, 2010 at 12:53 pm

    “Given that there is an inevitable runtime cost in transforming/optimizing a query, and (just as importantly) the chance of bugs will increase with the complexity of those algorithms, consistent plans for different queries isn’t necessarily the desired goal of Oracle/IBM/Microsoft.”

    This misses the point of my article: that redundancy in the language makes it more difficult and costly to optimize and leads to the need to manually optimize, which is rather a lost cause that the relational model explicitly intended to avoid.

    As to my prediction, I was younger and naive then: I still believed that the market will induce vendors to do the right thing. I am wiser now and realize that the assumptions behind that belief–educated informed demand and supply–are unrealistic.

    Hence my subsequent argument that the IT industry operates like the fashion industry.

  5. December 31, 2010 at 12:56 pm

    And, BTW, I also underestimated the difficulty of resolving problems created by poor relational and language design. Which only strengthens the arguments of us “relational purists”.

    SQL and its designers have a lot to answer for but they benefit from the ignorance of data fundamentals in the industry, which has gone for bad to atrocious.

  6. December 31, 2010 at 1:15 pm

    And here is a pertinent argument by Hugh Darwen from an exchange at dbdebunk:

    “Finally, I wish to add something to what Lex has said with reference to the claim that “it doesn’t really matter: we know how NULL behaves and so all we have to do is be careful to write correct code that avoids the pitfalls”. Lex has given our reasons for dismissing the claim, but I think it is important to understand why such claims are made, and made so vehemently, in the first place. I strongly believe that the answer lies in “job protection”. Bad languages give rise to experts, who can charge highly for their expertise. SQL is such an incredibly bad language (on all sorts of counts, not just NULL) that I was able make a good living out of for the last 10 years of my long career in IBM, not by being a consultant to users of SQL databases, or an SQL application program developer, or an SQL DBA, but by drafting text for the SQL international standard. Some of the text I had to draft was more difficult than anything I had ever had to write, in programming languages, in my former job as a computer programmer! I.e., it is more difficult to write the (retrospective) specification than it is to write the code!”
    http://www.dbdebunk.com/page/page/2928212.htm

    I recently had a db practitioner confess to me that he “built a house” out of fixing problems due to this type of complications. It echoes my argument in the preface to one of my books that there is an economic incentive for complexity in the industry.

  7. Iggy Fernandez
    June 5, 2011 at 3:50 pm

    fabian pascal :

    And, BTW, I also underestimated the difficulty of resolving problems created by poor relational and language design. Which only strengthens the arguments of us “relational purists”.

    SQL and its designers have a lot to answer for but they benefit from the ignorance of data fundamentals in the industry, which has gone for bad to atrocious.

    Perhaps NoSQL is the answer. See my answer at http://bit.ly/kEQMR7

  1. No trackbacks yet.

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

%d bloggers like this: