Ребята, как называется более легкий LIMIT? который не подгружает сначала

Question

pgsql – PostgreSQL

herenickname ️

Ребята, как называется более легкий LIMIT? который не подгружает сначала

всю выдачу, а сразу обрубает

#backend #devops #pgsql #programming #russian

0

20.07.2021

5 ответов

13 просмотров

Aleksey Stavrov

В таком запросе select * from table limit 10 Вы итак получаете сразу 10 записей и только их. Другие не будут подниматься с диска. В таком запросе select * from table order by x limit 10 и есть индекс по x, то Pg снова прочитает только 10 строк и несколько страниц в индексе. Если индекса нет, то магии не будет, конечно, прочитается вся таблица, посортируется и возьмётся первые 10. В других СУБД думаю так же.

0

21.07.2021

Radist

Aleksey Stavrov
В таком запросе select * from table limit 10 Вы ит...

Памяти на такую сортировку (последний случай) уйдёт гораздо меньше, чем на полный quicksort, который будет без limit, потому что сперва честно отсортируются 10 записей, затем БД пройдёт скользящим окном из этих 10 записей, вписывая новые строки только если они должны занять место до уже существующих строк.

0

21.07.2021

Aleksey Stavrov

Radist
Памяти на такую сортировку (последний случай) уйдё...

О, интересное замечание. Т.е. там, видимо, heap (структура данных). В него кладут и извлекают быстро за log от числа записей в heap. Так?

0

22.07.2021

Radist

Aleksey Stavrov
О, интересное замечание. Т.е. там, видимо, heap (с...

За log2(число записей) можно найти в отсортированном массиве строку, в которую надо вставить следующую запись из неотсортированных данных (при этом, большая часть строк попадёт в конец массива и будет просто отброшена), сами данные строк, видимо, действительно в heap-е размещаются, в итоге. В итоге, сложность по сравнениям получается O(N*log2(m)), где N - общее число строк, а m = limit + offset, если m << N, это будет быстрее, чем делать честную сортировку всех данных, у которой сложность O(N*log2(N)). Я не читал исходники, если что, просто это очевидный путь к ускорению быстрого получения top m строк, как небольшое расширение получения top 1 строки.

0

22.07.2021

Евгений Смирнов · Accepted Answer

Евгений Смирнов

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

0

21.07.2021

172 похожих чатов

Ребята, как называется более легкий LIMIT? который не подгружает сначала

5 ответов

Похожие вопросы