查询优化 ■查询优化:从所有等价的执行计划中选择代价最小的一个 ●代价是利用数据库目录( catalog)中的统计信息估算 而得的 自如:每个关系中的元组数,每个元组的长度,等等 关键问题 ●如何度量查询代价 执行关系代数运算的算法 如何进行单元运算的组合,以实现整个表达式计算 ●如何优化查询,即如何找到代价最小的查询执行计划
查询优化 查询优化：从所有等价的执行计划中选择代价最小的一个 代价是利用数据库目录（catalog）中的统计信息估算 而得的 如：每个关系中的元组数，每个元组的长度，等等 关键问题 如何度量查询代价 执行关系代数运算的算法 如何进行单元运算的组合，以实现整个表达式计算 如何优化查询，即如何找到代价最小的查询执行计划
查询处理与查询优化概况 SQL query parse arse tree convert answer logical query plan execute apply laws statistics Pi “ improved"lq1p pick best estimate result sizes 1. q p. +sizes (P1,c1)P2,C2).y↑ consider physical plans estimate costs {P1,P2…}
parse convert apply laws estimate result sizes consider physical plans estimate costs pick best execute {P1,P2,…..} {(P1,C1),(P2,C2)...} Pi answer SQL query parse tree logical query plan “improved” l.q.p l.q.p. +sizes statistics 查询处理与查询优化概况
例1:SQL查询 SELECT title FROM StarsIn WHERE starName IN SELECT name FROM MoViestar WheRe birthdate LIKE%1960 (Find the movies with stars born in 1960)
例1: SQL查询 SELECT title FROM StarsIn WHERE starName IN ( SELECT name FROM MovieStar WHERE birthdate LIKE ‘%1960’ ); (Find the movies with stars born in 1960)
构造语法树 SELECT <SelList> FRom Fromuist> WHERE <Condition <Attribute> <RelName> <Tuple> IN <Query> title StarsIn <Attribute >(<Query> starName <SFW> SELECT <SelList> FRoM FromList> WHERE <Condition> <Attribute <RelName> <Attribute> LIKE <Pattern> name Movie star birthDate 961960
构造语法树
生成关系代数表达式 O StarsIn <condition> <tuple> IN name <attribute> o birthdate LIKE%1960' starName Movies
生成关系代数表达式 Πtitle σ StarsIn <condition> <tuple> IN Πname <attribute> σbirthdate LIKE ‘%1960’ starName MovieStar