[wp-trac] Re: [WordPress Trac] #5303: "Manage > Pages" becomes very slow with hundreds of pages

[WordPress Trac]

#5303: "Manage > Pages"  becomes very slow with hundreds of pages
-----------------------+----------------------------------------------------
 Reporter:  MartijnD   |        Owner:  anonymous
     Type:  task       |       Status:  closed   
 Priority:  low        |    Milestone:  2.5      
Component:  General    |      Version:           
 Severity:  normal     |   Resolution:  fixed    
 Keywords:             |  
-----------------------+----------------------------------------------------
Changes (by hailin):

  * status:  new => closed
  * resolution:  => fixed

Comment:

 Let N = number of pages
 The original algorithm takes O(N^x) where x>=2. That is why it is very
 slow to display pages when N is large (over 200)

 The proposed new algorithm accepts as input pages array sorted by
 post_parent, ID ASC.

 Then splice the array into two trunks:
 trunk#1 contains pages whose post_parent is 0
 turnk#2 contains pages whose post_parent > 0

 For every page is trunk#1, we look into trunk#2 to see if there is a
 child.
 If yes, we display the child page, remove the child page, then recursively
 examine trunk#2 again to see if there are nested pages to be displayed.

 We take advantage of the fact that child pages in trunk#2 is sorted by
 post_parent,
 And use heuristics to enable us to do minimal lookups needed.

 The time complexity is optimal for this problem – it is O(N).

 Note that this algorithm depends on the assumption that input pages are
 sorted  on post_parent, ID.  I just discovered that current wporg core has
 another bug which can cause cached pages in query results out of order.

-- 
Ticket URL: <http://trac.wordpress.org/ticket/5303#comment:6>
WordPress Trac <http://trac.wordpress.org/>
WordPress blogging software