Thuật toán tìm ngẫu nhiên N records trong một bảng lớn (khoảng vài triệu record)?

algorithm
mysql

(thienph) #21

Auto ID nhưng không liên tục do từng bị xoá. Bạn sẽ dùng cách gì để biết ID bị đứt đoạn ở đâu khi không được scan toàn bộ table (lệnh select rand() chính là sẽ scan toàn bộ table)?

Theo cách mình nêu ở trên muốn lấy n record có 2 cách

  1. Chạy n lần thì có n record trãi đều --> cách này khá tệ
  2. select chừng 100 record liên tục với offset random được kết quả (I). Tiếp tục rand (I) với limit n (số lượng record cần). -> nhanh, kết quả chấp nhận được

(‏) #22

xài where id >= random_id là được rồi mà như chủ thớt đã ghi :V

select col from tbl where id >= a1 Limit 1
union
select col from tbl where id >= a2 Limit 1
union
...
union
select col from tbl where id >= an Limit 1

cách này ko chắc chắn thu về đúng n kết quả được, ví dụ lỗ hổng mấy đoạn id [1-99], n=50, 2 số random a10 và a50 là 45 75 thì where id >= an đều trả về id=100, union lại chỉ còn n=49 số chứ ko phải n=50 số :V Lại phải làm 1 vòng while n thu được < n cần :V

nhanh hơn nhưng cần phải viết code ngoài db tạo cái chuỗi query, rồi code nhập nhiều kết quả n thu được lại thành 1, rồi phải random sampling kết quả này :V :V

à mà cách where id >= x này có thể cho xác suất ngẫu nhiên ko đều: ví dụ 100 record, mất 98 record 2-99, còn lại record 1 và 100, thì random x từ 1-100 99% thu được x > 1, 1 % thu được x = 1, vậy where id >= x trả về 99% là id=100, 1% là id=1 :V Trong khi đáng lẽ phải trả về 50%- 50%. Cách này tùy vào lỗ hổng rộng bao nhiêu mà độ “ngẫu nhiên” cao hay thấp :V

muốn chính xác toàn bộ thì bước 1 phải quét tất cả id trong bảng lên, rồi sample n id từ bảng này, rồi select … in (n samples), vậy cũng gần y hệt như order by rand() rồi :V Ko biết order by rand() nó có biết tối ưu thay vì sort nó đi sample ko nhỉ :V


(XXXTentacion) #23

đúng là nếu muốn kết quả chính xác nhất thì chỉ có Order By Rand(), nhưng tiếc là cái performance nó cực kỳ tệ :frowning:


(‏) #24

kiến nghị lên hội đồng SQL thêm keyword SAMPLE đi =] SELECT * FROM table SAMPLE 10 =]

í mà đọc doc thấy nó ghi order by rand() là nó assign cho mỗi dòng 1 giá trị rand() mới, rồi sort theo giá trị ngẫu nhiên này, nhưng như vậy thì cũng có khả năng sort 10 dòng có giá trị rand() giống nhau vậy sort cũng như ko, cũng ko phải ngẫu nhiên 100% :V


(Đào An) #25

Mua bản enterprise rồi vào support chửi thử xem có cách gì ko :smile:


(Cao Ngoc Tau) #26

Cái này không phải là tìm kiếm. Nhưng nó lấy một số ngẫu nhiên thì


(rogp10) #27
SELECT id
FROM table
WHERE create_at BETWEEN "2019-01-01" AND "2019-02-01"
SAMPLE 10 -- <-- chưa có 

tìm kiếm đó :smiley:

Căn bản vẫn là phải sinh ra tất cả kết quả rồi mới sample được :smiley: rồi index ntn nữa.


(‏) #28

thử dòng sql này xem: https://www.periscopedata.com/blog/how-to-sample-rows-in-sql-273x-faster

select * from users
where id in (
  select round(random() * 21e6)::integer as id
  from generate_series(1, 110)
  group by id -- Discard duplicates
)
limit 100

chắc cũng gần gần đúng =]


(thienph) #29

generate_series --> chỉ hỗ trợ trong postgresql


(‏) #30

vậy chắc phải xài tới ngôn ngữ ngoài SQL :V Mà cái này cũng ko đúng 100% vì có group by id ở cái select bên trong, nghĩa là 110 id ở trong tạo ra sẽ được sắp xếp lại theo thứ tự nào đó, có thể là tăng dần, mà tăng dần thì số nhỏ sẽ được ưu tiên hơn số lớn khi chọn ra 100 id :V Bất tiện thứ 2 là số 21e6 có thể thay đổi, chọn số 110 dựa trên tiêu chí gì, nếu là 10% của 100 thì magic number 10% ở đâu ra v.v… :V Có thể ví dụ trong bài kia là id liên tục, còn ở đây id có thể ko liên tục, vậy ko biết % id bị xóa là bao nhiêu %, nếu là 50% thì magic number kia chắc phải vặn lên 100%-200% :V nếu chỉ bị xóa 10% thì có thể còn 20% v.v… nhưng với random ngẫu nhiên thì vẫn có xác suất thu về ko đủ 100 dòng, vậy rốt cuộc vẫn phải quay lại làm 1 vòng while ở ngoài đếm đủ số lượng :V


(‏) #31

plot
maxid=500, count()=400, 1 cái gap bự và mấy chục cái gap ngẫu nhiên :V

màu xanh dương là random sample
màu vàng là where id <= a1 :V
màu xanh lá là group by id bên trong :V

màu xanh dương random “chính xác”, gần như đường thẳng
màu vàng cứ id nằm sau mỗi gap thì xác suất ra nó cao hơn
màu xanh lá gần đúng như màu xanh dương, nhưng với id cao thì xác suất ra thấp hơn, vì group by id có thể sort id từ bé tới lớn, rồi cắt ngang 100 id đầu tiên, dẫn tới các id số lớn bị thiệt thòi :V

là hơn hết nữa là màu vàng và xanh lá đều ko chính xác 100 id trả về, có thể thấp hơn, đòi hỏi phải tùy chỉnh hằng số k như trong màu xanh lá hoặc làm vòng while :V

thử cái link repl cái :rofl:

nếu vặn k trong sample3 lên max(p) / len(p) * 1.5 thì nó ra mean=250 nghĩa là lúc nào cũng trả về đúng 100 phần tử, ko bị thiếu, nhưng lại ra hình xác suất thế này =]
index


(XXXTentacion) #32

nếu phải while thì mình nghĩ generate 1 mảng 50 số rồi whereIn id() cho nó chạy while sẽ chính xác hơn

btw, nice solution


(Hà Mã Tím) #33

Nếu mấy bạn đã không chịu dùng search engine như Hà Mã Tím đáng yêu gợi ý thì thôi.
Vẫn còn một cách khác, đừng bao giờ bắt csdl random 1 triệu records rồi lấy ra 50 records, rất tốn điện và thời gian. :crazy_face::crazy_face::crazy_face:
Bây giờ bạn hãy viết 1 func random() cho ra 50 số ngẫu nhiên trong dãy 1 triệu, sau đó query 50 lần lấy ra 50 records với id tương ứng, tại sao phải query 50 lần?:male_detective::male_detective::male_detective:

  1. Thứ nhất để có thể kết hợp với cached, vì nếu là tổ hợp chập 50 thì tỷ lệ query trúng cached rất thấp. Nên ta query từng lệnh để tăng tỷ lệ dùng cached.
  2. Dễ try_catch nếu id không tồn tại. Nếu gặp tình trạng id không tồn tại ta có thể random tiêp với điều kiện đến khi đủ 50 records trả về.

Nếu kết hợp với query cached thì chắc chắn tốc độ là khét lẹt.


(XXXTentacion) #34

cơ mà lỡ random 1000 trong 1 triệu thì phải query 1000 lần? :frowning:

nhưng vừa check query cache ở MYSQL thì nó ra vầy …


83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?