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)?

#1

Xuất phát từ câu hỏi MySQL select 10 random rows from 600K rows fast

Mình tìm được vài điểm bất hợp lý sau:

1. Với accepted answer

SELECT name
  FROM random AS r1 JOIN
       (SELECT CEIL(RAND() *
                     (SELECT MAX(id)
                        FROM random)) AS id)
        AS r2
 WHERE r1.id >= r2.id
 ORDER BY r1.id ASC
 LIMIT 1

===> Các record được chọn sẽ là liên tục, không phải ngẫu nhiên

2. Với cách dùng ORDER BY RAND()

SELECT column FROM table
ORDER BY RAND()
LIMIT 10

===> tốc độ query sẽ chậm (tầm hơn 1s cho 100 records random với table 1 triệu records)

Và dưới đây là solution của mình: dùng UNION + Limit trong mysql kết hợp PHP:

  • Chạy vòng for từ 0 -> N
  • Với mỗi vòng for, random 1 số a = 0 -> MAX(id) -1
  • câu query sẽ có dạng sau:
select column from table where id >= a1
Limit 1
union
select column from table where id >= a2
Limit 1
union
...
select column from table where id >= an
Limit 1

Và tốc độ của câu query trên là 0.4s cho 100 records random với table 1 triệu records

p/s: mình vẫn thấy cách này vẫn chưa tối ưu / tốt lắm. Mọi người ai có cách nào thì thảo luận nhé. Cám ơn mọi người

Lưu ý: điều kiện của bảng là id có thể KHÔNG LIÊN TỤC

1 Like
#2

Sao ko random bằng index rồi select by index mà fetch data ?

3 Likes
#3

bạn trình bày rõ hơn được không? Mình chưa hiểu ý bạn lắm

#4

Giả sử dữ liệu ko thường thay đổi thì bạn có thể lưu riêng id ra 1 array rồi random array này
Rồi sài Select in

"select * from info WHERE `id` IN ('$ids')"

m nghĩ chắc chắn là nhanh hơn so với query trên db.
Còn nữa bạn có thể sài postgresql thay thế vì một số tính năng hay ho, tối ưu toàn chỉ có trên mysql enterprise mà thôi

2 Likes
#5

Cái này chạy đâu có đúng vì bảng id ko liên tục mà :v

Xài union limit 1 n lần cũng ko đúng vì có thể bị trùng id :v sort by rand() là ‘chuẩn’ rồi :v có thể tăng tốc bằng cách chỉ sort cột id thay vì toàn bộ các cột như mấy answer ở dưới trong link SO đó đó :v

2 Likes
#6

mình đã từng nghĩ đến cách này, nhưng nó sẽ có thể không lấy được N số với db bị thủng vài record, bắt buộc phải do/while để lấy được N record như ý muốn

p/s: cách của mình cũng chỉ tương đối, chứ không phải chính xác như Order By Rand()

#7

với một lượng dữ liệu ở mức hàng triệu tới hàng tỉ records bạn nên dùng search engine, 2 search engine trâu bò nhất hiện thời là Elastic và Sphinx, Hà Mã Tím đáng yêu đang dùng Sphinx
VD: duyệt tìm trong cơ sở dữ liệu 24 tỉ bản ghi trong 900ms

2 Likes
#8

Order By Rand cực kỳ tệ trong trường hợp table có vài triệu record :frowning:

#9

Bác làm vậy thì khác nào bảo chủ thớt sài luôn NoSql ~~.
Theo m thì chủ thớt cứ thử test thử các dbsql khác mysql xem vì query sql chỉ có vài cách như thế thôi ko hơn đc đâu.

3 Likes
#10

Chẳng phải như tiêu đề thớt bảo mục đích chính của thớt là tìm kiếm sao :laughing::laughing: nên dùng Search Engine là chuẩn bài òi :stuck_out_tongue_closed_eyes::stuck_out_tongue_closed_eyes::stuck_out_tongue_closed_eyes::stuck_out_tongue_winking_eye::stuck_out_tongue_winking_eye::stuck_out_tongue_winking_eye::smiling_face_with_three_hearts::smiling_face_with_three_hearts::smiling_face_with_three_hearts:

1 Like
#11

tiếc là mình đang cần solution cho thằng mysql T__T

1 Like
#12

tonviet712
không vấn đề gì vì search engine chỉ tạo ra 1 search interface nằm giữa, nên tích hợp rất dễ nha :male_detective:

3 Likes
#13

vậy à, mình sẽ nghiên cứu. Thank bạn trước :smiley:

1 Like
#14

1 triệu record chắc vài ký Ram mất ~~

2 Likes
#15

thử cái này chưa: https://stackoverflow.com/a/41581041

SELECT * FROM tbl WHERE id IN 
    (SELECT id FROM (SELECT id FROM tbl ORDER BY RAND() LIMIT 10) t)

chỉ sort ID thôi, 1 triệu id ~ 4-8MB chắc cũng lẹ lắm :V

1 Like
#16 
set @total:= (SELECT TABLE_ROWS - 1 FROM INFORMATION_SCHEMA.TABLES WHERE TABLE_SCHEMA = '<db>' and TABLE_NAME='<tb>');
set @offset:= FLOOR(RAND() * @total);
PREPARE EX FROM 'select * from <tb> limit ?,1';
EXECUTE EX USING @offset;

Bạn thử cách này xem

2 Likes
#17

image
image.png1486×224 39.5 KB

Vẫn xài Order By Rand cho bảng bự mà. Mình thấy không tối ưu lắm

#18

bạn giải thích rõ hơn về câu query này được không?

#19
  1. Lấy tổng record của table dựa vào INFORMATION_SCHEMA (đây là nơi lưu toàn bộ thông tin của database mysql, nhanh hơn table cần lấy rất nhiều)
  2. Random offset dựa vào tổng ở (1)
  3. Query table theo offset đã có ở (2)

Cách này tương đương performance của select limit
*** Bởi vì mysql query không chấp nhận var bên trong limit nên cần dùng thêm PREPARE và EXECUTE

1 Like
#20

mình vừa test, thuật toán của bạn cho kết quả tương tự solution 1 trên stackoverflow
nó sẽ ra kết quả 1 dãy ID liên tục. Với thuật toán này thì trường hợp để có 10 record mà trong đó ID rải đều từ 1 đến 1 triệu là không thể

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