Как эффективно запросить n записей для каждой категории

Question

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

SELECT category, category_id, value FROM
(
    SELECT category, value, row_number() OVER (PARTITION by category) as category_id
    FROM myTable
)
WHERE  category_id < N;

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

Это крайне неэффективно для больших таблиц, так как будет проходить назначение идентификаторов для всех записей, даже если нас интересует только N записей в каждой категории.

Следующее не работает на движке SQL, с которым я работаю - не уверен, работает ли он вообще на каком-либо движке.

SELECT category, value, row_number() OVER (PARTITION by category) as category_id
FROM myTable
WHERE category_id < N

Кто-нибудь знает какие-либо другие способы достижения этого с лучшей временной сложностью?

Больше мыслей:

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

   1. SELECT DISTINCT(category) FROM myTable
   2. FOREACH category SELECT N rows

---

больше информации: мои данные физически разделены category, в состоянии явно использовать то, что было бы полезно

Answer 1

Как отметил @Lamak в комментарии, вы не можете избежать сортировки всех строк в таблице, но не по указанной причине. Сортировка необходима для определения отдельных категорий, по которым следует разделить результирующий набор, и, при отсутствии явного упорядочения внутри каждого раздела, номера строк легко определяются как побочный эффект сортировки по категориям.

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

В последнем случае упрощенный алгоритм может выглядеть примерно так:

1. Прочитайте предварительно отсортированные записи, содержащие все необходимые столбцы, включая номера строк, из индекса.
2. Отменить записи с номером строки больше чем n,

Ваш "идеальный" запрос

SELECT category, value, row_number() OVER (PARTITION by category) as
category_id FROM myTable WHERE category_id < N

вероятно, не будет работать в любой базе данных SQL, потому что SELECT список обрабатывается после WHERE условие предиката, так category_id неизвестно, когда предикаты оцениваются.

Answer 2

Другой метод rownumber, но у меня тоже есть сомнения в производительности. Я согласен @mustaccio. Мой пример взять 5 строк...

select distinct f1.category, f3.*             
from yourtable f1                        
inner join lateral                                          
(                                                           
 select f2.value from yourtable f2              
 where f2.category=f1.category 
 fetch first 5 rows only                                    
) f3 on 1=1