张晨煜, 刘文洁, 庞天泽, 岳艳涛

(1.西北工业大学 计算机学院, 陕西 西安 710129; 2.交通银行, 上海 200120)

随着互联网的发展和数据量的不断激增，分布式数据库已经逐渐取代单机数据库，成为金融、互联网等行业应用的主流存储系统。

在当前的数据库使用中，读操作占了数据库操作的大多数，反映到SQL语句中即查询语句被经常使用。将一个由SELECT-FROM-WHERE组成的结构称为查询块，对于一个查询块作为另一个查询块的查询条件嵌套在其中的语句，称为子查询[1]。目前对于子查询的执行，如果是不依赖于父查询的非相关子查询，实现比较简单，只需先对子查询进行处理，将结果与父查询绑定后执行父查询，由内向外每个查询只需要执行一次。但对于依赖于父查询的相关子查询，需要先对父查询计算，对于父查询结果中的每一个元组，都需要将其重写到子查询中进行一次子查询的计算。这种执行策略使得相关子查询的执行会随着父查询元组数的增多而增长，对于嵌套层次更多的复杂相关子查询，时间开销将会是指数级增加。同时，在分布式数据库环境中，这种执行策略还会增加数据通信的时间开销。

子查询为SQL查询提供了更为丰富的表达能力，在数据库使用当中，大多数查询语句都含有子查询，比如在TPC-H基准测试中就含有近乎一半的子查询语句。因此，对于相关子查询进行性能优化，对于分布式数据库的高效执行有着重要的作用。

现有的查询优化主要是基于2个方面进行，即基于规则的查询优化和基于代价的查询优化。……