Всем привет!

Допустим есть таблица с колонкой типа число.

CREATE TABLE tbl (value int NOT NULL);

и в этой таблице, допустим 10000 записей.

Надо вернуть тысячу самых маленьких значений.

SELECT * FROM tbl ORDER BY value LIMIT 1000;

В результате, эти значения будут упорядочены: 1, 2, 3...

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

Здравствуйте, valker, Вы писали:

V>Существует ли способ сделать этот запрос быстрее, если нас не интересует упорядоченность результирующего списка строк (2, 3, 1, ...) ?

Если есть индекс по value, и LIMIT не слишком велик, доступ по индексу даст нужный результат без сортировки.

Если индекса нет или он неприменим, то, в зависимости от используемой СУБД и ее версии, для таких запросов может использоваться оптимизированный top-N алгоритм. Значения на выходе будут все равно упорядоченными, но он будет эффективнее, чем полная сортировка. Точно знаю, про современные версии SQL Server и Oracle. Скорее всего, в PostgreSQL он тоже есть (точно не знаю).

Здравствуйте, valker, Вы писали:

V>Существует ли способ сделать этот запрос быстрее, если нас не интересует упорядоченность результирующего списка строк (2, 3, 1, ...) ?

SoF по теме https://stackoverflow.com/questions/33936485/understanding-order-by-using-top-n-heapsort-in-postgres

Здравствуйте, valker, Вы писали:
V>Существует ли способ сделать этот запрос быстрее, если нас не интересует упорядоченность результирующего списка строк (2, 3, 1, ...) ?
Нет.
Во-первых, limit без order by не имеет смысла — СУБД вольна возвращать результат select в произвольном порядке; вряд ли вы захотите видеть "любые 1000 записей". (а если захотите именно любые, то вам нужен надёжный способ их перемешивать).
Во-вторых, невозможно отобрать top N записей по некоторому критерию без сортировки всего набора по этому критерию.
Поэтому упорядоченность у вас будет так или иначе достигнута. Она будет достигнута быстро, если вы сортируете по (суб)ключу некоторого индекса. Ещё быстрее — если это будет кластерный индекс, или индекс, покрывающий ваш список атрибутов в select.

Здравствуйте, Sinclair, Вы писали:

S>невозможно отобрать top N записей по некоторому критерию без сортировки всего набора по этому критерию.

Еще как возможно, если под "сортировкой всего набора" понимать материализацию отсортированного набора в памяти. Для top N же достаточно O(N) памяти.

Здравствуйте, wildwind, Вы писали:
W>Еще как возможно, если под "сортировкой всего набора" понимать материализацию отсортированного набора в памяти. Для top N же достаточно O(N) памяти.
А зачем это так понимать? Речь идёт о том, что придётся просмотреть весь набор. И в памяти придётся держать N позиций отсортированными.

Здравствуйте, Sinclair, Вы писали:

S>А зачем это так понимать? Речь идёт о том, что придётся просмотреть весь набор. И в памяти придётся держать N позиций отсортированными.
"Просмотреть", согласен, это другое дело.

Здравствуйте, Sinclair, Вы писали:


S> И в памяти придётся держать N позиций отсортированными.

Прогуляли курс "алгоритмы и структуры данных" в универе? Есть, как-минимум, два способа вернуть top-N без выделения памяти на весь объём данных: heap и балансировочные деревья.

Здравствуйте, cppguard, Вы писали:
C>Прогуляли курс "алгоритмы и структуры данных" в универе? Есть, как-минимум, два способа вернуть top-N без выделения памяти на весь объём данных: heap и балансировочные деревья.
Нет, просто вы невнимательно читаете. И heap и балансировочные деревья держат N позиций в памяти до окончания сортировки.
Вы, наверное, перепутали то N, которое top-N с тем, которое "всего позиций".