Specifying SEARCH consideration

Using a queuing (First In First Out) mechanism to track 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 retrieval is an implementation distinction, however, and not a guarantee.

Applications might want to guarantee how the data is retrieved. Some applications might 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, name the recursive join value, identify a set sequence column, and provide the sequence column in an outer ORDER BY clause. The results are output in depth or breadth first order. Note this ordering is ultimately a relationship sort and not a value-based sort.

Here is the preceding example output in depth first 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. With 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. With DEPTH FIRST, the query engine needs to represent the entire ancestry of join values leading up to the current row and put that information in a queue entry. Also, because these sort values are not coming from an external data source, the sort implementation is always a temporary sorted list (no indexes possible).

Do not use the SEARCH option if you do not need your data materialized in a depth or breadth first manner. There is additional CPU and memory overhead to manage the sequencing information.