人类社会产生的数据量正呈爆炸式增长,大数据的应用无处不在,查询的响应速度直接影响大数据从业者的工作效率,进而可以影响到社会发展。因此,对查询进行优化,缩短查询的执行时间是十分重要的。查询优化中涉及连接顺序,连接站点,和连接方法等因素且各因素互相影响。所以,建立清晰的模型来描述和评价查询执行过程,设计出适用于当前最新的跨数据源跨数据中心的分布式数据库系统的有效查询优化算法具有重要的理论和现实意义。本文研究了跨数据源跨数据中心的分布式数据库系统中查询的优化问题,建立了一种以二叉树为载体的查询执行计划描述模型,该模型可以描述查询执行的具体过程。另外,本文还设计了一套查询执行成本计算公式框架,通过该框架,辅以合适的评价公式,就可以对查询执行计划进行准确的评价。算法方面,本文设计了分级动态规划增补集算法、受限分级动态规划增补集算法和改进的基于连接图的贪婪算法三种算法,为看对比算法效果,还给出了一种近乎完全随机的随机左深子树算法和传统的基于连接图的贪婪算法。分级动态规划增补集算法将查询对应的连接图分为多个连通子图,对每个子图应用动态规划,在应用过程中,通过枚举增补实现树对来避免不必要的中间结果。在绝大多数情况下,该算法可以得到全搜索空间中的最优解。受限分级动态规划增补集算法是在分级动态规划增补集算法基础上衍生出来的,该算法通过限制搜索空间的方式仅寻找左深子树结构的查询执行计划中的最优解,降低了算法复杂度。根据经验绝大多数情况下该最优解不会与全搜索空间中的最优解有数量级的差别。针对超大规模的查询,本文在传统基于查询图的贪婪算法基础上进行改进,设计了改进的基于连接图的贪婪算法,将选择因子和传输速度综合考虑,更适合当前跨数据中心的数据库系统。最后,本文进行了大量数值实验,实验结果证明,所提的三种算法的结果比随机左深子树算法优两到三个数量级,其中分级动态规划增补集算法和受限分级动态规划增补集算法的结果又比改进的基于连接图的贪婪算法优一个数量级。但前两者的执行时间随查询涉及的数据表数量呈指数增长,而后者是线性增长。受限分级动态规划增补集算法的结果比分级动态规划增补集算法的结果差约20%,但是求解规模扩大了约30%。