Joins- Histograms Prices Inventory HP 999 HP IBM 2100 Asus 20 Asus 1500 丨BM 60 Dell 1300 Dell 30 Pr[ iny. count≥30]= 4 Selectivity 326 Prlprices. price 1400] 4416
Joins - Histograms Inventory HP 40 Asus 20 IBM 60 Dell 30 Prices HP 999 IBM 2100 Asus 1500 Dell 1300 4 2 Pr[ . 1400] 4 3 Pr[ . 30] = = prices price inv count 16 6 4 2 4 3 Selectivity = =
Joins- Synopsis Inventory Prices HP 40 HP 999 Asus 20 IBM 2100 IBM 60 Asus 1500 Dell 30 Dell 1300 Select a sample from INVENTORY:(hp, 40),(asus, 20) Join sample with PRICES. We get results(HP, 40, 99) (ASUS, 20, 1500). This new sample captures the foreign key relationship between the two tables. We run out join on this sample
Joins - Synopsis Inventory HP 40 Asus 20 IBM 60 Dell 30 Prices HP 999 IBM 2100 Asus 1500 Dell 1300 ◼ Select a sample from INVENTORY: (hp,40), (asus,20). ◼ Join sample with PRICES. We get results (HP,40,99), (ASUS, 20, 1500). This new sample captures the foreign key relationship between the two tables. We run out join on this sample
代价评估阶段 通过对采样的结果进行直接计算获得 Selectivity的结果 口对 A and b and c需要生成各种组合的 Selectivity 优点 a避免了AV假设 a不存在高维的问题 a对各种查询均有效 口操作简单
代价评估阶段 ◼ 通过对采样的结果进行直接计算获得 Selectivity的结果 ❑ 对A and B and C需要生成各种组合的Selectivity ◼ 优点 ❑ 避免了AVI假设 ❑ 不存在高维的问题 ❑ 对各种查询均有效 ❑ 操作简单
生成概率分布函数 对N条元组的表T,取其一个采样S=s1,s2,,.sn (采用随机采样的方法)。对谓词P,X=(1 x2,,xn)是一个向量,x代表sl是否满足谓词P 求满足T中满足P的比例p。需要计算p的概率分布。 等价于求条件密度函数f(zX)。 f(Z X) P[Ⅹ|p=z]f(z) Pr[ⅹ|p=y]f(y)dy
生成概率分布函数 ◼ 对N条元组的表T，取其一个采样S=s1,s2,…, sn (采用随机采样的方法)。对谓词P，X=（x1, x2,…,xn）是一个向量，xi代表si是否满足谓词P。 求满足T中满足P的比例p。需要计算p的概率分布。 等价于求条件密度函数f(z|X)。 = = = 1 0 Pr[X || p y]f(y)dy Pr[X | p z]f(z) f(Z| X)
生成概率分布函数 f(z)的两种处理方法 口通过背景知识( selecity在实际运行中的分布)进行推算 口基于采样的结果进行推测, selectivity的分布符合beta分 布参数是(1/2,1/2) 公式其他的部分 口PⅨX|p=]=Cnz(1-z)nk
生成概率分布函数 ◼ f(z)的两种处理方法 ❑ 通过背景知识(selecity在实际运行中的分布)进行推算 ❑ 基于采样的结果进行推测，selectivity的分布符合beta分 布参数是（1/2，1/2） ◼ 公式其他的部分 ❑ Pr[X|p=z]= zk (1-z)n-k k Cn