PrestoSQL中UNNEST查询的时间复杂度差异及计算方式咨询

先明确场景前提：表共N行，col1、col2、col3为数组类型列，且每个列的数组平均元素个数（基数）相同，记为K。三个查询如下：

SELECT c1 from Table, UNNEST(col1) AS t(c1)

SELECT c1, c2 from Table, UNNEST(col1, col2) AS t(c1, c2)

SELECT c1, c2, c3 from Table, UNNEST(col1, col2, col3) AS t(c1, c2, c3)

三个查询的时间复杂度差异 #

三个查询的时间复杂度并非指数级差异，核心原因是Presto中多列UNNEST是按位置配对展开，而非笛卡尔积：

• 第一个查询：遍历N行，每行展开col1的K个元素，最终结果行数为N*K，时间复杂度为O(N*K)。
• 第二个查询：对每行的col1和col2按位置一一配对展开（要求两数组长度一致，否则用NULL补全），最终结果行数仍为N*K，时间复杂度为O(N*K)——仅需在展开时同时读取两列的对应元素，额外开销为常数级，不会随列数增长而翻倍。
• 第三个查询：原理与第二个一致，同时展开三列的对应位置元素，结果行数还是N*K，时间复杂度仍为O(N*K)。

关于“N²/N³倍”的误解 #

你的猜想不成立，因为这种写法的UNNEST不是多列笛卡尔积展开。只有当你显式用CROSS JOIN多次UNNEST时（比如先UNNEST col1，再CROSS JOIN UNNEST col2），才会产生N*K*K的结果行数，时间复杂度达到O(N*K²)；但当前写法是Presto原生的多列并行UNNEST，不存在笛卡尔积逻辑。

结合列基数与表规模的时间复杂度衡量方式 #

1. 核心参数定义：
   • 表规模：总行数N
   • 列基数：数组类型列的平均元素个数K（这里的“基数”需明确是数组元素数量，而非列的distinct值数量）
2. 复杂度计算逻辑：
   • 单/多列等长数组的UNNEST：时间复杂度均为O(N*K)，因为不管展开几列，都是对每行的K组元素进行处理，额外列的读取和输出是常数级开销。
   • 若数组长度不一致：Presto会将所有数组补全到最长数组的长度K_max，此时复杂度为O(N*K_max)。
   • 若需笛卡尔积式展开：显式使用CROSS JOIN UNNEST，每多一层UNNEST，复杂度会乘以对应列的平均元素数，比如两次笛卡尔积UNNEST的复杂度为O(N*K1*K2)。

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