выберите топ N для каждой категории без сортировки, если строк меньше N - PullRequest
0 голосов
/ 22 февраля 2019

Учитывая следующую таблицу, вопрос состоит в том, чтобы найти, например, верхний N C2 из каждого C1.

C1 C2 
1  1
1  2
1  3
1  4
1  ...
2  1
2  2
2  3
2  4
2  ...
....

Так что, если N = 3, результат будет

C1 C2 
1  1
1  2
1  3
2  1
2  2
2  3
....

Предлагаемые решения используют оконную функцию и разбиение на

Например,

SELECT rs.Field1,rs.Field2 
FROM (
    SELECT Field1,Field2, Rank() 
      over (Partition BY Section
            ORDER BY RankCriteria DESC ) AS Rank
    FROM table
) rs WHERE Rank <= 3

Я думаю, что он делаетсортирует, затем выбирает верхнюю N.

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

Приведенный выше запрос использует Rank ().Мой вопрос относится к другим оконным функциям, таким как row_num () или dens_rank ().

Есть ли способ игнорировать сортировку в случае?

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

Использование partition + order + где позволяет получить элемент top-N из каждой категории.Он отлично работает, если в каждой категории больше N элемента, но в противном случае имеет дополнительную стоимость сортировки.У меня вопрос, есть ли другой подход, который хорошо работает в обоих случаях.В идеале он делает следующее

for each category {
   if # of element <= N:
      continue
   sort and get the top N
}

Например, но есть ли лучший SQL?

WITH table_with_count AS (
         SELECT Field1, Field2, RankCriteria, count() over (PARTITION BY Section) as c
         FROM table
),

rs AS (
    SELECT Field1,Field2, Rank() 
      over (Partition BY Section
            ORDER BY RankCriteria DESC ) AS Rank
    FROM table_with_count 
    where c > 10
) 

(SELECT Field1,Field2e FROM rs WHERE Rank <= 10)
     union
(SELECT Field1,Field2 FROM table_with_count WHERE c <= 10)

Ответы [ 2 ]

0 голосов
/ 24 февраля 2019

Нет, там действительно не должно быть.В целом, здесь вы описываете проблему XY.

Вы, кажется:

  • Беспокоитесь о сортировке, хотя на самом деле сортировка (с дополнительной вторичной сортировкой) является наиболее эффективным способомперемешивание / перераспределение данных, так как это не приводит к распространению файловых дескрипторов.На практике Spark строго предпочитает сортировку альтернатив (хеширование) именно по этой причине.
  • Беспокойство по поводу "ненужной" сортировки небольших групп, когда на самом деле проблема заключается в неэффективности оконных функций, которые требуют полного перемешивания всехпоэтому данные демонстрируют ту же модель поведения, что и печально известную groupByKey.

Существуют более эффективные шаблоны (MLPairRDDFunctions.topByKey является наиболее ярким примером), но они не были перенесены в Dataset APIи потребует пользовательского Aggregator Также возможно приблизительное выделение (например, с помощью квантильной аппроксимации), но это увеличивает количество проходов по данным и во многих случаях не обеспечивает какого-либо увеличения производительности.

0 голосов
/ 22 февраля 2019

Это слишком долго для комментария.

Нет такой оптимизации.По сути, все данные сортируются при использовании предложений по управлению окнами.Я полагаю, что механизм базы данных мог бы фактически использовать алгоритм хеширования для partition by и алгоритм сортировки для order by, но я не думаю, что это общий подход.

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

Также обратите внимание, что происходит сравнение с «3»(логически) после оконной функции.Я не думаю, что оконные функции обычно оптимизируются для такой пост-фильтрации (хотя, опять же, это возможная оптимизация).

...