A follow-on to: http://drupal.org/node/151583 for issues not resolved by that patch.

The queries and the indices on {menu_links} and {menu_router} need to be optimized, since many of the queries now will perform a scan and/or tablesort since there is not an appropriate index.

CommentFileSizeAuthor
#24 menu_opt_9.patch34.35 KBpwolanin
#21 menu_opt_8.patch34.01 KBpwolanin
#19 menu_opt_7.patch30.24 KBpwolanin
#17 explain.txt17.49 KBpwolanin
#16 menu_opt_6.patch29.35 KBpwolanin
#15 menu_opt_5.patch26.23 KBpwolanin
#13 menu_opt_4.patch26.22 KBpwolanin
#9 menu_opt_3.patch25.1 KBpwolanin
#6 menu_opt_2.patch21.72 KBpwolanin
#4 menu_opt_1.patch10.07 KBpwolanin
Support from Acquia helps fund testing for Drupal Acquia logo

Comments

pwolanin’s picture

pwolanin CreditAttribution: pwolanin commented
Priority: Normal » Critical

this really needs to be tackled

BioALIEN’s picture

BioALIEN CreditAttribution: BioALIEN commented

+1 for this. I just had a look at the menu and nodes table.

To be honest, the menu system is not the only place that needs some optimisation!

pwolanin’s picture

pwolanin CreditAttribution: pwolanin commented

ok, starting with the most important query:

mysql> explain SELECT * FROM menu_router WHERE path IN ('node', 'node/%', 'node/1') ORDER BY fit DESC;
+----+-------------+-------------+-------+---------------+---------+---------+------+------+-----------------------------+
| id | select_type | table       | type  | possible_keys | key     | key_len | ref  | rows | Extra                       |
+----+-------------+-------------+-------+---------------+---------+---------+------+------+-----------------------------+
|  1 | SIMPLE      | menu_router | range | PRIMARY       | PRIMARY |     765 | NULL |    3 | Using where; Using filesort |

Since we're using a range query IN(), there seems from the MySQL docs no way to avoid the filesort. Changing the PRIMARY key to (path, fit) does not change the outcome of this.

pwolanin’s picture

pwolanin CreditAttribution: pwolanin commented
FileSize
menu_opt_1.patch10.07 KB

Attached is a starting patch. Doesn't work yet - don't try it.

Thanks to an idea by David Strauss, chx and I are also working on a scheme to make 'masks' so that we only issue the above query against {menu_router} for a smaller set of possible wildcards. We'd keep a list of which ones actually exist, rather than blindly building all.

pwolanin’s picture

pwolanin CreditAttribution: pwolanin commented

Adding into this a helpful patch by dmitrig01: http://drupal.org/node/164640

pwolanin’s picture

pwolanin CreditAttribution: pwolanin commented
FileSize
menu_opt_2.patch21.72 KB

This new patch seems to work, but still needs menu masks (or maybe that should be a separate issue).

Note - increases max depth to 9.

Also, I played a bit with MySQL and these indices seem to behave well for all the queries, but more testing appreciated.

pwolanin’s picture

pwolanin CreditAttribution: pwolanin commented
Status: Active » Needs review
pwolanin’s picture

pwolanin CreditAttribution: pwolanin commented
Status: Needs review » Needs work

per: http://drupal.org/node/164813 the queries need to order by every pN up to N = MENU_MAX_DEPTH, and the index should be extended to the last column also.

pwolanin’s picture

pwolanin CreditAttribution: pwolanin commented
Status: Needs work » Needs review
FileSize
menu_opt_3.patch25.1 KB

Also added menu masks - this is a mechanism to only look for those paths with patterns of wildcards that actually exist in the router table. With all core modules enabled, this reduces the to ~20 from 32 the number of possible ancestors returned by function menu_get_ancestors() for a path with 6 parts. I think the query in menu_get_item() will be roughly linear (less latency, query setup, and sorting) in this number, so this represents a significant boost. (note - credit goes to David Strauss for the general concept).

Per discussion with Karoly, this boost should also make it reasonably safe to increase MENU_MAX_PARTS to 7.

Note - the change to the way 'hidden' links are handled is partly to get better use of the indices, but will also help with this issue: http://drupal.org/node/155624

chx’s picture

chx CreditAttribution: chx commented

I still think the best would be to store the masks in appropriate order and iterate them instead of what happens now. This also will help the performance esp for longer paths.

chx’s picture

chx CreditAttribution: chx commented

Also, I would like point out an error of mine on IRC, the number of posible ancestors for six depth is not 32 but 63 -- 32 are the exact six deep ancestors, 16 are the five long ones and so on. So we are down to ~20 from 63, that's a big change , though I am still surprised, I would have expected even less... I will test this throughly later and check a dump of the masks with all modules enabled.

pwolanin’s picture

pwolanin CreditAttribution: pwolanin commented

@chx - I tried your original suggestion - it did not work. The correct ancestors are not returned. This code would need a much more radical re-write in order to be able to iterate over the masks.

pwolanin’s picture

pwolanin CreditAttribution: pwolanin commented
FileSize
menu_opt_4.patch26.22 KB

@chx - ok, well I think *can* make it work the other way (see attached patch), but I think the patch above is more efficient for typical (i.e. short) paths.

The reason - the way you suggested (iterating over all masks) means that even for a path with 1 part (e.g. /admin) we have to run through the loop ~20 times instead of once. The way I wrote it above, the number of iterations is determined by the #parts. Obviously, this will become less efficient as we look at paths with 5 or 6 parts.

So, which is the better tradeoff?

chx’s picture

chx CreditAttribution: chx commented

Aye but this way you only run through a very tight small loop while the former loop runs the inner one as well. The latter is better and I checked the new menu_get_ancestors function and it works as it should.

pwolanin’s picture

pwolanin CreditAttribution: pwolanin commented
Assigned: Unassigned » pwolanin
FileSize
menu_opt_5.patch26.23 KB

minor code comment fix.

pwolanin’s picture

pwolanin CreditAttribution: pwolanin commented
FileSize
menu_opt_6.patch29.35 KB

This patch reworks the indices a little more based on extensive use of MySQL's EXPLAIN utility (details to follow).

This patch also fixes a minor bug in menu_tree_page_data() and refactors code that was duplicated 3x into a single helper function.

pwolanin’s picture

pwolanin CreditAttribution: pwolanin commented
FileSize
explain.txt17.49 KB

see attached document for before/after comparison of EXPLAIN results for the 2 different sets of indices for common queries.

pwolanin’s picture

pwolanin CreditAttribution: pwolanin commented

PS - this is with MySQL 5.0.45 (community edition).

pwolanin’s picture

pwolanin CreditAttribution: pwolanin commented
FileSize
menu_opt_7.patch30.24 KB

improved patch with additional option for dynamic translation of page/link titles.

chx’s picture

chx CreditAttribution: chx commented

Changes are:

  1. Use of masks. Here is an example. If you are at user/1/foo/bar and there is no path which is stored like something/%/%/anything then there is no point in checking for user/%/%/bar because it can not match. So, we store possible matches at router build time thus longer paths make very little trouble and use them at runtime. The way code is done, there is a very tight small loop (for - if) which runs 2**N-1 times for N long paths -- but the inner loop does not run nor do we create an immense sized IN (...) query. As basically every piece that we add to IN makes the query run again, there is indeed a near-linear speedup thanks to this.
  2. Simplified queries -- already we had hidden elements queries, now we query callbacks as well. In current HEAD because of the hidden (disabled in menu module, MENU_SUGGESTED_ITEM in code) elements we already check for hidden, it's not a big difference.
  3. The local tasks is queried a number of times (normally three) and dmitri (hats off!) changed an empty to isset so that we only run the necessary query once on a non-tab page. Nice job.
  4. Through careful analysis many useful indexes are added.
  5. A bug in the title localization is fixed, this did not manifest in core earlier, if you have a non-t title callback and the user edited the link title then that callback was not called. Bummer. Also, title arguments should unserialize as every other arguments do. A future patch might fix the menu module UI so that you can't even edit the title of non-t title callback entries but this needs discussion so let's not clutter this issue with that.

With all that said, codewise this is ready. I hope someone will do a functional review soon...

pwolanin’s picture

pwolanin CreditAttribution: pwolanin commented
FileSize
menu_opt_8.patch34.01 KB

thanks to interactive review by webernet - additional fixes:

don't show Primary/Secondary link if the link is disabled.

If a menu link save fails, menu module should show an error message (see also: http://drupal.org/node/165675 )

cleanup whitespace problems.

webernet’s picture

webernet CreditAttribution: webernet commented

Tested patch in #19, everything seems to be working properly. The patch in #21 looks good, and should fix the minor issues that were found during testing.

Note: This patch also fixes http://drupal.org/node/164813

chx’s picture

chx CreditAttribution: chx commented
Status: Needs review » Reviewed & tested by the community

So, I read the code (more than once, as the patch progressed), webernet checked the functionality... this seems like a patch ready.

pwolanin’s picture

pwolanin CreditAttribution: pwolanin commented
FileSize
menu_opt_9.patch34.35 KB

minor additional suggestion from webernet - use $type = 'error' for the drupal_set message calls if a link can't be saved.

Gábor Hojtsy’s picture

Gábor Hojtsy
he/him
Primary language Hungarian
Location Hungary
CreditAttribution: Gábor Hojtsy commented
Status: Reviewed & tested by the community » Needs review

I checked the patch, and it looks good. But although you bumped MENU_MAX_PARTS, the help module related $empty arrays are not modified. I would like to reiterate here, that those might be better off generated depending on MENU_MAX_PARTS, especially now that you have included more generated arrays in this patch too.

pwolanin’s picture

pwolanin CreditAttribution: pwolanin commented

@Gabor - I can certainly increase it - I just didn't bother since it already has 12 parts - still well beyond the seven allowed with this patch.

chx’s picture

chx CreditAttribution: chx commented
Status: Needs review » Reviewed & tested by the community

That is just for returning help text - so the dev would want to specify help based on > 12 args to care -- who the heck writes help based on a path like part1/part2/part3/......part12 ? The 12 is harmless extreme overkill already.

Dries’s picture

Dries CreditAttribution: Dries commented

I've reviewed the patch and I've no objections. As Gabor had a remark, I'll leave it up to him to commit this patch (if he's satisfied with the answer he got).

Dries’s picture

Dries CreditAttribution: Dries commented
Status: Reviewed & tested by the community » Fixed

I went ahead and committed this patch because it was holding up a potential performance improvement. :)

Gábor Hojtsy’s picture

Gábor Hojtsy
he/him
Primary language Hungarian
Location Hungary
CreditAttribution: Gábor Hojtsy commented

Great. I only had some reservations about the side effect of this patch with help module, but those were already thought of, so I fine with this patch being committed.

cburschka’s picture

cburschka
they
CreditAttribution: cburschka commented

For some reason, this change broke my test site. I've poked around a bit and it seems that menu_masks stays an empty array when it is saved in _menu_router_rebuild. This causes menu_get_ancestors to return empty arrays as well, as its foreach loop isn't entered.

The end result is this:

You have an error in your SQL syntax; check the manual that corresponds to your MySQL server version for the right syntax to use near ') ORDER BY fit DESC LIMIT 0, 1' at line 1 query: SELECT * FROM head_menu_router WHERE path IN () ORDER BY fit DESC LIMIT 0, 1 in /home/.jordon/cburschka/software/drupal-versions/head/includes/database.mysqli.inc on line 154.

(And 404 on all pages, of course)

I'll research a bit more to see why the rebuilding function doesn't properly fill the $masks array.

Gábor Hojtsy’s picture

Gábor Hojtsy
he/him
Primary language Hungarian
Location Hungary
CreditAttribution: Gábor Hojtsy commented
Status: Fixed » Active

That comment makes this active, then. Please set it back to fixed, if you find the issue is not related. Or post pointers/patches on how to fix it. Thanks!

pwolanin’s picture

pwolanin CreditAttribution: pwolanin commented

@Arancaytar - are you still seeing this? I have no other such reports.

chx’s picture

chx CreditAttribution: chx commented
Status: Active » Postponed (maintainer needs more info)
chx’s picture

chx CreditAttribution: chx commented
Status: Postponed (maintainer needs more info) » Closed (fixed)

Three weeks no updates. This issue is done.