Recursive MySQL function call eats up too much memory and dies.

Question

I have the following recursive function which works... up until a point. Then the script asks for more memory once the queries exceed about 100, and when I add more memory, the script typically just dies (I end up with a white screen on my browser).

public function returnPArray($parent=0,$depth=0,$orderBy = 'showOrder ASC'){



    $query = mysql_query("SELECT *, UNIX_TIMESTAMP(lastDate) AS whenTime 
        FROM these_pages 
        WHERE parent = '".$parent."' AND deleted = 'N' ORDER BY ".$orderBy."");

    $rows = mysql_num_rows($query);

    while($row = mysql_fetch_assoc($query)){

        // This uses my class and places the content in an array.
        MyClass::$_navArray[] = array(

            'id' => $row['id'], 
            'parent' => $row['parent']

        );

        MyClass::returnPArray($row['id'],($depth+1));   

    }
    $i++;

}

Can anyone help me make this query less resource intensive? Or find a way to free up memory between calls... somehow.

Answer 1

The white screen is likely because of a stack overflow. Do you have a row where the parent_id is it's own id? Try adding AND id != '".(int)$parent."' to the where clause to prevent that kind of bug from creeping in...

**EDIT: To account for circular references, try modifying the assignment to something like:

while($row = mysql_fetch_assoc($query)){
    if (isset(MyClass::$_navArray[$row['id']])) continue;

    MyClass::$_navArray[$row['id']] = array(
        'id' => $row['id'], 
        'parent' => $row['parent']
    );
    MyClass::returnPArray($row['id'],($depth+1));
}

Answer 2

Shouldn't you stop recursion at some point (I guess you do need to return from method if the number of rows is 0) ? From the code you posted I see an endless recursive calls to returnPArray.

Answer 3

Let me ask you this... are you just trying to build out a tree of pages? If so, is there some point along the hierarchy that you can call an ultimate parent? I've found that when storing tress in a db, storing the ultimate parent id in addition to the immediate parent makes it much faster to get back as you don't need any recursion or iteration against the db.

It is a bit of denormalization, but just a small bit, and it's better to denorm than to recurse or iterate vs the db.

If your needs are more complex, it may be better to retrieve more of the tree than you need and use app code to iterate through to get just the nodes/rows you need. Most application code is far superior to any DB at iteration/recursion.

Answer 4

Most likely you're overloading on active query result sets. If, as you say, you're getting about 100 iterations deep into the recursion, that means you've got 100 queries/resultsets open. Even if each query only returns one row, the whole resultset is kept open until the second fetch call (which would return false). You never get back to any particular level to do that second call, so you just keep firing off new queries and opening new result sets.

If you're going for a simple breadcrumb trail, with a single result needed per tree level, then I'd suggest not doing a while() loop to iterate over the result set. Fetch the record for each particular level, then close the resultset with mysql_free_result(), THEN do the recursive call.

Otherwise, try switching to a breadth-first query method, and again, free the resulset after building each tree level.

Answer 5

Why are you using a recursive function? When I look at the code, it looks as though you're simply creating a table which will contain both the child and parent ID of all records. If that's what you want as a result then you don't even need recursion. A simple select, not filtering on parent_id (but probably ordering on it) will do, and you only iterate over it once.

The following will probably return the same results as your current recursive function :

public function returnPArray($orderBy = 'showOrder ASC'){
    $query = mysql_query("SELECT *, UNIX_TIMESTAMP(lastDate) AS whenTime 
        FROM these_pages 
        WHERE deleted = 'N' ORDER BY parent ASC,".$orderBy."");

    $rows = mysql_num_rows($query);

    while($row = mysql_fetch_assoc($query)){

        // This uses my class and places the content in an array.
        MyClass::$_navArray[] = array(

            'id' => $row['id'], 
            'parent' => $row['parent']

        );
    }
}

Answer 6

I'd suggest getting all rows in one query and build up the tree-structure using pure PHP:

$nodeList = array();
$tree     = array();

$query = mysql_query("SELECT *, UNIX_TIMESTAMP(lastDate) AS whenTime 
    FROM these_pages WHERE deleted = 'N' ORDER BY ".$orderBy."");
while($row = mysql_fetch_assoc($query)){
    $nodeList[$row['id']] = array_merge($row, array('children' => array()));
}
mysql_free_result($query);

foreach ($nodeList as $nodeId => &$node) {
    if (!$node['parent_id'] || !array_key_exists($node['parent_id'], $nodeList)) {
        $tree[] = &$node;
    } else {
        $nodeList[$node['parent_id']]['children'][] = &$node;
    }
}
unset($node);
unset($nodeList);

Adjust as needed.

Answer 7

There are a few problems.

1. You already noticed the memory problem. You can set unlimited memory by using ini_set('memory_limit', -1).
2. The reason you get a white screen is because the script exceeds the max execution time and you either have display_errors turned off or error_reporting is set to E_NONE. You can set unlimited execution time by using set_time_limit(0).
3. Even with "unlimited" memory and "unlimited" time, you are still obviously constrained by the limits of your server and your own precious time. The algorithm and data model that you have selected will not scale well, and if this is meant for a production website, then you have already blown your time and memory budget.

The solution to #3 is to use a better data model which supports a more efficient algorithm.

Your function is named poorly, but I'm guessing it means to "return an array of all parents of a particular page".

If that's what you want to do, then check out Modified Pre-order Tree Traversal as a strategy for more efficient querying. This behavior is already built into some frameworks, such as Doctrine ORM, which makes it particularly easy to use.