Aman Garg Aman Garg - 2 months ago 21
MySQL Question

Optimize PHP code to build Tree structure out of large dataset

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

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