如何在DuckDB中高效实现笛卡尔积的无偏随机采样？

针对t1（100行）、t2（200行）抽取300组无偏差随机配对样本的需求，以下是几个可行的高效方案，避免全笛卡尔积计算：

方案1：使用RESERVOIR采样（推荐） #

DuckDB的RESERVOIR采样算法支持流式处理固定大小的样本，无需预计算完整笛卡尔积。它会在生成配对的过程中动态维护样本池，只保留需要的300个样本，内存和计算效率远高于全笛卡尔积后采样。

SELECT * FROM t1, t2 USING SAMPLE 300 RESERVOIR;

该方案保证每个可能的配对被选中的概率均等，且实现最简单，适合大表场景。

方案2：随机索引配对法（无放回采样） #

如果需要严格无放回采样（避免重复配对），可以通过给两表分配随机行号，生成随机索引对后连接，全程无需计算笛卡尔积：

WITH 
t1_randomized AS (
    -- 给t1每行分配随机排序后的行号
    SELECT *, ROW_NUMBER() OVER (ORDER BY RANDOM()) AS t1_row_id
    FROM t1
),
t2_randomized AS (
    -- 给t2每行分配随机排序后的行号
    SELECT *, ROW_NUMBER() OVER (ORDER BY RANDOM()) AS t2_row_id
    FROM t2
),
sample_pairs AS (
    -- 生成300个不重复的随机索引对，多生成50个确保去重后足够数量
    SELECT DISTINCT
        FLOOR(RANDOM() * (SELECT COUNT(*) FROM t1)) + 1 AS target_t1_id,
        FLOOR(RANDOM() * (SELECT COUNT(*) FROM t2)) + 1 AS target_t2_id
    FROM generate_series(1, 350)
    LIMIT 300
)
-- 通过索引对连接两表获取样本
SELECT t1r.*, t2r.*
FROM sample_pairs
JOIN t1_randomized t1r ON sample_pairs.target_t1_id = t1r.t1_row_id
JOIN t2_randomized t2r ON sample_pairs.target_t2_id = t2r.t2_row_id;

优势： #

• 严格无放回，每个配对仅可能被选中一次
• 仅需对两表分别做随机排序（DuckDB对该操作优化良好），无需处理笛卡尔积

方案3：LATERAL JOIN分层采样 #

通过LATERAL JOIN对每个t1行随机采样t2行，控制总样本数接近300后取前300，适合需要细粒度控制采样分布的场景：

SELECT t1.*, t2.*
FROM t1
LATERAL (
    -- 每个t1行随机采样3个t2行（300/100=3），用BERNOULLI保证均匀性
    SELECT * FROM t2 USING SAMPLE 3 BERNOULLI
) t2
-- 若总样本不足300，补充少量采样
UNION ALL
SELECT t1.*, t2.*
FROM t1
LATERAL (
    SELECT * FROM t2 USING SAMPLE 1 BERNOULLI
) t2
LIMIT 300;

注意： #

• 该方案可能出现少量重复配对，若需无放回需额外加DISTINCT
• 采样数量可根据两表行数动态调整，比如用(300.0 / (SELECT COUNT(*) FROM t1))替代硬编码的3

内容的提问来源于stack exchange，提问作者Nick Crews