1

I'm working on a system where users are sorted into groups, and then those groups are applied on files.

At a high level, what I need to do is to be able to pull out the 10 most recently-updated files that the user has access to, which I'm trying with a query like this:

SELECT
    files.id
FROM files
INNER JOIN user_groups
ON files.group_id = user_groups.group_id
WHERE user_groups.user_id = x
ORDER BY files.updated_at DESC
LIMIT 10

I understand that there's no index here that would really help, because the user_groups results are usually going to be smaller than files results, so it's almost always picked as the first table in the join. This means that it's always running a filesort, so it's really slow for users with access to millions of files.

I've reworked this query into two, so we pull out the list of groups that the user belongs to and execute on that instead:

SELECT
    files.id
FROM files
WHERE files.group_id IN (1, 2, 3, 4, 5...)
ORDER BY files.updated_at DESC
LIMIT 10

This is sometimes faster, but it still uses a filesort; I'm guessing that's because the optimal order here is really group_id, updated_at, which really doesn't work for this case.

The table structure looks like this:

CREATE TABLE `users` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  PRIMARY KEY (`id`),
) ENGINE=InnoDB AUTO_INCREMENT=22012 DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci;

CREATE TABLE `user_groups` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `user_id` int(10) COLLATE utf8_unicode_ci NOT NULL,
  `group_id` int(10) COLLATE utf8_unicode_ci NOT NULL,
  PRIMARY KEY (`id`),
  UNIQUE KEY `group_id_user_id_index` (`group_id`, `user_id`),
) ENGINE=InnoDB AUTO_INCREMENT=22012 DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci;

CREATE TABLE `files` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `group_id` int(10) COLLATE utf8_unicode_ci NOT NULL,
  `updated_at` timestamp NULL DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `group_id_index` (`group_id`),
  KEY `group_id_updated_at_index` (`group_id`, `updated_at`),
) ENGINE=InnoDB AUTO_INCREMENT=22012 DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci;

I've also tried adding a files_groups table in between, which solves this problem only if I do a STRAIGHT_JOIN:

SELECT
    files.id
FROM files
STRAIGHT_JOIN files_groups
ON files.id = files_groups.file_id
INNER JOIN user_groups
ON files.group_id = user_groups.group_id
WHERE user_groups.user_id = x
ORDER BY files.updated_at DESC
LIMIT 10

Adding in the STRAIGHT_JOIN means that it has to scan a lot more rows, unless the user is lucky enough to have access to the first 10.

I feel like there's just something I'm missing here. Is there a way that these tables or this query can be re-arranged to avoid the filesort here?

5
  • Thanks for this! It's definitely faster and eliminates the filesort, but in a query like this, the limit applies to total indexed rows, right? So if the user doesn't have access to the first 10 records, then it won't return anything.
    – chraume
    Mar 8 at 22:18
  • 1
    You might like to read dev.mysql.com/doc/refman/8.0/en/limit-optimization.html Mar 8 at 22:37
  • then you need to update to mysql 8 and use window function, there is the possibility of simulating it in 5.7 but that would slow it significant
    – nbk
    Mar 8 at 22:37
  • makes sense! 8 is on my roadmap, but not as soon as I'd like, unfortunately
    – chraume
    Mar 8 at 23:45

2 Answers 2

0

The second query needs this composite index:

 files:  INDEX(group_id, updated_at,  id)

1st:

files:  INDEX(group_id, updated_at,  id)
user_groups:  INDEX(user_id, group_id)

But that won't help much since the filtering is in one table but the ordering and is in the other. This rewrite may help:

SELECT files.id
    FROM files
    WHERE EXISTS ( SELECT 1 FROM user_groups
             WHERE user_groups.group_id = files.group_id
               AND user_groups.user_id = x
    ORDER BY files.updated_at DESC
    LIMIT 10; 

A many-to-many table should not have an id, but should have, for example

PRIMARY KEY(user, group),
INDEX(group, user)
2
  • Oh, wow, that query makes a huge difference 🤔 I'm genuinely not sure I understand why, but I really appreciate this!
    – chraume
    Mar 9 at 22:49
  • @chraume - Two tips: () IN ( SELECT... ) often optimizes poorly. () EXISTS ( SELECT 1 ... ) stops when it finds any matching row -- When this type of test is appropriate, it may be faster. The composite indexes and the many-to-many tip may be the real benefits.
    – Rick James
    Mar 9 at 23:00
0

Here's a dbfiddle with creation of test data and several queries.

A multicolumn index on (group_id,updated_at) can be used to find the most recent files in one group. Basically "WHERE group_id=constant ORDER BY group_id DESC, updated_at DESC" can be turned into an index scan, skipping the sort. This only works for one group. If several groups are used, then...

SELECT count(*) FROM files;

65536

SELECT files.* FROM files JOIN users_groups USING (group_id)
WHERE user_id=1 ORDER BY updated_at DESC LIMIT 10;

Execution time: 145.15ms

It uses the index to find files by group_id, but since several groups are selected, it cannot use the multicolumn index and sorts all files belonging to these groups.

SELECT files.* FROM files WHERE EXISTS(
   SELECT * FROM users_groups ug WHERE ug.user_id=1 AND ug.group_id=files.group_id
) ORDER BY updated_at DESC LIMIT 10;

Execution time: 53.39ms

This really the same query, but for some reason MySQL executes it faster.

SELECT foo.* FROM users_groups ug
JOIN LATERAL (SELECT * FROM files WHERE files.group_id=ug.group_id ORDER BY group_id DESC, updated_at DESC LIMIT 10) foo
USING (group_id) ORDER BY updated_at DESC LIMIT 10;

Execution time: 0.89ms

This one grabs the latest 10 files in each group using JOIN LATERAL. In case you never heard of it, it's like a dependent subquery: for each row in users_groups, the joined table expression is evaluated again, giving the latest 10 files in this group. The whole point here is that this uses the multicolumn index and skips the big sort.

The result of this step is not the desired final result, it contains extra rows which we must get rid of. So it is sorted again, which is very fast due to the small size.

This is the optimum implementation (it is much faster) but it requires a version of MySQL that supports LATERAL.

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.