Насколько дорого стоит SQL ORDER BY?

Question

Я не совсем понимаю, как команда SQL будет сортировать большой набор результатов. Это делается в памяти на лету (то есть, когда выполняется запрос)?

Будет ли сортировка быстрее с использованием ORDER BY в SQL, а не сортировка, скажем, связанного списка объектов, содержащих результаты на языке, подобном Java (при условии быстрой встроенной сортировки, возможно, с использованием быстрой сортировки)?

Answer 1

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

Например, в зависимости от запроса оптимизатор базы данных может выбрать план запроса, который возвращает данные по порядку, не выполняя сортировку. Например, база данных знает, что данные в индексе отсортированы, поэтому она может выбрать сканирование индекса, чтобы вернуть данные по порядку без необходимости материализации и сортировки всего набора результатов. Если он должен материализовать весь результат, ему нужны только столбцы, по которым вы сортируете, и какой-то идентификатор строки (т. Е. ROWID в Oracle), а не сортировка всей строки данных, как, например, реализация наивного среднего уровня. , Например, если у вас есть составной индекс (col1, col2), и вы решили отсортировать по UPPER (col2), LOWER (col1), база данных может считывать значения col1 и col2 из индекса, сортировать идентификаторы строк и затем идите за данными из таблицы. Конечно, база данных не должна этого делать - оптимизатор будет учитывать стоимость выполнения сортировки по сравнению со стоимостью выборки данных из таблицы или из различных индексов. База данных вполне может прийти к выводу, что наиболее эффективный подход - это выполнить сканирование таблицы, прочитать всю строку в память и отсортировать ее. Можно сделать вывод, что использование индекса приводит к увеличению количества операций ввода-вывода для извлечения данных, но компенсирует это уменьшением или устранением затрат на сортировку.

Answer 2

Ответ ... это зависит. Если часть ORDER BY может быть выполнена с использованием индекса в базе данных, тогда план выполнения для этого запроса будет использовать этот индекс, и результаты будут возвращаться в правильном порядке прямо из БД. Если нет, то база данных выполнит сортировку, но, скорее всего, лучше, чем вы читаете все результаты в память (и, конечно, лучше, чем чтение результатов в связанный список).

Answer 3

Точный метод зависит от продукта, который вы используете, но обычно полнофункциональная СУБД имеет в своем распоряжении несколько алгоритмов сортировки.Некоторые работают на диске, оптимизируя пространство с течением времени, некоторые работают в памяти, оптимизируя скорость.Проверьте исходный код доступных программ с открытым исходным кодом, если вас интересуют кровавые подробности.

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

Answer 4

Если сортировка не основана на индексе, если вы используете сортировку базы данных, вы гарантируете, что подождете, пока весь набор результатов не будет разрешен и отсортирован в базе данных, прежде чем вы увидите хотя бы одну строку набора результатов.

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

В зависимости от сценария развертывания может быть большая разница, когда дополнительные расходы, связанные с сортировкой, должны быть оплачены. В сценариях, в которых я работаю со средним уровнем, он одноразовый и масштабируемый, в то время как уровень данных более дорогой для масштабирования. Если он стоит того же ЦП, но ЦП базы данных стоит 5х или 10х с точки зрения эксплуатационных затрат, то в реальном выражении становится дешевле делать это вне базы данных.