1

I represent trees in MySql using nested sets.

There are several different "types" of tree and every user can have one tree of each type.

The table looks something like this:

CREATE TABLE folders (
    id INT UNSIGNED NOT NULL AUTO_INCREMENT,
    typeId TINYINT(1) UNSIGNED NOT NULL,
    userId INT UNSIGNED NOT NULL,
    lft INT NOT NULL,
    rgt INT NOT NULL,
    title VARCHAR(50) DEFAULT NULL,
    PRIMARY KEY(id),
    FOREIGN KEY(typeId) REFERENCES folderTypes(id),
    FOREIGN KEY(userId) REFERENCES users(id) ON DELETE CASCADE
) ENGINE=InnoDB;

A query to insert a node somewhere in a tree, for example, will then look something like this:

START TRANSACTION;

# given id, lock relevant rows

SELECT          f2.id 
FROM            folders f1, folders f2 
WHERE           f1.id = ? and 
                f1.typeId = f2.typeId AND
                f1.userId = f2.userId
FOR UPDATE;

# given id, select typeId, userId & lft

SELECT          @typeId := typeId, @userId := userId, @lft := lft 
FROM            folders 
WHERE           id = ?;

# update tree

UPDATE          folders 
SET             rgt = rgt + 2 
WHERE           rgt > @lft and
                typeId = @typeId AND
                userId = @userId;

UPDATE          folders
SET             lft = lft + 2
WHERE           lft > @lft and
                typeId = @typeId AND        
                userId = @userId;

# insert node

INSERT INTO     folders (typeId, userId, title, lft, rgt)
VALUES          (@typeId, @userId, 'new', (@lft + 1), (@lft + 2));  

COMMIT;

This works fine. However I am noticing that as more trees & rows get added, this query, and the other, similar queries for node manipulation in nested sets, are not quite as fast as they used to be.

I did read this article (https://explainextended.com/2009/09/29/adjacency-list-vs-nested-sets-mysql/) however I need to use InnoDB, so it seems like a spatial index wont work for me. (And tbh even if I could switch to MyISAM for this, refactoring all of the queries is not really an option right now.)

I am wondering: Are there any other indexes that can / should be added to this InnoDB table that will help MySql out a bit?

4
  • Left-right is a nifty toy. But it is terrible for performance after a few dozen items. Abandon that tree schema!
    – Rick James
    Commented Sep 18, 2022 at 3:37
  • @Rick -- thanks for the reply. That's likely the correct answer, but unfortunately that isn't an option for me, in the short term at least. I was hoping there might be some low-hanging fruit to keep things happy as-is for a bit longer. Commented Sep 18, 2022 at 3:52
  • This comment is not related to your query optimization request, but please modernize your JOIN syntax. The old comma-style join syntax has been obsolete since 1992. Commented Sep 18, 2022 at 16:49
  • Please provide SHOW CREATE TABLE folders; I'll try to devise the optimal indexes for these queries.
    – Rick James
    Commented Sep 18, 2022 at 17:37

1 Answer 1

2
CREATE INDEX folders_type_user_rgt ON folders(typeId, userId, rgt);
CREATE INDEX folders_type_user_lft ON folders(typeId, userId, lft);

You already have single-column indexes on typeId and userId; they were created automatically by your foreign keys.

These compound indexes should help your UPDATE statements better than the single-column indexes.

You can verify that the indexes are used by using EXPLAIN.

5
  • 1
    Also, considering that lft < rgt in all rows in the nested sets model, they could have just the first index and combine the two UPDATE statements in one. Something like: UPDATE folders SET rgt = rgt + 2, lft = CASE WHEN lft > @lft THEN lft + 2 ELSE lft END WHERE rgt > @lft AND typeId = @typeId AND userId = @userId; Commented Sep 18, 2022 at 17:27
  • @bill awesome, thanks. Indexes have always seemed a bit mysterious to me, but I have spent the afternoon reading up on composite indexes and how to use them properly, and that makes perfect sense now. Commented Sep 18, 2022 at 23:55
  • also @ypercube, that's an interesting suggestion of combining the queries like that -- I will experiment with this a bit. Thanks for the suggestion! Commented Sep 18, 2022 at 23:57
  • You might like my presentation How to Design Indexes, Really, or the video. Commented Sep 19, 2022 at 0:22
  • 1
    That's great stuff Bill -- thanks for sharing those links! Commented Sep 19, 2022 at 2:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.