Query optimization: Too many NOT IN clauses leading to slow performance

Nodeloc

I'm working on a custom feature for Flarum and I've encountered a performance issue. In one of my queries, I need to apply a series of NOT IN clauses to filter discussions based on user permissions for tags. However, when the dataset is large, this query becomes very slow due to full table scans. Here's the relevant part of the code:

class ScopeDiscussionVisibilityForAbility
{
    public function __invoke(User $actor, Builder $query, string $ability): void
    {
        // Automatic scoping should be applied to the global `view` ability,
        // and to arbitrary abilities that aren't subqueries of `view`.
        // For example, if we want to scope discussions where the user can
        // edit posts, this should apply.
        // But if we are expanding a restriction of `view` (for example,
        // `viewPrivate`), we shouldn't apply this query again.
        if (Str::startsWith($ability, 'view') && $ability !== 'view') {
            return;
        }

        // Avoid an infinite recursive loop.
        if (Str::endsWith($ability, 'InRestrictedTags')) {
            return;
        }

        // `view` is a special case where the permission string is represented by `viewForum`.
        $permission = $ability === 'view' ? 'viewForum' : $ability;

        // Restrict discussions where users don't have necessary permissions in all tags.
        // We use a double notIn instead of a doubleIn because the permission must be present in ALL tags,
        // not just one.
        $query->where(function ($query) use ($actor, $permission) {
            $query
                ->whereNotIn('discussions.id', function ($query) use ($actor, $permission) {
                    return $query->select('discussion_id')
                        ->from('discussion_tag')
                        ->whereNotIn('tag_id', function ($query) use ($actor, $permission) {
                            Tag::query()->setQuery($query->from('tags'))->whereHasPermission($actor, $permission)->select('tags.id');
                        });
                })
                ->orWhere(function ($query) use ($actor, $permission) {
                    // Allow extensions a way to override scoping for any given permission.
                    $query->whereVisibleTo($actor, "{$permission}InRestrictedTags");
                });
        });

        // Hide discussions with no tags if the user doesn't have that global
        // permission.
        if (! $actor->hasPermission($permission)) {
            $query->has('tags');
        }
    }
}

The issue is that the nested NOT IN clauses cause performance bottlenecks when dealing with a large number of discussions and tags.

Can anyone suggest a more optimized approach to achieve the same result without relying so heavily on NOT IN? Perhaps there's a more efficient query structure or indexing strategy that can help with large datasets.

Thanks in advance!

SychO

You should share details/code about the query/logic you are building. Hard to provide any help without that.

Nodeloc

SychO Here is the SQL from Mysql slow log.

( SELECT
	`discussions`.* 
	FROM
		`discussions` 
	WHERE
		(
			`discussions`.`id` NOT IN (
			SELECT
				`discussion_id` 
			FROM
				`discussion_tag` 
			WHERE
				`tag_id` NOT IN (
				SELECT DISTINCT
					`tags`.`id` 
				FROM
					`tags`
					INNER JOIN `discussion_tag` ON `tags`.`id` = `discussion_tag`.`tag_id`
					INNER JOIN `discussions` ON `discussion_tag`.`discussion_id` = `discussions`.`id`
					INNER JOIN `tags` AS `perm_tags` ON `tags`.`id` = `perm_tags`.`id` 
					OR `tags`.`parent_id` = `perm_tags`.`id` 
					AND (
						`perm_tags`.`is_restricted` = 1 
					AND `perm_tags`.`id` IN ( '13', '27' )) 
					OR `perm_tags`.`is_restricted` = 0 
				))) 
		AND (
			`discussions`.`is_private` = 0 
			OR (((
						`discussions`.`is_approved` = 0 
						AND (
							`discussions`.`user_id` = 2925 
							OR ((
									`discussions`.`id` NOT IN (
									SELECT
										`discussion_id` 
									FROM
										`discussion_tag` 
									WHERE
										`tag_id` NOT IN (
										SELECT DISTINCT
											`tags`.`id` 
										FROM
											`tags`
											INNER JOIN `discussion_tag` ON `tags`.`id` = `discussion_tag`.`tag_id`
											INNER JOIN `discussions` ON `discussion_tag`.`discussion_id` = `discussions`.`id`
											INNER JOIN `tags` AS `perm_tags` ON `tags`.`id` = `perm_tags`.`id` 
											OR `tags`.`parent_id` = `perm_tags`.`id` 
										AND ( `perm_tags`.`is_restricted` = 1 AND 0 = 1 )))) 
							AND EXISTS ( SELECT * FROM `tags` INNER JOIN `discussion_tag` ON `tags`.`id` = `discussion_tag`.`tag_id` WHERE `discussions`.`id` = `discussion_tag`.`discussion_id` ))))))) 
		AND (
			`discussions`.`hidden_at` IS NULL 
			OR `discussions`.`user_id` = 2925 
			OR ((
					`discussions`.`id` NOT IN (
					SELECT
						`discussion_id` 
					FROM
						`discussion_tag` 
					WHERE
						`tag_id` NOT IN (
						SELECT DISTINCT
							`tags`.`id` 
						FROM
							`tags`
							INNER JOIN `discussion_tag` ON `tags`.`id` = `discussion_tag`.`tag_id`
							INNER JOIN `discussions` ON `discussion_tag`.`discussion_id` = `discussions`.`id`
							INNER JOIN `tags` AS `perm_tags` ON `tags`.`id` = `perm_tags`.`id` 
							OR `tags`.`parent_id` = `perm_tags`.`id` 
						AND ( `perm_tags`.`is_restricted` = 1 AND 0 = 1 )))) 
			AND EXISTS ( SELECT * FROM `tags` INNER JOIN `discussion_tag` ON `tags`.`id` = `discussion_tag`.`tag_id` WHERE `discussions`.`id` = `discussion_tag`.`discussion_id` ))) 
		AND (
			`discussions`.`comment_count` > 0 
			OR `discussions`.`user_id` = 2925 
			OR ((
					`discussions`.`id` NOT IN (
					SELECT
						`discussion_id` 
					FROM
						`discussion_tag` 
					WHERE
						`tag_id` NOT IN (
						SELECT DISTINCT
							`tags`.`id` 
						FROM
							`tags`
							INNER JOIN `discussion_tag` ON `tags`.`id` = `discussion_tag`.`tag_id`
							INNER JOIN `discussions` ON `discussion_tag`.`discussion_id` = `discussions`.`id`
							INNER JOIN `tags` AS `perm_tags` ON `tags`.`id` = `perm_tags`.`id` 
							OR `tags`.`parent_id` = `perm_tags`.`id` 
						AND ( `perm_tags`.`is_restricted` = 1 AND 0 = 1 )))) 
			AND EXISTS ( SELECT * FROM `tags` INNER JOIN `discussion_tag` ON `tags`.`id` = `discussion_tag`.`tag_id` WHERE `discussions`.`id` = `discussion_tag`.`discussion_id` ))) 
		AND NOT EXISTS ( SELECT 1 FROM `discussion_user` WHERE `discussions`.`id` = `discussion_id` AND `user_id` = 2925 AND `subscription` = 'ignore' ) 
		AND `discussions`.`id` NOT IN (
		SELECT
			`discussion_id` 
		FROM
			`discussion_tag` 
		WHERE
		`tag_id` IN ( SELECT `tag_id` FROM `tag_user` WHERE `user_id` = 2925 AND `subscription` = 'hide' )) 
		AND (
			`discussions`.`id` NOT IN (
			SELECT DISTINCT
				`discussion_id` 
			FROM
				`discussion_tag` 
			WHERE
			`tag_id` IN ( 5, 27, 31 )) 
			OR (
				`discussions`.`user_id` IN (
					155,
					614,
					945,
					1506,
					2901,
					3346,
					4388,
					463,
					535,
					1267,
					1345,
					1458,
					1700,
					2294,
					2601,
					3677,
					3686,
					3761,
					3956,
					4320,
					4328,
					4686,
					7913,
					8157,
					8158,
					9699,
					9708,
					9965,
					10785 
				))) 
	ORDER BY
		`last_posted_at` DESC 
		LIMIT 21 
	) UNION
	(
	SELECT
		`discussions`.* 
	FROM
		`discussions` 
	WHERE
		(
			`discussions`.`id` NOT IN (
			SELECT
				`discussion_id` 
			FROM
				`discussion_tag` 
			WHERE
				`tag_id` NOT IN (
				SELECT DISTINCT
					`tags`.`id` 
				FROM
					`tags`
					INNER JOIN `discussion_tag` ON `tags`.`id` = `discussion_tag`.`tag_id`
					INNER JOIN `discussions` ON `discussion_tag`.`discussion_id` = `discussions`.`id`
					INNER JOIN `tags` AS `perm_tags` ON `tags`.`id` = `perm_tags`.`id` 
					OR `tags`.`parent_id` = `perm_tags`.`id` 
					AND (
						`perm_tags`.`is_restricted` = 1 
					AND `perm_tags`.`id` IN ( '13', '27' )) 
					OR `perm_tags`.`is_restricted` = 0 
				))) 
		AND (
			`discussions`.`is_private` = 0 
			OR (((
						`discussions`.`is_approved` = 0 
						AND (
							`discussions`.`user_id` = 2925 
							OR ((
									`discussions`.`id` NOT IN (
									SELECT
										`discussion_id` 
									FROM
										`discussion_tag` 
									WHERE
										`tag_id` NOT IN (
										SELECT DISTINCT
											`tags`.`id` 
										FROM
											`tags`
											INNER JOIN `discussion_tag` ON `tags`.`id` = `discussion_tag`.`tag_id`
											INNER JOIN `discussions` ON `discussion_tag`.`discussion_id` = `discussions`.`id`
											INNER JOIN `tags` AS `perm_tags` ON `tags`.`id` = `perm_tags`.`id` 
											OR `tags`.`parent_id` = `perm_tags`.`id` 
										AND ( `perm_tags`.`is_restricted` = 1 AND 0 = 1 )))) 
							AND EXISTS ( SELECT * FROM `tags` INNER JOIN `discussion_tag` ON `tags`.`id` = `discussion_tag`.`tag_id` WHERE `discussions`.`id` = `discussion_tag`.`discussion_id` ))))))) 
		AND (
			`discussions`.`hidden_at` IS NULL 
			OR `discussions`.`user_id` = 2925 
			OR ((
					`discussions`.`id` NOT IN (
					SELECT
						`discussion_id` 
					FROM
						`discussion_tag` 
					WHERE
						`tag_id` NOT IN (
						SELECT DISTINCT
							`tags`.`id` 
						FROM
							`tags`
							INNER JOIN `discussion_tag` ON `tags`.`id` = `discussion_tag`.`tag_id`
							INNER JOIN `discussions` ON `discussion_tag`.`discussion_id` = `discussions`.`id`
							INNER JOIN `tags` AS `perm_tags` ON `tags`.`id` = `perm_tags`.`id` 
							OR `tags`.`parent_id` = `perm_tags`.`id` 
						AND ( `perm_tags`.`is_restricted` = 1 AND 0 = 1 )))) 
			AND EXISTS ( SELECT * FROM `tags` INNER JOIN `discussion_tag` ON `tags`.`id` = `discussion_tag`.`tag_id` WHERE `discussions`.`id` = `discussion_tag`.`discussion_id` ))) 
		AND (
			`discussions`.`comment_count` > 0 
			OR `discussions`.`user_id` = 2925 
			OR ((
					`discussions`.`id` NOT IN (
					SELECT
						`discussion_id` 
					FROM
						`discussion_tag` 
					WHERE
						`tag_id` NOT IN (
						SELECT DISTINCT
							`tags`.`id` 
						FROM
							`tags`
							INNER JOIN `discussion_tag` ON `tags`.`id` = `discussion_tag`.`tag_id`
							INNER JOIN `discussions` ON `discussion_tag`.`discussion_id` = `discussions`.`id`
							INNER JOIN `tags` AS `perm_tags` ON `tags`.`id` = `perm_tags`.`id` 
							OR `tags`.`parent_id` = `perm_tags`.`id` 
						AND ( `perm_tags`.`is_restricted` = 1 AND 0 = 1 )))) 
			AND EXISTS ( SELECT * FROM `tags` INNER JOIN `discussion_tag` ON `tags`.`id` = `discussion_tag`.`tag_id` WHERE `discussions`.`id` = `discussion_tag`.`discussion_id` ))) 
		AND NOT EXISTS ( SELECT 1 FROM `discussion_user` WHERE `discussions`.`id` = `discussion_id` AND `user_id` = 2925 AND `subscription` = 'ignore' ) 
		AND `discussions`.`id` NOT IN (
		SELECT
			`discussion_id` 
		FROM
			`discussion_tag` 
		WHERE
		`tag_id` IN ( SELECT `tag_id` FROM `tag_user` WHERE `user_id` = 2925 AND `subscription` = 'hide' )) 
		AND (
			`discussions`.`id` NOT IN (
			SELECT DISTINCT
				`discussion_id` 
			FROM
				`discussion_tag` 
			WHERE
			`tag_id` IN ( 5, 27, 31 )) 
			OR (
				`discussions`.`user_id` IN (
					155,
					614,
					945,
					1506,
					2901,
					3346,
					4388,
					463,
					535,
					1267,
					1345,
					1458,
					1700,
					2294,
					2601,
					3677,
					3686,
					3761,
					3956,
					4320,
					4328,
					4686,
					7913,
					8157,
					8158,
					9699,
					9708,
					9965,
					10785 
				))) 
		AND `is_sticky` = 1 
		LIMIT 21 
	) 
ORDER BY
	is_sticky 
	AND NOT EXISTS ( SELECT 1 FROM `discussion_user` AS `sticky` WHERE `sticky`.`discussion_id` = `id` AND `sticky`.`user_id` = 2925 AND `sticky`.`last_read_post_number` >= `last_post_number` ) 
	AND last_posted_at > '2025-01-20 17:27:14' DESC,
	`last_posted_at` DESC 
	LIMIT 21;

And here is the EXPLAIN

As you see, It's a big SQL with many NOT IN.

SychO

Not really what I meant.

If you can explain what you are trying to do, and how you're doing it. Maybe show some snippets of your extension code, that would allow others to understand the problem and perhaps suggest alternative optimal ways of doing things.