Improving WP hierarchical data structure / Use SQL trees
|Reported by:||hailin||Owned by:||hailin|
Currently WordPress uses simple Adjacency List Model to manage hierarchical data, including pages, categories, terms.
As the size of data sets grow larger and larger, we run into inherent limitations imposed by our current data structure.
When there are 5500 pages, in order to list a particular subset of pages,
we have to retrieve all of them from the db (step 1), and enumerate through each one to construct a sub-tree (step 2).
We did some algorithmic improvement before to improves part (#2) by reducing the complexity from O(n2) to O(n) in
function page_rows($pages, $pagenum = 1, $per_page = 20)
it reduced the processing time in step 2 from 20 sec to 0.3 sec in a case when there are ~2000 pages.
However, step 1 is still a major hurdle, because limitations of our current pages data structure.
In the case of one blog with 5500+ pages, it takes 33 seconds to display wp-admin/edit-pages.php. In particular, 17 seconds are spent in update_post_caches(), and 11 seconds are spent in apply_filters('the_posts', $this->posts), simply because we are operating over all 5500+ pages! And because the we only store rudimentary parent-child information in the table, we had to query the whole 5500 pages.
If we improve the data structure and store the pages in efficient hierarchical order in db, then for every operation, we could retrieve only the ones we want, eg, 30 pages at a time. This can bring down the page load time from 33 seconds to sub-second, substantially improving user experience.
The above is just one example, the same can be applied to any other cases involving
hierarchical data sets.
The potential change will have a lot of ripple effects, as it may affect a lot of other functions or even maybe themes, which depend on the existing behavior. So we should proceed cautiously and pay great attention to backward compatibility, etc.
We could consider:
Modified Preorder Tree Traversal Algorithm
Or the ones recommended in the classical book:
Besides, WordPress is evolving into a CMS, and that mandates us having a better foundation on which to manipulate various data formats. Such a solid, efficient, elegant, robust data structure will serve as a strong foundation for us to evolve well into the future.
Change History (18)
- Priority changed from high to normal
- Type changed from enhancement to feature request
- Component changed from General to Optimization
- Priority changed from normal to low
- Severity changed from normal to minor
- Summary changed from Improving WP hierarchical data structure to Improving WP hierarchical data structure / Use SQL trees
- Owner changed from anonymous to hailin
- Status changed from new to assigned