March 2010

March 2010
Beginning with this issue, the Specialist moves to a bi-monthly format but with the same great content as always.
THE LIGHTER SIDE
Dilbert Was a Database Professional

Databases have figured dozens of times in Dilbert cartoons.  Our favorite is Dogbert Defeats The Database Guru (November 9, 1995) because we like to make fun of ourselves. Here are some more Dilbert cartoons featuring databases:

 

Asok rewrites the Elbonian database with just six keystrokes (December 21, 1996)
Asok creates a database of serial killers (March 23, 1998)
Asok learns the hard way (November 28, 2004)
Asok destroys the customer database (February 13, 2005)
Asok learns how to avoid work (July 10, 2005)
Asok corrects the pointy-haired boss (December 14, 2005)

 

Asok has potential, doesn’t he

?

STUMP THE SPECIALISTS
Hints on SQL Hints

This month’s question came to us from a customer:

“I used an Index hint in SQL statement but Oracle ignored it. How can I force Oracle to use a specific index?”

Senior Staff Consultant Ian Jones thoughtfully responds:

 

The only question more puzzling than “why isn’t Oracle using my index” is “why isn’t Oracle using my index hint.”

 

But first I should point out that a hint is really a directive, not something that Oracle ignores capriciously. For example, consider the following hinted query. We need to produce a manager-wise summary but inadvertently instruct Oracle to use an index on the LAST_NAME column instead of the correct index on the MANAGER_ID column. As the query plan below shows, Oracle blindly obeys the hint.

 

SQL> select /*+ INDEX(employees(last_name)) */ manager_id, count(*)
2  from employees
3  group by manager_id
4  order by manager_id;

 

MANAGER_ID   COUNT(*)
———- ———-
100         14
101          5
102          1
103          4
108          5
114          5
120          8
121          8
122          8
123          8
124          8
145          6
146          6
147          6
148          6
149          6
201          1
205          1
1

 

19 rows selected.

Execution Plan

 

—————————————————-
| Id  | Operation                    | Name        |
—————————————————-
|   0 | SELECT STATEMENT             |             |
|   1 |  SORT GROUP BY               |             |
|   2 |   TABLE ACCESS BY INDEX ROWID| EMPLOYEES   |
|   3 |    INDEX FULL SCAN           | EMP_NAME_IX |
—————————————————-

 

However, let’s try using the right hint and see what Oracle does. Surprisingly, Oracle appears to ignore the hint completely and resorts to a full table scan!

 

SQL> select /*+ INDEX(employees(manager_id)) */ manager_id, count(*)
2  from employees
3  group by manager_id
4  order by manager_id;

 

MANAGER_ID   COUNT(*)
———- ———-
100         14
101          5
102          1
103          4
108          5
114          5
120          8
121          8
122          8
123          8
124          8
145          6
146          6
147          6
148          6
149          6
201          1
205          1
1

19 rows selected.
Execution Plan
———————————————————-
Plan hash value: 2107619104

 

—————————————-
| Id  | Operation          | Name      |
—————————————-
|   0 | SELECT STATEMENT   |           |
|   1 |  SORT GROUP BY     |           |
|   2 |   TABLE ACCESS FULL| EMPLOYEES |
—————————————-

 

What happened? You see, MANAGER_ID just so happens to be a nullable column and null values are not included in indexes. Therefore the MANAGER_ID index contains fewer entries than there are rows in the table and therefore cannot be used for the above query. There are lots of other reasons why Oracle may not use your hint but the most common are syntax errors and referring to a table by its name instead of the alias used in the query. Jonathan Lewis has a fine collection of blog posts on the use of hints.

 

I hope this short answer helps you. Best of luck.

SQL CORNER
Sudoku Anyone? 

Oracle introducted recursive common table expressions in Oracle Database 11g Release 2. Oracle was late to the party because recursive common table expressions have been part of the SQL standard since 2003 but, to Oracle’s credit, it has provided the CONNECT BY clause for hierarchical queries from the very beginning. However, recursive common table expressions can be used for much more than hierarchical queries. Also note that Oracle uses the non-standard terms “subquery factoring” and “recursive subquery factoring” for “common table expressions” and “recursive common table expressions” respectively.

 

Here is a quick recap of common table expressions of the non-recursive kind. They are an alternative to inline views and make a complex SQL query much easier to read and maintain. Another advantage is that they only need to be evaluated once if they are used more than once within the query. A great example of using common table expressions to make complex SQL statements readable is the winning solution to the First International NoCOUG SQL Challenge by Alberto Dell’Era from Italy. A simpler example, Suppliers Who Supply All Parts, can be found in Beginning Oracle Database 11g Administration by Senior Staff Consultant Iggy Fernandez.

 

A recursive common table expression (recursive CTE) has “anchor members” and “recursive members.” The rows produced by the anchor members are processed by the recursive members. The recursive members produce other rows that are fed right back to them for further processing. Recursion stops only when the recursive members fail to produce additional rows. The explanation in the Oracle documentation is fairly cryptic but a good explanation can be found on the Microsoft Developer Network.

  1. Run the anchor member(s) creating the first invocation or base result set (T0).
  2. Run the recursive member(s) with Ti as an input and Ti+1 as an output.
  3. Repeat step 2 until an empty set is returned.
  4. Return the result set. This is a UNION ALL of T0 to Tn.

Here’s a simple example of a recursive common table expression: a number generator. The following example generates the consecutive numbers from 1 to 9. The anchor member generates the first row which is then processed by the recursive member. The recursive member uses the name of the recursive CTE as a placeholder for the output of the anchor member or a previous execution of the recursive CTE. In this example, each execution of the recursive member produces one more row. Recursion stops when nine records have been produced.

 

WITH

— The following number generator is a simple example of a recursive CTE. It
— produces the consecutive digits from 1 to 9.

Numbers(n) AS
(

— The “anchor member.” It contains exactly one row (N = 1).

SELECT 1 AS N
FROM dual

UNION ALL

— The “recursive member.” Notice that it references the name of the recursive
— CTE as a placeholder for the results of the anchor member or the previous
— execution of the recursive CTE. Each iteration of the recursive member
— produces the next value of N. Recursive execution stops when N = 9.

SELECT N + 1 AS N
FROM Numbers
WHERE N < 9

)

SELECT *
FROM Numbers;

 

The above example can be simply duplicated using the CONNECT BY clause as follows:

 

SELECT level AS N
FROM dual
CONNECT BY level <= 9;

 

Next consider a standard hierarchical query; an org-chart of managers and employees. First, here’s the old solution using the CONNECT BY clause; it is short and sweet.

 

SELECT
LPAD (‘ ‘, 4 * (LEVEL – 1)) || first_name || ‘ ‘ || last_name AS name
FROM employees
START WITH manager_id IS NULL
CONNECT BY manager_id = PRIOR employee_id;

 

The solution using recursive common table expressions is much more verbose. Note especially the SEARCH DEPTH FIRST clause; refer to the Oracle documentation for an explanation.

 

WITH

RCTE (employee_id, first_name, last_name, lvl) AS
(

SELECT
employee_id,
first_name,
last_name,
1 AS lvl
FROM
employees
WHERE manager_id IS NULL

UNION ALL

SELECT
e.employee_id,
e.first_name,
e.last_name,
lvl + 1 AS lvl
FROM
RCTE INNER JOIN employees e
ON (RCTE.employee_id = e.manager_id)
)
SEARCH DEPTH FIRST BY employee_id ASC SET seq#
SELECT LPAD (‘ ‘, 4 * (lvl – 1)) || first_name || ‘ ‘ || last_name AS name
FROM RCTE
ORDER BY seq#;

 

From the two examples above, it might appear that a recursive CTE is little more than a verbose way of specifying what could be more succinctly achieved with the CONNECT BY clause. However recursive common table expressions are more powerful than the CONNECT BY clause. For example, consider the following example from the TSQL Challenges team:

 

Given a list of products and a list of discount coupons, we needed to find the minimum price for all the products based on certain rules:

  1. A maximum of two coupons can be applied to the same product.
  2. The discounted price can not be less than 70% of the original price.
  3. The total amount of the discount can not exceed $30.

Syed Mehroz Alam has provided an elegant solution to the above problem using recursive common table expressions.

 

Our final exhibit is a Sudoku puzzle. It turns out that a Sudoku puzzle can be elegantly solved with recursive common table expressions. The solution was discovered by Anton Scheffer. The listing below is a heavily annotated version of Anton Scheffer’s solution with some cosmetic changes for better understandability.

 

— The following SQL statement solves a Sudoku puzzle that is provided in the
— form of a one-dimensional array of 81 digits. Note that a Sudoku puzzle is
— really a 9×9 square grid. Here is how the positions in the one-dimensional
— array correspond to positions in the 9×9 grid.

— +———+———+———+
— |  1  2  3|  4  5  6|  7  8  9|
— | 10 11 12| 13 14 15| 16 17 18|
— | 19 20 21| 22 23 24| 25 26 27|
— +———+———+———+
— | 28 29 30| 31 32 33| 34 35 36|
— | 37 38 39| 40 41 42| 43 44 45|
— | 46 47 48| 49 50 51| 52 53 54|
— +———+———+———+
— | 55 56 57| 58 59 60| 61 62 63|
— | 64 65 66| 67 68 69| 70 71 72|
— | 73 74 75| 76 77 78| 79 80 81|
— +———+———+———+

— A recursive common table expression (CTE) is used to solve the puzzle. The
— “anchor member” of the recursive CTE contains the unsolved Sudoku puzzle.
— The “recursive member” generates partially solved Sudokus. Each iteration
— of the recursive member completes one blank cell. Recursive execution stops
— when no more blank cells are left or if no value can be found for a blank
— cell (meaning that the Sudoku has no solution). All solutions are produced
— if the puzzle has multiple solutions.

— Consider the following Sudoku puzzle: (All but the last 9 cells are filled.)

— 534678912672195348198342567859761423426853791713924856961537284287419635

— Here is the output produced for the above puzzle: (The output has been
— condensed in order to accomodate it within the available space.)

— Partially Solved Sudoku
— —————————————————————————-
— 534678912672195348198342567859 … 4856961537284287419635
— 534678912672195348198342567859 … 48569615372842874196353
— 534678912672195348198342567859 … 485696153728428741963534
— 534678912672195348198342567859 … 4856961537284287419635345
— 534678912672195348198342567859 … 48569615372842874196353452
— 534678912672195348198342567859 … 485696153728428741963534528
— 534678912672195348198342567859 … 4856961537284287419635345286
— 534678912672195348198342567859 … 48569615372842874196353452861
— 534678912672195348198342567859 … 485696153728428741963534528617
— 534678912672195348198342567859 … 4856961537284287419635345286179

SET sqlblanklines on
SET linesize 132
SET pagesize 66

WITH

— The following number generator is itself an example of a recursive CTE. It
— produces the consecutive digits from 1 to 9.

Numbers(n) AS
(

— The “anchor member.” It contains exactly one row (N = 1).

SELECT 1 AS N
FROM dual

UNION ALL

— The “recursive member.” Each iteration of the recursive member produces
— the next value of N. Recursive execution stops when N = 9.

SELECT N + 1 AS N
FROM Numbers
WHERE N < 9

),

RecursiveCTE(PartiallySolvedSudoku, BlankCell) AS
(
— The “anchor member” of the recursive CTE. It contains exactly one row: the
— unsolved Sudoku puzzle.

SELECT
cast(rpad(‘&&SudokuPuzzle’, 81) AS VARCHAR2(81)) AS SudokuPuzzle,
instr(rpad(‘&&SudokuPuzzle’, 81), ‘ ‘, 1) AS FirstBlankCell
FROM dual

UNION ALL

— The “recursive member” of the recursive CTE. It generates intermediate
— solutions by providing values for the first blank cell in the intermediate
— solutions produced by the previous iteration. Recursive execution stops
— when no more blank cells are left or if none of the intermediate solutions
— generated by the previous iteration can be improved (meaning that the
— Sudoku puzzle has no solution). All solutions are generated if the puzzle
— has multiple solutions.

SELECT

— Construct an intermediate solution by completing one blank cell.

cast(
substr(RecursiveCTE.PartiallySolvedSudoku, 1, BlankCell – 1)
|| to_char(Candidates.N)
|| substr(RecursiveCTE.PartiallySolvedSudoku, BlankCell + 1)
AS VARCHAR2(81)
) AS PartiallySolvedSudoku,

— Locate the next blank cell, if any.

instr(
RecursiveCTE.PartiallySolvedSudoku,
‘ ‘,
RecursiveCTE.BlankCell + 1
) AS NextBlankCell

FROM

— The intermediate solutions from the previous iteration.
RecursiveCTE,

— Consider all 9 candidate values from the Numbers table.
Numbers Candidates

WHERE NOT EXISTS

— Filter out candidate values that have already been used in the same row,
— the same column, or the same 3×3 grid as the blank cell. Note that a Sudoku
— puzzle is really a 9×9 grid but we are using a one-dimensional array of 81
— cells instead. Recursive execution will stop if none of the intermediate
— solutions generated by the previous iteration can be improved.

— The position within the one-dimensional array of the first cell in the same
— row of the 9×9 grid as the blank cell is trunc((BlankCell-1)/9)*9 + 1. The
— position of the Nth cell is trunc((BlankCell-1)/9)*9 + 1 + (N-1). For
— example, if BlankCell = 41, then the positions of the cells of interest are
— 37, 38, 39, 40, 41, 42, 43, 44, and 45.

— The position of the first cell in the same column of the 9×9 grid as the
— blank cell is mod(BlankCell-1,9) + 1. The position of the Nth cell is
— mod(BlankCell-1,9) + 1 + 9*(N-1). For example, if BlankCell = 41, then the
— positions of the cells of interest are 5, 14, 23, 32, 41, 50, 59, 68, and
— 77.

— The position of the first cell in the same 3×3 grid as the blank cell is
— trunc((BlankCell-1)/27)*27 + mod(trunc((BlankCell-1)/3),3)*3 + 1. The
— position of the Nth cell in the same 3×3 grid is trunc((BlankCell-1)/27)*27
— + mod(trunc((BlankCell-1)/3),3)*3 + 1 + (N-1) + trunc((N-1)/3)*6. For
— example, if BlankCell = 41, then the positions of the cells of interest are
— 31, 32, 33, 40, 41, 42, 49, 50, 51

(
SELECT N FROM Numbers

WHERE to_char(Candidates.N) IN
(
— Check the contents of the row containing the blank cell

substr
(
RecursiveCTE.PartiallySolvedSudoku,
trunc((BlankCell-1)/9)*9 + 1
+ (N-1),
1
),

— Check the contents of the column containing the blank cell

substr
(
RecursiveCTE.PartiallySolvedSudoku,
mod(BlankCell-1,9) + 1
+ 9*(N-1),
1
),

— Check the contents of the 3×3 grid containing the blank cell

substr
(
RecursiveCTE.PartiallySolvedSudoku,
trunc((BlankCell-1)/27)*27 + mod(trunc((BlankCell-1)/3),3)*3 + 1
+ (N-1) + trunc((N-1)/3)*6,
1
)
)
)

— Stop processing when no more blank cells are left.

AND BlankCell > 0

)

SELECT PartiallySolvedSudoku “Partially Solved Sudoku”
FROM RecursiveCTE;

 

P.S. The recursive examples in this article will only work in Oracle Database 11g Release 2. Anton Scheffer has two solutions which work with Oracle Database 10g Release 2: a solution using the MODEL clause and a solution using collections.

BOOK BEAT
For the Pointy Haired Manager In Your Life

 

Does your project manager know the color of an Oracle database? If not, here’s the perfect book for him or her: Introduction to Oracle: Basic Skills for Any Oracle User by Bert Scalzo. As it says in the product description:

 

“Are you new to Oracle databases? Have you just been assigned your first Oracle task or project? Maybe you’re already database literate – but accustomed to working with another database such as Microsoft SQL Server, IBM’s DB2 or MySQL. No matter what the case – if you must hit the ground running with Oracle, then this book is for you. From non-technical or more business centric end users to the even the most technically oriented information systems professionals, this book can serve as your sole source for an introduction to and ongoing reference for successfully working with Oracle databases. It covers every aspect required for getting you quickly indoctrinated and very productive, including Oracle terminology, Windows PC configuration issues, Oracle client configuration issues, Database connection methods, and much more. Plus this book offers a painless yet thorough introduction to and explanation of Structured Query Language or SQL. Finally, it shows clear examples just how to access and work with your Oracle database using popular tools such as Microsoft Excel, SQL*Plus, SQL*Developer, TOAD and many others.”

 

Soon you and your project manager can be talking the same language!

 

Call Database Specialists when you need remote DBA services or onsite support for your mission-critical Oracle database systems. Arrange a free consultation with a senior Database Specialists team member to find out how we can help increase your uptime, improve performance, minimize risk, and reduce costs. Visit our website for no-cost resources, white papers, conference presentations and handy scripts.

Sincerely,
David Wolff
CEO, Database Specialists, Inc.

dwolff@dbspecialists.com

(415) 344-0500 x48

Leave a Reply

Your email address will not be published. Required fields are marked *