Как базы данных реализуют SQL 'ORDER BY x'?

Question

Мне интересно, как они работают под капотом, особенно для больших наборов результатов. Например, может ли БД записать необработанный результат на диск, а затем выполнить внешнюю сортировку?

Мне также интересно, как это работает с LIMIT ... OFFSET. Если БД не может использовать существующий индекс, кажется, что БД должна была бы отсортировать все целиком и извлечь подмножество необработанного результирующего набора.

Answer 1

Указатели заказаны;если есть подходящий индекс, он будет использован.В противном случае они должны будут сортироваться, как вы предполагаете.План выполнения запроса (который можно получить, например, с помощью EXPLAIN или с помощью клиентских меню ; точный способ его получения зависит от СУБД) может содержать подсказки о том, какзапрос будет отсортирован.

См .:

1. MySQL: оптимизация ORDER BY
2. PostgreSQL: индексы и ORDER BY
3. Индексы SQL Server
4. Oracle: общие сведения об индексах

Answer 2

Вы можете найти эту страницу интересной:

http://dev.mysql.com/doc/refman/5.6/en/order-by-optimization.html

Answer 3

MySQL показывает свой собственный заказ По оптимизации на по этой ссылке

Oracle показывает свою собственную процедуру заказа по алгоритму здесь

В основноместь индекс, он заказан.Но когда вы не делаете сортировку, это O(n log n)

Answer 4

Вы в значительной степени имеете право на это. Если ничего не было подготовлено или предварительно запланировано (т. Е. Индексы или данные, ранее подготовленные или кэшированные иным образом), то да, все данные, которые необходимо учитывать для формирования правильного порядка, должны быть прочитаны, и если объем данных для переработка не может поместиться в доступную / выделенную память, тогда необходимо выполнить кэширование диска.

Это нетривиальная проблема с производительностью, и у каждой СУБД найдутся хитрые способы ее решения и оптимизации, так что вы будете использовать их продукт, а не тот подлый "Бренд Х".