Mysql – Recursive Query in MySQL using stored proceedure and CURSOR

cursorsMySQLrecursivestored-procedurestree

I'm expanding our user/group system to allow for dynamic groups which are made up of other groups members. I have three tables users, groups, and relationships.

For simplicity sake, lets say users only contains one field user_id, and groups only contains group_id. relationships uses three fields: user_id, group_id, related_group_id to represent both user to group and group to group relationships.

A dynamically populated group hierarchy would be something like:

Users A, B, C belong to Group 1 and Users D, E, F belong to Group 2. All of these are represented in the relationships table as (user_id,group_id):

A,1
B,1
C,1
D,2
E,2
F,2

The dynamic Group 3 would have two group to group relationship records (group_id,related_group_id):

3,1
3,2

To illustrate my problem better lets add a Dynamic Group 4 and have it include Group 3:

4,3

Piecing together what I've learned of MySQL CURSOR's, I've created the following stored procedure called fetch_inheritance_groups:

DROP PROCEDURE IF EXISTS `fetch_inheritance_groups`;

CREATE PROCEDURE `fetch_inheritance_groups`(IN parent_id INT)
    READS SQL DATA
    BEGIN

    DECLARE inherit_id char(32);
    DECLARE eol BOOLEAN;
    DECLARE inherit_cur CURSOR FOR SELECT r.Related_Group_ID FROM usr_relationships r WHERE r.Group_ID = parent_id AND r.Related_Group_ID IS NOT NULL;
    DECLARE CONTINUE HANDLER FOR NOT FOUND SET eol = TRUE;

    OPEN inherit_cur;
    inherited: LOOP
        FETCH inherit_cur INTO inherit_id;

        IF eol 
            THEN
            CLOSE inherit_cur;
            LEAVE inherited;
        ELSE
            CALL fetch_inheritance_groups(inherit_id);
        END IF;

        SELECT inherit_id;

    END LOOP inherited;

END;

…which is called with…

CALL fetch_inheritance_groups(4);

…and returns the expected results of

3
2
1

Herein begins my problem, they're returned as three separate result sets rather than three rows in a single result set, and secondly, the results are meant to be used within a query like:

SELECT r.uer_id FROM relationships r WHERE r.group_id = 4 OR r.group_id IN (CALL fetch_inheritance_groups(4));

So the three questions I'm hoping someone can answer are:

1. Should I be using a CURSOR here or is there an alternative that will get the same recursive result?

2. How can I get the results back in a single result set so that it can be used in the same fashion as a subselect?

3. What is the proper way of using the results from the CALL because I can't at least as far as I've tried get the sample SELECT statement above to work? I believe this is because I can't use CALL inline but I'm not sure.


UPDATE: In a related question here: How long will a temporary MEMORY table persist if I don't drop it (MySQL) I posted a set of updates to the stored proceedure used above which is still recursive, but provides the list of ID's back as a variable, and in a format compatible with FIND_IN_SET() giving me EXACTLY what I needed.

Best Answer

So the three questions I'm hoping someone can answer are:

1.Should I be using a CURSOR here or is there an alternative that will get the same recursive result?

No, you should not. The CURSOR keep being opened over and over. Thinking of the overhead make me cringe. Personally, I stay away from CURSORs.

2.How can I get the results back in a single result set so that it can be used in the same fashion as a subselect?

3.What is the proper way of using the results from the CALL because I can't at least as far as I've tried get the sample SELECT statement above to work? I believe this is because I can't use CALL inline but I'm not sure.

I would like to bail you out of this by suggesting something I learned from my college days when learning about data structures. You need to perform tree traversal using a queue. This allows you to start at a root and express all descendants of a tree.

The algorithm goes like this

  • STEP 01 : Start with an empty queue
  • STEP 02 : Dequeue Node From the Front of the Queue
  • STEP 03 : Enqueue All Children of the Latest Node
  • STEP 04 : Process Info From the Latest Node
  • STEP 05 : If the Queue is Not Empty, Go Back to STEP 02
  • STEP 06 : All Done

This allows you to traverse a recursive structure without using Programmatic Recursion. At this point, you are probably asking: How can I traverse a tree structure without recursion?

I wrote a post about how to script three Stored Procedures that can using a loop in a single CALL that will traverse a table with nodes and its parent in a table:

  • GetParentIDByID
  • GetAncestry
  • GetFamilyTree

The post is Find highest level of a hierarchical field: with vs without CTEs (Oct 24, 2011). It contains the Stored Procedures already written that will traverse the following table structure:

+------------+--------------+------+-----+---------+----------------+
| Field      | Type         | Null | Key | Default | Extra          |
+------------+--------------+------+-----+---------+----------------+
| id         | int(11)      | NO   | PRI | NULL    | auto_increment | 
| parent_id  | int(11)      | YES  |     | NULL    |                | 
| name       | varchar(255) | YES  |     | NULL    |                | 
| notes      | text         | YES  |     | NULL    |                | 
+------------+--------------+------+-----+---------+----------------+

Please read the code carefully and apply the principles.

Give it a Try !!!