EXPLAIN EXTENDED

Continuing the series:

What is better to store hierarchical data: nested sets model or adjacency list (parent-child) model?

For detailed explanations of the terms, see the first article in the series:

• Adjacency list vs. nested sets: PostgreSQL

Today is Oracle time.

Adjacent sets require recursion, and Oracle has a native way to implement recursion in SQL statements. To do this it uses a special clause, CONNECT BY.

Unlike other systems, Oracle always supported recursion in SQL statements since version 2 (this is the name the first version of Oracle was released under).

This was done because by that time there already were several hierarchical databases on the market which are quite good for storing hierarchical data. If not for this clause, transition from a hierarchical DBMS to the relational DBMS would be too hard.

Oracle's way to query self-relations is somewhat different from recursive CTE's that other systems use:

• Recursive CTEs can use an arbitrary set in recursive steps. The recursion base and recursion stack are not visible in further steps. The recursive operation is a set operation (usually a JOIN) on the recursion parameter (a set) and the result of the previous operation:

  

• CONNECT BY queries can only use the value of a single row in recursive steps.

  The recursion base and recursion stack are visible, the values outside the recursion stack are not.

  The recursive operation is a set operation on each row of the current row and the base rowset.

  Unlike recursive CTE, CONNECT BY operates row-wise, that is each row of the result spans its own recursion branch with its own stack:

  

The main difference it that the CONNECT BY operation cannot produce anything that was not in the original rowset, while a recursive CTE can.

However, CONNECT BY has numerous benefits too: it's very fast, allows to track the hierarchy path easily (using a built-in funtion named SYS_CONNECT_BY_PATH) and implicitly sorts the recordset in tree order (with additional clause ORDER SIBLINGS BY to sort the siblings).

This method, of course, allows traversing adjacency lists easily.

To compare efficiency of adjacency lists and that of nested sets, let's create a sample table:

Table creation details

 CREATE TABLE t_hierarchy (id NOT NULL, parent NOT NULL, lft NOT NULL, rgt NOT NULL, data NOT NULL, stuffing NOT NULL) AS WITH nums AS ( SELECT level AS num, 100 AS value FROM dual CONNECT BY level <= 5 ), digits AS ( SELECT SYS_CONNECT_BY_PATH(num, '/') AS digit, level AS len FROM nums CONNECT BY level <= 9 ) SELECT id, FLOOR((id - 1) / 5), lft, lft + FLOOR(2929687 / POWER(5, len)) - 1, CAST('Value ' || id AS VARCHAR2(100)), CAST(RPAD('*', 100, '*') AS VARCHAR2(100)) FROM ( SELECT digit, len, ( SELECT SUM(SUBSTR(digit, level * 2, 1) * POWER(5, len - level)) FROM dual CONNECT BY level <= len ) AS id, ( SELECT SUM((SUBSTR(digit, level * 2, 1) - 1) * FLOOR(2929687 / POWER(5, level)) + 1) FROM dual CONNECT BY level <= len ) AS lft FROM digits ) / ALTER TABLE t_hierarchy ADD CONSTRAINT pk_hierarchy_id PRIMARY KEY (id) / CREATE INDEX ix_hierarchy_parent ON t_hierarchy (parent) / CREATE INDEX ix_hierarchy_lft ON t_hierarchy (lft) / CREATE INDEX ix_hierarchy_rgt ON t_hierarchy (rgt) / 

The table contains both adjacency list data and nested sets data, with 8 levels of nesting, 5 children of each parent node and 2,441,405 records.

As in the previous articles, we'll test performance of the three most used queries:

• Find all descendants of a given node
• Find all ancestors of a given node
• Find all descendants of a given node up to a certain depth

All descendants

Nested sets

 SELECT SUM(LENGTH(hc.stuffing)) FROM t_hierarchy hp JOIN t_hierarchy hc ON hc.lft BETWEEN hp.lft AND hp.rgt WHERE hp.id = 42 

View query details

SELECT STATEMENT SORT AGGREGATE NESTED LOOPS TABLE ACCESS BY INDEX ROWID, 20090928_nested.T_HIERARCHY INDEX UNIQUE SCAN, 20090928_nested.PK_HIERARCHY_ID TABLE ACCESS BY INDEX ROWID, 20090928_nested.T_HIERARCHY INDEX RANGE SCAN, 20090928_nested.IX_HIERARCHY_LFT 

This is super fast, faster than in any system before that: only 10 ms. The plan is quite predictable: a UNIQUE scan to find the parent record and a range scan to find all children.

Adjacency list

 SELECT SUM(LENGTH(stuffing)) FROM t_hierarchy START WITH id = 42 CONNECT BY parent = PRIOR id 

View query details

SELECT STATEMENT SORT AGGREGATE CONNECT BY WITH FILTERING TABLE ACCESS BY INDEX ROWID, 20090928_nested.T_HIERARCHY INDEX UNIQUE SCAN, 20090928_nested.PK_HIERARCHY_ID NESTED LOOPS BUFFER SORT CONNECT BY PUMP TABLE ACCESS BY INDEX ROWID, 20090928_nested.T_HIERARCHY INDEX RANGE SCAN, 20090928_nested.IX_HIERARCHY_PARENT TABLE ACCESS FULL, 20090928_nested.T_HIERARCHY 

This is quite fast too: 140 ms. The plan loops over the parent ranges for each id.

Note the TABLE ACCESS FULL in the end of the plan. Oracle reserves a right to do a FULL SCAN instead of a RANGE SCAN if it considers a certain parent range too large to use the index. However, this is recursion, not a single operation, and it's impossible to tell in advance which id values will be returned on each recursion step. That's why Oracle shows both methods, just in case, and chooses the most efficient method in runtime.

In our table, at most 5 rows share a parent (of more then 2 million), so it's very unlikely this plan branch will be ever chosen.

Find all ancestors

Nested sets

 SELECT hp.id, hp.parent, hp.lft, hp.rgt, hp.data FROM t_hierarchy hc JOIN t_hierarchy hp ON hc.lft BETWEEN hp.lft AND hp.rgt WHERE hc.id = 1000000 ORDER BY hp.lft 

View query details

SELECT STATEMENT NESTED LOOPS TABLE ACCESS BY INDEX ROWID, 20090928_nested.T_HIERARCHY INDEX UNIQUE SCAN, 20090928_nested.PK_HIERARCHY_ID TABLE ACCESS BY INDEX ROWID, 20090928_nested.T_HIERARCHY INDEX RANGE SCAN, 20090928_nested.IX_HIERARCHY_LFT 

The plan used is exactly the same as for the query to choose all descendants.

However, the range on lft is too broad and the query works for more than 3 seconds.

Adjacency list

 SELECT id, parent, lft, rgt, data, level FROM t_hierarchy START WITH id = 1000000 CONNECT BY id = PRIOR parent ORDER BY level DESC 

View query details

SELECT STATEMENT SORT ORDER BY CONNECT BY WITH FILTERING TABLE ACCESS BY INDEX ROWID, 20090928_nested.T_HIERARCHY INDEX UNIQUE SCAN, 20090928_nested.PK_HIERARCHY_ID NESTED LOOPS BUFFER SORT CONNECT BY PUMP TABLE ACCESS BY INDEX ROWID, 20090928_nested.T_HIERARCHY INDEX UNIQUE SCAN, 20090928_nested.PK_HIERARCHY_ID TABLE ACCESS FULL, 20090928_nested.T_HIERARCHY 

This query completes in less than 1 ms, which is instant.

Note that unlike recursive CTE's, Oracle supplies a built-in preudocolumn, level, that returns the current recursion level. This comes handy in cases like this.

Descendants up to a given level

Nested sets

 SELECT hc.id, hc.parent, hc.lft, hc.rgt, hc.data FROM t_hierarchy hp JOIN t_hierarchy hc ON hc.lft BETWEEN hp.lft AND hp.rgt WHERE hp.id = ? AND ( SELECT COUNT(*) FROM t_hierarchy hn WHERE hc.lft BETWEEN hn.lft AND hn.rgt AND hn.lft BETWEEN hp.lft AND hp.rgt ) <= 3 

View the query for node 42

 SELECT hc.id, hc.parent, hc.lft, hc.rgt, hc.data FROM t_hierarchy hp JOIN t_hierarchy hc ON hc.lft BETWEEN hp.lft AND hp.rgt WHERE hp.id = 42 AND ( SELECT COUNT(*) FROM t_hierarchy hn WHERE hc.lft BETWEEN hn.lft AND hn.rgt AND hn.lft BETWEEN hp.lft AND hp.rgt ) <= 3 

SELECT STATEMENT NESTED LOOPS TABLE ACCESS BY INDEX ROWID, 20090928_nested.T_HIERARCHY INDEX UNIQUE SCAN, 20090928_nested.PK_HIERARCHY_ID TABLE ACCESS BY INDEX ROWID, 20090928_nested.T_HIERARCHY INDEX RANGE SCAN, 20090928_nested.IX_HIERARCHY_LFT SORT AGGREGATE FILTER TABLE ACCESS BY INDEX ROWID, 20090928_nested.T_HIERARCHY INDEX RANGE SCAN, 20090928_nested.IX_HIERARCHY_LFT 

View the query for node 31,415

 SELECT hc.id, hc.parent, hc.lft, hc.rgt, hc.data FROM t_hierarchy hp JOIN t_hierarchy hc ON hc.lft BETWEEN hp.lft AND hp.rgt WHERE hp.id = 31415 AND ( SELECT COUNT(*) FROM t_hierarchy hn WHERE hc.lft BETWEEN hn.lft AND hn.rgt AND hn.lft BETWEEN hp.lft AND hp.rgt ) <= 3 

SELECT STATEMENT NESTED LOOPS TABLE ACCESS BY INDEX ROWID, 20090928_nested.T_HIERARCHY INDEX UNIQUE SCAN, 20090928_nested.PK_HIERARCHY_ID TABLE ACCESS BY INDEX ROWID, 20090928_nested.T_HIERARCHY INDEX RANGE SCAN, 20090928_nested.IX_HIERARCHY_LFT SORT AGGREGATE FILTER TABLE ACCESS BY INDEX ROWID, 20090928_nested.T_HIERARCHY INDEX RANGE SCAN, 20090928_nested.IX_HIERARCHY_LFT 

As in other systems, performance heavily depends on how many descendants does the record have.

For the node 42 which is close to the root node and has lots of descendants, the query runs for 122 seconds. For the node 31,415, the query takes 1.5 ms (next to instant).

Adjacency list

 SELECT id, parent, lft, rgt, data FROM t_hierarchy START WITH id = ? CONNECT BY parent = PRIOR id AND level <= 3 

Limiting the recursion depth query is very simple in Oracle: we just add the additional condition to CONNECT BY clause constraining the limit.

View the query for node 42

 SELECT id, parent, lft, rgt, data FROM t_hierarchy START WITH id = 42 CONNECT BY parent = PRIOR id AND level <= 3 

SELECT STATEMENT CONNECT BY WITH FILTERING TABLE ACCESS BY INDEX ROWID, 20090928_nested.T_HIERARCHY INDEX UNIQUE SCAN, 20090928_nested.PK_HIERARCHY_ID NESTED LOOPS BUFFER SORT CONNECT BY PUMP FILTER TABLE ACCESS BY INDEX ROWID, 20090928_nested.T_HIERARCHY INDEX RANGE SCAN, 20090928_nested.IX_HIERARCHY_PARENT TABLE ACCESS FULL, 20090928_nested.T_HIERARCHY 

View the query for node 31,415

 SELECT id, parent, lft, rgt, data FROM t_hierarchy START WITH id = 31415 CONNECT BY parent = PRIOR id AND level <= 3 

SELECT STATEMENT CONNECT BY WITH FILTERING TABLE ACCESS BY INDEX ROWID, 20090928_nested.T_HIERARCHY INDEX UNIQUE SCAN, 20090928_nested.PK_HIERARCHY_ID NESTED LOOPS BUFFER SORT CONNECT BY PUMP FILTER TABLE ACCESS BY INDEX ROWID, 20090928_nested.T_HIERARCHY INDEX RANGE SCAN, 20090928_nested.IX_HIERARCHY_PARENT TABLE ACCESS FULL, 20090928_nested.T_HIERARCHY 

Both queries complete in 1 ms, that is instant.

Summary

Oracle implements a special clause, CONNECT BY, that makes traversing adjacency lists in general and parent-child relationships in particular very easy, since this is exactly what this clause was intended for.

Except for finding all descendants of a single node (without finding out or limiting the depth), nested sets model is less efficient in Oracle than adjacency lists.

Adjacency lists are not only more efficient but the queries using them are more elegant and easy to maintain due to the native support.

That's why adjacency list model should be used instead of nested sets model in Oracle too, as well as in SQL Server and PostgreSQL 8.4.