MySQL Query to Show & Order an Infinite or Recursive Page Depth
I am attempting to write a SQL query that will give me a list of my CMS pages. The catch is that I want them displayed in the correct order with the sub pages appearing under their parent pages. I figured out how to do that with a little PHP.
The raw sample data that I have in my Pages table is shown (db_view.png), and the result on my website is shown (result.png). In the database, I store the page's parent page in a field, so I can query all the sub pages when I need to. All pages with a parent_id of -1 are top level pages.
In order to get that result, I had to run several queries and use some recursion. The code I used is below.
<?php
public function list_pages($parent_id = -1, &$data = null, $indent = 0)
{
if (!$data) $data = array();
$parent_id = (int)$parent_id;
$query = $this->db->query("SELECT * FROM Pages WHERE parent_id = $parent_id");
foreach ($query->result_array() as $row)
{
$row['indent'] = str_repeat('— ', $indent);
$data[] = $row;
/* now get the subpages if any */
$this->list_pages($row['page_id'], $data, $indent + 1);
}
return $data;
}
?>This uses the CodeIgniter framework, so some of the MySQL functions not the PHP-standard functions. Every time I retrieve a page from the DB, I check to see if there are any sub pages by calling the same function, passing the ever-growing $data array to itself to add more rows (pages) if it finds any.
This is technically a working solution, but it doesn't scale. The problem is that if my application has 1000 pages (unlikely, but bear with me), to get them in the right order, it has to query them all into memory as one giant PHP array. That's not what a database is designed to do. I should be able to select a few at a time in the order I want.
Maybe I should be setting up my table relationships up differently, but I know this concept is used in other areas, like this forum's threaded comment view. The comments can have an infinite hierarchy relationships, yet they are paginated and we only see a few at a time if the thread gets huge. So is this some how done by using SQL, or does the entire thread get loaded and sorted/split using PHP?
| Attachment | Size |
|---|---|
| db_view.png | 72.34 KB |
| result.png | 15.93 KB |
teammatt3 posted this at 15:18 — 12th June 2008.
He has: 2,102 posts
Joined: Sep 2003
I have had the same problems as you. The solution is on the SQL side of things, and it's kind of a pain to do (at least the solution I know about). There was an article on sitepoint about it and there is a lengthy section on it in my Pro MySQL book. I have never implemented it, but it's the only way I know about where recursion on the application code side isn't needed.
The technique is called "nested set model" and you were using the "adjacent list model" and there's another technique called "path enumeration model" to traverse hierarchical data - so says my book
pr0gr4mm3r posted this at 15:56 — 12th June 2008.
He has: 1,502 posts
Joined: Sep 2006
That sitepoint article is exactly what I need - thanks! I feel better knowing I was on the right track with the PHP solution. The code in that article strongly resembles the function I wrote up.
What is this book you speak of?
teammatt3 posted this at 16:07 — 12th June 2008.
He has: 2,102 posts
Joined: Sep 2003
Pro MySQL. I love it. It makes me seem so smart on these forums
. It's one of the only tech books I've read from cover to cover. I learned a ton about MySQL and SQL in general.
pr0gr4mm3r posted this at 03:25 — 18th June 2008.
He has: 1,502 posts
Joined: Sep 2006
I thought I would post back with what I ended up doing in case people were following.
I mostly followed that Sitepoint article that Matt posted except for a couple things.
1) I added an extra field in the database for the page depth, which is used to know how much to indent the page when creating a list. The article had some complex & confusing algorithm for finding it, but I figured that it doesn't change dynamically unless we edit a page, so why not store it in the table? It saves CPU & processing time when forming a page list.
2) I didn't implement the way of adding/deleting pages w/o reforming the entire tree...because I'm lazy. Calling the rebuild_tree() function when I create/delete pages is not a big deal. Optimizing the method of showing pages to visitors is way more important.
Here is the final function that I am using.
<?php
public function rebuild_tree($parent_id = -1, $left = 0, $depth = -1)
{
/* the right value of this node is the left value + 1 */
$right = $left + 1;
/* get all children of this node */
$query = $this->db->query("SELECT page_id FROM Pages WHERE parent_id = $parent_id ORDER BY created DESC");
foreach ($query->result_array() as $row)
{
/* does this page have children? */
$right = $this->rebuild_tree($row['page_id'], $right, $depth + 1);
}
/* update this page with the (possibly) new left, right, and depth values */
$query = $this->db->query("UPDATE Pages SET lft = $left, rgt = $right, depth = $depth WHERE page_id = $parent_id ORDER BY created DESC LIMIT 1");
/* return the right value of this node + 1 */
return $right + 1;
}
?>
Want to join the discussion? Create an account or log in if you already have one. Joining is fast, free and painless! We’ll even whisk you back here when you’ve finished.