Предвзятое случайное в SQL?

Question

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

Таким образом, у меня, по сути, есть поля ID и BOOST. Повышение рассчитывается таким образом, что оно получается как целое число, представляющее процент того, как часто эта запись должна попадать в сравнении.

ID  Boost
1   1
2   2
3   7

Так что, если я запускаю свою произвольную функцию бесконечно, у меня должно получиться Х попаданий по ИД 1, вдвое больше по ИД 2 и в 7 раз больше по ИД 3.

Таким образом, каждое попадание должно быть случайным, но с вероятностью (boost / sum of boosts). Таким образом, вероятность для идентификатора 3 в этом примере должна быть 0,7 (потому что сумма равна 10. Я выбираю эти значения для простоты).

Я думал о чем-то вроде следующего запроса:

SELECT id FROM table WHERE CEIL(RAND() * MAX(boost)) >= boost ORDER BY rand();

К сожалению, это не работает, после рассмотрения следующих записей в таблице:

ID  Boost
1   1
2   2

С вероятностью 50/50 будет случайным образом выбирать только 2-й или оба элемента.

Таким образом, 0,5 попадания переходит ко второму элементу. И 0,5 попадания идет к (второму и первому) элементу, который выбирается случайным образом, так что каждый по 0,25. Таким образом, мы получаем соотношение 0,25 / 0,75, но оно должно быть 0,33 / 0,66

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

Я также подумал о накопительном увеличении поля накопления, поэтому я просто делаю запрос диапазона из (0-sum()), но тогда мне придется переиндексировать все, что идет после одного элемента, если я изменю его или разработаю какой-нибудь алгоритм обмена что-то ... но это действительно не элегантно и прочее.

Как вставка / обновление, так и выбор должны быть быстрыми!

Есть ли у вас какие-либо решения этой проблемы?

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

редактирование:

Благодаря ответу Kens я подумал о следующем подходе:

1. вычислить случайное значение из 0-суммы (отчетливое повышение)

   SET @randval = (выбрать ceil (rand () * sum (DISTINCT boost)) из теста);

2. выбор коэффициента усиления из всех различных коэффициентов усиления, которые суммируются, превышает случайное значение

тогда мы имеем в нашем 1-м примере 1 с 0,1, 2 с 0,2 и 7 с вероятностью 0,7.

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

ПРОБЛЕМА: , потому что количество записей с одним повышением всегда различно. Например, если есть только 1 усиленная запись, я получаю ее в 1 из 10 вызовов, но если есть 1 миллион с 7, каждый из них почти никогда не возвращается ... так что это не сработает :( пытаюсь уточнить это.

Мне нужно как-то включить количество записей с этим коэффициентом повышения ... но я как-то застрял на этом ...

Answer 1

Вам нужно сгенерировать случайное число в строке и взвесить его.

В этом случае RAND(CHECKSUM(NEWID())) обходит оценку "за запрос" RAND. Затем просто умножьте его на boost и ORDER BY на результат DESC. SUM..OVER дает вам общее повышение

DECLARE @sample TABLE (id int, boost int)

INSERT @sample VALUES (1, 1), (2, 2), (3, 7)

SELECT
    RAND(CHECKSUM(NEWID())) * boost  AS weighted,
    SUM(boost) OVER () AS boostcount,
    id
FROM
    @sample
GROUP BY
    id, boost
ORDER BY
    weighted DESC

Если у вас сильно различаются значения усиления (о которых я думаю, вы упомянули), я бы также подумал об использовании LOG (который является основой e) для сглаживания распределения.

Наконец, ORDER BY NEWID () - это случайность, которая не учитывает повышение. Полезно сеять RAND, но не само по себе.

Этот образец был собран на SQL Server 2008, кстати

Answer 2

Я позволю себе предложить простое решение с двумя запросами, используя кумулятивный расчет усиления.

Сначала выберите сумму повышений и сгенерируйте некоторое число между 0 и суммой усиления:

select ceil(rand() * sum(boost)) from table;

Это значение должно быть сохранено как переменная, назовем его {random_number}

Затем выберите строки таблицы, рассчитав кумулятивную сумму бустов, и найдите первую строку, у которой кумулятивный буст больше, чем {случайное число}:

SET @cumulative_boost=0;
SELECT
  id,
  @cumulative_boost:=(@cumulative_boost + boost) AS cumulative_boost,
FROM
  table
WHERE
  cumulative_boost >= {random_number}
ORDER BY id
LIMIT 1;

Answer 3

Моя проблема была похожей: у каждого человека было подсчитанное количество билетов в финальном розыгрыше. Если бы у вас было больше билетов, у вас был бы более высокий шанс выиграть «лотерею».

Поскольку я не доверял ни одному из найденных результатов rand() * multiplier или результату с -log(rand()) в Интернете, я хотел реализовать собственное простое решение.

То, что я сделал и в вашем случае выглядело бы примерно так:

(SELECT id, boost FROM foo) AS values
INNER JOIN (
    SELECT id % 100 + 1 AS counter 
    FROM user 
    GROUP BY counter) AS numbers ON numbers.counter <= values.boost
ORDER BY RAND()

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

Прежде чем использовать этот запрос, я проверил две вещи:

1. Максимальное число boost меньше максимального значения, возвращенного в запросе числа
2. что внутренний запрос возвращает ВСЕ числа от 1..100. Это может не зависеть от вашего стола!

Так как у меня есть все отличные числа от 1..100, то соединение с numbers.counter <= values.boost будет означать, что если строка будет иметь увеличение 2, это в конечном итоге будет дублироваться в конечном результате. Если ряд имеет повышение 100, он будет в конечном итоге 100 раз. Или другими словами. Если сумма бустов равна 4212, как в моем случае, в конечном наборе будет 4212 строк.

Наконец я позволил MySql отсортировать его случайным образом.

Редактировать: Для правильной работы внутреннего запроса убедитесь, что используется большая таблица, или убедитесь, что идентификаторы не пропускают никаких чисел. Еще лучше и, возможно, немного быстрее, вы даже можете создать временную таблицу, в которой просто будут все числа от 1..n. Тогда вы можете просто использовать INNER JOIN numbers ON numbers.id <= values.boost