Page 207 - 《软件学报》2021年第10期

危剑豪 等:多查询共享技术研究综述 3179

接下来描述一个多查询共享实例,3 个常见关系分别是用户(user)、订单(order)、产品(item)表示,见表 1.查
询 Q1、Q2、Q3 见表 2.这 3 个查询语句均是访问 USERS 表,因此存在共享机会.首先在查询编译期间合并三者
的公共子表达式,生成一棵多查询树,该查询树将 3 个 SQL 语句的选择谓词合并到同一个算子中,如图 2 所示.
之后,查询引擎会通过该多查询计划树中的运算符选择合适的多查询算法,从而生成物理查询计划.最后,查询
引擎执行该查询计划,并将各自的结果返回给客户端.多查询共享的策略有很多,且贯穿于查询执行的各个阶
段,本例描述的策略只是其中一种.
Table 1 Relation of user, order and product
表 1 常见的用户-订单-产品的关系
关系 属性
用户(user) 用户编号(user_id),名字(username),年龄(age),国籍(country)
订单(order) 订单编号(order_id),产品编号(item_id),用户编号(user_id),状态(status),交易日期(date)
产品(item) 产品编号(item_id),库存(available),价格(price),类别(category)

Table 2 Seven ordinary queries
表 2 常见的 7 个查询
查询 语句
SELECT COUNTRY, COUNT(*) FROM
Q1
USERS GROUP BY COUNTRY WHERE AGE>?;
SELECT USERNAME, COUNTRY FROM USERS
Q2
WHERE COUNTRY=‘CHINA’ OR COUNTRY=‘USA’;
SELECT USERNAME FROM USERS WHERE
Q3
COUNTRY=‘CHINA’ AND AGE>? AND AGE<?;
SELECT * FROM USERS U, ORDERS O WHERE
Q4
U.USER_ID=O.USER_ID AND U.USERNAME=? AND O.STATUS=‘OK’;
SELECT * FROM USERS U, ORDERS O, ITEMS I WHERE
Q5
U.USER_ID=O.USER_ID AND O.ITEM_ID=I.ITEM_ID AND I.AVAILABLE<?;
SELECT * FROM ORDERS O, ITEMS I WHERE
Q6
O.ITEM_ID=I.ITEM_ID AND O.DATE>? ORDER BY I.PRICE;
Q7 SELECT * FROM ITEMS I WHERE I.CATEGORY=? ORDER BY I.PRICE;

Fig.2 A multiple query plan tree for Q1, Q2, Q3
图 2 Q1、Q2、Q3 的多查询计划树

1.2 多查询共享研究问题分类
目前,所有关于多查询共享的研究都围绕着两种原型系统展开,即基于全局查询计划的多查询原型系统
(multi-query prototype system based on global query plan,简称 GQP 系统)和以运算符为中心的多查询原型系统
(operator-centric multi-query prototype system,简称 OMP 系统),我们将在下一节对它们进行详细的描述.基于这
两种多查询系统架构,研究内容主要可以分为:(1) 查询编译阶段的多查询共享技术,包括多查询计划的表示方
法、合并规则、路径搜索以及运算符的共享算法等研究内容;(2) 查询执行阶段中的共享查询技术,包括缓存管