Как получить X% процентиль в Кассандре - PullRequest
Новая
       34

Как получить X% процентиль в Кассандре

0 голосов
/ 27 сентября 2018

Рассмотрим таблицу со структурой: 

CREATE TABLE statistics (name text, when timestamp, value int, 
PRIMARY KEY ((name, when)));

Как лучше всего рассчитать, например, 50% -ый процентиль значения по имени?Я думал о:

а) написании пользовательской агрегатной функции + запрос типа: 

SELECT PERCENTILE(value, 0.5) FROM statistics WHERE name = '...'

б) сначала подсчитать количество элементов по имени 

SELECT COUNT(value) FROM statistics WHERE name = '...'

затем найти (0,5 /count) значение строки с подкачкой при сортировке по возрастанию.Скажем, если счет равен 100, это будет 50-й ряд.

в) ваши идеи

Я не уверен, что случай А справится с этой задачей.Случай B может быть сложным, если существует нечетное количество строк.

1 Ответ

0 голосов
/ 27 сентября 2018

Пока вы всегда предоставляете name - этот запрос может быть очень дорогим без указания раздела и наличия всего в одном.Я предполагаю, что вы имеете в виду ((name), when), а не ((name, when)) в вашей таблице, иначе то, что вы просите, невозможно без полного сканирования таблицы (с использованием hadoop или spark).

UDA будет работать - но это может быть дорого, если толькоВы готовы принять приближение.Чтобы сделать его абсолютно точным, вам нужно сделать 2 прохода (то есть сделать подсчет, чем 2 прохода, чтобы перейти в сет, но без изоляции это тоже не будет идеально).Поэтому, если вам это нужно, чтобы быть абсолютно точным, лучше всего сделать ставку на локальный раздел statistics[name] или сделать так, чтобы UDA построил весь набор (или большинство) на карте (не рекомендуется, если разделы вообще становятся большими) перед расчетом.Например: 

CREATE OR REPLACE FUNCTION all(state tuple<double, map<int, int>>, val int, percentile double)
  CALLED ON NULL INPUT RETURNS tuple<double, map<int, int>> LANGUAGE java AS '
java.util.Map<Integer, Integer> m = state.getMap(1, Integer.class, Integer.class);
m.put(m.size(), val);
state.setMap(1, m);
state.setDouble(0, percentile);
return state;';

CREATE OR REPLACE FUNCTION calcAllPercentile (state tuple<double, map<int, int>>)
  CALLED ON NULL INPUT RETURNS int LANGUAGE java AS 
  'java.util.Map<Integer, Integer> m = state.getMap(1, Integer.class, Integer.class);
  int offset = (int) (m.size() * state.getDouble(0));
  return m.get(offset);';

CREATE AGGREGATE IF NOT EXISTS percentile (int , double) 
  SFUNC all STYPE tuple<double, map<int, int>>
  FINALFUNC calcAllPercentile
  INITCOND (0.0, {});

Если вы хотите принять приближение, вы можете использовать резервуар для выборки, скажем, 1024 хранимых вами элемента, и, когда ваш UDA получает элементы, вы заменяете элементы в нем с уменьшающейся статистической вероятностью.( алгоритм Виттера R ) Это довольно легко реализовать, и если ожидается, что ваш набор данных будет иметь нормальное распределение, вы получите приличное приближение.Если ваш набор данных не является нормальным распределением, это может быть довольно далеко.При нормальном распределении на самом деле есть много других вариантов, но я думаю, что проще всего реализовать в UDA.как: 

CREATE OR REPLACE FUNCTION reservoir (state tuple<int, double, map<int, int>>, val int, percentile double)
  CALLED ON NULL INPUT RETURNS tuple<int, double, map<int, int>> LANGUAGE java AS '
java.util.Map<Integer, Integer> m = state.getMap(2, Integer.class, Integer.class);
int current = state.getInt(0) + 1;
if (current < 1024) {
    // fill the reservoir
    m.put(current, val);
} else {
    // replace elements with gradually decreasing probability
    int replace = (int) (java.lang.Math.random() * (current + 1));
    if (replace <= 1024) {
        m.put(replace, val);
    }
}
state.setMap(2, m);
state.setDouble(1, percentile);
state.setInt(0, current);
return state;';

CREATE OR REPLACE FUNCTION calcApproxPercentile (state tuple<int, double, map<int, int>>)
  CALLED ON NULL INPUT RETURNS int LANGUAGE java AS 
  'java.util.Map<Integer, Integer> m = state.getMap(2, Integer.class, Integer.class);
  int offset = (int) (java.lang.Math.min(state.getInt(0), 1024) * state.getDouble(1));
  if(m.get(offset) != null)
      return m.get(offset);
  else
      return 0;';

CREATE AGGREGATE IF NOT EXISTS percentile_approx (int , double) 
  SFUNC reservoir STYPE tuple<int, double, map<int, int>>
  FINALFUNC calcApproxPercentile
  INITCOND (0, 0.0, {});

В приведенном выше примере процентиль будет работать медленнее, игра с размером сэмплера может дать вам более или менее высокую точность, но слишком большую, и вы начнете влиять на производительность.Обычно UDA, превышающий 10 тыс. Значений (даже такие простые функции, как count), начинает давать сбой.В этих сценариях также важно понимать, что хотя один запрос возвращает одно значение, для его получения требуется немало усилий.Поэтому многие из этих запросов или много параллелизма окажут большое давление на ваших координаторов.Для этого требуется> 3,8 (я бы порекомендовал 3.11.latest +) для CASSANDRA-10783

примечание: я не даю никаких обещаний, что я не пропустил ошибку "отключено на 1" в примере UDA- Я не проверял полностью, но должен быть достаточно близко, чтобы вы могли заставить его работать оттуда

...