Specifying SEARCH consideration

 

Certain applications dealing with hierarchical, recursive data, may have a requirement in how data is processed: by depth or by breadth.

Using a queuing (First In First Out) mechanism to keep track of the recursive join key values implies the results are retrieved in breadth first order. Breadth first means retrieving all the direct children of a parent row before retrieving any of the grandchildren of that same row. This is an implementation distinction, however, and not a guarantee. Applications may want to guarantee how the data is retrieved. Some applications may want to retrieve the hierarchical data in depth first order. Depth first means that all the descendents of each immediate child row are retrieved before the descendents of the next child are retrieved.

The SQL architecture allows for the guaranteed specification of how the application retrieves the resulting data by the use of the SEARCH DEPTH FIRST or BREADTH FIRST keyword. When this option is specified along with naming the recursive join value, identifying a set sequence column and providing the sequence column in an outer ORDER BY clause, the results will be output in depth or breadth first order. Note this is ultimately a relationship sort and not a value based sort.

Here is the example above output in depth order.

WITH destinations (departure, arrival, connects, cost ) AS
(
   SELECT f.departure, f.arrival, 0 , ticket  
				FROM flights f  
				WHERE f.departure='Chicago' OR f.departure='New York'
   UNION ALL 
    SELECT
			r.departure,b.arrival, r.connects+1 ,
			r.cost+b.ticket 
			FROM  destinations r, flights b 
			WHERE r.arrival=b.departure) 


SEARCH DEPTH FIRST BY arrival SET depth_sequence 

	SELECT * 
		FROM destinations 
		ORDER BY depth_sequence

If the ORDER BY clause is not specified in the main query, the sequencing option is ignored. To facilitate the correct sort there is additional information put on the queue entry during recursion. In the case of BREADTH FIRST, it is the recursion level number and the immediate ancestor join value, so sibling rows can be sorted together. A depth first search is a little more data intensive. In the case of DEPTH FIRST, the query engine needs to represent the entire ancestry of join values leading up to the current row and puts that information in a queue entry. Also, because these sort values are not coming from a external data source, the implementation for the sort will always be a temporary sorted list (no indexes possible).

Do not use the SEARCH option if you do not have a requirement that your data be materialized in a depth or breadth first manner as there is additional CPU and memory overhead to manage the sequencing information.

 

Parent topic:

Recursive query optimization