POSTGRES выберите n одинаково распределенных строк по времени по миллионам записей

Question

У меня есть таблица со столбцами id,filter1,filter2,time,value, которая содержит миллионы записей. Я хочу получить n равномерно распределенные строки между двумя временными метками. Если количество записей между отметками времени меньше n, я хочу получить все записи.

Мой текущий запрос выглядит следующим образом, предполагая, n=200

SELECT s.* FROM (
    SELECT t.time, t.value,
           ROW_NUMBER() OVER(ORDER BY t.time) as rnk,
           COUNT(*) OVER() as total_cnt
    FROM table_name t
    WHERE t.filter1='filter_value' 
    and t.filter2='another_value' 
    and t.time between '2020-04-18' AND '2020-04-19') s

WHERE MOD(s.rnk,(total_cnt/200)) = 0 ;

У меня есть Индекс «фильтр1, фильтр2, время». Тем не менее этот запрос является чрезвычайно медленным, когда существует около 10 миллионов записей.

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

Answer 1

Если ...

• ... у вас нет дополнительной мета-информации о логическом или физическом распределении данных
• ... и вам нужно равномерно распределить выборку по время

... тогда ваш исходный запрос в основном так же хорош, как и получает. У вас есть индекс на (filter1,filter2,time), как предложил Гордон. Это помогает (очень), если менее нескольких процентов проходят фильтры. Затем мы должны подсчитать и пронумеровать все подходящие строки (дорогая часть для многих подходящих строк), чтобы получить строго равномерное распределение в выборке.

Несколько незначительных предложений:

SELECT s.*
FROM  (
   SELECT t.time, t.value
        , row_number() OVER (ORDER BY t.time) AS rn  -- ①
        , count(*) OVER() AS total_cnt
   FROM   table_name t
   WHERE  t.filter1 = 'filter_value' 
   AND    t.filter2 = 'another_value' 
   AND    t.time >= '2020-04-18'  -- assuming data type timestamp!
   AND    t.time <  '2020-04-20'  -- ②
   ) s
WHERE  mod(s.rn, total_cnt/n) = total_cnt/n/2 + 1;  -- ③

① Используйте псевдоним столбца rn (или любой другой) для row_number(); rnk намекает на rank().

② Предполагая, что столбец "time" имеет тип данных timestamp, поскольку ни date, ни time не имеет смысла. («время» кажется вводящим в заблуждение.) Так что этот предикат скорее всего неверен :

t.time between '2020-04-18' AND '2020-04-19'

Указанные литералы даты приводятся к меткам времени 2020-04-18 0:0 / 2020-04-19 0:0. Поскольку BETWEEN включает нижнюю и верхнюю границу, фильтр эффективно выбирает все значения 2020-04-18 плюс первый момент 2020-04-19. Вряд ли когда-нибудь имеет смысл. Мое предлагаемое исправление включает в себя все 2020-04-18 и 2020-04-19.

Если столбец "time" имеет тип данных timestamptz, то вышеупомянутое в основном также применимо. Кроме того, вы добавляете зависимость от настройки timezone сеанса базы данных в миксе. Не надо! См .:

• Вычесть часы из функции now ()
• Генерация временных рядов между двумя датами в PostgreSQL

③ Ваше исходное состояние MOD(s.rnk,(total_cnt/n)) = 0 выбирает каждую total_cnt/n -ю строку, всегда пропуская первые total_cnt/n - 1 строки, что создает смещение для последующих строк . Для иллюстрации:

ooooXooooXooooXooooX

Моя альтернатива смещает выделение к центру, что кажется более разумным:

ooXooooXooooXooooXoo

Целочисленное деление может привести к 0. Добавление 1 (total_cnt/n/2 + 1) предотвращает от происходящего. Кроме того, в любом случае это больше в «центре».

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

Тем не менее, мы можем использовать любую мета-информацию о распределении данных в наших интересах. Или если мы можем ослабить требования для строго равномерного распределения в образце (до какой степени?).

Радикально быстрее только при сканировании по индексу

Если мы можем предположить равномерное распределение данных по времени для всех (или некоторых) комбинаций (filter1, filter2), мы можем просто разделить время интервал и уйти с n очень дешевый индекс (только) сканирования (Или, если мы не слишком заботимся о равномерном распределении данных, мы все равно могли бы это сделать.) Для иллюстрации:

WITH input (f1    , f2    , lo                    , hi                    , n) AS (
   VALUES  ('val2', 'val2', timestamp '2020-04-18', timestamp '2020-04-20', 200)
   )
SELECT g.lo, s.*
FROM   (SELECT *, (hi - lo) / n AS span FROM input) i
CROSS  JOIN generate_series(lo, hi - span, span) g(lo)
LEFT   JOIN LATERAL (   
   SELECT t.time, t.value
   FROM   table_name t
   WHERE  t.filter1 = i.f1
   AND    t.filter2 = i.f2
   AND    t.time >= g.lo
   AND    t.time <  g.lo + span
   ORDER  BY time
   LIMIT  1
   ) s ON true;

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

Основная цель - избежать обработки всех строк и выбрать только те, которые возвращаются.

запрос начинается с нижней границы, создавая шаблон выбора, например:

XooooXooooXooooXoooo

LEFT JOIN содержит пустые временные интервалы в результате, которые указывают на неравномерное распределение данных.

Любой вид мета-информации о дизайне таблицы, распределении данных, шаблонах записи и т. д. может быть использован для дальнейшей оптимизации. Индексирование может быть оптимизировано: сканирование только по индексу, частичные индексы, ...

Answer 2

Для этого запроса:

SELECT s.*
FROM (SELECT t.time, t.value,
             ROW_NUMBER() OVER (ORDER BY t.time) as rnk,
             COUNT(*) OVER () as total_cnt
      FROM table_name t
      WHERE t.filter1 = 'filter_value' AND
            t.filter2 = 'another_value' AND
            t.time between '2020-04-18' AND '2020-04-19'
     ) s
WHERE MOD(s.rnk, (total_cnt / 200)) = 0 ;

Требуется индекс для (filter1, filter2, time). Это должно помочь производительности.