SmartESQL优化器

SmartESQL 使用基于规则的查询优化器，旨在实现以下目标：

可预测且快速的查询执行；
为开发人员提供最大灵活性，以便通过简单规则调整查询并指定最佳执行计划。

查询优化主要依赖索引，并尽量避免顺序扫描。优化器可以下推谓词，并处理升序或降序索引、排序子句和比较运算符（如 <=, > 等）的任意组合。

某些操作不使用索引，例如 BETWEEN 表达式。对于 BETWEEN，引擎会根据范围的一个边界进行查找，然后验证另一个边界的有效性。

优化器采用智能算法选择合适的索引，而不是基于成本。它会选择支持所需排序且能替换最多谓词的最短索引。例如，对于查询条件 "x=1 AND y=2 AND z=3"，如果有索引 tree<x>、tree<y> 和 tree<z,x>，则会选择 tree<z,x>。即使有更长的索引 tree<x,y,a,b,c>，也不会选择它，因为它虽然覆盖了相同的条件数，但包含更多键组件，选择性较低。

使用 explain 操作符可以在 SELECT 语句前显示执行计划。大写缩写表示优化算法，缩进表示嵌套级别，方括号中的整数是数据源 ID。

要影响优化器的选择，可以通过以下方式：

- 更改 JOIN 中表的顺序：将更大的表或具有更高选择性的表放在前面。
- 更改合取项（AND 连接的部分）的顺序：优化器优先使用最左边的键索引，但如果存在复合索引涵盖多个合取项，则会使用该索引。
- 明确禁止使用某些索引：当应用程序从其他索引或顺序扫描中受益时，可以通过添加“虚拟”表达式来禁用特定索引。

    XSQL>explain select * from TTT where a=1;
    XSQL>create table TTT(a int using index);
    Plan
    -------------------------------------------------------------
    INDEX-SCAN[1] using index TTT.a(a)
     
    Selected records: 1
    XSQL>explain select * from TTT where a+0=1;
    XSQL>create table TTT(a int using index);
    Plan
    -------------------------------------------------------------
    FILTER (Eq (IntAdd TTT.a 0) 1)
    .SEQ_SCAN[1] of table TTT
     
    Selected records: 1

请注意，优化器当前不支持常量传播（即它不会用计算得出的常量表达式替换常量值）。因此，在查询中不要使用类似 (2+2) 的表达式。

优化器无法将子查询转换（展平）为普通连接。这必须手动完成，例如重写：

    select c1 from t1 where c1 in (select c1 from t2);
    
    // 重写为
    
    select t1.c1 from t1, t2 where t1.c1=t2.c2;

如果查询中包含长计算（如序列聚合函数）并带有排序和 LIMIT 子句，建议将该计算分离到子查询中。当前优化器无法自动处理这种情况，因此需要手动进行。

可以使用 ShuffleJoin 替代 HashJoin。ShuffleJoin 不会将整个内部表加载到内存中，而是根据连接键的哈希值将内外表划分为 N 个文件。通过 SqlOptimizerParameters 的 nShuffleFiles 字段指定分区数量，默认为 128。也可以使用 setShuffleFiles(n) 函数在当前会话中更改分区数量，并返回之前的值。ShuffleJoin 的内存占用可估算为 (sizeof(OuterTable) + sizeof(InnerTable)) / N。注意，如果分区数量 N 较高（如 N > 1000），系统可能会耗尽文件描述符。

是否使用 ShuffleJoin 替代 HashJoin 取决于应用程序需求。SQL 中添加了关键字“shuffle”，可以与标准连接限定符（如左连接、外连接、自然连接）一起使用。例如：

    select * from A shuffle join B on A.id = B.id;

关系运算符和执行计划

下表描述了一些关系运算符的实现注意事项，并解释了每个运算符的优缺点：

关系运算	“解释”计划缩写	优化器在以下情况使用时	优点	缺点
顺序表扫描	SEQ-SCAN	查询中没有可用的索引	按照顺序（按照写入数据库的顺序）访问记录	每条记录的访问开销较大。没有单独的表空间
索引扫描	INDEX-SCAN	搜索谓词包含键字段；结果集需要按键排序	快速	通常来说是随机访问存储以访问。这可以通过在批量插入时按索引顺序预排序表来缓解
范围内的索引扫描（左右边界都有）	INDEX-RANGE-SCAN	使用 BETWEEN 子句时；对键使用一对比较运算符	这比 INDEXSCAN 和 FILTER 的组合更高效，因为扫描会尽快中断	不支持复合键
嵌套循环连接	嵌套循环连接	当哈希连接和索引连接都不可能时使用	非常通用 - 可处理任何连接条件，包括交叉连接（将第一个表中的每一行与第二个表中的每一行组合）	非常慢
索引连接	索引连接	内表连接键存在索引	最快的连接算法	引用的局部性差（哈希在任何方式上都不有序）
筛选	FILTER	查询包含 WHEN 子句且没有可用的索引	用途广泛	慢
投影	SELECT	选择列（字段）的子集	减小结果集（所选数据集）的大小。有时效果显著	需要填充临时记录而不是直接引用对象，从而导致内存和性能开销
大型聚合	GRAND-AGGREGATE	不使用 GROUP BY 的简单聚合	不带 GROUP BY 的最快聚合方式	无
排序聚合	SORT-AGGREGATE	利用分组键的排序操作进行聚合	灵活 - 可处理聚合中的任意表达式	内存开销：需要在内存中生成结果集并进行排序。可能会超出配额
排序	ORDER-BY	当查询排序无法通过索引扫描满足时使用	灵活：可处理任意排序子句	内存开销：排序需要在内存中生成结果集。可能超出配额
顶级 N 排序	ORDER-BY.LIMIT	当查询包含 ORDER-BY 子句后跟 LIMIT 子句时使用	在内存中仅保留 N 条记录	对于较大的 N，可能比 SORT + LIMIT 组合慢
交集两个结果集	INTERSECT	使用 INTERSECT 子句	除了提供功能外没有其他用途	输入结果集必须已排序
去除重复项	DISTINCT	使用 DISTINCT 子句	除了提供功能外没有其他用途	输入数据集必须已排序
并集两个结果集	UNION	使用 UNION 子句	除了提供功能外没有其他用途	结果集的大小无法提前确定
从两个结果集中减去	EXCEPT	使用 EXCEPT 子句	除了提供功能外无其他	输入数据集必须已排序
按标记为不同的列排序，然后分组，并且每个组仅保留第一列	DISTINCT-GROUP	这是 SmartEDB SQL 的一个特殊扩展	获取组内首/尾记录的紧凑、简单且高效的方式	用以替代标准 SQL 的 WINDOW 子句
将序列转换为行（从垂直表示转换为水平表示）	FLATTEN	使用带有 FLATTENED 限定符的选择	允许对垂直数据应用标准 SQL 操作符	显著增加结果集大小
在内存中实现结果集	MATERIALIZE	不依赖于外部查询的子查询	通过缓冲中间查询的结果集避免冗余计算	内存占用大

以下是一些有助于理解优化器如何确定查询执行计划的定义：

可索引表达式

如果满足以下条件，则表达式为可索引表达式：

这是正在被检查的表中的一列（在执行表连接时），并且在数据库模式中为此字段或一组字段（复合键）定义了索引，其中此字段为首位。
表达式是一个引用访问表达式（指针字段.引用表达式），其中指针字段是正在被检查的表中的引用字段，引用表达式是可索引表达式，并且在数据库模式中为指针字段定义了索引。在这种情况下，SmartESQL 将首先执行索引搜索以选择与引用表达式匹配的记录，然后在此表中使用指针字段的索引执行索引搜索，定位指针字段指向此选择中的记录之一的记录。

例如，假设我们有两个表，供应商表（Supplier）和订单表（Order），以及以下查询：

    select * from Order where supplier.location.city=’New York’;

如果满足以下条件，此查询可以使用索引搜索来执行：

在“供应商”表中，字段 location.city 有一个索引。
在“订单”表中，字段 supplier 有一个索引（其中 supplier 是一个类型为 autoid_t 的引用字段，它引用“供应商”记录的 autoid）。
为“供应商”表维护 AUTOID。

如果这些条件为真，那么 SmartESQL 将首先在“供应商”表中执行索引搜索，选择位于纽约的供应商，并且对于每个选定的记录，在“订单”表中字段 supplier 的索引中搜索其 AUTOID。

请注意，在使用 SQL 数据定义语言（DDL）定义表时，若要使优化器能够利用基于索引的优化，索引字段必须声明为非空。例如：

    XSQL>create table t (i int not null, j int not null);
    XSQL>create index idx on t (i, j);

已知值

如果表达式是一个字面值或查询参数，并且是被检查表的表编号较小的表中的字段，则该表达式为已知值。

例如，考虑两个表格：

    Create table Person (pid integer primary key, name string using index);
    Create table Hobby (pid person key, description string);

要选择一个人的所有爱好，有两种可能的 SQL 表达方式：好的示例：

    Select * from Person p, Hobby h where p.name=’John Smith’ and p.pid = h.pid;

不好的示例：

    Select * from Hobby h, Person p where p.name=’John Smith’ and p.pid = h.pid;

从前面给出的信息可知，这些连词的排列顺序如下：

GOOD EXAMPLE	BAD EXAMPLE
`p.name = “John Smith”`	`p.pid = h.pid`
`p.pid = h.pid`	`p.name = “John Smith”`

在“良好”的示例中，将首先评估对 p.name = "John Smith" 的索引搜索，然后进行索引连接以选择其爱好（或多个爱好）。

在“BAD”示例中，将对 Hobby 表进行顺序扫描，并针对每条记录使用索引连接查找相关的 Person，然后检查此人的姓名是否为“John Smith”。

    db.executeQuery("select * from T where name like %s", "John%");

并且在查询中使用顺序搜索：

    db.executeQuery("select * from T where name like %s", "%John%");

预编译的执行计划所含信息不足，无法做出此判断。

SmartESQL优化器

关系运算符和执行计划

可索引表达式

已知值

唯一

排序依据

子查询

显示计划