Bagaimana cara mengambil sampel acak sederhana yang efisien dalam SQL? Database yang dimaksud menjalankan MySQL; tabel saya setidaknya 200.000 baris, dan saya ingin sampel acak sederhana sekitar 10.000.

Jawaban yang "jelas" adalah:

SELECT * FROM table ORDER BY RAND() LIMIT 10000

Untuk tabel besar, itu terlalu lambat: ia memanggil RAND()setiap baris (yang sudah menempatkannya di O (n)), dan mengurutkannya, menjadikannya O (n lg n) paling baik. Apakah ada cara untuk melakukan ini lebih cepat dari O (n)?

Catatan : Seperti yang ditunjukkan Andrew Mao di komentar, Jika Anda menggunakan pendekatan ini di SQL Server, Anda harus menggunakan fungsi T-SQL NEWID(), karena RAND () dapat mengembalikan nilai yang sama untuk semua baris .

EDIT: 5 TAHUN KEMUDIAN

Saya mengalami masalah ini lagi dengan tabel yang lebih besar, dan akhirnya menggunakan versi solusi @ ignorant, dengan dua penyesuaian:

• Sampel baris menjadi 2-5x ukuran sampel yang saya inginkan, dengan harga murah ORDER BY RAND()
• Simpan hasil RAND()ke kolom terindeks di setiap penyisipan / pembaruan. (Jika kumpulan data Anda tidak terlalu banyak memperbarui, Anda mungkin perlu menemukan cara lain untuk menjaga kolom ini tetap segar.)

Untuk mengambil sampel 1000 item dari sebuah tabel, saya menghitung baris dan mengambil sampel hasilnya hingga, rata-rata, 10.000 baris dengan kolom frozen_rand:

SELECT COUNT(*) FROM table; -- Use this to determine rand_low and rand_high

  SELECT *
    FROM table
   WHERE frozen_rand BETWEEN %(rand_low)s AND %(rand_high)s
ORDER BY RAND() LIMIT 1000

(Implementasi aktual saya melibatkan lebih banyak pekerjaan untuk memastikan saya tidak kekurangan sampel, dan untuk membungkus secara manual rand_high, tetapi ide dasarnya adalah "secara acak potong N Anda menjadi beberapa ribu.")

Meskipun ini membuat beberapa pengorbanan, ini memungkinkan saya untuk mengambil sampel database menggunakan pemindaian indeks, hingga cukup kecil untuk digunakan ORDER BY RAND()kembali.

Ada diskusi yang sangat menarik tentang jenis masalah ini di sini: http://www.titov.net/2005/09/21/do-not-use-order-by-rand-or-how-to-get-random-rows-from-table/

Saya pikir sama sekali tidak ada asumsi tentang tabel bahwa solusi O (n lg n) Anda adalah yang terbaik. Meskipun sebenarnya dengan pengoptimal yang baik atau teknik yang sedikit berbeda, kueri yang Anda daftar mungkin sedikit lebih baik, O (m * n) di mana m adalah jumlah baris acak yang diinginkan, karena tidak perlu mengurutkan seluruh larik besar , itu hanya bisa mencari m kali terkecil. Tetapi untuk jenis nomor yang Anda posting, m lebih besar dari lg n.

Tiga asumsi yang bisa kita coba:

1. ada kunci utama yang unik dan terindeks dalam tabel

2. jumlah baris acak yang ingin Anda pilih (m) jauh lebih kecil dari jumlah baris pada tabel (n)

3. kunci utama unik adalah bilangan bulat yang berkisar dari 1 hingga n tanpa celah

Dengan hanya asumsi 1 dan 2 saya pikir ini dapat dilakukan di O (n), meskipun Anda harus menulis seluruh indeks ke tabel untuk mencocokkan asumsi 3, jadi tidak perlu O (n) yang cepat. Jika kita bisa secara TAMBAHAN mengasumsikan sesuatu yang bagus tentang tabel, kita bisa melakukan tugas di O (m log m). Asumsi 3 akan menjadi properti tambahan yang bagus dan mudah untuk dikerjakan. Dengan generator nomor acak yang menjamin tidak ada duplikat saat menghasilkan nomor m berturut-turut, solusi O (m) akan dimungkinkan.

Mengingat ketiga asumsi tersebut, ide dasarnya adalah untuk menghasilkan m bilangan acak unik antara 1 dan n, dan kemudian memilih baris dengan kunci tersebut dari tabel. Saya tidak memiliki mysql atau apapun di depan saya sekarang, jadi dalam sedikit pseudocode ini akan terlihat seperti:

create table RandomKeys (RandomKey int)
create table RandomKeysAttempt (RandomKey int)

-- generate m random keys between 1 and n
for i = 1 to m
  insert RandomKeysAttempt select rand()*n + 1

-- eliminate duplicates
insert RandomKeys select distinct RandomKey from RandomKeysAttempt

-- as long as we don't have enough, keep generating new keys,
-- with luck (and m much less than n), this won't be necessary
while count(RandomKeys) < m
  NextAttempt = rand()*n + 1
  if not exists (select * from RandomKeys where RandomKey = NextAttempt)
    insert RandomKeys select NextAttempt

-- get our random rows
select *
from RandomKeys r
join table t ON r.RandomKey = t.UniqueKey

Jika Anda benar-benar prihatin tentang efisiensi, Anda dapat mempertimbangkan untuk melakukan pembuatan kunci acak dalam beberapa jenis bahasa prosedural dan memasukkan hasilnya ke dalam database, karena hampir semua hal selain SQL mungkin akan lebih baik pada jenis perulangan dan pembuatan nomor acak yang diperlukan .

Saya pikir solusi tercepat adalah

select * from table where rand() <= .3

Inilah mengapa saya pikir ini harus melakukan pekerjaan itu.

• Ini akan membuat nomor acak untuk setiap baris. Angka tersebut antara 0 dan 1
• Ini mengevaluasi apakah akan menampilkan baris itu jika angka yang dihasilkan antara 0 dan .3 (30%).

Ini mengasumsikan bahwa rand () menghasilkan angka dalam distribusi seragam. Ini adalah cara tercepat untuk melakukan ini.

Saya melihat bahwa seseorang telah merekomendasikan solusi itu dan mereka ditembak jatuh tanpa bukti .. inilah yang akan saya katakan untuk itu -

• Ini adalah O (n) tetapi tidak diperlukan penyortiran sehingga lebih cepat daripada O (n lg n)

• mysql sangat mampu menghasilkan angka acak untuk setiap baris. Coba ini -

  pilih rand () dari INFORMATION_SCHEMA.TABLES batas 10;

Karena database yang dimaksud adalah mySQL, ini adalah solusi yang tepat.

Rupanya di beberapa versi SQL ada TABLESAMPLEperintah, tetapi tidak di semua implementasi SQL (terutama, Redshift).

http://technet.microsoft.com/en-us/library/ms189108(v=sql.105).aspx

Gunakan saja

WHERE RAND() < 0.1 

untuk mendapatkan 10% dari rekaman atau

WHERE RAND() < 0.01 

untuk mendapatkan 1% dari rekaman, dll.

Lebih cepat dari ORDER BY RAND ()

Saya menguji metode ini untuk menjadi jauh lebih cepat daripada ORDER BY RAND(), karena itu berjalan dalam waktu O (n) , dan melakukannya dengan sangat cepat.

Dari http://technet.microsoft.com/en-us/library/ms189108%28v=sql.105%29.aspx :

Versi non-MSSQL - Saya tidak menguji ini

SELECT * FROM Sales.SalesOrderDetail
WHERE 0.01 >= RAND()

Versi MSSQL:

SELECT * FROM Sales.SalesOrderDetail
WHERE 0.01 >= CAST(CHECKSUM(NEWID(), SalesOrderID) & 0x7fffffff AS float) / CAST (0x7fffffff AS int)

Ini akan memilih ~ 1% dari rekaman. Jadi, jika Anda membutuhkan # tepat persentase atau rekaman untuk dipilih, perkirakan persentase Anda dengan beberapa margin keamanan, lalu petik kelebihan rekaman secara acak dari set yang dihasilkan, dengan menggunakan metode yang lebih mahal ORDER BY RAND().

Bahkan lebih cepat

Saya dapat meningkatkan metode ini lebih jauh karena saya memiliki rentang nilai kolom terindeks yang terkenal.

Misalnya, jika Anda memiliki kolom terindeks dengan bilangan bulat terdistribusi seragam [0..maks], Anda dapat menggunakannya untuk memilih N interval kecil secara acak. Lakukan ini secara dinamis dalam program Anda untuk mendapatkan kumpulan berbeda untuk setiap kueri yang dijalankan. Pilihan subset ini akan menjadi O (N) , yang dapat memiliki banyak urutan lebih kecil dari kumpulan data lengkap Anda.

Dalam pengujian saya, saya mengurangi waktu yang diperlukan untuk mendapatkan 20 (dari 20 juta) rekaman sampel dari 3 menit menggunakan ORDER BY RAND () menjadi 0,0 detik !

Saya ingin menunjukkan bahwa semua solusi ini tampaknya mengambil sampel tanpa penggantian. Memilih baris K teratas dari pengurutan acak atau bergabung ke tabel yang berisi kunci unik dalam urutan acak akan menghasilkan sampel acak yang dihasilkan tanpa penggantian.

Jika Anda ingin sampel Anda independen, Anda harus mengambil sampel dengan penggantian. Lihat Pertanyaan 25451034 untuk satu contoh bagaimana melakukan ini menggunakan GABUNG dengan cara yang mirip dengan solusi user12861. Solusinya ditulis untuk T-SQL, tetapi konsep ini berfungsi di semua db SQL.

Dimulai dengan pengamatan bahwa kita dapat mengambil id dari sebuah tabel (mis. Hitung 5) berdasarkan satu set:

select *
from table_name
where _id in (4, 1, 2, 5, 3)

kita bisa sampai pada hasil bahwa jika kita bisa menghasilkan string "(4, 1, 2, 5, 3)", maka kita akan memiliki cara yang lebih efisien daripada RAND().

Misalnya, di Jawa:

ArrayList<Integer> indices = new ArrayList<Integer>(rowsCount);
for (int i = 0; i < rowsCount; i++) {
    indices.add(i);
}
Collections.shuffle(indices);
String inClause = indices.toString().replace('[', '(').replace(']', ')');

Jika id memiliki celah, maka daftar larik awal indicesadalah hasil dari kueri sql pada id.

Jika Anda membutuhkan mbaris persis , secara realistis Anda akan menghasilkan subset ID di luar SQL. Kebanyakan metode memerlukan di beberapa titik untuk memilih entri "nth", dan tabel SQL sebenarnya bukan array sama sekali. Asumsi bahwa kunci berurutan untuk hanya menggabungkan int acak antara 1 dan hitungan juga sulit dipenuhi - MySQL misalnya tidak mendukungnya secara asli, dan kondisi kunci ... rumit .

Berikut adalah solusi O(max(n, m lg n))-time, O(n)-space dengan asumsi hanya kunci BTREE biasa:

1. Ambil semua nilai kolom kunci dari tabel data dalam urutan apa pun ke dalam larik dalam bahasa skrip favorit Anda di O(n)
2. Lakukan pengacakan Fisher-Yates , hentikan setelah mpenukaran, dan ekstrak subarray [0:m-1]masukϴ(m)
3. "Gabung" subarray dengan dataset asli (misalnya SELECT ... WHERE id IN (<subarray>)) diO(m lg n)

Setiap metode yang menghasilkan subset acak di luar SQL setidaknya harus memiliki kompleksitas ini. Gabungan tidak bisa lebih cepat daripada O(m lg n)dengan BTREE (jadi O(m)klaim adalah fantasi untuk sebagian besar mesin) dan pengocokan dibatasi di bawah ndan m lg ndan tidak mempengaruhi perilaku asimtotik.

Dalam pseudocode Pythonic:

ids = sql.query('SELECT id FROM t')
for i in range(m):
  r = int(random() * (len(ids) - i))
  ids[i], ids[i + r] = ids[i + r], ids[i]

results = sql.query('SELECT * FROM t WHERE id IN (%s)' % ', '.join(ids[0:m-1])

Pilih 3000 catatan acak di Netezza:

WITH IDS AS (
     SELECT ID
     FROM MYTABLE;
)

SELECT ID FROM IDS ORDER BY mt_random() LIMIT 3000

Mencoba

SELECT TOP 10000 * FROM table ORDER BY NEWID()

Apakah ini akan memberikan hasil yang diinginkan, tanpa terlalu rumit?

Dalam dialek tertentu seperti Microsoft SQL Server, PostgreSQL, dan Oracle (tetapi bukan MySQL atau SQLite), Anda dapat melakukan sesuatu seperti

select distinct top 10000 customer_id from nielsen.dbo.customer TABLESAMPLE (20000 rows) REPEATABLE (123);

Alasan untuk tidak hanya melakukannya (10000 rows)tanpa topadalah karena TABLESAMPLElogikanya memberi Anda jumlah baris yang sangat tidak tepat (seperti terkadang 75%, terkadang 1,25% kali), jadi Anda ingin mengambil sampel berlebihan dan memilih angka yang tepat yang Anda inginkan. Ini REPEATABLE (123)untuk menyediakan benih acak.

Mungkin Anda bisa melakukannya

SELECT * FROM table LIMIT 10000 OFFSET FLOOR(RAND() * 190000)