在我们的开源Golang SQL查询引擎中实施联接计划

Dolt是Git for Data。它是一个SQL数据库，您可以对其进行克隆，派生，分支和合并。 Dolt的SQLengine是go-mysql-server，今天我们将讨论它如何实现联接计划以使涉及多个表的查询计划尽可能高效。

当一个查询涉及多个表时，可以通过多种方式访问​​这些表以获得正确的结果。但是某些方法比其他方法要快得多！选择访问表中的顺序和策略以组合结果行的方式称为联接计划。用示例最容易解释。

让我们创建三个表来跟踪城市和州的人口以及其中的人口。如果您已安装Dolt（在边栏中的链接），则可以继续进行。

％mkdir加入-planning＆amp;＆amp; cd join -planning％dolt init成功初始化了dolt数据存储库。 ％dolt sql＃欢迎使用DoltSQL shell。 ＃语句必须以＆＃39 ;;＆＃39终止。 ＃＆＃34;退出＆＃34;或＆＃34; quit＆＃34; （或Ctrl-D）退出。join_planning＆gt;创建表状态（名称varchar（100）主键不为null，pull int为无符号）； join_planning＆gt;创建表城市（名称varchar（100）主键不为null，状态varchar（100）不为null，pull int unsigned）； join_planning＆gt;创建表人员（名称varchar（100）主键不为null，city varchar（100）不为null）;

假设我们想要一个名为“约翰·史密斯”的人的名单。以及他们所居住的城市和州的名称和人口。我们将编写如下查询：

从人们中选择*从p加入城市c在p .city = c .name上加入州s在s .name = c .state，其中p .name =＆＃34; John Smith＆＃34; ;

查询计划者可以通过多种方式执行此查询。糟糕的方法是查看所有三个表中每一行的每个组合，并测试每个组合是否符合JOIN条件和WHERE子句。这是正确和有效的，但是非常昂贵。如果说州，城市和人口统计表分别包含S，C和P行，则此查询计划（称为交叉联接）将导致S * C * P行访问和比较。这是一个坏主意。

您可以使用一些简单的技巧来加快查询的执行速度。使用下推优化，可以消除对人员表的大多数访问。假设约翰·史密斯（John Smiths）的人数在数据库中被称为J，它比P小得多。然后使用下推智能地降低了我们访问S * C * J的成本。

直到几周前，这与Dolt在三个或更多表的联接上所做的一样好。对于两个表，我们将使用索引（如果有）。但是三个，没有运气。通过这种查询模式和非平凡的数据大小，产品边界线无法用于工作负载。

这篇博客文章介绍了我们如何优化联接计划程序，以针对任何数量的表生成更智能，更有效的查询计划。在Dolt的当今版本中，相同的查询将生成以下查询计划：

join_planning＆gt;解释选择*从人中p加入城市c on p .city = c .name加入国家s on s .name = c .state其中p .name =＆＃34; John Smith＆＃34; ; + ------------------------------------------------- ------------ + |计划+ ------------------------------------------------- ------------ + | IndexedJoin（p .city = c .name）| | ├─过滤器（p .name =＆＃34; John Smith＆＃34;）| | │└─计划在[名称城市]上使用表格| | │└─TableAlias（p）| | │└─索引[people.name]上的索引表访问| | │└─交换（平行度= 16）| | │└─桌子（人）| | ed─IndexedJoin（s .name = c .state）| | ├─TableAlias（c）| | │└─IndexedTableAccess（[citys.name]上的城市）| | Table─TableAlias（s）| | └─IndexedTableAccess（[states.name]上的状态）| + ------------------------------------------------- ------------ +

该计划首先在人们的姓名列上建立索引访问，以查找所有John Smiths。然后，对于每一行，它使用主键索引来查找城市。然后，对于每个城市，它使用另一个主键来查找州。总之，这将导致J * 3的总查询成本。

用一些实数来说明问题：让我们以美国为例，说有3.3亿人行，2万个城市行和52个州行（我们并没有忘记您，哥伦比亚特区和波多黎各）。交叉联接查询计划将访问等于这些数字乘积的行数，这大约是343万亿次访问。数量很多。您的查询将无法完成。

美国大约有48,000名名为JohnSmithin的人。因此，使用下推式优化可使我们减少到大约500亿行访问。这比以前好了很多，但是仍然很可怕。查询不会返回。

另一方面，同时使用下推到人员表和对城市和州的索引访问，将查询执行限制为仅对人员表进行48,000次访问，然后对这些行中的每行分别访问1个城市和州表。这就是3 * 48,000，即总共144,000个表访问。

与下推博客不同，Iwon不必费心说明节省的百分比。我们正在为第一个优化考虑4个十进制数量级的改进，然后为第二个优化考虑另外5个数量级的改进。 Dolt是可用的查询引擎或坏的空间加热器之间的区别。

要制定有效的查询计划，您必须首先回答一个非常重要的问题：

这确实使一切有所不同。在上面的示例中，人员的表访问顺序>城市＆gt;状态让我们在后两个表上使用主键索引。如果我们改为选择订单状态＆gt;城市＆gt;人们，我们不能使用早期表中的信息来减少对后来表的查找次数，从而使我们得到交叉连接。

有很多有趣的细节会出错，但是要正确使用表顺序，您可以使用一些非常简单的试探法。

我可以使用什么索引访问该表？这些列是联接条件的一部分吗？

是否有必需的列可用作键？联接条件中的其他表是否在此条件之前？

如果需要进行全表扫描，此表中有多少行？

这是LEFT或RIGHT联接吗？如果是，此表是否在联接的一边，要求它首先出现？

稍后，我们将返回表排序算法的实际实现。现在，让我们假设它存在，并告诉我们访问表的顺序。我们如何用该访问顺序构建联接计划？

在go-mysql-server中，查询计划组织在Node对象树中。到目前为止，所有节点最多具有两个子节点，从而使查询计划成为二叉树。 Join节点知道如何从其左子节点获取行，然后在其右子节点上迭代以查找joincondition上的匹配项。当右子迭代器的行数不足时，它将从左子迭代器获得下一行。最终，它耗尽了左子级中的行，并从其迭代器返回io.EOF。

像其他所有内容一样，使用某些示例最容易看出这一点。对于所有这些，我们将使用一个字母的表名以及与表名匹配的单列。这是两个表A和B之间的简单连接：

当我们向联接中添加其他表时，它们成为树的新根，原始子树为左子树。

从A上的B选择* *在b = c上加入B；在b = c上加入C；

从A上选择* *在a = b上加入B在b = c上加入C在c = d上加入D;

让我们更仔细地研究最后一个示例。当我们在查询的根节点上打开迭代器时会发生什么？它在其左子节点上打开一个迭代器，依次在其左子节点上打开一个迭代器，依此类推。每个节点在从其左子节点访问一行之后，都尝试从其右子节点查找匹配的行。我们最终得到的表访问顺序与词汇查询中的相同：A＆gt; B＆gt; C＞ D。

连接节点a = b从A获得一行。然后遍历B的行，查找与连接条件a = b相匹配的行。当找到这样的行时，将其返回。

节点b = c从其左子级获取行，该子级是表A和B的行的并置。然后，它在其右子级C的行上进行迭代，以查找与联接条件b = c相匹配的行。找到这样的行后，它将返回。

节点c = d从其左子级获得行，该子级是A，B和C的行的串联。然后，它如上所述尝试匹配其右子D的行。

重要的是，有时存在许多可能的二叉树，它们可以实现上述逻辑以针对任何给定的可访问顺序产生正确的结果。上面的树构建算法将子树向下推到新连接节点的左子节点，这正是解析器默认情况下为我们提供的内容，因为它是左关联的。但是我们可以绘制其他具有相同结果的树。例如，这是一个平衡的连接树：

像原始文件一样，这会产生A＆gt; B＆gt; C＞ D。如果我们想以相反的顺序访问表，我们可以像这样简单地翻转原始树中每个节点的左右子节点：

同样，对于给定的表顺序，有时会有许多可能的连接树。但是它们都有一个共同点：它们的连接条件引用可以在其左子对象和右子对象中找到的表。否则，节点无法评估其加入条件。例如，假设我们正在查询三个表，并希望以B＆gt;的顺序访问它们。 ＆gt; C.这是一个无效的联接计划，其表顺序为：

该计划无效，因为节点b = c没有表Bas的后代，因此它无法评估其连接条件。我们可以通过交换联接条件来解决此问题，或者：

这次仍然不满足较低的联接条件，因为它需要表B并且不将其作为后代。为了获得订单B＆gt; ＆gt; C并且仍然满足连接条件，我们需要改为生成此树：

我们可以利用以上有关构建联接树的见解，并使用通用算法来实现这一点。这是解决/搜索问题的约束，在源代码中我称其为联合搜索。

使用剩余的表和连接条件，递归构造此连接条件的所有可能的左子树。

检查每个潜在的左子树的有效性：这些表必须是有序的，并且必须满足连接条件。如果子树无效，则将其丢弃并检查下一个。

使用剩余的表和联接条件（确保从考虑中删除所有由左子树使用的表和联接条件）来递归地为此联接条件构造所有可能的右子树。再次丢弃无效的子树。

如果找不到有效的左或右子树，请放弃并返回第一步，选择一个新的加入条件。

像本技术博客系列中的大多数内容一样，这个想法相对简单，但是有许多小细节需要解决。由于使用Node对象非常麻烦，因此我创建了简化类型来表示搜索过程中的连接树：

// joinSearchNode是代表联接树节点的简化类型，它是内部节点（联接）或//叶节点（表）。联接树中的顶级节点始终是内部节点。每个内部节点都有//左右子节点。类型joinSearchNode struct {表字符串//如果是内部节点则为空joinCond * joinCond //如果这是叶节点则为null父* joinSearchNode // //如果这是根节点剩余则为零* joinSearchNode //如果这是叶则为nil节点右侧* joinSearchNode // //如果是叶节点则为nil * joinSearchParams //组成该节点的搜索参数}

除了普通的树结构之外，此类型还跟踪父指针（以使其更容易从根遍历以验证表排序规则）并搜索参数以跟踪可使用哪些表和联接条件。

这是实现此算法的searchJoins函数的一部分。完整的代码在上面链接。

func searchJoins（父* joinSearchNode，params * joinSearchParams）[] * joinSearchNode {//我们的目标是为给定的父级构造所有可能的子节点。合法子树的每个排列都应//进入此列表。 children：= make（[] * joinSearchNode，0）//＆lt;将表添加到子列表的快照代码＆gt;对于i，cond：=范围参数.joinConds {如果params。 joinCondIndexUsed（i）{继续} paramsCopy：= params。复制（）paramsCopy .usedJoinCondsIndexes =追加（paramsCopy .usedJoinCondsIndexes，i）候选者：=＆amp; joinSearchNode {joinCond：cond，parent：parent，params：paramsCopy，} //对于左右分支中的每一个，找到所有可能的孩子，将所有有效的子树添加到列表候选人=候选人。 targetLeft（）leftChildren：= searchJoins（candidate，paramsCopy）//注意此块中_的变量阴影，left：= range leftChildren {如果！ isValidJoinSubTree（左）{继续}候选人：=候选人。 withChild（左）。 targetRight（）候选.params =候选。 accumulateAllUsed（）rightChildren：= searchJoins（candidate，paramsCopy）_，right：= range rightChildren {如果！ isValidJoinSubTree（右）{继续}候选人：=候选人。 withChild（正确），如果isValidJoinSubTree（候选）{children = append（children，候选人）}}}}返回child}

现在我们有了表顺序和实现该顺序的联接计划，我们需要一种将关键信息获取到计划中以后的表的方法。我们对表进行排序的全部原因是为了能够在除第一个表之外的每个表上使用索引查找。对于这些表中的每一个，我们都希望传递联接中所有早期表中行的隐性，以便我们可以使用此信息来构造索引的查找键。

考虑这个四表加入计划。对于树中的每个边缘，我们将用子节点需要访问的表来标记该边缘，以便在其左侧的任何表中查找关键信息。

每个连接节点将为其左侧的子节点提供接收到的行（对于根节点，为空）。然后，它将向其右手孩子提供该行和左手孩子的行的串联。这相当于树的有序遍历，它将按照我们在开始时指定的顺序访问表。首先，根节点以空行向左移动。同样的事情发生在第一个子节点（a = b）中。当此子节点向右遍历时，它从其左手子节点A提供行。然后，根节点向右遍历，并从其左子节点提供行（对应于AB）。最终节点（c = d）中发生了同样的事情，最终的右手子代由其父行（AB）和左手子代（C）串联而成。

与其余大多数引擎分析不同，我们无法对树进行自下而上的转换。从根本上讲，它是按顺序进行的，因此我们必须使用自定义功能自上而下进行操作。这是其中有趣的部分（进行一些小的编辑，例如删除错误处理样板并简化返回类型）。

func replaceTableAccessWithIndexedAccess（节点sql .Node，架构sql .Schema，合并范围* Scope，joinIndexes，joinIndexesByTable，exprAliases ExprAliases，tableAliases，TableAliases，）sql.Node {switch node：= node。 （type）{case * plan .TableAlias，* plan .ResolvedTable：//如果可用模式使该表上的索引成为可能，请使用它，将其替换为索引访问索引：= joinIndexes [node。 （sql .Nameable）。名称（）] indexToApply：=索引。 getUsableIndex（schema）如果indexToApply == nil {返回节点}节点，err：=计划。 TransformUp（node，func（node sql .Node）（sql .Node，error）{切换node：= node。（type）{case * plan .ResolvedTable：if _，ok：= node .Table。（sql .IndexAddressableTable） ;！ok {返回节点} keyExprs：= createIndexLookupKeyExpression（indexToApply，exprAliases，tableAliases）keyExprs，err：= FixFieldIndexesOnExpressions（作用域，架构，keyExprs ...）返回计划。NewIndexedTableAccess（node，indexToApply .index，keyExprs）默认：返回node}}）返回节点的大小写* plan .IndexedJoin：//用输入模式left，replaceLeft，err递归左下：= replaceTableAccessWithIndexedAccess（node。Left（），模式，范围，joinIndexes，exprAliases，tableAliases）/ /然后在右侧，从左向右追加模式，replaceRight，err：= replaceTableAccessWithIndexedAccess（node。Right（），append（schema，left。Schema（）...），scope，joinIndexes，exprAliases，tableAliases）/ /如果表的顺序更改了cond，err：= FixFieldIndexes（scope，append（schema，append（left。模式（），正确。模式（）...）...），节点。 NewIndexedJoin（左，右，节点。JoinType（），cond）默认值：//其他节点类型newChild，replaced，err：= replaceTableAccessWithIndexedAccess（node.Child，架构，作用域，joinIndexes，exprAliases，tableAliases）返回节点。 WithChildren（newChild）}}

现在，我们回到开始的地方：如何确定应访问哪些订单表？现在，我们已经将所有其他部分放在一起，这部分相对容易。为了确定最佳排序，我们需要的是一组带有索引信息的连接条件。然后该函数编写起来非常简单：

// // orderTables返回提供的表的访问顺序，尝试最小化总查询成本func orderTables（tables [] NameableNode，tableByName map [string] NameableNode，joinIndexes joinIndexesByTable）[] string {tableNames：= make（[[] string，len （tablesByName））索引：= make（[[] int，len（tablesByName）））i，table：=范围表{tableNames [i] =字符串。 ToLower（table。Name（））索引[i] = i} //生成表顺序accessOrders的所有排列：=排列（索引）最低成本：= int64（数学.MaxInt64）最低成本IDx：= 0，i，accessOrder：=范围accessOrders {cost：= estimateTableOrderCost（tableNames，tableByName，accessOrder，joinIndexes，lowestCost），如果成本小于最低成本{最低成本=成本最低成本IDx = i}} cheapestOrder：=使（i，j：（[]字符串，len（tableNames）））（）

但是，这有点埋头苦脑。估算表排序的成本是多汁的部分。

//估算给定表排序的成本。 数字越小越好。 如果成本//超过目前找到的最低值，则纾困并返回到目前为止的成本。 如果我们有表和键的统计信息，我们可以做得更好。 funcestimateTableOrderCost（表[]字符串，表节点映射[字符串] NameableNode，accessOrder [] int，joinIndexes joinIndexesByTable，最低成本int64，）int64 {cost：= int64（1）var availableSchemaForKeys sql .i，idx：= range accessOrder { 如果成本＆gt; =最低成本{返回成本}表：=表[idx] availableSchemaForKeys =追加（availableSchemaForKeys，tableNodes [table]。Schema（）...）索引：= joinIndexes [table] //如果此表是 左联接或右联接，则断言表的顺序正确。 没有桌子// ......