Chọn hàng ngẫu nhiên từ một bảng PostgreSQL với xác suất hàng trọng

Question

Ví dụ đầu vào:

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

Làm thế nào bạn sẽ viết truy vấn như vậy, rằng trung bình 50% thời gian tôi có thể nhận được hàng với id = 1, 35 % hàng thời gian có id = 2 và 15% hàng thời gian có id = 3?

Tôi đã thử một cái gì đó như SELECT id FROM test ORDER BY p * random() DESC LIMIT 1, nhưng nó cho kết quả sai. Sau 10.000 lần chạy, tôi nhận được bản phân phối như: {1=6293, 2=3302, 3=405}, nhưng tôi dự kiến ​​phân phối sẽ gần như: {1=5000, 2=3500, 3=1500}.

Bất kỳ ý tưởng nào?

Answer 1

này nên làm như lừa:

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; 

Tiểu truy vấn Q cho kết quả sau:

1 50 
2 85 
3 100 

Sau đó chúng tôi chỉ đơn giản là tạo ra một số ngẫu nhiên trong khoảng [0, 100) và chọn hàng đầu tiên nằm tại hoặc vượt quá con số đó (mệnh đề WHERE). Chúng tôi sử dụng biểu thức bảng chung (WITH) để đảm bảo số ngẫu nhiên chỉ được tính một lần.

BTW, SELECT SUM(percent) FROM YOUR_TABLE cho phép bạn có bất kỳ trọng số nào trong số percent - chúng không nhất thiết phải là tỷ lệ phần trăm (tức là bổ sung lên 100).

[SQL Fiddle]

Answer 2

Truy vấn được đề xuất của bạn dường như hoạt động; xem this SQLFiddle demo. Nó tạo ra sự phân phối sai mặc dù; xem bên dưới.

Để ngăn PostgreSQL tối ưu hóa truy vấn con tôi đã gói nó trong hàm SQL VOLATILE. PostgreSQL không có cách nào để biết rằng bạn có ý định truy vấn con chạy một lần cho mỗi hàng của truy vấn bên ngoài, vì vậy nếu bạn không ép nó biến động, nó sẽ thực thi nó một lần. Một khả năng khác - mặc dù một khả năng mà trình hoạch định truy vấn có thể tối ưu hóa trong tương lai - là làm cho nó xuất hiện như một truy vấn con tương quan, như hack này sử dụng mệnh đề where-true, như sau: http://sqlfiddle.com/#!12/3039b/9

Khi đoán (trước khi bạn cập nhật để giải thích lý do tại sao nó không hoạt động) phương pháp thử nghiệm của bạn bị lỗi hoặc bạn đang sử dụng phương thức này làm truy vấn con trong truy vấn bên ngoài, nơi PostgreSQL nhận thấy đó không phải là truy vấn con tương quan và thực thi nó một lần , như trong số this example. .

CẬP NHẬT: Bản phân phối được tạo ra không phải là những gì bạn mong đợi. Vấn đề ở đây là bạn đang lệch phân phối bằng cách lấy nhiều mẫu trong số random(); bạn cần mẫu đơn.

truy vấn này tạo ra sự phân bố chính xác (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; 

Hiệu suất là, không cần phải nói, khủng khiếp. Nó sử dụng hai bộ cửa sổ lồng nhau. Những gì tôi đang làm là:

• Tạo (id, percent, previous_percent) sau đó sử dụng để tạo hai số tiền chạy được sử dụng làm dấu ngoặc; sau đó
• Lấy một giá trị ngẫu nhiên, nhân rộng nó vào phạm vi của trọng lượng, và sau đó chọn một giá trị mà có trọng lượng trong khung mục tiêu

Answer 3

Dưới đây là một cái gì đó để bạn có thể chơi với:

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; 

Về cơ bản thực hiện phép nối ngoài bên trái để bạn có hai cột để áp dụng mệnh đề giữa.

Lưu ý rằng nó sẽ chỉ hoạt động nếu bạn đặt bảng của mình theo đúng cách.

Answer 4

ORDER BY ngẫu nhiên()^(1.0/p)

từ các thuật toán được mô tả bởi Efraimidis và Spirakis.