[PostgreSQL] RANDOM SELECT와 성능

실제 쿼리를 작성하다보면, 때때로는 랜덤으로 데이터를 조회하고 싶을 때가 있다.
그럴때 흔히 사용하는 방법이 ORDER BY 절에 랜덤값을 넘겨서 무작위 데이터를 가져오는 것이다.

이 방법은 구현이 간단하고 직관적이나, 데이터의 크기가 커진다면 제 성능을 내기 어렵다는 단점이 있다. 테이블을 전체 풀스캔을 돌린 다음에, 난수값으로 전체 정렬을 돌리는 것이기 때문이다.
본질적으로 인덱스를 활용하지 못하는 구조다.

그래서 여기서는 랜덤으로 데이터를 뽑아올 수 있는 방법들 몇가지를 소개해보고, 각 성능과 한계점을 정리해보려 한다.

데이터 세팅

실제 성능 비교를 위해 데이터를 적당히 2000만개 정도만 세팅해봤다.

CREATE TABLE foo (
    id BIGSERIAL PRIMARY KEY,
    a BIGINT NOT NULL,
    b BIGINT NOT NULL,
    c BIGINT NOT NULL
);

INSERT INTO foo (a, b, c)
SELECT
    (random() * 100)::INTEGER as a,
    (random() * 1000)::INTEGER as b,
    (random() * 10000)::INTEGER as c
FROM
    generate_series(1, 20000000) AS t;

ORDER BY RANDOM

가장 간단한 구현법이다.

explain(analyze) select * from foo order by random() limit 100;

이 방법은 위에서 말했듯, 풀스캔 후 정렬을 하는 것이라 대규모 데이터셋에 대해서는 성능을 장담할 수 없다.
이 경우에만 해도 2초 정도나 걸렸다.

매우 느리고, 데이터가 커질수록 불리해지나. 랜덤 분포 자체에 대해서는 가장 완벽한 방법이다.

OFFSET RANDOM()

행이 총 몇개인지 알고있다면, 그냥 OFFSET에 랜덤값을 넣어서 돌리는 것도 꽤 나쁘지 않은 방법이다.
우리는 2000만개라는걸 알고 있으므로, 그냥 이런 식으로 쿼리를 날려볼 수도 있다.

explain(analyze) SELECT * FROM foo OFFSET floor(random() * 20000000) LIMIT 100;

사실 OFFSET 자체도 풀스캔 기반으로 인덱스를 스킵하는거라, 인덱스를 타지 못한다는 것은 크게 다르지 않다.
최악의 경우, 오프셋이 거의 맨 뒤에 있다면 전체 데이터를 풀스캔하는 것보다 나을 것이 없기 때문이다.

그래도 확률적으로는 맨 뒤까지 난수가 잡힐 확률은 낮고, 무거운 정렬도 없기 때문에, 아까 처음보다는 처리속도가 빨라진 것을 볼 수 있다.
대체로는 오프셋이 운좋게 초반에 잡히면 밀리초 단위로도 됐고, 웬만하면 1초 아래로 실행이 됐다.

단점은, 랜덤 분포가 고르지 않고 순차적으로 뭉쳐져 있는 덩어리 단위로만 가져올 수 있다는 단점이 있다. 고르게 가져오려면 여러번에 걸쳐 한개씩 가져오거나 해야한다.

RANDOM() < 0.01

필터링 기반으로 행을 거르는 것도 하나의 방법이다.
알다시피 RANDOM()은 1.0-0 범위의 값을 반환하고, 0.01보다 작은것만 필터링한다면 확률적으로 1%의 행만 필터링하는 셈이 된다.

실제로도 1%인 20만개 정도의 행만 집계가 된다.

이걸 응용하면 랜덤으로 일부 부분집합을 빠르게 빼내는 방법을 취할 수 있다. 인위적인 샘플링이다.

explain(analyze) select * from foo where random() < 0.01 limit 100;

이러면 앞부분에 있는 행만 나올 가능성이 크고, 뒤에있는건 거의 버려질 것이기 때문에 랜덤성은 낮은 편이다.
하지만 매우 빠르다는게 장점이다.

TABLESAMPLE

TABLESAMPLE은 테이블에서 일부 데이터를 빠르게 가져오기 위한 용도로 제공되는 기능이다.
나름 SQL 표준안에 정의된 기능이고, 딱 이런 사용사례를 위해 제공된다고 볼 수 있다.

예를 들어, 다음 쿼리는 테이블의 1%를 샘플링해서 가져온 다음에 거기서 100개만 가져온다.

explain(analyze) SELECT * FROM foo TABLESAMPLE SYSTEM(1) LIMIT 100;

랜덤 선택 자체를 데이터베이스에서 제공해주는 것이라서, 불필요한 오버헤드 없이 매우 빠르다는게 장점이다.

그리고 샘플링 방식도 선택할 수 있다. 여기서는 SYSTEM 방식을 썼지만, 이외에도 BERNOULLI, REPEATABLE라는 옵션이 존재한다.

TABLESAMPLE - System

System은 가장 기본적인 형태의 샘플링 알고리즘이다.

System은 저 비율값을 기반으로 "페이지"를 무작위로 선택해서 스캔한다.
페이지에 데이터가 몇개 들어있을지는 확실히 알 수 없기 때문에, 동일한 비율로 실행하더라도 실제 행 개수는 그때그때 다를 수 있다는게 단점이다.
그리고 페이지 단위로 읽어오는 거라서 페이지 단위로 값이 모여있을 수 있다. 그러니까 랜덤 분포 수준이 그리 높지 않다.

성능 자체는 가장 빠른 축에 속한다.

TABLESAMPLE - BERNOULLI

BERNOULLI는 조금 더 진짜 랜덤 선택에 가까운 방식이라고 할 수 있다.
이건 페이지 단위로 읽지 않고, 진짜 행 단위로 선택을 한다.

이것도 행 개수가 일정하지 않다는 것은 마찬가지고

SYSTEM SAMPLE에 비해서 성능은 매우 느린 편이다.
대신 랜덤 분포도가 더 좋다는게 장점이다.

그리고 REPEATABLE 절을 사용하면 랜덤 샘플링에 대해서, 시드값을 지정할 수 있다.
같은 시드값이 지정되면 같은 행을 반환하게 된다.

이걸 쓰면 분포를 통제할 수 있다.

TABLESAMPLE의 단점

이렇게만 보면 좋아보이지만, 이것도 단점은 있다.

유의할 점 중 하나로는, WHERE 필터와 섞어쓰기에 어려운 부분이 많다는 것이다.
TABLESAMPLE 테이블 스캔 거의 바로 직후에 실행된다. 그래서 샘플링한 이후에 WHERE 필터가 실행되는데, 원본 테이블에 그 필터 조건의 값이 있더라도 샘플링된 이후에 없으면 도루묵인 셈이다.

그리고 당연히 인덱스 스캔의 효과를 볼 수도 없다.

참조
https://stackoverflow.com/questions/8674718/best-way-to-select-random-rows-postgresql
https://medium.com/@seungwooyu2000kr/postgresql-tablesample-bernoulli%EB%8A%94-order-by-random-%EC%9D%98-%EB%8C%80%EC%B2%B4%EC%A0%9C%EA%B0%80-%EC%95%84%EB%8B%88%EB%8B%A4-5f50f3ea96a3
https://wiki.postgresql.org/wiki/TABLESAMPLE_Implementation
https://www.depesz.com/2007/09/16/my-thoughts-on-getting-random-row/