Оптимизация «ORDER BY», когда результирующий набор очень большой и его нельзя упорядочить по индексу

Question

Как сделать так, чтобы предложение ORDER BY с небольшим LIMIT (т.е. 20 строк за раз) быстро возвращалось, когда я не могу использовать индекс для удовлетворения порядка строк?

Допустим, я хотел бы получить определенное количество заголовков из таблицы 'узел' (упрощенно ниже). Кстати, я использую MySQL.

node_ID INT(11) NOT NULL auto_increment,
node_title VARCHAR(127) NOT NULL,
node_lastupdated INT(11) NOT NULL,
node_created INT(11) NOT NULL

Но мне нужно ограничить количество возвращаемых строк только теми, к которым у определенного пользователя есть доступ. Многие пользователи имеют доступ к большому количеству узлов. У меня есть эта информация, предварительно рассчитанная в большой справочной таблице (попытка упростить задачу), где первичный ключ охватывает оба столбца, а наличие строки означает, что группа пользователей имеет доступ к этому узлу:

viewpermission_nodeID INT(11) NOT NULL,
viewpermission_usergroupID INT(11) NOT NULL

Поэтому мой запрос содержит что-то вроде

FROM
  node
  INNER JOIN viewpermission ON
    viewpermission_nodeID=node_ID
    AND viewpermission_usergroupID IN (<...usergroups of current user...>)

... и я также использую GROUP BY или DISTINCT, чтобы узел возвращался только один раз, даже если две пользовательские группы пользователей имеют доступ к этому узлу.

Моя проблема в том, что предложение ORDER BY, которое сортирует результаты по дате создания или последней обновленной дате, по-видимому, не может использовать индекс, поскольку возвращаемые строки зависят от значений в другой таблице viewpermission.

Поэтому MySQL должен будет найти все строк, которые соответствуют критериям, а затем отсортировать их все самостоятельно. Если для конкретного пользователя существует один миллион строк, и мы хотим просмотреть, скажем, последние 100 или 100-200 строк, упорядоченных по последнему обновлению, БД необходимо выяснить, какой миллион строк может видеть пользователь, отсортировать весь этот набор результатов, прежде чем он сможет вернуть эти 100 строк, верно?

Есть ли какой-нибудь творческий способ обойти это? Я думал так:

• Каким-то образом добавить даты в таблицу поиска viewpermission, чтобы я мог построить индекс, содержащий даты, а также разрешения. Это возможность, я думаю.

Редактировать: Упрощенный вопрос

Возможно, я могу упростить вопрос, переписав его так:

Есть ли способ переписать этот запрос или создать индекс для следующего, чтобы индекс мог использоваться для упорядочения (а не только для выбора строк)?

SELECT nodeid
FROM lookup
WHERE
  usergroup IN (2, 3)
GROUP BY
  nodeid

Индекс в (usergroup) позволяет части WHERE удовлетворяться индексом, но GROUP BY принудительно создает временную таблицу и файловую сортировку для этих строк. Индекс на (nodeid) ничего не делает для меня, потому что для предложения WHERE нужен индекс с пользовательской группой в качестве первого столбца. Индекс on (usergroup, nodeid) вызывает временную таблицу и сортировку файлов, поскольку GROUP BY не первый столбец индекса, который может изменяться.

Какие-нибудь решения?

Answer 1

Могу ли я ответить на свой вопрос?

Полагаю, я обнаружил, что единственный способ сделать то, что я описываю, - это чтобы моя справочная таблица имела строки для каждой возможной комбинации групп пользователей, членом которой может быть желаемое.

Чтобы выбрать упрощенный пример, вместо этого:

SELECT id FROM ids WHERE groups IN(1,2) ORDER BY id

Если вам нужно использовать индекс как для выбора строк, так и для их упорядочения, вы должны абстрагировать этот IN (1,2), чтобы он был постоянным, а не диапазоном, то есть:

SELECT id FROM ids WHERE grouplist='1,2' ORDER BY id

Конечно, вместо использования строки '1,2' у вас может быть внешний ключ и т. Д. Дело в том, что вам нужно иметь строку не только для каждой группы, но и для каждой комбинации нескольких групп.

Итак, мой ответ.

В любом случае, для моего приложения я считаю, что поддерживать поиск всех возможных комбинаций групп пользователей для каждого узла не стоит. Для моих целей я предсказываю, что большинство узлов видны большинству пользователей, поэтому я считаю приемлемым просто заставить GROUP BY использовать индекс, поскольку фильтрация не нуждается в этом так сильно.

Другими словами, подход, который я выберу для своего исходного запроса, может выглядеть примерно так:

SELECT
    <fields>
FROM
  node
  INNER JOIN viewpermission ON
    viewpermission_nodeID=node_ID
    AND viewpermission_usergroupID IN (<...usergroups of current user...>)
  FORCE INDEX(node_created_and_node_ID)
GROUP BY
  node_created, node_ID

GROUP BY может использовать индекс, если он начинается в крайнем левом столбце индекса и находится в первой неконстантной несистемной таблице, которая должна быть обработана. Затем соединение обрабатывает весь список (который уже упорядочен), и ВНУТРЕННЕЕ СОЕДИНЕНИЕ удаляет только те, которые не видны текущему пользователю (что составляет небольшую часть).

Answer 2

select * from
(
select *
FROM  node  
INNER JOIN viewpermission 
ON    viewpermission_nodeID=node_ID    
AND viewpermission_usergroupID IN (<...usergroups of current user...>)
) a
order by a.node_lastupdated desc

Внутренний запрос дает отфильтрованное подмножество, которое, насколько я понимаю, существенно меньше, чем весь набор Только меньшее должно быть отсортировано.

Answer 3

MySQL имеет проблемы, когда вы используете GROUP BY и ORDER BY в одном запросе. Это приводит к сортировке файлов, и это, вероятно, самое большое снижение производительности.

Вы можете устранить необходимость в DISTINCT (или GROUP BY), используя некоррелированный подзапрос вместо JOIN.

SELECT * FROM node
WHERE node_id IN (
  SELECT viewpermission_nodeID
  FROM viewpermission
  WHERE viewpermissiong_usergroupID IN ( <...usergroups...> )
)
ORDER BY node_lastupdated DESC
LIMIT 100;

Нет необходимости сортировать или выполнять DISTINCT в подзапросе, поскольку IN (1, 1, 2, 3) совпадает с IN (1, 3, 2).

Обратите внимание, что MySQL может использовать только один индекс на таблицу в данном запросе, поэтому он попытается сделать лучший выбор между индексом на node_id и индексом на node_lastupdated. Он не может использовать оба, и даже если вы создали составной индекс, в этом случае это не поможет.

Не забудьте проанализировать различные решения с помощью EXPLAIN.

Answer 4

Скопируйте значение, по которому вы хотите заказать, в таблицу viewpermission и добавьте его в свой индекс.

Вы можете использовать триггер для сохранения этого значения из другой таблицы.