Optimize PHP code to build Tree structure out of large dataset

Question

I have a program to populate highest level node or parent node to be populated next to each of the child and grand child nodes.

I have first made a tree structure and then parse through to populate highest level node or root node next to each child/grandchild nodes.

But when I run the program on a large data set >20000 rows i get this error:

Fatal error:  Out of memory (allocated 1807745024) (tried to allocate 36 bytes) in C:\xampp\htdocs\test_project\index.php on line 20

Here is my code:

<?php

include('mysql_config.php');

set_time_limit(0);
ini_set('memory_limit', '2048M');
$r = mysql_query("SELECT Emp_ID AS id,fname AS name,Manager_ID AS parent_id FROM targets");
        $data = array();
        while($row = mysql_fetch_assoc($r)) {
         $data[] = $row;
         }    
$j = mysql_query("SELECT Emp_ID AS id,fname AS name,Manager_ID AS parent_id FROM targets where Type = 'Super Manager'");
        $parent_data = array();
        while($row = mysql_fetch_assoc($j)) {
         $parent_data[] = $row;
         }           

function buildtree($src_arr, $parent_id = 0, $tree = array())
{
    foreach($src_arr as $idx => $row)
    {
        if($row['parent_id'] == $parent_id)
        {
            foreach($row as $k => $v)
                $tree[$row['id']][$k] = $v;
            unset($src_arr[$idx]);
            $tree[$row['id']]['children'] = buildtree($src_arr, $row['id']);
        }
    }
    ksort($tree);
    return $tree;
}

function fetch_recursive($tree, $parent_id, $parentfound = false, $list = array())
{
    foreach($tree as $k => $v)
    {
        if($parentfound || $k == $parent_id)
        {
            $rowdata = array();
            foreach($v as $field => $value)
                if($field != 'children')
                    $rowdata[$field] = $value;
            $list[] = $rowdata;
            if($v['children'])
                $list = array_merge($list, fetch_recursive($v['children'], $parent_id, true));
        }
        elseif($v['children'])
            $list = array_merge($list, fetch_recursive($v['children'], $parent_id));
    }
    return $list;
}
foreach($parent_data as $value)
{ 
echo '<pre>';
$result_data = fetch_recursive(buildtree($data),(int)$value['id']);
print_r($result_data);
echo '</pre>';
  if(!empty($result_data)){
   foreach($result_data as $child_val){
     $su_id=(int)$value['id'];
     $name_man=(string)$value['name'];
     $dest_id=$child_val['id'];
       mysql_query("update targets set SM_ID ='$su_id',SM_Name='$name_man' where Emp_ID='$dest_id'") or die (mysql_error());
     }
    }
}

?>

How can i optimize the code to solve this error. I tried this code with 100 rows and it worked fine.

Original Problem Statement

I have the following Data in My DB:

Manager_ID Employee_ID

AAA   BBB
AAA   CCC
AAA   DDD
BBB   EEE
BBB   FFF
CCC   GGG
FFF   HHH
III   JJJ
JJJ   KKK
JJJ   LLL

I wish to populate the child nodes with their respective highest level roots nodes such that all child nodes have a root level data/parent mapped to them something like this:

Employee_ID 1st Level Node
AAA         Root
BBB         AAA
CCC         AAA
DDD         AAA
EEE         AAA
FFF         AAA
GGG         AAA
HHH         AAA
III         Root
JJJ         III
KKK         III
LLL         III

I have tried creating a PHP function to create a tree but am unable to take it from there to populate the last or highest level root to the respective child nodes.

Answer 1

Rule of thumb: PHP has 40 bytes of overhead for each scalar value. That adds up fast.

Don't use the deprecated mysql_* interface; use either mysqli_* or PDO.

Solution to your problem: Put all the data into temporary MySQL tables, then use SQL statements to rearrange into the hierarchical format. Ah; you seem to have the data already in a table.

The SQL would involve one SQL statement per level of the hierarchy, probably doing all records at that level in a single statement. PHP code would control the levels, since MySQL has no concept of hierarchy.

Quite possibly this change will even run faster that PHP would have -- you end up with a small number of queries, instead of the 20000 (or more) you currently are designed for.

Here's a way to transform your code. Start with the innermost for loop. Think about how that loop can be turned into one SQL statement. Then do it. (You may be happy enough after this one step.)

Answer 2

Clearly recreating the tree in memory is not working. The simple self referencing table is indeed a simple and obvious solution to the problem of describing a tree in a relational database, but as you have discovered, it is also very limited. This would be relatively easy if your data was stored in an adjacency list.

If we have even a single field we can update, then its possible to flag the trees iteratively, something like....

 run_query('update yourtable set flag=0');
 foreach ($root_id as $root) {
     $d=1;
     run_query('update yourtable set flag=$d where id=$root');
     do {
        $rows_changed=run_query('update yourtable y1 
           set y1.flag=$d+1
           where y1.parent in (select y2.id from yourtable y2
             where y2.flag=$d');
        ++$d;
     } while ($rows_changed);
     run_query('update yourtable set root=$root, flag=0
        where flag>0');
 }

(Note code not tested).

Of course this can be implemented as in a mysql procedure which will run slightly faster than a mixed php/mysql solution.

Answer 3

First add a column to your table for each child's root ID:

ALTER TABLE targets ADD COLUMN Root_ID INT;

Then set the root ID to the manager's ID:

$sql = "UPDATE targets SET Root_ID = Manager_ID";
if (!$conn->query($sql)) {
    error_log($conn->error);
    die("Database error occurred, see log.");
}

Then iteratively update the root ID to that employee's manager's ID. The loop stops when no changes are made, because there is no child left whose root ID itself has a manager. At this point, all records will have their root ID set to an employee record that has no manager (i.e. root employees).

$affectedRows = 1;
while ($affectedRows > 0) {
    $sql = "UPDATE targets AS child
        INNER JOIN targets AS parent
          ON child.Root_ID = parent.Emp_ID
        SET child.Root_Id = parent.Manager_ID";
    if (!$conn->query($sql)) {
        error_log($conn->error);
        die("Database error occurred, see log.");
    }
    $affectedRows = $conn->affected_rows;
    echo "Changed $affectedRows rows\n"; // demo only, remove this echo
}

Now you can print out the employees with their roots, row by row, without having to store all the data at any one time:

$sql = "(SELECT Emp_ID, Root_ID FROM targets)
    UNION
    (SELECT t1.Manager_ID, 'Root' FROM targets AS t1
     LEFT OUTER JOIN targets AS t2 ON t1.Manager_ID = t2.Emp_ID
     WHERE t2.Emp_ID IS NULL)
    ORDER BY Emp_ID";
if (($result = $conn->query($sql, MYSQLI_USE_RESULT)) === false) {
    error_log($conn->error);
    die("Database error occurred, see log.");
}
printf("%-10s %-10s\n", "Emp_ID", "Root_ID");
while ($row = $result->fetch_assoc()) {
    printf("%-10s %-10s\n", $row["Emp_ID"], $row["Root_ID"]);
}
$result->free();

Output:

Emp_ID     Root_ID   
AAA        Root      
BBB        AAA       
CCC        AAA       
DDD        AAA       
EEE        AAA       
FFF        AAA       
GGG        AAA       
HHH        AAA       
III        Root      
JJJ        III       
KKK        III       
LLL        III       

---

Re your comment:

To optimize this, I added an index PRIMARY KEY (Emp_ID, Manager_ID). Here's my table definition:

CREATE TABLE `targets` (
  `Manager_Id` char(3) NOT NULL,
  `Emp_Id` char(3) NOT NULL,
  `Root_ID` char(3) DEFAULT NULL,
  PRIMARY KEY (`Emp_Id`,`Manager_Id`)
) ENGINE=InnoDB;

Here's the query EXPLAIN for the UPDATE:

*************************** 1. row ***************************
               id: 1
      select_type: UPDATE
            table: child
       partitions: NULL
             type: ALL
    possible_keys: NULL
              key: NULL
          key_len: NULL
              ref: NULL
             rows: 10
         filtered: 100.00
            Extra: Using where
*************************** 2. row ***************************
               id: 1
      select_type: SIMPLE
            table: parent
       partitions: NULL
             type: ref
    possible_keys: PRIMARY
              key: PRIMARY
          key_len: 3
              ref: test.child.Root_ID
             rows: 1
         filtered: 100.00
            Extra: Using index

Here's the EXPLAIN for the SELECT UNION:

*************************** 1. row ***************************
           id: 1
  select_type: PRIMARY
        table: targets
   partitions: NULL
         type: ALL
possible_keys: NULL
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 10
     filtered: 100.00
        Extra: NULL
*************************** 2. row ***************************
           id: 2
  select_type: UNION
        table: t1
   partitions: NULL
         type: index
possible_keys: NULL
          key: PRIMARY
      key_len: 6
          ref: NULL
         rows: 10
     filtered: 100.00
        Extra: Using index
*************************** 3. row ***************************
           id: 2
  select_type: UNION
        table: t2
   partitions: NULL
         type: ref
possible_keys: PRIMARY
          key: PRIMARY
      key_len: 3
          ref: test.t1.Manager_Id
         rows: 1
     filtered: 100.00
        Extra: Using where; Not exists; Using index
*************************** 4. row ***************************
           id: NULL
  select_type: UNION RESULT
        table: <union1,2>
   partitions: NULL
         type: ALL
possible_keys: NULL
          key: NULL
      key_len: NULL
          ref: NULL
         rows: NULL
     filtered: NULL
        Extra: Using temporary; Using filesort