查询优化方法及查询编译器

技术领域

本发明涉及一种查询优化方法及查询编译器，具体地，涉及数据库管理 系统的查询编译器，尤其涉及一种实现查询的优化的查询编译器及其方法。

本发明是从作为韩国知识经济部的产业融合源泉技术开发事业的一环 而执行的研究中得出的（10040824，实时处理大容量传感器流数据的开放式 传感器DBMS开发）。

背景技术

一般，数据库中存储着互相关联的数据，而且存储于数据库中的数据需 要以最新的数据进行更新、插入、删除。为此，数据库由软件系统DBMS（Data  Base Management System：数据库管理系统）所管理。DBMS是一种检索或 变更应用程序所需的数据从而能够始终向应用程序提供具有一致性的结果 的综合型数据管理系统。

要取得存储于数据库中的数据需要使用结构化查询语言（SQL:Structrer  Query Language）这种查询语言来生成查询。在数据库中，将SQL查询转换 成可在数据库执行的查询执行计划（query execution plan）的作业是在查询 编译器中执行的。查询执行计划由以查询执行中所必须的多个执行单位 （operation）为节点的树构成。

实际上，在查询编译器中将SQL查询转换成查询执行计划的作业以下述 方式执行。

首先，分析查询而生成分析树的结构。然后，在重写查询的过程中分析 树被变形为含义相同但更普通的形态。之后，利用统计信息以费用最少的执 行计划来执行变形的树。

一般，分析用户输入的查询后直接执行也会得到正确的结果。通过查询 的重写将分析树转换成更普通的形态是为了制作更多的执行计划，由此能够 提高得到优化的执行计划的可能性。

另外，查询的重写还用于除去虽包含于查询但不必进行运算的部分来对 查询进行优化，从而提高查询编译器的性能。

因此，优选对查询进行优化从而能够在查询编译器建立优化的执行计 划。

发明内容

因此，本发明的目的在于，提供一种对查询进行优化的查询编译器及其 方法。

为达到上述目的，根据本发明的实施例，提供一种查询优化的方法以及 用于实现所述方法的查询编译器。

根据本发明实施例的实现查询优化的方法包括如下步骤：检索SQL查询 内的子查询；从检索到的所述子查询中识别标量子查询；分析所识别的所述 标量子查询来识别关联标量子查询；根据所识别的所述关联标量子查询的结 果形式，将具有所识别的所述关联标量子查询的查询反嵌套为准连接 （quasi-join）。

在上述实施例中，从检索到的所述子查询中识别标量子查询的步骤包括 如下步骤：在检索到的所述子查询中，将包含于where语句且与比较运算符 一起生成的子查询识别为所述标量子查询。

在上述实施例中，从检索到的所述子查询中识别标量子查询的步骤包括 如下步骤：在检索到的所述子查询中，将包含于select语句中的子查询识别 为所述关联标量子查询。

在上述实施例中，分析所识别的所述标量子查询来识别关联标量子查询 的步骤包括如下步骤：在所述标量子查询中，将使用包含于所述查询的表的 列的标量子查询识别为所述关联标量子查询。

在上述实施例中，所述准连接包括aggregation inner/outer join和max1row  inner/outer join；就所述aggregation inner/outer join而言，对与所述查询的行 连接的所述关联标量子查询的多个行进行聚合，并返回所述查询的行和聚合 值来作为结果，就所述max1row inner/outer join而言，当与所述查询的行连 接的子查询的行为两个以上时，产生出错信息，并返回与所述查询的行连接 的子查询的行来作为结果。

在上述实施例中，将具有所识别的所述关联标量子查询的查询反嵌套为 准连接的步骤包括如下步骤：在所识别的所述关联标量子查询为返回聚合结 果的形态时，将具有所识别的所述关联标量子查询的查询反嵌套为 aggregation inner/outer join。

在上述实施例中，将具有所识别的所述关联标量子查询的查询反嵌套为 准连接的步骤包括如下步骤：在所识别的所述关联标量子查询为返回一个列 的形态时，将具有所识别的所述关联标量子查询的查询反嵌套为max1row  inner/outer join。

在上述实施例中，所述准连接对与left row连接的多个row条件性地以 event形式进行处理。

在上述实施例中，所述aggregation join和max1row join以hash、merge、 nested loop形式的连接方法体现。

另外，本发明的查询编译器，其包括：分析器，其对提供于所述查询编 译器的查询进行分析来形成分析树的结构；查询重写器，其分析具有所述分 析树的结构的所述查询来检索子查询，并从检索到的所述子查询中识别标量 子查询，分析所识别的所述标量子查询来识别关联标量子查询，并根据所识 别的所述关联标量子查询的结果形式，将具有所识别的所述关联标量子查询 的查询进行变换，以使其反嵌套为准连接；查询优化器，其利用统计信息根 据具有已变换的所述分析树的所述查询生成多个实行计划，从中选择费用最 少且路径最佳的实行计划，并生成能够以最佳效率执行的查询执行计划。

在上述实施例中，所述查询重写器从检索到的所述子查询中将包含于 where语句且与比较运算符一起使用的子查询识别为所述标量子查询。

在上述实施例中，所述查询重写器从检索到的所述子查询中将包含于 select语句中的子查询识别为所述关联标量子查询。

在上述实施例中，所述查询重写器在所述标量子查询中将使用包含于所 述查询的表的列的标量子查询识别为所述关联标量子查询。

在上述实施例中，所述准连接包括aggregation inner/outer join和max1row  inner/outer join；就所述aggregation inner/outer join而言，对与所述查询的行 连接的所述关联标量子查询的多个行进行聚合，并返回所述查询的行和聚合 值来作为结果，就所述max1row inner/outer join而言，当与所述查询的行连 接的子查询的行为两个以上时，产生出错信息，并返回与所述查询的行连接 的子查询的行来作为结果。

在上述实施例中，在所识别的所述关联标量子查询为返回聚合结果的形 态时，所述查询重写器将具有所识别的所述关联标量子查询的查询反嵌套为 aggregation inner/outer join。

在上述实施例中，在所识别的所述关联标量子查询为返回一个列的形态 时，所述查询重写器将具有所识别的所述关联标量子查询的查询反嵌套为 max1row inner/outer join。

在上述实施例中，所述准连接对与left row连接的多个row条件性地以 event形式进行处理。

在上述实施例中，所述aggregation join和max1row join以hash、merge、 nested loop形式的连接方法体现。

另外，在上述实施例中，查询优化方法，其包括如下步骤：分析SQL 查询来识别inline view；在所识别的所述inline view中，group by的结果与 不同的表以N:1（table:group by with aggregation）或1:1连接时，将所述查询 反嵌套为aggregation inner/outer join；就所述aggregation inner/outer join而言， 对与所述查询的行连接的所述关联标量子查询的多个行进行聚合，并返回所 述查询的行和聚合值来作为结果。

另外，在上述实施例中，查询优化方法，其分析SQL查询来在Group by  with aggregation的下面存在join且一侧的关键词用作group by key而作为另 一侧列仅使用aggregation时，将具有所述group by with aggregation的查询反 嵌套为aggregation inner/outer join；就所述aggregation inner/outer join而言， 对与所述查询的行连接的所述关联标量子查询的多个行进行聚合，并返回所 述查询的行和聚合值来作为结果。

如上所述，通过将包含于查询的关联标量子查询变换为join（连接）方 式，与现有技术相比增加生成更多查询执行计划的可能性，从而能够改善查 询编译器中查询的执行速度。

附图说明

图1是在本发明所适用的数据库管理系统中使用的查询编译器的方框 图。

图2是说明本发明实施例的实现查询优化的方法的流程图。

图3A和图3B示出根据本发明实施例分别将具有关联标量子查询的主查 询反嵌套为聚合内连接（aggregation inner join）和聚合外连接（aggregation  outer join）方式的步骤。

图4A和图4B示出根据本发明实施例分别将具有关联标量子查询的主查 询反嵌套为max1row内连接（max1row inner join）和max1row外连接 （max1row outer join）方式的步骤。

图5A和图5B示出根据本发明实施例将具有除了关联标量子查询之外的 子查询的查询反嵌套为聚合连接方式的步骤。

其中，附图标记的说明如下：

10：查询编译器 12：分析器

14：查询重写器 16：查询优化器

具体实施方式

下面，参照附图对本发明的实施例进行详细说明。

下面，参照图1，示出了在本发明适用的数据库管理系统中使用的查询 编译器10的方框图。查询编译器10包含分析器12、查询重写器14、查询 优化器16。

分析器12分析提供于查询编译器10的查询而形成为分析树的结构。在 由分析器12执行的分析过程中确认在查询中有无语法错误或者有无歧义， 并转移到查询重写（query rewrite）过程。查询重写器14将具有分析树结构 的查询制作成更普通的形态，从而使得能够在下一级的查询优化器16中生 成更多的执行计划。查询优化器16利用统计信息从具有变形的树结构的查 询生成多个实行计划，从中选择费用最少、路径最佳且具有最佳效率的实行 计划。根据由查询优化器16生成的最佳实行计划实行查询并返回其结果。

因此，查询重写器14优选以如下方式构成：将查询制作成更普通的形 态以在查询优化器16中能够生成更多的执行计划，并除去不必进行运算的 子查询。

查询重写作业有很多种，代表性的如下所示。

1.简化外连接（Outer join simplification）：

在该作业中，虽然在SQL查询内存在外连接，但根据方案（schema）信 息或写入where的条件确定不是外连接（outer join）而是内连接（inner join） 时，变更为内连接。

2.简单视图合并（Simple view merging）：

该作业在SQL查询中使用视图（view）时删除视图，将相应的查询合并 于上层查询块或主查询。

3.表达式重写（Expression rewriting）：

在该作业中，在包含于查询中的表达式（expression）是可以事先简单执 行的表达式或者虽然复杂且执行需要长时间、但可以用简单的表达式来表示 的表达式时，变更相应的查询。

4.子查询反嵌套（Subquery unnesting）：

在该作业中，对包含于查询中的子查询（subquery）进行反嵌套并将相 应的查询合并于上层查询块，从而使查询和子查询之间的层结构变为相同的 层。

在上述的查询重写作业中第四个子查询反嵌套（subquery unnesting）与 本发明实施例相关。

在上述子查询反嵌套中反嵌套的子查询可分为如下四种。

4-1.非关联标量子查询（uncorrelated scalar subquery）：

该子查询是指不接收上层查询块所供给的列（column）并只返回一个结 果的子查询。例如，可以列举出以如下方式生成的子查询。

select emp_no from emp

where salary=(select max(salary)from emp)

4-2.非关联非标量子查询（uncorrelated non-scalar subquery）：

该子查询是指不接收上层查询块所供给的列并以集（set）形式返回结果 的子查询。例如，可以列举出以如下方式生成的子查询。

select emp_no from emp

where dept_code in

      (select dept_code from dept where company='tibero'

4-3.关联标量子查询（correlated scalar subquery）：

该子查询是指接收主查询所供给的列并只返回一个结果的子查询。例 如，可以列举出以如下方式生成的子查询。

Select emp_no from emp m

Where salary=(select max(salary)from emp s

            where s.dept_code=m.dept_code)

4-4.关联非标量子查询（correlated non-scalar subquery）：

该子查询是指接受列的供给并以组（set）形式返回结果的子查询。例如， 可以列举出以如下方式生成的子查询。

Select emp_no from emp m

Where sold_item in(select sold_item fro item s

                where s.htd>m.speciality)

在上述子查询中，记载于4-1的子查询由于其结果值始终相同，所以不 需要进行反嵌套（unnest），但记载于4-2乃至4-4的子查询则需要进行反嵌 套。

4-2的子查询为非关联，所以貌似可以不进行反嵌套，但若存在于子查 询内部的表（table）的大小变大，则需要在存储器（memory）中存储子查询 结果并按照主查询的每一行与子查询的结果进行比较，因此可能进行反嵌套 比较好。

由于记载于4-3和4-4的子查询为关联子查询，所以需要按照主查询的 每一行执行子查询，因此始终进行反嵌套比较好。

例如，有如下所述的包含关联标量子查询的主查询时，在相关技术中可 以以如下所述的多种方式处理上述主查询。该查询是按部门筛选出年薪最多 的公司职员的查询。

select emp_name

from emp m

where salary=(select max(salary)

           from emp s

           where m.dept_code=s.dept_code)

（1）对主查询内标量子查询不进行反嵌套，对子查询以row by row（一 排排）的方式传递correlated value（关联值），来通过利用子查询结果值的 filter（过滤器）来进行处理。

（2）当主查询内标量子查询的结果为aggregation（聚合）时以如下方 式处理。

select emp_name

from emp m,

        (select dept_code,max(salary)maxsalary

        from emp group by dept_code)s

    where m.dept_code=s.dept_code and m.salary=s.maxsalary

即，以上述方式在inline view（内嵌视图）中进行group by（分组）和 aggregation（聚合）后，处理为对其的join（连接）。

（3）在第二个处理方式中，也可以追加rowid（行编号）来作为对主查 询的row（行）的关键词，从而可将group by放到join的上面。若用SQL查 询表示则如下所述。

select emp_name

from(select m.emp_name,m.salary,max(s.salary)maxsalary

from emp m,emp s

where m.dept_code=s.dept_code

group by m.rowid,m.emp_name,m.salary)

where salary=maxsalary

就上述（1）的处理方式而言，存在如下缺点，即，当correlated value （关联值）的distinct count（不同计数）小时，若使用标量子查询的cache （闪存器）则速度快，但在相反的情况下需要执行与dept_code（部门代码） 的distinct count相同次数的查询。

就上述（2）的处理方式而言，当correlated value（关联值）的distinct count （不同计数）大时，在进行一次group by（分组）后便进行join（连接）， 故比第一个方式要好，但当distinct count（不同计数）小时，若以nested loop （嵌套循环）方式处理，则与上述相同，但因没有cache（闪存器），因此 对相同的值也会再次进行计算，所以并不理想，但若以hash join（哈希连接） 方式处理则根据数据的不同无法断定好坏。而该方式需要追加进行group by （分组），因此存在对此的memory（存储器）和处理时间增加的问题。

就上述（3）的处理方式而言，在join（连接）中减少的量多时优于第二 个处理方式，否则，在join（连接）中作为结果输出的row（行）比group by （分组）在下面时要处理的row（行）量多很多，因而并不良好。另外，该 方式也需要追加进行group by（分组）。

在子查询结果为列时可以生成如下查询。

select emp_name,

(select dept_name from dept s

where m.dept_code=s.dept_code)

from emp m

在如上所述的SQL的情况下，主查询的每一row（行）应当只输出一个 子查询结果，但若按上述第2、3、4的处理方式将子查询进行反嵌套，则无 法对子查询结果为一个以上的情况进行错误（error）处理。因此对子查询不 进行反嵌套，所以可能会增加子查询的执行作业。

本案发明人通过执行很多查询以及反复操作得知如下信息：若将关联标 量子查询变换为新形态的join（连接）方式，则包括上述（1）、（2）的方 式来作为join method（NESTED LOOP,HASH,MERGE）（连接方法（嵌套 循环、哈希、合并）），并且在各节点处理的工作被带到join（连接）节点， 在内部使用cache（闪存器）和shortcut（快捷键）能够缩短执行时间。

根据本发明，查询编译器10从用户输入的SQL查询中检索子查询，从 并根据检索到的子查询识别在SQL规约中规定的标量子查询，分析以这种方 式识别的标量子查询来识别关联标量子查询，根据识别的关联标量子查询的 结果形态，将具有识别的关联标量子查询的查询进行转换，使得以新连接形 态动作。

在此，新join（连接）形态包含aggregation（inner/outer）join（聚合内 外连接）和max1row（inner/outer）join（max1row内外连接）。这种新连 接形态是无法用通常的SQL形式来表达的由本案发明人所提出的新的连接 方法，为方便表达，在本实施例中称为准连接（quasi-join）。

下面参照图2，对通过查询编译器10来执行的对查询进行优化的方法进 行说明。图2是根据本发明实施例说明对查询进行优化的方法的流程图。

首先，在步骤22中，查询编译器10的查询重写器14分析SQL查询文 本来检索主查询内是否存在子查询。

之后在步骤24中，查询编译器10的查询重写器14从检索到的多个子 查询中将包含于where语句并且并非与如in或exist等集合运算符一起使用 而是与比较运算符（=，>）一起使用的子查询、或者包含于select语句的子 查询识别为标量子查询。

之后在步骤26中，执行分析所识别的标量子查询来识别关联标量子查 询的步骤。该识别步骤将使用包含于主查询表的列的（多个）标量子查询识 别为关联标量子查询。

之后在步骤28中，根据关联标量子查询的结果形式，将具有识别的关 联标量子查询的查询变换为根据本发明实施例的新join（连接）形态。

在步骤28中识别的关联标量子查询返回聚合结果的形式时，查询编译 器10的查询重写器14将具有所识别的关联标量子查询的查询反嵌套为聚合 内外连接（aggregation inner/outer join）（步骤30）。aggregation inner/outer join （聚合内外连接）执行如下作业：对与主查询的row（行）join（连接）的关 联标量子查询的多个row（行）进行aggregation（聚合），并将主查询的row （行）和aggregation（聚合）值作为结果来返回。

图3A示出将具有例如在下面所述的关联标量子查询的主查询反嵌套为 aggregation inner join（聚合内连接）形态的步骤。下面的查询同样是输出在 各部门中年薪最多的公司职员的SQL。

select emp_name

from emp m

where salary=(select max(salary)

       from emp s

       where m.dept_c_code=s.dept_code)

图3B示意性地示出将具有例如在下面所述的关联标量子查询的主查询 反嵌套为aggregation outer join（聚合外连接）形态的步骤。下面的查询也是 按部门输出年薪总和的SQL。

select dept_name

(select sum(salary)

from emp s

where m.dept_code=s.dept_code)

    from dept m

但是，若在步骤28中判断识别的关联标量子查询为返回一个列的形态， 则查询编译器10的查询重写器14将具有识别的关联标量子查询的查询反嵌 套为max1row inner/outer join（max1row内外连接）形态（步骤32）。max1row  inner/outer join执行如下作业：在与主查询的row（行）join（连接）的子查 询的row（行）为两个以上时产生出错信息（error），并将与主查询的row （行）join（连接）的子查询的row（行）作为结果来返回。

图4A示出将具有例如在下面所述的关联标量子查询的主查询反嵌套为 max1row inner join形态的步骤。该查询是输出部长名字的SQL。

select emp_name

from emp m

where emp_no=

(select dept_boss_no

from dept s

where m.dept_code=s.dept_code)

图4B示出将具有例如在下面所述的关联标量子查询的主查询反嵌套为 max1row outer join形态的步骤。该查询是输出公司职员的名字和公司职员所 属的部门名字的查询。

select emp_name,

(select dept_name from depts.

Where e.dept_code=d.dept_code)

   from emp m

可由图3A、图3B及图4A、图4B得知，本实施例的新连接形态的 quais-join具有如下形态：对与left row（左侧行）join（连接）的多个row（行）， 条件性地以event（事件）形式处理。

由于本实施例的新join（连接）形态是由本案发明人新建成的，所以无 法用通常的SQL形态来表达。因此，实际在查询编译器10中执行时，删除 关联标量子查询，并对包含相应的子查询的主查询进行转换，使得以join（连 接）的方式动作，从而在查询优化器16中生成多个查询执行计划。

本实施例的新join（连接）形态的Aggregation join如现有的连接方式那 样支持包含hash join（哈希连接）、nested loop join（嵌套循环连接）、merge join（合并连接）的连接方法，并返回输出与left row（左侧行）join（连接） 的多个right row（右侧行）的aggregation（聚合）的结果。

反之，本实施例的新连接方式的Max1row连接如上述Aggregation join （聚合连接）那样支持hash join（哈希连接）、nested loop join（嵌套循环连 接）、merge join（合并连接）的连接方法，其不同点在于在与left row（左 侧行）join（连接）的right row（右侧行）为两个以上时产生出错信息。

上述实施例对将具有关联标量子查询的主查询转换为新连接方式的方 法进行了描述。

根据本发明，不仅是关联标量子查询，其他形式的子查询也可以变换为 本实施例的新join（连接）方式。例如，在上述现有技术的第二和第三处理 方式中举出的SQL查询是返回与具有关联标量子查询的SQL查询相同的结 果的SQL查询，因此能够适用本实施例的aggregation join（聚合连接）。

详细地说，在现有技术的第二处理方式中，在一般join（连接）中参与 join（连接）的表为group by with aggregation的inline view（内嵌视图）时，， 视图（view）与另一侧的表通过不包含aggregation（聚合）的多个join predicate （连接谓词）来以N:1或1:1连接时，也可以删除group by with aggregation 变换成本实施例的准连接的agregation join（聚合连接）。结果，意味着join （连接）和下面的group by with aggregation合并为aggregation join（聚合连 接）。View（视图）与另一侧表以N:1连接的含义如下：相对于表的row（行）， view（视图）的row（行）始终只有一个row（行）与其join（连接）。但是， 与其相反的关系是不能成立的。

图5A示出例如在下面所述的连接中删除具有group by with  aggregation的SQL查询并反嵌套为aggregation join（聚合连接）方式的步骤。 该查询是输出在各部门中年薪最多的公司职员的SQL。

select emp_name

from emp m,

        (select dept_code,max(salary)maxsalary

        from emp group by dept_code)s

    where m.dept_code=s.dept_code and m.salary=s.maxsalary

另一方面，在现有技术的第三处理方式中，在join（连接）的上面存在 group by with aggregation时，包括一侧表的多个关键词列（在表中的row（行） 没有重复值的唯一（unique）的列组合）来作为group by的关键词列，而另 一侧表中只有aggregation结果。查询的形式是如下情况。该查询也是输出在 各部门中年薪最多的公司职员的SQL。

select emp_name 

from(select m.emp_name,m.salary,max(s.salary)maxsalary 

from emp m,emp s 

where m.dept_code=s.dept_code group by m.rowid,m.emp_name,m.salary)

where salary=maxsalary

如在查询中所示，对m、s进行join（连接）后，对m的rowid、emp_name、 dept_code、salary进行了组合，但rowid在emp中是唯一值，而对于s，仅 在max(s.salary）中使用，因此会建立aggregation join（聚合连接）。

图5B示出将上述SQL查询反嵌套为aggregation join（聚合连接）方式 的步骤。

因此，如上所述，能够将包含于查询的关联标量子查询变换为连接方式， 从而能够提高查询编译中的查询的执行速度。