Snowflake中TABLESAMPLE采样查询工作原理及时间复杂度问题

1. 采样运行逻辑 #

你所用的select * from tablename sample ROW(20000 rows);采样语句，在PostgreSQL、Hive、Spark SQL等主流支持该语法的数据库中，执行逻辑都是无固定间隔的随机选行，不存在固定的行跳过规则：

• 执行时会为遍历到的每一行生成一个独立的0~1区间的随机数
• 数据库会先根据你指定的20000行采样量和表的预估总行数，计算出选中概率阈值 p = 20000 / 表预估总行数
• 每一行只要生成的随机数小于p就会被选中，直到累计选中行数达到20000行就终止查询
• 由于每一行的随机数生成完全独立，因此选中行的分布没有规律，可能出现连续多行被选中、也可能连续跳过大量行的情况。

2. 时间复杂度 #

默认实现下时间复杂度为 O(n)（n为表的总行数），仅特殊优化场景下可接近O(20000)：

• 常规实现中，数据库需要逐行扫描全表为每一行生成随机数并判断是否命中，哪怕最终只返回2万条数据，也需要完成全表遍历，因此复杂度和表总行数正相关
• 仅当数据库做了针对性优化（比如提前预存每行的随机标签并建索引、或者支持块级采样跳过几乎不可能命中的存储块）时，才可以避免全表扫描，复杂度接近采样行数的量级。

内容的提问来源于stack exchange，提问作者abhishek maurya