在 MySQL 中，從 10 萬條主鍵不連續的數據里隨機取 3000 條，如何做到高效？

12-29

幾百萬記錄的表，每天大概有10萬條記錄發生更新，從這10萬條里隨機取3000條做數據分析，
select id from table where date_refresh = 20120329 order by rand() limit 0,3000
狂慢！！！大概三四十秒吧

你 sort 那幾百萬行的表幹啥……

SELECT id FROM table WHERE date_refresh = 20120329

取出當日更新的10萬 id （你給 date_refresh 建了索引對吧？），放內存裡面隨機 shuffle 一下，頂多佔用幾 MB 內存，取前 3000 個，然後

SELECT * FROM table WHERE id IN (id_0, id_1, id_2, ..., id_2999)

這個問題有點意思。

按照我的理解，「從10萬條數據里隨機取3000條用於數據分析」這個需求，關鍵是取樣的均勻性。也就是說，不能簡單地連續取3000條數據，而是要讓取樣盡量覆蓋整個數據區間。但是對於均勻性來說，隨機取樣並不是必要的，或者更嚴格地說，隨機取樣其實不能完全滿足均勻性的要求，因為在極端情況下，隨機取樣仍然可能集中在區間的某一部分。簡單的均勻取樣的方式就是從區間m中均勻地取n個樣本，也就是每m/n條記錄取一條。

但是，更重要的問題是ID是不連續的。也就是說，無法簡單地通過n/m的步長來事先計算id以取得數據。也就是說，這個問題歸結為「在傾斜數據集中進行均勻取樣」的演算法。

在這種情況下，最直觀的方法是使用臨時表先將ID變成連續的。樓上Rio提出的演算法：

取出當日更新的10萬 id放入一個數組
在數組中隨機取出3000個id
用select in讀取指定的3000條記錄

就是「通過臨時表先將ID變成連續」的解決方式。另外幾位提出了進一步的優化，即在每次更新原表時，就將ID先存入一個臨時表或數組裡，避免了在讀取數據時再創建臨時表,但演算法本質上是一樣的。

這個演算法最大的開銷是要建立一個臨時表。假設當日更新有記錄有m條，需要隨時選取n條，那麼成本包括：

讀取原表中所有當日更新的id O(m)
把所有這些id寫入臨時表
O(m)
在臨時表中隨機選取n個id O(n)
在原表中讀取n條記錄
O(n)

一共是O(m)*2 + O(n)*2，其中最大的成本是兩個O(m)。一般來說，取樣數量n比較小，但是區間m可能會非常大。如果m不是10萬條，而是10億條甚至更多呢？O(m)*2就會大得讓人吃不消了。

有沒有辦法只對m讀取一次呢？有。如果我們知道m和n，就可以在遍歷m的時候，直接按照n/m的步長取值。

實現如下：創建一個store procedure。首先通過select count(*)取得所有當日更新記錄的數量（m，假設為10萬）。已知n為3000，所以步長為100000/3000=33。在select where date_refresh = 20120329上打開一個cursor，往下fetch，每33條記錄中返回一條。比較鬱悶的是，mysql的cursor不支持跳過記錄，所以必須逐行fetch。當cursor結束時，取樣即完成。

這裡有一個小變化。如果你實在不滿意每隔m/n條取一條的方式，堅持要隨機取樣，那麼可以在每個m/n條記錄的區間進行隨機取樣，也就是說，每次返回記錄時，按rand()*33決定返回的記錄。隨機函數的調用次數為n次而不是m次，所以是可以接受的。

但是且慢。當通過select count(*)取得所有當日更新記錄的數量，仍然需要掃描所有當日更新的id。當然，由於它不需要返回m個id，而只返回一個數字，運行速度肯定比select id要快得多。但是演算法複雜度仍然為O(m)。

一個優化方法是，設置一個內存計數器，在每次更新原表記錄時，將計數器加1，最終可以得到所有當日更新記錄的數量。這看起來，跟「更新原表時將ID先存入一個臨時表或數組裡」的方法差不多，實際性能差別極大。因為對整數進行單調遞增，是一個CPU原子操作。既不需要建立臨時表，也不需要建立數組，更不用處理鎖和並行的問題，簡單地執行一條CPU指令就可以了。

到這裡，可以看出新演算法在性能上提高了很多，但是看來我們還是沒有完全避免O(m)*2。有沒有辦法達到O(m)？有沒有辦法在事先不知道m的情況下進行取樣？甚至進一步，連O(m)都避免，只是簡單地讀取n條記錄，完全無視沒有落在取樣範圍以外的其它記錄？

回答是有。這要用到一種特殊的可變步長採樣演算法，而且可能無法用sql實現，需要hack mysql的內核。如果有機會我會貼一篇文章，暫時就不多說了。

LZ的問題：

在MySQL中，從10萬條主鍵不連續的數據里隨機取3000條，如何做到高效？修改

幾百萬記錄的表，每天大概有10萬條記錄發生更新，從這10萬條里隨機取3000條做數據分析，select id from table where date_refresh = 20120329 order by rand() limit 0,3000，狂慢！！！大概三四十秒吧

回答：

1.select id from table where date_refresh = 20120329 order by rand() limit 0,3000;是非常不明智的做法，因為RAND()函數的隨機因子變成這個表總數據量，所以速度會非常慢，跟讀取多少條記錄不是特別大的關係；

2. 表總記錄是幾百萬，也即不超過1KW

3.每天有大概10W條記錄發生更新，我理解為UPDATE，若是錯了，請LZ糾正，因為按此思路進行解答；

4.像這樣的記錄，應該有欄位記錄數據是否發生過變更，也即應該會有一個更新時間，比如TIMESTAMP類型的欄位非常適合，若是沒有，那隻能藉助觸發器，解決性能損失大點，從你的WHERE子句的欄位看，就是欄位：date_refresh

5.每天從主表中讀取 date_refresh發生變化的所有記錄的ID到一張表中，且ID欄位為主鍵；

6.再對這張表進行select id from table order by rand() limit 0,3000 ，或者不直接隨機，也即搞複雜點，利用程序實現內存隨機讀取數據的方案，若真是10W條可以考慮採用資料庫方式完成，畢竟一個欄位且是主鍵會非常快的

7.根據隨機到的3KID，再去主表讀取數據，進行下一步的分析...

[b]推薦：[/b]

[url=http://www.mysqlops.com/2012/03/29/oracle-dba-taobao-alibaba.html]淘寶和阿里巴巴去Oracle化事件引發資料庫技術人員大討論[/url]

因為你用了rand()，遍歷每條記錄都要運算一次rand()，當然慢了

我以前翻譯過一篇國外mysql牛人寫的關於隨機排序的文章，僅供參考

ORDER BY RAND()

主要的思路是，如果id是連續分布，那直接根據max(id)進行獲得隨機id，然後直接取出

如果id不連續，存在空擋，那麼可以總是選擇比隨機出的id大（或小）的記錄

如果id不連續，且必須儘可能平均地獲取記錄，那麼需要額外做一個表，將不連續的id映射成連續id，然後進行隨機

把所有的當天更新的ID取出來，放在文件里，我們就可以知道最大的行數。然後根據行數來隨機選擇某一行的數據。這個東西的難點在於你不能使用readline一行一行的讀，而要使用read來根據
判斷一行，找到相應的行。速度不會快，但估計比你那個快，你用的rand根本無法優化

需要看你所需3000條數據的分布，密度有沒有強要求。

從方案來說，不要把隨機種子的壓力放在DB上是根本，數據存儲基本都是b+tree，隨機是效率很低的行為。

如果知道id的範圍和分布，完全可以用程序隨機出3000個id，分別獲取，當然要注意盡量用fetch，否則3000次的單獨抓取效率也是很低的。

如果不知道id分布，可以把塊數據集取到本機的內存中（某欄位排序加limit），再用動態語言去隨機取數據。但是這樣的問題要注意內存的開銷，一次取多少塊數據可以滿足你的分布需求，篩選粒度的均勻程度，都會決定最終的性能。

Fastest PHP/MySQL algorithm to get random rows from a huge table

1.- SELECT MIN(id) AS minid from table where date_refresh = 20120329;

2.- SELECT id FROM pages WHERE (RAND()*100000)+minid;

3.- SELECT * FROM table WHERE id IN(id1,id2....id3000);

我覺的你的ID 如果是連續的你可以用上面方法

不明白你的記錄為什麼不是連續的

給每條記錄一個autoincrement的編號不可以嗎？

如果不是連續的那就只能用上面提到的辦法

讀出所有的10萬條記錄到個文件里，或者一個新的表裡

再按序處理

================================================

更新一下

那我試著用python處理一下

Python 不是很會，邊學邊寫的

拿小表格測試了，應該能運行

1.從表中讀取出當天發生更新的10萬條數據放到個list里

2.利用python的 random.shuffle()打亂這個list數據的順序

3.讀出前3000個數據

然後你就可以處理這3000個數據，或者查找這3000個ID對應的表的內容了

================================================

#!/usr/bin/python

import MySQLdb

import random

conn = MySQLdb.connect (host = "localhost",

user = "user",

passwd = "pwd",

db = "test")

cursor = conn.cursor ()

data =[]

#讀取資料庫里的當天發生更新的主鍵

cursor.execute("SELECT id FROM table where date_refresh = 20120329")

resList = cursor.fetchall()

#某種list的准換，我也不太明白，說是列表表列的區別（1L，2L，3L....）=&>[1,2,3]

data = [int(e[0])for e in resList]

#隨機打亂順序,我測試10 000個數據還是挺快的

random.shuffle(data)

# 取前3000個

data = data[:3000]

print data

cursor.close ()

conn.close ()

經本人精心研究及仔細測試，樓上除了加cache以外似乎沒有最優解，於是來一段我最常用的：

前言：要隨機篩選不連續的ID，用 &>= 或者 &<= 是必然的 hack 手段。

1、首先，請來一段 Random = 0-1 的隨機。例如：

&

表的數據越大，小數點需要留的越多。

2、於是，再建立以下的查詢

&= (SELECT FLOOR( MAX(id) * ".$rand.") FROM `table` ) ORDER BY id LIMIT 1;"; //run sql ?&>

再試試你平常用的手法呵呵。

當然，這個還是得掃表（範圍：RAND - MAXID），對於有極限要求的人來說還是不夠滴。

本回答只是提供一種思路。。。。

如果是強調隨機抽樣，那麼可以嘗試使用蓄水池抽樣演算法，保證每條數據被選中的概率是need_num/total_num。

我寫過一解決這問題的博文,請移步:如何隨機獲取資料庫不連續ID的數據？

每天新增的時候，記錄下id，存在內存中。再從內存中，在程序中，對10萬條id，隨機出3000個id，再到資料庫中查。

1.取出當天更新的最大和最小更新的ID

2.在程序里根據上步操作，得到的id區間隨機出3000個數字

3.根據這三千個數字作為id去查詢資料庫

此order by 是針對幾百萬條數據做rand()運算，然後再抽取3000條數據，效率低是正常的

支持Rio的說法：

為何不將原SQL拆分為兩步操作，即將data_refresh=20120329的所有ID至一個臨時表中，然後再做rand() 隨機抽取3000個id做分析？

個人認為此效率應當會大大提高。

1.只有資料庫可以用的話，冗餘一個表，做成連續id 對應不連續id，然後用max(id)取隨機數。

2.實際的業務，取某一個數據往往有cache層，如果主鍵分布不均勻可以把主鍵放到redis的集合中，從redis集合中隨機取就無敵的快了。

我有一個想法不知大家意下如何：先不管資料庫，先寫程序在從1到10萬這10萬個數中隨機取不重複的3000個數，把這3000個隨機數作為行號把數據取出來就是。像前面有的同學說把10萬個ID查出來，我覺得這樣這部分時間就可以省下來了~

程序控制

SELECT *

FROM `table` AS t1 JOIN (SELECT ROUND(RAND() * ((SELECT MAX(id) FROM `table`)-(SELECT MIN(id) FROM `table`))+(SELECT MIN(id) FROM `table`)) AS id) AS t2

WHERE t1.id &>= t2.id

ORDER BY t1.id LIMIT 1;

贊同Rio，請把資料庫只當做存儲。