Recursive query example

A recursive query is one that is defined by a Union All with an initialization fullselect that seeds the recursion. The iterative fullselect contains a direct reference to itself in the FROM clause.

There are additional restrictions as to what can be specified in the definition of a recursive query. Those restrictions can be found in SQL Programming topic.

Functions like grouping, aggregation, or distinct require a materialization of all the qualifying records before performing the function. These functions cannot be allowed within the iterative fullselect itself. The functions must be placed in the main query, allowing the recursion to complete.

The following is an example of a recursive query over a table called flights, that contains information about departure and arrival cities. The query returns all the flight destinations available by recursion from the two specified cities (New York and Chicago). It also returns the number of connections and total cost to arrive at that final destination.

This example uses the recursion process to also accumulate information like the running cost and number of connections. Four values are put in the queue entry. These values are:

  • The originating departure city (either Chicago or New York) because it remains fixed from the start of the recursion
  • The arrival city which is used for subsequent joins
  • The incrementing connection count
  • The accumulating total cost to reach each destination

Typically the data needed for the queue entry is less than the full record (sometimes much less) although that is not the case for this example.

CREATE TABLE flights 
	( 
		departure CHAR (10) NOT NULL WITH DEFAULT,   
		arrival CHAR (10) NOT NULL WITH DEFAULT,  
		carrier CHAR (15) NOT NULL WITH DEFAULT, 
		flight_num CHAR (5) NOT NULL WITH DEFAULT,   
		ticket INT NOT NULL WITH DEFAULT)

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
  ) 
SELECT DISTINCT departure, arrival, connects, cost 
FROM destinations

The following is the initialization fullselect of the preceding query. It seeds the rows that start the recursion process. It provides the initial destinations (arrival cities) that are a direct flight from Chicago or New York.

SELECT  f.departure,f.arrival, 0, ticket 
FROM flights f 
WHERE f.departure='Chicago' OR
      	f.departure='New York'

The following is the iterative fullselect of the preceding query. It contains a single reference in the FROM clause to the destination recursive common table expression. It also sources further recursive joins to the same flights table. The arrival values of the parent row (initially direct flights from New York or Chicago) are joined with the departure value of the subsequent child rows. It is important to identify the correct parent/child relationship on the recursive join predicate or infinite recursion can occur. Other local predicates can also be used to limit the recursion. For example, for a limit of at most 3 connecting flights, a local predicate using the accumulating connection count, r.connects<=3, can be specified. 

SELECT
  r.departure, b.arrival, r.connects + 1 ,
  r.cost + b.ticket 
FROM  destinations r, flights b 
WHERE r.arrival=b.departure

The main query is the query that references the recursive common table expression or view. It is in the main query where requests like grouping, ordering, and distinct are specified. 

SELECT DISTINCT departure, arrival, connects, cost 
FROM destinations

Implementation considerations

To implement a source for the recursion, a new temporary data object is provided called a queue. As rows meet the requirements of either the initialization fullselect or the iterative fullselect, they are pulled up through the union all. Values necessary to feed the continuing recursion process are captured and placed in an entry on the queue: an enqueue operation.

At query runtime, the queue data source then takes the place of the recursive reference in the common table expression or view. The iterative fullselect processing ends when the queue is exhausted of entries or a fetch N rows limitation has been met. The recursive queue feeds the recursion process and holds transient data. The join between dequeuing of these queue entries and the rest of the fullselect tables is always a constrained join, with the queue on the left.

Visual Explain diagram