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