Link to home
Get AccessLog in
Avatar of MatthewP
MatthewPFlag for United Kingdom of Great Britain and Northern Ireland

asked on

Recursively looping large hashes - Possibly solvable with cunning MySQL Selects

The core of this question is about PHP data structures, and as Ive said some mysql wizardry may help. In order to explain it easily ive explained exactly what Im trying to do.

I have a set of css styled menus in my application, that are generated from databases. Essentially, the databased content is parsed by PHP wich generates HTML <ul><li> tags, with text and links, and supports nested lists up to five levels deep, and I use style sheets to make them into all singing all dancing pop up menus.

Items are assigned their position by two fields  primarily a parent_id field, and then an ordering field. Basically everything with a parent id of 0 is a top level item, and any item can be inserted anywhere in the menu simply by adding a parent_id to the new item which is the id of the item immediately above it in the menu. The ordering field controls the ordering of items with the same parent_id. Hence I can construct complex menu structures.

Below is a simple example:

Home      About            Contact
           ->HTML                ->Email
           ->PDF                   ->Phone

In this example Phone is under Contact. Contact is ID 3, so I give Phone a parent ID of 3 and an ordering value of 1 (as email comes first  this also has parent of 3 but an ID of 0).

Being databased, its easy to edit items, add items, choose what their parent is and where in the order they should come.

This was working very nicely (a little slow mind) until I added 300 odd items into the menu, and it has now slowed down to a crawl.

The script goes like this:

1.      Select all items for the menu ordered by parent_id, then by ordering, all ascending. (This could possibly use work, as ideally it would pull everything out in the order it is required to stop multiple loops through the results being required. Im not sure if this is possible??)

2.      Go through items in order. Obviously it starts off in order as I pull put parent 0 and id 0, same with parent 0 id 1, however this item has child items as denoted by parent_ids in other rows. I have this covered as before it prints a close list item tag (</li>), it loops through the entire record set again searching for parent_ids that match the current id. If it finds one, it can then print a new <ul>.. and so on and so forth.

As Im doing it 5 levels deep, this code is nested 5 times, and thus the menu is created. Or rather was, until I added quite a lot of items to it, 300 to be precise.

Its not hard to work out why: First loop  300 times. Second inner loop, same result set 300 times. 300x300=90 000. Five loops in gives a possible 2 430 000 000 000  just shy of two and a half trillion passes through the code. (Im not quite doing that many as a few things in the code stop it in certain places, but not a lot and this basically illustrates the problem!)

I guess one way to correct it would be to have a field containing a comma separated list of children instead of a field listing the parent. That way each time it hit a row I can see if Ive got any children, and print them there and then, deleting the printed rows as I go. I dont want to do this particularly, as its nice and easy to add items only updating one row, but it is an option.

Im currently thinking along the lines of: for each row, take a slice of the array where parent_id is equal to the current id. This would be similar to doing a select, but on the array and not on the database. (I want to stay away from 300 SELECT statements for obvious reasons too : ) Im not sure if such a thing is actually possible however, without looping through the whole array anyway to work out which bits it wants.

Im curious to know if anyones come up against this before and found a way to do it without adding children to the rows.

Any and all suggestions welcome!

Thanks,
Matt

Working Code below:
function build_menu_from_table($incoming_menu_id){
        $sql="SELECT * from menu_items where menu_id=$incoming_menu_id order by parent_id, ordering";
        $all_rows=array();
        $result=mysql_query($sql) or die("Error " . mysql_error());
        $count_after=0;
 
 
        $menu_html = "<div id=\"menu\">\n\n<ul class=\"menu_level1\">\n";
        $printed_ids=array(); # array of all ids that have been printed
 
        #
        # Start looping through everything
        #
 
        // get the last item id for level 0
        $maxsql = "select max(ordering) as highest_order from menu_items where menu_id=$incoming_menu_id AND parent_id=0";
        $maxresult=mysql_query($maxsql) or die ("error " . mysql_error());
        $highest="";
        while ($maxrow = mysql_fetch_array($maxresult,MYSQL_ASSOC)){
                $highest=$maxrow['highest_order'];
        }
 
        $maxid = "select id from menu_items where menu_id=$incoming_menu_id AND parent_id =0 AND ordering = " . $highest;
        $maxresult=mysql_query($maxid) or die ("error " . mysql_error());
        $last_id="";
        while ($maxrow = mysql_fetch_array($maxresult,MYSQL_ASSOC)){
                $last_id=$maxrow['id'];
        }
 
        foreach ($all_rows as $eachrow => $eachrow_array){
 
                $already_printed=0;
                foreach ($printed_ids as $row_printed){
                        if ($row_printed == $eachrow_array['id']){$already_printed=1; continue 2;}
                }
                      
               $menu_html .= "\n<li class=\"listitem_level1\">";
 
                $menu_html .= "<a href=\"" . $eachrow_array['url'] . "\">".$eachrow_array['item_text']."</a>";
                array_push($printed_ids,$eachrow_array['id']);
 
                #
                # Looping through second set now
                #
                foreach ($all_rows as $eachrow2 => $eachrow_array2){
                $already_printed2=0;
                foreach ($printed_ids as $row_printed){
                        if ($row_printed == $eachrow_array2['id']){$already_printed2=1; continue 2;}
                }
                        if ($eachrow_array2['parent_id']==$eachrow_array['id']){
                                $already_printed2=0;
                                if (!$second_ul_printed){$menu_html .= "\n<ul class=\"menu_level2\">\n"; $second_ul_printed=1;}
                                $menu_html .= "\n<li class=\"listitem_level2\">";
                                $menu_html .= "<a href=\"" . $eachrow_array2['url'] . "\">".$eachrow_array2['item_text']."</a>";
                                array_push($printed_ids,$eachrow_array2['id']);
 
                                #
                                # third loop
                                #
                                foreach ($all_rows as $eachrow3 => $eachrow_array3){
                                        $already_printed3=0;
                                        
                                        foreach ($printed_ids as $row_printed){
                                                if ($row_printed == $eachrow_array3['id']){$already_printed3=1; continue(1);}
                                        }
                                        if ($eachrow_array3['parent_id']==$eachrow_array2['id']){
                                                if (!$third_ul_printed){$menu_html .= "<ul class=\"menu_level3\">\n"; $third_ul_printed=1;}
                                                if (!$already_printed3){
                                                     $menu_html .= "<li class=\"listitem_level3\"><a href=\"" . $eachrow_array3['url'] . "\">".$eachrow_array3['item_text']."</a>";
                                                        array_push($printed_ids,$eachrow_array3['id']);
                                                }
 
 
                                        #
                                        # fourth loop
                                        #
                                        foreach ($all_rows as $eachrow4 => $eachrow_array4){
                                                $already_printed4=0;
 
                                                foreach ($printed_ids as $row_printed){
                                                        if ($row_printed == $eachrow_array4['id']){$already_printed4=1; continue 1;}
                                                }
                                                if ($eachrow_array4['parent_id']==$eachrow_array3['id']){
                                                        if (!$fourth_ul_printed){$menu_html .= "<ul class=\"menu_level4\">\n"; $fourth_ul_printed=1;}
                                                        if (!$already_printed4){
                                                                $menu_html .= "<li class=\"listitem_level4\"><a href=\"" . $eachrow_array4['url'] . "\">".$eachrow_array4['item_text']."</a>";
                                                        array_push($printed_ids,$eachrow_array4['id']);
                                                        }
 
                                                        #
                                                        # fifth loop
                                                        #
                                                        foreach ($all_rows as $eachrow5 => $eachrow_array5){
                                                                $already_printed5=0;
 
                                                                foreach ($printed_ids as $row_printed){
                                                                        if ($row_printed == $eachrow_array5['id']){$already_printed5=1; continue 1;}
                                                                }
                                                                if ($eachrow_array5['parent_id']==$eachrow_array4['id']){
                                                                        if (!$fifth_ul_printed){$menu_html .= "<ul class=\"menu_level5\">"; $fifth_ul_printed=1;}
                                                                if (!$already_printed5){
                                                                                $menu_html .= "<li class=\"listitem_level5\"><a href=\"" .  $eachrow_array5['url'] . "\">".$eachrow_array5['item_text']."</a>";
                                                                                array_push($printed_ids,$eachrow_array5['id']);
                                                                        }
                                                                        $menu_html .= "</li>\n"; # closes 5th level li
                                                                }
                                                        }# close foreach 5
                                                        if ($fifth_ul_printed){
                                                                $menu_html .= "</ul>\n"; $fifth_ul_printed=0;
                                                        }
 
                                                        $menu_html .= "</li>"; # closes 4th level li
                                             }
                                        }# close foreach 4
                                        if ($fourth_ul_printed){
                                                $menu_html .= "</ul>\n"; $fourth_ul_printed=0;
                                        }
                                        $menu_html .= "</li>\n"; # closes 3rd level li
                                        }# close foreach 3
                                }
                                if ($third_ul_printed){
                                        $menu_html .= "</ul>\n"; $third_ul_printed=0;
                                }
                        }
                } # close foreach 2
                if ($second_ul_printed){$menu_html .= "</ul>\n"; $second_ul_printed=0;}
        }
        // the last li with a parent of 0 needs a different class..
        $menu_html .= "</ul>\n";
        $menu_html .= "</div>\n";
        return $menu_html;
}

Open in new window

Avatar of MatthewP
MatthewP
Flag of United Kingdom of Great Britain and Northern Ireland image

ASKER

BTW - will up points to 500, having probs getting some at the moment :(
ASKER CERTIFIED SOLUTION
Avatar of mespinozae
mespinozae
Flag of Costa Rica image

Link to home
membership
This content is only available to members.
To access this content, you must be a member of Experts Exchange.
Get Access
Yeah, i've thought about that. Was rather hoping that there'd be some cunning way of going through the results - it's essentially an ordering thing - if I had everything in order somehow i wouldn't have to keep loopi g through everything.

Cheers,
Matt
One thing that brought my attentions is this right here:
"In this example Phone is under Contact. Contact is ID 3, so I give Phone a parent ID of 3 and an ordering value of 1 (as email comes first  this also has parent of 3 but an ID of 0)."
I know you are fetching and setting this programmatically  but think its best if you keep it like all starting from zero or all starting from 1, makes a little more sense when looking it altogether.

in the end, no matter if you do it with multiple selects (using more php power) or a nicer database schema the important thing is that you do a lighter database operation, because with so many menus and a potentially large users portfolio, your database may suffer greatly.

One thing I can think of is perhaps a bit complicated.... just trying to help though :p something along this line
## one table only
(PK) item_id         integer, auto_increment, not_null
        is_menu       boolean, not_null
        item_level    integer, not_null
        item_text      varchar(15), not null
        parent_id     integer, default(0), not_null

So with this table you would have cyclic references (think thats the name...) meaning this table references to itself in a relation.
You can fetch all items whose item_level is 0 (meaning they are the top menu) AND they is_menu (meaning they have sub items), while they have sub items you keep fetching the next level, makes sense?
And you use the parent_id to check which one belongs to what, like this you can build your menu in a somewhat recursive way, im not sure about the resources consumption though or if its at all working but worth the shot I think :p
Hi & Thanks for the comments.

The thing is, the way it works is that the menu is editable by people, so items can be added at various times. These will all of course finish up at the end of the list (having a higher value in the id column which auto-increments) even if they are to appear at the beginning of the list.

I have started the numbering from zero, however the table actually contains various different menus, so when i select on "where menu_id = 4" for example, i may be starting with a lowest id of 50 or something for the first item in it.

I think the problem comes because once Im looking at that first item (say its id 0) I have to read through all the other data (say theres 300 items in the menu) to see if there's an item with a parent id of that- and that will need to be done for each item that does get pulled out. So if there is one, do it all again etc, if not move onto the next id in the list (next top level item) and do it all again.

Im doing order by parent_id first, so it pulls out all the top level straight away. So it works like this:

1. - Start looping through array of data
2. First item is first - ie parent_id of 0 and ordering of 0. Print it
3 - Start looping through array again
2. Does row have a parent id of 0? If yes, print it (bearing in mind the second parameter to order by was the 'ordering' so we know we're getting them in the correct order.
3. - Start looping through array again Now we're checking for items where the parent_id matches the id of the last one that matched.

etc etc.

Strange that this takes so long (well 30 seconds plus at the moment)

With multiple SQL queries:
- Select all where parent_id=0
- foreach of these, select where parent_id = the item's id
- foreach of these, select where parent_id = the item's id

mmm but this is still going to give 300 odd queries for a 300 item menu, which is a bit much?

Decidedly tricky one this, perhaps looking again at the way the data is stored is the answer? ie. have children and not parents?

Cheers again.
Looks like this is the only way this can be done - thanks!