Optimize while loop

Question

I am using this procedure that I created to create a member's downline.

PROCEDURE get_downline(IN id INT)
BEGIN
    declare cur_depth int default 1;

    -- Create the structure of the final table
    drop temporary table if exists tmp_downline;
    create temporary table tmp_downline (
        member_id int unsigned,
        referrer_id int unsigned,
        depth tinyint unsigned
    );

    -- Create a table for the previous list of users
    drop temporary table if exists tmp_members;
    create temporary table tmp_members(
        member_id int unsigned
    );

    -- Make a duplicate of tmp_members so we can select on both
    drop temporary table if exists tmp_members2;
    create temporary table tmp_members2(
        member_id int unsigned
    );

    -- Create the level 1 downline
    insert into tmp_downline select id, member_id, cur_depth from members where referrer_id = id;
    -- Add those members into the tmp table
    insert into tmp_members select member_id from members where referrer_id = id;

    myLoop: while ((select count(*) from tmp_members) > 0) do
        -- Set next level of users
        set cur_depth = cur_depth + 1;

        -- Insert next level of users into table
        insert into tmp_downline select id, member_id, cur_depth from members where referrer_id in(select member_id from tmp_members);

        -- Re-fill duplicate temporary table
        truncate table tmp_members2;
        insert into tmp_members2 select member_id from tmp_members;

        -- Reset the default temporary table
        truncate table tmp_members;
        insert into tmp_members select member_id from members where referrer_id in(select member_id from tmp_members2);

    end while;

    -- Get the final list of results
    select * from tmp_downline order by depth;
END

Here are my results:

Found rows: 424,097; Duration for 1 query: 12.438 sec.

All the queries look like they are using optimized indexes, but it is still taking a while to run. Is there a better way to run my while loop? I feel that making 2 temporary tables might be part of the issue, but when running my last insert query I can't reopen the temporary table which is why I made a duplicate table.

Here is a slimmed down version of the original table (original has 50 cols):

CREATE TABLE `members` (
    `member_id` INT(11) NOT NULL AUTO_INCREMENT,
    `referrer_id` INT(11) NOT NULL DEFAULT '0',
    PRIMARY KEY (`member_id`),
    INDEX `referrer_id_idx` (`referrer_id`)
);

What I am trying to achieve is to get an MLM downline.

Here is a picture that shows a downline where the number shows the level and you are the main circle at the top.

Level 1: People you referred to the program
Level 2: People your referrals referred to the program
Level 3: People your referrals, referrals referred to the program
Level 4: ...
Level 5: ....
Level ........

Answer 1

Re-evaluating select count(*) from tmp_members for each iteration is expensive and unnecessary. Find the initial count then deduct mysql_affected_rows() after each operation. Doing a proper join in the the insert....select...in (select...) will likely result in better plans.

You've not shown the structure of the members table nor the EXPLAIN plans for the queries, so its impossible to say if there's any scope for optimising there, but you've probably get a big performance uplift by using a proper graph database rather than a relational one for this task. Or maintain a denormalised view of the results populated when you add a new record to the base table. Or use a more appropriate tree representation such as an adjacency list.

Answer 2

I think you might be able to do away with the second tmp_members table...

PROCEDURE get_downline(IN id INT)
BEGIN
    declare cur_depth int default 1;

    -- Create the structure of the final table
    drop temporary table if exists tmp_downline;
    create temporary table tmp_downline (
        member_id int unsigned,
        referrer_id int unsigned,
        depth tinyint unsigned
    );

    -- Create a table for the previous list of users
    drop temporary table if exists tmp_members;
    create temporary table tmp_members(
        member_id int unsigned
    );

    -- Create the level 1 downline
    insert into tmp_downline 
        select id, member_id, cur_depth 
        from members 
        where referrer_id = id
    ;

    myLoop: while (mysql_affected_rows()>1) do

        -- Load tmp_members with previously added referred members
        -- to use as the next potential referrers
        truncate tmp_members;
        insert into tmp_members 
            select referrer_id 
            from tmp_downline 
            where depth = cur_depth
        ;

        -- Set next level of users
        set cur_depth = cur_depth + 1;

        -- Insert next level of users into table
        insert into tmp_downline 
            select id, m.member_id, cur_depth 
            from members AS m
            INNER JOIN tmp_members AS t ON m.referrer_id = t.member_id
        ;

    end while;

    -- Get the final list of results
    select * from tmp_downline order by depth;
END

In this case, tmp_members could be more appropriately named tmp_candidate_referrers, but I left it as it was to show how little of a change it was.

Also, for this version, you might consider adding indexes for tmp_downline.cur_depth and tmp_members.member_id since they are repeatedly used.

--- Edit ---

I made a correction in the first insert within the loop above. referrer_id should be selected from tmp_downline, not member_id; which brings me to a question...

Why bother with the tmp_downline.member_id field when it always contains the value of the argument passed?

If you need it in the final results, you can always finish with

SELECT id AS member_id, referrer_id, depth FROM tmp_downline ORDER BY depth;