【GreatSQL优化器-09】make_join_query_block

2025-01-08 189

【GreatSQL优化器-09】make_join_query_block

一、make_join_query_block介绍

GreatSQL优化器对于多张表join的连接顺序在前面的章节介绍过的best_access_path函数已经执行了，接着就是把where条件进行切割然后推给合适的表。这个过程就是由函数make_join_query_block来执行的。

下面用几个简单的例子来说明join连接中条件推送是什么。

CREATE TABLE t1 (c1 INT PRIMARY KEY, c2 INT,date1 DATETIME);
INSERT INTO t1 VALUES (1,10,'2021-03-25 16:44:00.123456'),(2,1,'2022-03-26 16:44:00.123456'),(3,4,'2023-03-27 16:44:00.123456'),(5,5,'2024-03-25 16:44:00.123456'),(7,null,'2020-03-25 16:44:00.123456'),(8,10,'2020-10-25 16:44:00.123456'),(11,16,'2023-03-25 16:44:00.123456');
CREATE TABLE t2 (cc1 INT PRIMARY KEY, cc2 INT);
INSERT INTO t2 VALUES (1,3),(2,1),(3,2),(4,3),(5,15);
CREATE TABLE t3 (ccc1 INT, ccc2 varchar(100));
INSERT INTO t3 VALUES (1,'aa1'),(2,'bb1'),(3,'cc1'),(4,'dd1'),(null,'ee');
CREATE INDEX idx1 ON t1(c2);
CREATE INDEX idx2 ON t1(c2,date1);
CREATE INDEX idx2_1 ON t2(cc2);
CREATE INDEX idx3_1 ON t3(ccc1);

下面这个例子((t1.c1 = t3.ccc1) or (t3.ccc1 < 3))条件推送给t1

greatsql> EXPLAIN FORMAT=TREE SELECT * FROM t1 join t3 ON t1.c1=t3.ccc1 or t3.ccc1<3;
+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| EXPLAIN                                                                                                                                                                                                                                                         |
+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| -> Filter: ((t1.c1 = t3.ccc1) or (t3.ccc1 < 3))  (cost=5.26 rows=35)
    -> Inner hash join (no condition)  (cost=5.26 rows=35)
        -> Index scan on t1 using idx2  (cost=0.34 rows=7)
        -> Hash
            -> Table scan on t3  (cost=0.75 rows=5)
 |
+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
1 row in set (0.00 sec)

下面例子(t1.c1 < 3)条件推给t1，(ccc1=t1.c1)条件推给t3

greatsql> EXPLAIN FORMAT=TREE SELECT * FROM t1 join t3 ON t1.c1=t3.ccc1 and t3.ccc1<3;
+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| EXPLAIN                                                                                                                                                                                                                          |
+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| -> Nested loop inner join  (cost=2.40 rows=2)
    -> Filter: (t1.c1 < 3)  (cost=1.70 rows=2)
        -> Index scan on t1 using idx2  (cost=1.70 rows=7)
    -> Index lookup on t3 using idx3_1 (ccc1=t1.c1)  (cost=0.30 rows=1)
 |
+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+

下面例子((t3.ccc1 = t1.c2) or (t3.ccc1 is null) or (t3.ccc2 like 'a%'))条件推给t3，(((t3.ccc1 = t1.c2) and (t2.cc1 = t1.c1)) or (t3.ccc1 is null) or (t3.ccc2 like 'a%'))条件推给t2

greatsql> EXPLAIN SELECT * FROM t2,t1,t3 WHERE t1.c1=t2.cc1 AND t1.c2=t3.ccc1 OR t3.ccc1 IS NULL OR t3.ccc2 LIKE 'a%';
| -> Filter: (((t3.ccc1 = t1.c2) and (t2.cc1 = t1.c1)) or (t3.ccc1 is null) or (t3.ccc2 like 'a%'))  (cost=14.27 rows=85)
    -> Inner hash join (no condition)  (cost=14.27 rows=85)
        -> Index scan on t2 using idx2_1  (cost=0.09 rows=5)
        -> Hash
            -> Filter: ((t3.ccc1 = t1.c2) or (t3.ccc1 is null) or (t3.ccc2 like 'a%'))  (cost=4.70 rows=17)
                -> Inner hash join (no condition)  (cost=4.70 rows=17)
                    -> Table scan on t3  (cost=0.07 rows=5)
                    -> Hash
                        -> Index scan on t1 using idx2  (cost=0.95 rows=7)

二、make_join_query_block代码解释

make_join_query_block函数通过join表顺序和每张表的table_map属性以及cond条件的属性来决定cond条件添加到哪张表,并且可能会重新对表的索引进行check找出cost更低的索引，下面是代码解析。

bool JOIN::optimize() {
  make_join_query_block();
}

static bool make_join_query_block(JOIN *join, Item *cond) {
  for (uint i = join->const_tables; i < join->tables; i++) {
      // 这四个变量说明见表一
      JOIN_TAB *const tab = join->best_ref[i];
      const plan_idx first_inner = tab->first_inner();
      const table_map used_tables = tab->prefix_tables();
      const table_map current_map = tab->added_tables();
      if (cond)
        // 这里通过table_map属性决定了是否给这个表添加条件，见下面表二、表四和表五说明
        tmp = make_cond_for_table(thd, cond, used_tables, current_map, false);
     // 如果recheck_reason=true，这里需要重新做一次确认，找出cost最低的索引。见表六
      if (recheck_reason)
        test_if_order_by_key();
        test_if_cheaper_ordering();
        test_quick_select();
      }  
      /* Add conditions added by add_not_null_conds(). */
      if (and_conditions(&tmp, tab->condition())) return true;
      if (join->attach_join_conditions(i)) return true;
  }
}
// 条件添加基本原则是条件带有表列的添加到该表，但是如果属性不一致的话也不会添加，只会添加到最后一张表。具体解释见下面实际例子。

表一：上面四个变量解释

变量	解释	说明
tab	当前检测是否需要加条件的表	这里是排序后的表
first_inner	多张表join的时候排序后的第一张表	例如：SELECT * FROM t1 LEFT OUTER JOIN (t2 JOIN t3) ON X
used_tables	包括当前表以及之前的左连接表的信息	如果该值=0代表所有表，used_tables信息在之前的set_prefix_tables()获得
current_map	当前检测表信息	包含被添加的一些信息

表二：make_cond_for_table()动作

场景	解释	返回
AND条件	遍历Item_cond包含的所有list，判断list是否有包含该表左连接的表的列，有的话加入新的Item_cond_and	new Item_cond_and
OR条件	遍历Item_cond包含的所有list，判断list是否有包含该表左连接的表的列，有的话加入新的Item_cond_or	new Item_cond_or
其他Item	如果条件没有涉及左连接的表，或者给所有表添加条件cond->is_expensive()	nullptr(无条件)
其他Item	如果条件涉及左连接的表并且item与表的属性一致(见表四)	该Item条件

表三：is_expensive_processor()函数

Item	is_expensive	说明
Item_udf_func	true	这个Item作为条件不会添加到所有join表里面
Item_func_sp	true	这个Item作为条件不会添加到所有join表里面
普通Item	false	这个Item作为条件可能会添加到join表里面

表四：Item的table_map属性

table_map	使用的Item	说明	举例
INNER_TABLE_BIT	Item_trigger_field，Item_sp_variable，Item_param，Item_func_connection_id，Item_func_get_system_var，Item_func_user，Item_load_file, Item_func_sp，Item_func_get_user_var	确定的常量，在表每行都一样	f1(1)@@optimizer_search_depth
OUTER_REF_TABLE_BIT	Item_field,Item_ref,Item_view_ref,Item_outer_ref	内部field需要外部query block的item信息	select (select t1.a from t1 as t2 limit 1) from t1 group by t1.pk，t1.a就是OUTER_REF_TABLE_BIT
RAND_TABLE_BIT	Item_func_rand,Item_func_sleep,Item_func_uuid,Item_func_sysdate_local，Item_func_reject_if,Item_func_sp，Item_func_get_user_var	不确定的，表每行都要换数据，非只有一行表，跟INNER_TABLE_BIT相反	f1(t1.c1)
PSEUDO_TABLE_BITS		包含以上三个

表五：表连接添加的属性

table_map	第一张表	中间的表	最后一张表
INNER_TABLE_BIT	yes	无	无
OUTER_REF_TABLE_BIT	allow_outer_refs	无	无
RAND_TABLE_BIT	无	无	yes

表六：表的索引是否要重新check

recheck_reason	说明
DONT_RECHECK	没有索引的表不需要重新check
NOT_FIRST_TABLE	不是第一张表需要重新check
LOW_LIMIT	带有limit语句的sql需要重新check

三、实际例子说明

接下来看几个例子来说明上面的代码。

首先看一下最后确定的连接顺序，为t1,t3,t2，因为条件不带有RAND_TABLE_BIT的Item，因此最后是按照cond含有的列推送给对应表来实现的。

例子一：

greatsql> EXPLAIN SELECT * FROM t2,t1,t3 WHERE t1.c1=t2.cc1 AND t1.c2=t3.ccc1 OR t3.ccc1 IS NULL OR t3.ccc2 LIKE 'a%';
+----+-------------+-------+------------+-------+-------------------+--------+---------+------+------+----------+---------------------------------------------------------+
| id | select_type | table | partitions | type  | possible_keys     | key    | key_len | ref  | rows | filtered | Extra                                                   |
+----+-------------+-------+------------+-------+-------------------+--------+---------+------+------+----------+---------------------------------------------------------+
|  1 | SIMPLE      | t1    | NULL       | index | PRIMARY,idx1,idx2 | idx2   | 11      | NULL |    7 |   100.00 | Using index                                             |
|  1 | SIMPLE      | t3    | NULL       | ALL   | idx3_1            | NULL   | NULL    | NULL |    5 |    48.80 | Using where; Using join buffer (hash join)              |
|  1 | SIMPLE      | t2    | NULL       | index | PRIMARY           | idx2_1 | 5       | NULL |    5 |   100.00 | Using where; Using index; Using join buffer (hash join) |
+----+-------------+-------+------------+-------+-------------------+--------+---------+------+------+----------+---------------------------------------------------------+

表一：是否把cond条件推送给表

COND	t1	[t1,]t3	[t1,t3,]t2
(t1.c1=t2.cc1)	no	no	yes
(t3.ccc1 = t1.c2)	no	yes	yes
(t3.ccc1 is null)	no	yes	yes
(t3.ccc2 like 'a%')	no	yes	yes

注：这里的中括号代表当前检测表的左连接表，中括号右边就是当前正在检测的表

表二：表的table_map值

COND	t1	t3	t2
best_ref->table_ref->map()	0x010	0x100	0x001
best_ref->prefix_tables()	INNER_TABLE_BIT+ OUTER_REF_TABLE_BIT+0x010	INNER_TABLE_BIT+ OUTER_REF_TABLE_BIT+0x010+0x100	INNER_TABLE_BIT+OUTER_REF_TABLE_BIT +RAND_TABLE_BIT+0x010+0x100+0x001
best_ref->added_tables()	INNER_TABLE_BIT+ OUTER_REF_TABLE_BIT+0x010	0x100	RAND_TABLE_BIT+0x001

注：这里的INNER_TABLE_BIT和OUTER_REF_TABLE_BIT在函数JOIN::set_prefix_tables()默认加上了

看一下结果是否符合预期，确实如上表所述。这里看到又执行了一次test_quick_select()来确定走哪个索引。

"attaching_conditions_to_tables": {
              "original_condition": "(((`t3`.`ccc1` = `t1`.`c2`) and (`t2`.`cc1` = `t1`.`c1`)) or (`t3`.`ccc1` is null) or (`t3`.`ccc2` like 'a%'))",
              "attached_conditions_computation": [
                {
                  "table": "`t2`",
                  "rechecking_index_usage": { 这里对索引重新做了一次check
                    "recheck_reason": "not_first_table",
                    "range_analysis": {
                      "table_scan": {
                        "rows": 5,
                        "cost": 3.6
                      },
                      "potential_range_indexes": [
                        {
                          "index": "PRIMARY",
                          "usable": true,
                          "key_parts": [
                            "cc1"
                          ]
                        },
                        {
                          "index": "idx2_1",
                          "usable": false,
                          "cause": "not_applicable"
                        }
                      ],
                      "best_covering_index_scan": {
                        "index": "idx2_1",
                        "cost": 0.751098,
                        "chosen": true
                      },
                      "setup_range_conditions": [
                      ],
                      "group_index_range": {
                        "chosen": false,
                        "cause": "not_single_table"
                      },
                      "skip_scan_range": {
                        "chosen": false,
                        "cause": "not_single_table"
                      }
                    }
                  }
                }
              ],
              "attached_conditions_summary": [
                {
                  "table": "`t1`",
                  "attached": null
                },
                {
                  "table": "`t3`",
                  "attached": "((`t3`.`ccc1` = `t1`.`c2`) or (`t3`.`ccc1` is null) or (`t3`.`ccc2` like 'a%'))"
                },
                {
                  "table": "`t2`",
                  "attached": "(((`t3`.`ccc1` = `t1`.`c2`) and (`t2`.`cc1` = `t1`.`c1`)) or (`t3`.`ccc1` is null) or (`t3`.`ccc2` like 'a%'))"
                }
              ]
            }
          },
          {
            "finalizing_table_conditions": [
              {
                "table": "`t3`",
                "original_table_condition": "((`t3`.`ccc1` = `t1`.`c2`) or (`t3`.`ccc1` is null) or (`t3`.`ccc2` like 'a%'))",
                "final_table_condition   ": "((`t3`.`ccc1` = `t1`.`c2`) or (`t3`.`ccc1` is null) or (`t3`.`ccc2` like 'a%'))"
              },
              {
                "table": "`t2`",
                "original_table_condition": "(((`t3`.`ccc1` = `t1`.`c2`) and (`t2`.`cc1` = `t1`.`c1`)) or (`t3`.`ccc1` is null) or (`t3`.`ccc2` like 'a%'))",
                "final_table_condition   ": "(((`t3`.`ccc1` = `t1`.`c2`) and (`t2`.`cc1` = `t1`.`c1`)) or (`t3`.`ccc1` is null) or (`t3`.`ccc2` like 'a%'))"
              }
            ]
          },
          {
            "refine_plan": [
              {
                "table": "`t1`"
              },
              {
                "table": "`t3`"
              },
              {
                "table": "`t2`"
              }
            ]
          }
        ]
      }
    }

如果条件带有RAND_TABLE_BIT的Item，那么即使cond带有表的列，也不会推送给对应的表，而是推送到最后一张表。看下面的t1.c1 < rand()这个条件。

例子二：

greatsql> SELECT * FROM t2,t1,t3 WHERE t1.c1=t2.cc1 AND t1.c2=t3.ccc1 OR t3.ccc1 IS NULL AND t1.c1 < rand();
              "attached_conditions_summary": [
                {
                  "table": "`t1`",
                  "attached": null
                },
                {
                  "table": "`t3`",
                  "attached": "((`t3`.`ccc1` = `t1`.`c2`) or (`t3`.`ccc1` is null))"
                },
                {
                  "table": "`t2`",
                  "attached": "(((`t3`.`ccc1` = `t1`.`c2`) and (`t2`.`cc1` = `t1`.`c1`)) or ((`t3`.`ccc1` is null) and (`t1`.`c1` < rand())))"  看到条件t1.c1 < rand()没有推送给t1而是推送到最后一张表t2去了
                }
              ]
            }
          },
          {
            "finalizing_table_conditions": [
              {
                "table": "`t3`",
                "original_table_condition": "((`t3`.`ccc1` = `t1`.`c2`) or (`t3`.`ccc1` is null))",
                "final_table_condition   ": "((`t3`.`ccc1` = `t1`.`c2`) or (`t3`.`ccc1` is null))"
              },
              {
                "table": "`t2`",
                "original_table_condition": "(((`t3`.`ccc1` = `t1`.`c2`) and (`t2`.`cc1` = `t1`.`c1`)) or ((`t3`.`ccc1` is null) and (`t1`.`c1` < rand())))",
                "final_table_condition   ": "(((`t3`.`ccc1` = `t1`.`c2`) and (`t2`.`cc1` = `t1`.`c1`)) or ((`t3`.`ccc1` is null) and (`t1`.`c1` < rand())))"
              }
            ]
          },
          {
            "refine_plan": [
              {
                "table": "`t1`"
              },
              {
                "table": "`t3`"
              },
              {
                "table": "`t2`"
              }

看一下每张表的属性：

COND	t1	t3	t2
best_ref->table_ref->map()	0x010	0x100	0x001
best_ref->prefix_tables()	INNER_TABLE_BIT+ OUTER_REF_TABLE_BIT+0x010	INNER_TABLE_BIT+ OUTER_REF_TABLE_BIT+0x010+0x100	INNER_TABLE_BIT+OUTER_REF_TABLE_BIT +RAND_TABLE_BIT+0x010+0x100+0x001
best_ref->added_tables()	INNER_TABLE_BIT+ OUTER_REF_TABLE_BIT+0x010	0x100	RAND_TABLE_BIT+0x001

四、总结

从上面优化器最早的步骤我们认识了make_join_query_block函数的作用，知道了通过join表顺序和每张表的table_map属性以及cond条件的属性来决定cond条件添加到哪张表,并且可能会重新对表的索引进行check找出cost更低的索引，需要注意的是有的带有表列的条件不会被添加到对应表，因为Item的属性跟表的属性不一致所以最后只会被添加到最后一张join表。

微信关注我们

原文链接：https://my.oschina.net/GreatSQL/blog/17113537

转载内容版权归作者及来源网站所有！

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。

阿里云 AI 搜索方案解读：大模型驱动下的智能搜索，助力企业数字化转型

在过去的一年里面，随着大模型的技术突飞猛进，大模型的能力日益增强。这些都驱动着我们的搜索技术快速的演进到了下一代，也就是 AI 搜索的技术。大模型的快速发展不仅重塑了搜索技术的基础，也为各行各业的数字化转型提供了强有力的支持。一、AI 搜索技术的特点 AI 搜索技术具有以下几个显著的特点：重构：一个是 AI 搜索技术方面的重构。AI 搜索技术目前正在基于大模型进行全面重构，通过大模型，搜索的全链路能力得到了重组，包括文本解析、切片和向量化等能力的重新定义。另一个是信息获取的方式与产品的形态的重构。传统搜索依赖关键词匹配，而现在更多采用自然语言的问答式交互，这带来了新的业务场景，如虚拟数字人、企业知识库问答和电商平台的智能客服。 AI 基建：AI 搜索技术已成为 AI native 应用的重要组成部分，包括搜索向量检索、语义搜索和检索生成技术，构成了众多 AI 应用的基础设施。这不仅提高了数据处理的效率，还提升了用户与系统的交互体验，帮助企业实现更高效的信息管理和服务。效果提升：目前，效果的关注度在学术界和工业界都达到了空前的高度。大模型的加持使得搜索效果相比传统搜索有了质的飞跃...

2025-01-08

229

Model Context Protocol (MCP) 是一种开放标准，旨在促进人工智能（AI）系统与各种数据源之间的安全双向连接。它为 AI 应用程序提供了统一的接口，使其能够高效地访问和利用外部数据，从而取代了以往需要为每个数据源定制集成的复杂做法。 https://modelcontextprotocol.io/docs/concepts/architecture 是什么？ Model Context Protocol（MCP）是由Anthropic推出的一项开放协议，旨在促进大型语言模型（LLM）与外部数据源之间的无缝集成。MCP通过提供一个标准化的客户端-服务器架构，使得不同的AI应用能够高效地访问和共享本地及远程资源，从而解决了数据孤岛问题。 MCP 协议让开发者能够以统一的方式，连接各种本地或远程资源。统一标准：开发者只需要针对 MCP 进行一次开发，就能够实现与各种数据来源的对接，免去为每个数据源编写单独连接器的麻烦，从而大幅减少开发和维护的成本。支持多种数据格式 MCP 能够处理各种不同的数据，包括结构化数据（如数据库）和非结构化数据（如文本或影像），这使得开...

2025-01-08

632

资源下载

更多资源

腾讯云软件源

为解决软件依赖安装时官方源访问速度慢的问题，腾讯云为一些软件搭建了缓存服务。您可以通过使用腾讯云软件源站来提升依赖包的安装速度。为了方便用户自由搭建服务架构，目前腾讯云软件源站支持公网访问和内网访问。

Spring

Spring框架（Spring Framework）是由Rod Johnson于2002年提出的开源Java企业级应用框架，旨在通过使用JavaBean替代传统EJB实现方式降低企业级编程开发的复杂性。该框架基于简单性、可测试性和松耦合性设计理念，提供核心容器、应用上下文、数据访问集成等模块，支持整合Hibernate、Struts等第三方框架，其适用范围不仅限于服务器端开发，绝大多数Java应用均可从中受益。

Rocky Linux

Rocky Linux（中文名：洛基）是由Gregory Kurtzer于2020年12月发起的企业级Linux发行版，作为CentOS稳定版停止维护后与RHEL（Red Hat Enterprise Linux）完全兼容的开源替代方案，由社区拥有并管理，支持x86_64、aarch64等架构。其通过重新编译RHEL源代码提供长期稳定性，采用模块化包装和SELinux安全架构，默认包含GNOME桌面环境及XFS文件系统，支持十年生命周期更新。

Sublime Text

Sublime Text具有漂亮的用户界面和强大的功能，例如代码缩略图，Python的插件，代码段等。还可自定义键绑定，菜单和工具栏。Sublime Text 的主要功能包括：拼写检查，书签，完整的 Python API ， Goto 功能，即时项目切换，多选择，多窗口等等。Sublime Text 是一个跨平台的编辑器，同时支持Windows、Linux、Mac OS X等操作系统。