SQL 데이터베이스의 단순 무작위 샘플

SQL 데이터베이스의 단순 무작위 샘플

---

SQL에서 효율적인 단순 무작위 샘플을 어떻게 가져 옵니까? 문제의 데이터베이스는 MySQL을 실행하고 있습니다. 내 테이블은 최소 200,000 개의 행이고 약 10,000 개의 간단한 무작위 샘플을 원합니다.

"명백한"대답은 다음과 같습니다.

SELECT * FROM table ORDER BY RAND() LIMIT 10000

큰 테이블의 경우 너무 느립니다. 모든 행 (이미 O (n)에 배치)에 대해 RAND ()를 호출하고 정렬하여 기껏해야 O (n lg n)로 만듭니다. O (n)보다 빠르게 수행 할 수있는 방법이 있습니까?

참고 : Andrew Mao가 주석에서 지적했듯이 SQL Server에서이 방법을 사용하는 경우 RAND () 가 모든 행에 대해 동일한 값을 반환 할 수 있으므로 T-SQL 함수 NEWID ()를 사용해야합니다 .

편집 : 5 년 후

나는 더 큰 테이블 로이 문제를 다시 만났고 두 가지 조정으로 @ignorant의 솔루션 버전을 사용하게되었습니다.

• 원하는 샘플 크기의 2-5 배로 행을 샘플링하여 저렴하게 ORDER BY RAND ()
• 삽입 / 업데이트 할 때마다 RAND ()의 결과를 색인화 된 열에 저장합니다. (데이터 세트가 업데이트가 많지 않은 경우이 열을 최신 상태로 유지하는 다른 방법을 찾아야 할 수 있습니다.)

테이블의 1000 개 항목 샘플을 가져 오기 위해 행 수를 세고 frozen_rand 열을 사용하여 평균 10,000 개 행으로 결과를 샘플링합니다.

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

(제 실제 구현에는 언더 샘플링을 방지하고 rand_high를 수동으로 래핑하는 데 더 많은 작업이 포함되지만 기본 아이디어는 "N을 몇 천으로 무작위로 줄이는 것"입니다.)

이로 인해 약간의 희생이 발생하지만 인덱스 스캔을 사용하여 데이터베이스를 샘플링하여 다시 ORDER BY RAND () 할 수있을만큼 작아 질 때까지 사용할 수 있습니다.

---

여기에 이러한 유형의 문제에 대한 매우 흥미로운 논의가 있습니다. http://www.titov.net/2005/09/21/do-not-use-order-by-rand-or-how-to-get-random-rows-from-table/

나는 당신의 O (n lg n) 솔루션이 최고라는 테이블에 대한 가정이 전혀 없다고 생각합니다. 실제로 좋은 최적화 프로그램이나 약간 다른 기술을 사용하면 나열하는 쿼리가 조금 더 좋을 수 있습니다. O (m * n) 여기서 m은 전체 큰 배열을 정렬 할 필요가 없기 때문에 원하는 임의의 행 수입니다. , 가장 작은 m 번만 검색 할 수 있습니다. 그러나 당신이 게시 한 숫자의 경우 m은 어쨌든 lg n보다 큽니다.

우리가 시도해 볼 수있는 세 가지 가정 :

1. 테이블에 고유 한 색인화 된 기본 키가 있습니다.

2. 선택하려는 임의의 행 수 (m)가 테이블의 행 수 (n)보다 훨씬 적습니다.

3. 고유 한 기본 키는 간격이없는 1에서 n까지의 정수입니다.

가정 1과 2 만 사용하면 O (n)에서 수행 할 수 있다고 생각하지만 가정 3과 일치하려면 테이블에 전체 인덱스를 작성해야하므로 반드시 빠른 O (n)이 아닙니다. 추가적으로 테이블에 대해 좋은 것을 가정 할 수 있다면 O (m log m)에서 작업을 수행 할 수 있습니다. 가정 3은 작업하기 쉽고 좋은 추가 속성입니다. 연속적으로 m 개의 숫자를 생성 할 때 중복을 보장하지 않는 멋진 난수 생성기를 사용하면 O (m) 솔루션이 가능합니다.

세 가지 가정이 주어지면 기본 아이디어는 1과 n 사이의 m 개의 고유 한 난수를 생성 한 다음 테이블에서 해당 키가있는 행을 선택하는 것입니다. 나는 지금 내 앞에 mysql이나 아무것도 없기 때문에 약간의 의사 코드에서 이것은 다음과 같이 보일 것입니다.

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

효율성에 대해 정말로 염려했다면 일종의 절차 적 언어로 임의 키 생성을 수행하고 결과를 데이터베이스에 삽입하는 것을 고려할 수 있습니다. .

---

가장 빠른 해결책은

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

이것이 제가 일을해야한다고 생각하는 이유입니다.

• 각 행에 대해 난수를 생성합니다. 숫자는 0과 1 사이입니다.
• 생성 된 숫자가 0에서 .3 (30 %) 사이 인 경우 해당 행을 표시할지 여부를 평가합니다.

이것은 rand ()가 균등 분포로 숫자를 생성한다고 가정합니다. 이를 수행하는 가장 빠른 방법입니다.

누군가가 그 해결책을 추천했고 그들은 증거없이 격추당하는 것을 보았다. 여기에 내가 말하고 싶은 것은-

• 이것은 O (n)이지만 정렬이 필요하지 않으므로 O (n lg n)보다 빠릅니다.

• mysql은 각 행에 대해 난수를 생성 할 수 있습니다. 이 시도 -

  INFORMATION_SCHEMA.TABLES 제한 10에서 rand ()를 선택합니다.

문제의 데이터베이스가 mySQL이므로 이것이 올바른 솔루션입니다.

---

ORDER BY RAND ()보다 빠름

이 방법이보다 훨씬 빠르다는 것을 테스트 ORDER BY RAND()했기 때문에 O (n) 시간에 실행되며 매우 빠릅니다.

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

비 MSSQL 버전 -나는 이것을 테스트하지 않았습니다.

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

MSSQL 버전 :

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

레코드의 ~ 1 %를 선택합니다. 따라서 정확한 백분율 또는 레코드 수를 선택해야하는 경우 일부 안전 여유를 사용하여 백분율을 추정 한 다음 더 비싼 ORDER BY RAND()방법을 사용하여 결과 집합에서 초과 레코드를 무작위로 추출 합니다.

더 빠르게

I was able to improve upon this method even further because I had a well-known indexed column value range.

For example, if you have an indexed column with uniformly distributed integers [0..max], you can use that to randomly select N small intervals. Do this dynamically in your program to get a different set for each query run. This subset selection will be O(N), which can many orders of magnitude smaller than your full data set.

In my test I reduced the time needed to get 20 (out 20 mil) sample records from 3 mins using ORDER BY RAND() down to 0.0 seconds!

---

Just use

WHERE RAND() < 0.1 

to get 10% of the records or

WHERE RAND() < 0.01 

to get 1% of the records, etc.

---

Apparently in some versions of SQL there's a TABLESAMPLE command, but it's not in all SQL implementations (notably, Redshift).

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

---

I want to point out that all of these solutions appear to sample without replacement. Selecting the top K rows from a random sort or joining to a table that contains unique keys in random order will yield a random sample generated without replacement.

If you want your sample to be independent, you'll need to sample with replacement. See Question 25451034 for one example of how to do this using a JOIN in a manner similar to user12861's solution. The solution is written for T-SQL, but the concept works in any SQL db.

---

Starting with the observation that we can retrieve the ids of a table (eg. count 5) based on a set:

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

we can come to the result that if we could generate the string "(4, 1, 2, 5, 3)", then we would have a more efficient way than RAND().

For example, in Java:

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(']', ')');

If ids have gaps, then the initial arraylist indices is the result of an sql query on ids.

---

If you need exactly m rows, realistically you'll generate your subset of IDs outside of SQL. Most methods require at some point to select the "nth" entry, and SQL tables are really not arrays at all. The assumption that the keys are consecutive in order to just join random ints between 1 and the count is also difficult to satisfy — MySQL for example doesn't support it natively, and the lock conditions are... tricky.

Here's an O(max(n, m lg n))-time, O(n)-space solution assuming just plain BTREE keys:

1. Fetch all values of the key column of the data table in any order into an array in your favorite scripting language in O(n)
2. Perform a Fisher-Yates shuffle, stopping after m swaps, and extract the subarray [0:m-1] in ϴ(m)
3. "Join" the subarray with the original dataset (e.g. SELECT ... WHERE id IN (<subarray>)) in O(m lg n)

Any method that generates the random subset outside of SQL must have at least this complexity. The join can't be any faster than O(m lg n) with BTREE (so O(m) claims are fantasy for most engines) and the shuffle is bounded below n and m lg n and doesn't affect the asymptotic behavior.

In Pythonic pseudocode:

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

---

Maybe you could do

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

참고URL : https://stackoverflow.com/questions/249301/simple-random-samples-from-a-sql-database