数据库查询优化算法浅析

【摘 要】数据库系统在实际工作中应用非常广泛，对数据库进行查询优化对推动计算机技术的发展具有十分重要的意义。并行数据库查询优化的研究主要围绕具有多个JOIN操作的复杂关系数据库查询的优化问题进行，本文主要对并行数据库查询优化技术进行探索。

【關键词】查询优化；并行数据库；语义查询；机群

1 引言

并行数据库查询优化主要围绕具有多个JOIN 操作的复杂关系数据库查询（简称MJ查询）的优化问题进行研究。1990年，Schneider等研究了查询树模型，提出了左线性树（Left-Deep Trees）、右线性树（RIGHT-Deep Trees）和浓密树（Bushy Trees）的概念。一个MJ查询可以表示为一个查询树T=（V，E），其中V是结点集合，E是边集合。每个叶子结点表示一个关系，每个内结点表示一个JOIN操作，同时表示这个JOIN操作的结果关系，每条边表示一个JOIN操作，JOIN谓词也可以由边来表示，即MJ查询的查询树是一个二叉树。查询树分为三类左线性树、右线性树和浓密树。

语义查询优化技术，将一个查询变换成一个或数个语义等价的查询，进而寻找并执行这些等价查询中具有较好实现策略的一个；基于遗传算法的并行优化算法主要是基于机群并行数据库中关系存储的选择、多连接查询优化和查询处理等关键技术。

2 左线性树查询优化算法（简称LDT算法）

LDT方法把两个JOIN关系分为内关系和外关系，把HASH-JOIN分为BUILD和PROBE两个基本操作，BUILD操作扫描内关系，建立HASH表；PROBE操作扫描外关系，搜索匹配HASH表，完成JOIN操作。具体算法如下：

（1）搜索给定MJ查询的左线性树空间，选择具有最小响应时间的优化左线性树T；……