Switch from base 36 to base 128 and use it for menu tree

Created on 27 December 2014, over 10 years ago

Updated 24 April 2025, 2 days ago

Problem/Motivation

This article http://bojanz.wordpress.com/2014/04/25/storing-hierarchical-data-materia... describes various ways to store materialized paths. Comments use base 36 + length prefix while menu stores the ids in a fixed number of columns. Neither is particularly efficient.

Proposed resolution

Use Base128 + length prefix. This creates always valid UTF-8 encoded paths -- using UTF-8 as an algorithm to encode numbers doesn't always result in valid UTF-8 (oh the irony). Think BOM and surrogates. Even counting for InnoDB index lengths, we are looking at tens of levels instead of a fixed nine: if there are less than 2M links then one path segment is 4 (or less but that's rare, already above 16384 we are looking at 3 bytes); if we allow for 128 bytes in the index then we are looking at 32 levels, if there are more then you still can do 25.

As for coding, the MongoDB storage has everything you need (since it works), most importantly encode128/decode128 functions and use it for comment threads and menu parents as well. To find children of a link, use ->condition('p', db_like($link['p']) . '%', 'LIKE'). To move children, do a simple search-replace on the p field (no need for preg; it's not like a given path is sometimes from the root sometimes not).

Remaining tasks

Do it.

User interface changes

None.

API changes

None. Easier before D8.0 really. After it, we are looking at schema changes which are never fun.

📌 Task

Status

Postponed: needs info

Version

11.0 🔥

Component

menu system

Created by

🇨🇦Canada chx

Live updates comments and jobs are added and updated live.

stale-issue-cleanup
To track issues in the developing policy for closing stale issues, [Policy, no patch] closing older issues

Incomplete comments

Comments & Activities

Not all content is available!

It's likely this issue predates Contrib.social: some issue and comment data are missing.

Comment 2 days ago →
🇺🇸United States smustgrave
Thank you for creating this issue to improve Drupal.

We are working to decide if this task is still relevant to a currently supported version of Drupal. There hasn't been any discussion here for over 8 years which suggests that this has either been implemented or is no longer relevant. Your thoughts on this will allow a decision to be made.

Since we need more information to move forward with this issue, the status is now Postponed (maintainer needs more info). If we don't receive additional information to help with the issue, it may be closed after three months.

Thanks!

contrib.social Blog FAQ Discussions

Production build 0.71.5 2024