Performance problem in Recursion!

Mohammad_Wajhe

Getting problem in showing 20,000 aprox. items in hierarchy lying in a mysql table. I have tried recursive looping; it worked but really very slow. Please tell me any other way to show items in hierarchy.

The Table Structure is as follow.
Col#
1 Item_ID int(11) auto increment
2 Item_Name varchar(255)
3 Hierarchy_No int(11)
4 Parent_Item_ID int(11)

Now we have items in table in this arrangement.

Item_ID Item_Name Hierarchy_No Parent_Item_ID
1 Parent Item 1 1 0
2 Parent Item 2 1 0
3 Parent Item 3 1 0
4 Sub Item 1 1 2 1
5 Sub Item 1 2 2 1
6 Sub Item 2 1 2 2
7 Sub Item 2 2 2 2
8 Sub Item 1 1 1 3 4
9 Sub Item 3 1 2 3
10 Sub Item 3 1 1 3 9
11 Sub Item 3 1 2 3 9
Up to 20,000 items. Up to “6” Hier no

Now I want the above items in the following arrangement.

Parent Item 1
----Sub Item 1 1
--------Sub Item 1 1 1
            ----Sub Item 1 2
            Parent Item 2
            ----Sub Item 2 1
            ----Sub Item 2 2
            Parent Item 3
            ----Sub Item 3 1
            --------Sub Item 3 1 1
            --------Sub Item 3 1 2

I have got this arrangement by using this recursive code.

function show_hier($id,$level){
      $font_size=2;
      $query="select item_id,itemname,parent_item_id,hierno from items where parent_item_id=".$id;

   $result=mysql_query($query);
   while ($row=mysql_fetch_row($result)){
  	$count1=0;
   	$id=$row[0];
           	$stn="";
for ($i=3; $i<=$row[3]; $i++) {
                  	for ($j=3;$j<=$row[3]; $j++) $stn.="&nbsp;";
$count1++;
           	}

     if ($count1>=4) echo "<i>";
     if ($count1>=4) $font_size=1;
       %>
&nbsp;<%=$stn%><%=ucfirst($row[1])%>
        <br>
      <%
      if ($count1>=3) echo "</i>";
      if ($level=="") $level=1000;
      if ($id!="" and $count1<$level) show_hier($id,$level);
     }//end of while loop
 }// end of function

The code is working fine for 600 – 700 items, but gradually becomes very very slow when items exceed more then 2000. Please help me find out some faster solution.

Wajhe

Drakla

Is it only going really slowly when you're outputting to a browser? If so it's the browser's rendering that's really slow. Time the script - if it says it runs in about 3 seconds, but the pages takes about 30 you'll know that's the case.

I've done a similar recursive heirarchy tree thing but it's based on Drawmack's simple table design of

ID
ParentID (pid)
name

function show_branch($catid=0)
{
	static $depth=-1;

$db=new MySQLThing("paswords-etc");
$db->use_db("hh");

$depth++;

$padder='';	
for($i=0;$i<$depth;$i++) $padder.="\t";

$query="SELECT * from cats WHERE pid=$catid";	
$db->safe_query($query);

while( $row=$db->fetch_assoc() )
{
	$name="<a href='browse-cats.php?catid=$row[id]'>$row[name]</a>";
	echo $padder.$name.'<br>';

	show_branch( $row['id'] );
	//find mah chillun
}

$db->free_result();
$db->close();

$depth--;
}

Don't know if that'll help, but I'm far too tired to read code at the moment.

Mohammad_Wajhe

Thanks for the reply.

I have read you code. but it looks similar to the above one.

Is it working fast for about 20,000 items?

Weedpacket

One way you could speed this whole deal up is to reduce the number of database queries to one, in which you pull the relevant fields of the entire table and store them in an array. Then instead of querying the database on every call to the function, pass it that array.

Even smarter, instead of just using an array, store the tree as a tree.

Weedpacket

Thought I'd toss something of the sort off.

function build_tree($root_id=0)
{	$sql = "select id,parentid,blah from mytable";
	$result = mysql_query($sql);
	// And that's one of the biggest timesinks out of the way.

$tree = array();

// Each row in the table gets a row in the tree array.
// Each row in the tree has two elements:
// $tree[$id]['blah'] is the blah field from table row $id
// $tree[$id]['children'] are the children of table row $id
//
while($row=mysql_fetch_array($result))
{	$id = $row['id'];
	$parentid = $row['parentid'];
	$blah = $row['blah'];

	$tree[$id]=array('children'=>array(), 'blah'=>$blah);
	if($id!=$root_id)
		$tree[$parentid]['children'][]=$id; //I'm home, Mum!
}

// On the off-chance that we pulled too many rows
// (since we probably couldn't tell in advance which rows are below
// the root until we'd read the entire table) we kill any
// rows that aren't accessible from the root here.
// The following block of code isn't necessary if it is known
// that the entire table is part of the tree. With suitable assignment
// of ids to rows, this part may be avoided, by allowing the construction
// of a suitable WHERE clause in the above query.
//
// In fact, this step isn't necessary except for memory savings anyway.
// If those savings aren't significant compared with the additional
// time needed to run it, then don't bother.
//
// If there is a cycle in the tree's structure (i.e., it isn't a tree
// after all), then this loop will be infinite.
$temptree=array($root_id=>$tree[$root_id]);
$found_ids=array($root_id);
do
{	$row=$temptree[array_pop($found_ids)];
	foreach($row['children'] as $child) $temptree[$child]=$tree[$child];
	$found_ids=array_merge($found_ids,$children);
} while(count($found_ids));
$tree=$temptree;


// Return that tree
return $tree;
}

So by applying that bit of forethought, that show_branch() function of Drakla's becomes

function show_branch($tree, $catid=0)
{	static $depth=-1;
	$depth++;
	$padder=str_repeat($depth,"\t");
	$name="<a href='browse-cats.php?catid=".$catid."'>".$tree[$catid]['blah']."</a>";
	echo $padder.$name.'<br>';
	foreach($tree[$catid]['children'] as $child)
		show_branch($tree, $child);
	$depth--;
}

Note that that's off the cuff; may have a couple of rough edges. Needless to say, "blah" is short for whatever other fields (besides id and parentid) are being returned.

If the tree structure doesn't change much then after it's generated once, it could be cached in some way and restored from that as necesssary. (var_export($tree), for example will generate a PHP-readable representation of $tree as a bunch of array() declarations that can be stored and retrieved as needed.)

drawmack

When you have slow code the first two things you should look at are your loops and your if statements. If/switch you can get rid of some of those you'll improve the performance of your code.

function show_hier($id,$level,$indentor){
    $font_size=2;
    $query="select item_id,itemname,parent_item_id,hierno from items where parent_item_id=".$id;

$result=mysql_query($query);
while ($row=mysql_fetch_row($result)){
    $count1=0;
    $id=$row[0];
    $stn="";
     /* We can completely do away with these two loops
    for ($i=3; $i<=$row[3]; $i++) {
        for ($j=3;$j<=$row[3]; $j++) $stn.="&nbsp;";
        $count1++;
    }
    By using this instead */

    $count1 = $row[3];
    $stn = $indentor;

     //here you're executing two if statements that do
     //the same exact thing, that's wasting a lot of
     //clock ticks
     //if ($count1>=4) echo "<i>";
     //if ($count1>=4) $font_size=1;
     //try this instead
     if($count1 >= 4) {
        echo "<i>":
        $font_size = 1;
        echo "nbsp;" . $stn . ucfirst($row[1]) . "</i><br>\n";    
     } else {
          echo "nbsp;" . $stn . ucfirst($row[1]) . "<br>\n";
     } //end if

  if ($level == "") $level=1000;
  if ($id != "" and $count1<$level) show_hier($id,$level.'&nbsp;&nbsp;&nbsp;&nbsp;' . $indentor);
 }//end of while loop
 }// end of function

That should speed it up significantly, also make sure your database is indexed properly, any field used in a where or orderby clause should be indexed.

freebie

I can't say for 100%, but this might be a good case for a "self join". See this article for more information.

http://www.devshed.com/Server_Side/MySQL/Join/page5.html

drawmack

in html white space is truncated to a single space no matter how many there are instead of using '\t' for your spacer use '&nbsp;&nbsp;&nbsp;&nbsp;'