Finding Circular References in Postgres

Circular references are rarely a good thing, especially in software. I was recently tasked with preventing circular references in a system where users are tied to other users as managers. We were running into an endless loop where user1 would have user2 as their manager, user2 would have user3 as their manager, and user3 would have user1 as their manager. This means when you try to traverse up the tree, you get stuck in an endless loop. The first step to preventing this from happening was to find all existing circular references in the database.

The Problem

Given a table of users with the columns of id, and manager_id, we wish to find all circular references. We want the final output here to be a useful list of circular references. I want to do this using SQL only.

Setting up some sample data

Lets generate a table with some random manager_ids. We can assume based on the numbers involved that there will be at least some circular references. If there aren't we can always jsut run it again!

CREATE TABLE users AS SELECT id, manager_id 
 from 
(SELECT generate_series (1,100) as id,(random()\*100)::int AS manager_id) users

This gives us a table of 100 users, with manager_ids ranging from 1 to 100.

Recursive Queries

To find the circular references in this table, we are going to use a Postgres feature that lets you create a recursive query. Basically the Recursive query is a special Common Table Expression query that allows the query to refer to its own input. A simple example of this is given in the Postgres documentation

WITH RECURSIVE t(n) AS (
     VALUES (1)
   UNION ALL
    SELECT n+1 FROM t WHERE n < 100
 )
 SELECT sum(n) FROM t;

This sums the numbers from 1 to 100 by means of a recursive query. The queries generally look the same, with a union and a condition in the second clause to prevent an endless loop. Here is what the query will look like for us.


WITH RECURSIVE circular_managers(id, manager_id, depth, path, cycle) AS (
	SELECT u.id, u.manager_id, 1,
		ARRAY[u.id],
		false
	FROM users u
	UNION ALL
	SELECT u.id, u.manager_id, cm.depth + 1,
		path || u.id,
		u.id = ANY(path)
	FROM users u, circular_managers cm
	WHERE u.id = cm.manager_id AND NOT cycle
	)

select * from circular_managers where cycle

This gives a big list of results, each of which contain a circular reference.

 id | manager_id | depth |                                    path                                     | cycle 
----+------------+-------+-----------------------------------------------------------------------------+-------
 30 |         30 |     2 | {30,30}                                                                     | t
 30 |         30 |     3 | {81,30,30}                                                                  | t
 30 |         30 |     3 | {34,30,30}                                                                  | t
 85 |         87 |     3 | {85,87,85}                                                                  | t
 87 |         85 |     3 | {87,85,87}                                                                  | t
 30 |         30 |     4 | {53,81,30,30}                                                               | t
 30 |         30 |     4 | {40,81,30,30}                                                               | t
 87 |         85 |     4 | {38,87,85,87}                                                               | t
 30 |         30 |     5 | {68,53,81,30,30}                                                            | t
 33 |         59 |     7 | {33,59,86,91,44,93,33}                                                      | t
 44 |         93 |     7 | {44,93,33,59,86,91,44}                                                      | t
 59 |         86 |     7 | {59,86,91,44,93,33,59}                                                      | t
 86 |         91 |     7 | {86,91,44,93,33,59,86}                                                      | t
 91 |         44 |     7 | {91,44,93,33,59,86,91}                                                      | t
 93 |         33 |     7 | {93,33,59,86,91,44,93}                                                      | t
 33 |         59 |     8 | {71,33,59,86,91,44,93,33}                                                   | t
 33 |         59 |     8 | {26,33,59,86,91,44,93,33}                                                   | t
 59 |         86 |     8 | {72,59,86,91,44,93,33,59}                                                   | t
 86 |         91 |     8 | {19,86,91,44,93,33,59,86}                                                   | t
 86 |         91 |     8 | {60,86,91,44,93,33,59,86}                                                   | t
 91 |         44 |     8 | {61,91,44,93,33,59,86,91}                                                   | t
 91 |         44 |     8 | {65,91,44,93,33,59,86,91}                                                   | t
 93 |         33 |     8 | {95,93,33,59,86,91,44,93}                                                   | t
 33 |         59 |     9 | {90,71,33,59,86,91,44,93,33}                                                | t
 59 |         86 |     9 | {36,72,59,86,91,44,93,33,59}                                                | t
 86 |         91 |     9 | {73,60,86,91,44,93,33,59,86}                                                | t
 86 |         91 |     9 | {9,19,86,91,44,93,33,59,86}                                                 | t
 91 |         44 |     9 | {62,61,91,44,93,33,59,86,91}                                                | t
 91 |         44 |     9 | {37,61,91,44,93,33,59,86,91}                                                | t
 91 |         44 |     9 | {58,61,91,44,93,33,59,86,91}                                                | t
 93 |         33 |     9 | {4,95,93,33,59,86,91,44,93}                                                 | t
 86 |         91 |    10 | {35,73,60,86,91,44,93,33,59,86}                                             | t
 86 |         91 |    10 | {55,73,60,86,91,44,93,33,59,86}                                             | t
 91 |         44 |    10 | {88,58,61,91,44,93,33,59,86,91}                                             | t
 91 |         44 |    10 | {49,58,61,91,44,93,33,59,86,91}                                             | t
 91 |         44 |    10 | {66,37,61,91,44,93,33,59,86,91}                                             | t
 91 |         44 |    10 | {54,37,61,91,44,93,33,59,86,91}                                             | t
 91 |         44 |    10 | {1,62,61,91,44,93,33,59,86,91}                                              | t
 91 |         44 |    10 | {51,58,61,91,44,93,33,59,86,91}                                             | t
 93 |         33 |    10 | {24,4,95,93,33,59,86,91,44,93}                                              | t
 86 |         91 |    11 | {3,55,73,60,86,91,44,93,33,59,86}                                           | t
 86 |         91 |    11 | {41,35,73,60,86,91,44,93,33,59,86}                                          | t
 91 |         44 |    11 | {27,88,58,61,91,44,93,33,59,86,91}                                          | t
 91 |         44 |    11 | {22,49,58,61,91,44,93,33,59,86,91}                                          | t
 91 |         44 |    11 | {16,54,37,61,91,44,93,33,59,86,91}                                          | t
 91 |         44 |    11 | {42,54,37,61,91,44,93,33,59,86,91}                                          | t
 91 |         44 |    11 | {80,49,58,61,91,44,93,33,59,86,91}                                          | t
 93 |         33 |    11 | {96,24,4,95,93,33,59,86,91,44,93}                                           | t
 93 |         33 |    11 | {69,24,4,95,93,33,59,86,91,44,93}                                           | t
 91 |         44 |    12 | {29,16,54,37,61,91,44,93,33,59,86,91}                                       | t
 91 |         44 |    12 | {43,80,49,58,61,91,44,93,33,59,86,91}                                       | t
 91 |         44 |    12 | {67,22,49,58,61,91,44,93,33,59,86,91}                                       | t
 93 |         33 |    12 | {100,69,24,4,95,93,33,59,86,91,44,93}                                       | t
 93 |         33 |    12 | {52,69,24,4,95,93,33,59,86,91,44,93}                                        | t
 93 |         33 |    12 | {48,69,24,4,95,93,33,59,86,91,44,93}                                        | t
 91 |         44 |    13 | {92,43,80,49,58,61,91,44,93,33,59,86,91}                                    | t
 93 |         33 |    13 | {10,48,69,24,4,95,93,33,59,86,91,44,93}                                     | t
 93 |         33 |    13 | {75,52,69,24,4,95,93,33,59,86,91,44,93}                                     | t
 93 |         33 |    13 | {89,52,69,24,4,95,93,33,59,86,91,44,93}                                     | t
 91 |         44 |    14 | {79,92,43,80,49,58,61,91,44,93,33,59,86,91}                                 | t
 91 |         44 |    14 | {77,92,43,80,49,58,61,91,44,93,33,59,86,91}                                 | t
 93 |         33 |    14 | {20,89,52,69,24,4,95,93,33,59,86,91,44,93}                                  | t
 93 |         33 |    14 | {14,10,48,69,24,4,95,93,33,59,86,91,44,93}                                  | t
 93 |         33 |    14 | {31,75,52,69,24,4,95,93,33,59,86,91,44,93}                                  | t
 91 |         44 |    15 | {46,79,92,43,80,49,58,61,91,44,93,33,59,86,91}                              | t
 91 |         44 |    15 | {23,79,92,43,80,49,58,61,91,44,93,33,59,86,91}                              | t
 91 |         44 |    15 | {99,77,92,43,80,49,58,61,91,44,93,33,59,86,91}                              | t
 91 |         44 |    15 | {18,79,92,43,80,49,58,61,91,44,93,33,59,86,91}                              | t
 91 |         44 |    16 | {15,99,77,92,43,80,49,58,61,91,44,93,33,59,86,91}                           | t
 91 |         44 |    16 | {76,23,79,92,43,80,49,58,61,91,44,93,33,59,86,91}                           | t
 91 |         44 |    16 | {83,18,79,92,43,80,49,58,61,91,44,93,33,59,86,91}                           | t
 91 |         44 |    16 | {47,46,79,92,43,80,49,58,61,91,44,93,33,59,86,91}                           | t
 91 |         44 |    16 | {12,99,77,92,43,80,49,58,61,91,44,93,33,59,86,91}                           | t
 91 |         44 |    17 | {8,12,99,77,92,43,80,49,58,61,91,44,93,33,59,86,91}                         | t
 91 |         44 |    17 | {7,15,99,77,92,43,80,49,58,61,91,44,93,33,59,86,91}                         | t
 91 |         44 |    17 | {28,12,99,77,92,43,80,49,58,61,91,44,93,33,59,86,91}                        | t
 91 |         44 |    17 | {98,15,99,77,92,43,80,49,58,61,91,44,93,33,59,86,91}                        | t
 91 |         44 |    18 | {2,28,12,99,77,92,43,80,49,58,61,91,44,93,33,59,86,91}                      | t
 91 |         44 |    18 | {94,8,12,99,77,92,43,80,49,58,61,91,44,93,33,59,86,91}                      | t
 91 |         44 |    18 | {78,98,15,99,77,92,43,80,49,58,61,91,44,93,33,59,86,91}                     | t
 91 |         44 |    19 | {25,94,8,12,99,77,92,43,80,49,58,61,91,44,93,33,59,86,91}                   | t
 91 |         44 |    19 | {32,78,98,15,99,77,92,43,80,49,58,61,91,44,93,33,59,86,91}                  | t
 91 |         44 |    20 | {50,32,78,98,15,99,77,92,43,80,49,58,61,91,44,93,33,59,86,91}               | t
 91 |         44 |    20 | {6,32,78,98,15,99,77,92,43,80,49,58,61,91,44,93,33,59,86,91}                | t
 91 |         44 |    21 | {70,6,32,78,98,15,99,77,92,43,80,49,58,61,91,44,93,33,59,86,91}             | t
 91 |         44 |    21 | {64,50,32,78,98,15,99,77,92,43,80,49,58,61,91,44,93,33,59,86,91}            | t
 91 |         44 |    21 | {82,50,32,78,98,15,99,77,92,43,80,49,58,61,91,44,93,33,59,86,91}            | t
 91 |         44 |    22 | {45,64,50,32,78,98,15,99,77,92,43,80,49,58,61,91,44,93,33,59,86,91}         | t
 91 |         44 |    22 | {11,70,6,32,78,98,15,99,77,92,43,80,49,58,61,91,44,93,33,59,86,91}          | t
 91 |         44 |    22 | {63,64,50,32,78,98,15,99,77,92,43,80,49,58,61,91,44,93,33,59,86,91}         | t
 91 |         44 |    22 | {57,70,6,32,78,98,15,99,77,92,43,80,49,58,61,91,44,93,33,59,86,91}          | t
 91 |         44 |    23 | {84,11,70,6,32,78,98,15,99,77,92,43,80,49,58,61,91,44,93,33,59,86,91}       | t
 91 |         44 |    23 | {13,57,70,6,32,78,98,15,99,77,92,43,80,49,58,61,91,44,93,33,59,86,91}       | t
 91 |         44 |    23 | {21,11,70,6,32,78,98,15,99,77,92,43,80,49,58,61,91,44,93,33,59,86,91}       | t
 91 |         44 |    23 | {97,45,64,50,32,78,98,15,99,77,92,43,80,49,58,61,91,44,93,33,59,86,91}      | t
 91 |         44 |    24 | {5,13,57,70,6,32,78,98,15,99,77,92,43,80,49,58,61,91,44,93,33,59,86,91}     | t
 91 |         44 |    24 | {74,13,57,70,6,32,78,98,15,99,77,92,43,80,49,58,61,91,44,93,33,59,86,91}    | t
 91 |         44 |    24 | {39,84,11,70,6,32,78,98,15,99,77,92,43,80,49,58,61,91,44,93,33,59,86,91}    | t
 91 |         44 |    25 | {17,5,13,57,70,6,32,78,98,15,99,77,92,43,80,49,58,61,91,44,93,33,59,86,91}  | t
 91 |         44 |    25 | {56,74,13,57,70,6,32,78,98,15,99,77,92,43,80,49,58,61,91,44,93,33,59,86,91} | t
(100 rows)

It is not all that useful for identifying the actual references though, especially for the larger circles. Just some spot checking though can confirm that the CTE is bringing back the correct circular references, for instance User 85 has User 87 as their manager, and vice versa. Lets modify the final query to get it into a better format.

WITH RECURSIVE circular_managers(id, manager_id, depth, path, cycle) AS (
    SELECT u.id, u.manager_id, 1,
        ARRAY[u.id],
        false
    FROM users u
    UNION ALL
    SELECT u.id, u.manager_id, cm.depth + 1,
        path || u.id,
        u.id = ANY(path)
    FROM users u, circular_managers cm
    WHERE u.id = cm.manager_id AND NOT cycle
    )

SELECT
depth,
array_to_string(path, ' > ') circular_managers 

FROM circular_managers 
WHERE cycle 
AND path[1] = path[array_upper(path, 1)]
group by 1,2

Here we only want the references where the beginning and end of the array are the same user. This means that the output will show only the core circular references themselves, rather than all relationship trees that touch a circular reference. If you did not get any results here, perhaps there were no circular references randomly generated in your data set. Try dropping the table and re-running the prior SQL or just force a few circular references manually.

 depth |        circular_managers         
-------+----------------------------------
     2 | 30 > 30
     3 | 85 > 87 > 85
     3 | 87 > 85 > 87
     7 | 33 > 59 > 86 > 91 > 44 > 93 > 33
     7 | 44 > 93 > 33 > 59 > 86 > 91 > 44
     7 | 59 > 86 > 91 > 44 > 93 > 33 > 59
     7 | 86 > 91 > 44 > 93 > 33 > 59 > 86
     7 | 91 > 44 > 93 > 33 > 59 > 86 > 91
     7 | 93 > 33 > 59 > 86 > 91 > 44 > 93
(9 rows)

Much better. We can see here that there are really 3 circular references in the table. To get these we need to do some more array manipulation. There is probably an easier way to do this but I used the array#sort method given by the intarray extension.

-- Get the extension if you don't already have it
CREATE EXTENSION IF NOT EXISTS intarray;

WITH RECURSIVE circular_managers(id, manager_id, depth, path, cycle) AS (
    SELECT u.id, u.manager_id, 1,
        ARRAY[u.id],
        false
    FROM users u
    UNION ALL
    SELECT u.id, u.manager_id, cm.depth + 1,
        path || u.id,
        u.id = ANY(path)
    FROM users u, circular_managers cm
    WHERE u.id = cm.manager_id AND NOT cycle
    )

SELECT
depth,
circular_managers
FROM
(
  SELECT
  DISTINCT ON (array_to_string(sort(path[0:(array_upper(path, 1) - 1)]),''))
  array_to_string(sort(path[0:(array_upper(path, 1) - 1)]),'') sorted_path,
  depth,
  array_to_string(path, ' > ') circular_managers

  FROM circular_managers
  WHERE cycle 
  AND path[1] = path[array_upper(path, 1)]
) circular
 depth |        circular_managers         
-------+----------------------------------
     2 | 30 > 30
     7 | 93 > 33 > 59 > 86 > 91 > 44 > 93
     3 | 87 > 85 > 87
(3 rows)

Perfect, an easily digestable list of circular references in the system that we can now take action to correct.

Conclusion

Recursive queries in Postgres can be quite difficult to wrap your head around (similar to recursion itself). It took me a while to understand even with the solid Postgres documentation. For a task like this though it was a great tool.

-JM

comments powered by Disqus