Presto实战

50

｜

第

4

章

现在我们来考虑下这个查询计划的计算复杂度。在知道实际实现细节之前，我们无法准确

地推测一个查询计划的复杂度，但可以假设一个查询计划节点的计算复杂度不会低于其产

生数据集的行数。因此，我们可以用描述渐近复杂度下界的大

Omega

表示法来估算复杂

度。如果

N

、

O

、

C

和

R

分别表示表

nation

、

orders

、

customer

和

region

表的行数，则有

以下内容。

•

TableScan[orders]

算子读取

orders

表并返回

O

行数据，则其复杂度是

Ω

(

O

)

。类似地，

对

nation

和

customer

表的

TableScan

分别返回

N

和

C

行，因此其复杂度分别为

Ω

(

N

)

和

Ω

(

C

)

。

•

TableScan[nation]

和

TableScan[orders]

之上的

CrossJoin

节点返回

nation

和

orders

表中行的组合（正交积），因此其复杂度是

Ω

(

N

×

O

)

。

•

再之上的

CrossJoin

节点将之前返回

N

×

O

行的

CrossJoin

节点的输出，与

TableScan[customer]

的输出相结合，

customer

表输出的行数是

C

，因此总的复杂度是

Ω

(

N

×

O

×

C

)

。

•

底层的

TableScan[region]

复杂度为

Ω

(

R

)

，但其上的

LateralJoin

会调用它

N

次，聚合

之后一共有

N

行被返回，因此总的计算复杂度是

Ω

(

R

×

N

)

。

•

Sort

操作需要排序

N

行，它的计算复杂度不小于

N

×

log(

N

)

。

我们先暂时忽略其他操作的代价，因为它们与分析过的复杂度相比可忽略不计。之前查询 ...