Подтвердить что ты не робот

Выберите случайную строку из таблицы PostgreSQL со взвешенными вероятностями строк

Пример ввода:

SELECT * FROM test;
 id | percent   
----+----------
  1 | 50 
  2 | 35   
  3 | 15   
(3 rows)

Как бы вы пишете такой запрос, что в среднем 50% времени я мог бы получить строку с id = 1, 35% временной строки с id = 2 и 15% временной строки с id = 3?

Я пробовал что-то вроде SELECT id FROM test ORDER BY p * random() DESC LIMIT 1, но он дал неправильные результаты. После 10 000 запусков я получаю распределение вроде: {1=6293, 2=3302, 3=405}, но я ожидал, что распределение будет почти: {1=5000, 2=3500, 3=1500}.

Любые идеи?

Ответ 1

Это должно сделать трюк:

WITH CTE AS (
    SELECT random() * (SELECT SUM(percent) FROM YOUR_TABLE) R
)
SELECT *
FROM (
    SELECT id, SUM(percent) OVER (ORDER BY id) S, R
    FROM YOUR_TABLE CROSS JOIN CTE
) Q
WHERE S >= R
ORDER BY id
LIMIT 1;

Подзапрос Q дает следующий результат:

1  50
2  85
3  100

Затем мы просто генерируем случайное число в диапазоне [0, 100) и выбираем первую строку, которая находится за или выше этого числа (предложение WHERE). Мы используем общее табличное выражение (WITH), чтобы случайное число вычислялось только один раз.

BTW, SELECT SUM(percent) FROM YOUR_TABLE позволяет вам иметь вес в percent - им не обязательно должны быть проценты (например, до 100).

[SQL Fiddle]

Ответ 2

Ваш предлагаемый запрос работает; см. эту демонстрацию SQLFiddle. Однако это создает неправильное распределение; см. ниже.

Чтобы предотвратить оптимизацию подзапроса PostgreSQL, я завернул его в функцию VOLATILE SQL. PostgreSQL не имеет никакого способа узнать, что вы намереваетесь, чтобы подзапрос запускался один раз для каждой строки внешнего запроса, поэтому, если вы не заставите его волатильно, он просто выполнит его один раз. Другая возможность, хотя планировщик запросов может оптимизироваться в будущем, состоит в том, чтобы заставить его выглядеть коррелированным подзапросом, как этот хак, который использует предложение always-true where следующим образом: http://sqlfiddle.com/#!12/3039b/9

В предположении (до того, как вы обновили объяснение, почему это не сработало) ваша методология тестирования была виновата, или вы используете это как подзапрос во внешнем запросе, где PostgreSQL замечает, что это не коррелированный подзапрос и выполнив его только один раз, как в в этом примере..

ОБНОВЛЕНИЕ: Выдающееся распределение не является тем, что вы ожидаете. Проблема здесь в том, что вы искажаете распределение, беря несколько образцов random(); вам нужен один образец.

Этот запрос создает правильное распределение (SQLFiddle):

WITH random_weight(rw) AS (SELECT random() * (SELECT sum(percent) FROM test))
 SELECT id
FROM (                   
  SELECT 
    id,
    sum(percent) OVER (ORDER BY id),
    coalesce(sum(prev_percent) OVER (ORDER BY id),0) FROM (
      SELECT 
        id,
        percent,
        lag(percent) OVER () AS prev_percent
      FROM test
    ) x
) weighted_ids(id, weight_upper, weight_lower)
CROSS JOIN random_weight
WHERE rw BETWEEN weight_lower AND weight_upper;

Производительность, разумеется, ужасна. Он использует два вложенных набора окон. Что я делаю:

Создание (id, percent, previous_percent), затем использование этого для создания двух текущих сумм весов, которые используются в качестве скобок диапазона; затем
Принимая случайное значение, масштабируя его до диапазона весов, а затем выбираем значение, имеющее весы в целевом скобке

Ответ 3

Вот вам что-то для игры:

select t1.id as id1
  , case when t2.id is null then 0 else t2.id end as id2
  , t1.percent as percent1
  , case when t2.percent is null then 0 else t2.percent end as percent2 
from "Test1" t1 
  left outer join "Test1" t2 on t1.id = t2.id + 1
where random() * 100 between t1.percent and 
  case when t2.percent is null then 0 else t2.percent end;

По существу выполняйте левое внешнее соединение, чтобы у вас было два столбца для применения предложения inter.

Обратите внимание, что это будет работать, только если вы правильно упорядочите таблицу.

Ответ 4

ORDER BY random() ^ (1.0/p)

из алгоритма, описанного Efraimidis и Spirakis.