TiDB 源码阅读系列文章（七）基于规则的优化

相关文章推荐

卖萌的小蝌蚪 · 走近莫言-山东大学经济学院· 7 月前 ·

爽快的咖啡豆 · 2023年10月中学进修活动表-北大附中初中部· 10 月前 ·

小眼睛的红豆 · 华为vr glass如何手机投屏-百度经验· 1 年前 ·

率性的米饭 · 鸣鸟不飞：乌云密布 - 知乎· 1 年前 ·

拉风的勺子 · 慈善晚会：上海27位主持人齐出动，林海携手9 ...· 1 年前 ·

</noscript><nav class="navbar index-module--header--+tJQO" role="navigation" aria-label="main navigation"><div class="navbar-brand index-module--mobileNavBar--shD-Y"><span><a class="navbar-item index-module--logo--nlzXC" href="/"><img src="data:image/svg+xml;base64,PHN2ZyB4bWxucz0iaHR0cDovL3d3dy53My5vcmcvMjAwMC9zdmciIHZpZXdCb3g9IjAgMCA2MTcuMzYgMTYwIj48ZGVmcz48c3R5bGU+LmNscy0xe2ZpbGw6I2ZmZjt9LmNscy0ye2ZpbGw6bm9uZTt9LmNscy0ze2ZpbGw6IzE3MmQ3Mjt9LmNscy00e2ZpbGw6IzAwYWVlZjt9LmNscy01e2ZpbGw6IzNkM2ZlYTt9PC9zdHlsZT48L2RlZnM+PGcgaWQ9IuWbvuWxgl8yIiBkYXRhLW5hbWU9IuWbvuWxgiAyIj48ZyBpZD0iTGF5ZXJfMSIgZGF0YS1uYW1lPSJMYXllciAxIj48cGF0aCBjbGFzcz0iY2xzLTEiIGQ9Ik00NzEuOCw5OC4zM2gwbC0uMTcuMjdhMzAuMjYsMzAuMjYsMCwwLDEtMTAuMzEsOS44NCwyNy42MSwyNy42MSwwLDAsMS0xNC4xLDQuMDhjLTguMjIsMC0xNS40MS0zLjI4LTIxLjM1LTkuNzRhMzIuOSwzMi45LDAsMCwxLTguNTQtMjMuMjcsMzIuMzYsMzIuMzYsMCwwLDEsOC44Mi0yMi4wN2M1LjczLTYuMTQsMTIuNjItOS4yNSwyMC41MS05LjI1LDEwLjc4LS4wOSwxOC45Miw0LjM2LDI0Ljg3LDEzLjYybC4xOC4yN2guMTZsNy00LjM0YTM5LDM5LDAsMCwwLTExLjU5LTEyLjMxLDM2LjEyLDM2LjEyLDAsMCwwLTIwLjA4LTYuMDgsMzUuMjIsMzUuMjIsMCwwLDAtMjYuOCwxMS40MmMtNy40Nyw3LjY5LTExLjI1LDE3LjQ5LTExLjI1LDI5LjEzYTQyLjEsNDIuMSwwLDAsMCwxMS4xNCwyOS4yMWM3LjM3LDgsMTYuMjksMTIsMjYuNTQsMTJoLjM4YzEzLjQ2LS4yOCwyNC41Ni02LjgsMzEuNjMtMTguNDdaIi8+PHBvbHlnb24gY2xhc3M9ImNscy0xIiBwb2ludHM9IjUyNC4xOCA0MC4zNyA1MTQuNjYgNDAuMzcgNDc5LjI0IDExOS42MyA0OTAuNTUgMTE5LjYzIDUwMS40OSA5My4yOSA1MDEuNTEgOTMuMjkgNTA1LjM3IDg1LjA1IDUwNS4zNiA4NS4wNSA1MTkuNjEgNTEuNiA1MzMuNTggODUuMDUgNTEzLjUzIDg1LjA1IDUwOS44NyA5My4yOSA1MzYuODQgOTMuMjkgNTQ3Ljg4IDExOS42MyA1NTcuODUgMTE5LjYzIDUyNC4xOCA0MC4zNyIvPjxwYXRoIGNsYXNzPSJjbHMtMSIgZD0iTTYwOS42NSw0Ny42MmMtNS4yNi00Ljc1LTExLjg4LTcuMTUtMTkuNjctNy4xNUg1NjQuMzN2NzkuMTZoOS4zNXYtMzFoMFY4MC4yOWgwVjQ5aDE2LjcxYTE4LjU0LDE4LjU0LDAsMCwxLDEyLjE4LDQuMjMsMTMuNjQsMTMuNjQsMCwwLDEsNS41NCwxMC40OSwxMy45MiwxMy45MiwwLDAsMS01LDEyLjA3LDE3LjU0LDE3LjU0LDAsMCwxLTEyLjI1LDQuNWgtOS42OHY4LjM0aDExLjJBMjUuMDUsMjUuMDUsMCwwLDAsNjA5Ljg1LDgyYTIxLjc0LDIxLjc0LDAsMCwwLDcuNS0xNi40NkEyMi40MSwyMi40MSwwLDAsMCw2MDkuNjUsNDcuNjJaIi8+PHJlY3QgY2xhc3M9ImNscy0xIiB4PSIyNjEuNjEiIHk9IjQxLjkzIiB3aWR0aD0iOS4zNCIgaGVpZ2h0PSI5LjM0Ii8+PHJlY3QgY2xhc3M9ImNscy0xIiB4PSIyNjEuNjEiIHk9IjYyLjg2IiB3aWR0aD0iOS4zNCIgaGVpZ2h0PSI1Ni44OSIvPjxwYXRoIGNsYXNzPSJjbHMtMSIgZD0iTTQwMi4zNSwxMTQuMDZWODkuNjNhMjksMjksMCwwLDAtOS4yLTIxLjkyLDI5LjYyLDI5LjYyLDAsMCwwLTQyLjk0LjQxLDMwLjE2LDMwLjE2LDAsMCwwLTguNDgsMjEuNDEsMzAuNzQsMzAuNzQsMCwwLDAsOS4yLDIyLjIyLDI4LjU4LDI4LjU4LDAsMCwwLDIxLjk0LDguOCwyOS4xNiwyOS4xNiwwLDAsMCwyMC42NC05LjI2djMuODdtMCwwYTE3LjgxLDE3LjgxLDAsMCwxLTYuMDksMTMuNDQsMjAuMzgsMjAuMzgsMCwwLDEtMTQuMjcsNS44LDIwLjg2LDIwLjg2LDAsMCwxLTEyLjcxLTQuMjQsMTkuNDEsMTkuNDEsMCwwLDEtNi43My03LjkxbC03LjE2LDQuMTNhMjcuNTIsMjcuNTIsMCwwLDAsNy40Nyw5LDMwLjcxLDMwLjcxLDAsMCwwLDE4LjIsNi40MWMuNDQsMCwuODksMCwxLjMzLDBhMzAuNywzMC43LDAsMCwwLDE5LjU1LTYuOTVjNi4xNC00Ljg5LDkuMjUtMTEuMTYsOS4yNS0xOC42MnYtMi4yMm0tOS0yMy44NEEyMS45MywyMS45MywwLDAsMSwzODcsMTA1LjQxYTE5LjMsMTkuMywwLDAsMS0xNC42NSw2LjMsMjAuNSwyMC41LDAsMCwxLTE1LjE2LTYuMzEsMjEuMTksMjEuMTksMCwwLDEtNi41MS0xNS4yOCwyMS41MywyMS41MywwLDAsMSw1LjkyLTE1LjQ4LDIwLjQ0LDIwLjQ0LDAsMCwxLDE0LjY3LTcuMDljLjM4LDAsLjc1LDAsMS4xMywwQTE5LjE3LDE5LjE3LDAsMCwxLDM4Nyw3NCwyMS40NCwyMS40NCwwLDAsMSwzOTMuMzEsOTAuMjJaIi8+PHBhdGggY2xhc3M9ImNscy0xIiBkPSJNMjQ1LDQ3LjYyYy01LjI2LTQuNzUtMTEuODgtNy4xNS0xOS42Ny03LjE1SDE5OS42NnY3OS4xNkgyMDl2LTMxaDBWODAuMjloMFY0OWgxNi43MWExOC41NCwxOC41NCwwLDAsMSwxMi4xOCw0LjIzLDEzLjY0LDEzLjY0LDAsMCwxLDUuNTQsMTAuNDksMTMuOTIsMTMuOTIsMCwwLDEtNSwxMi4wNywxNy41NCwxNy41NCwwLDAsMS0xMi4yNSw0LjVoLTkuNjh2OC4zNGgxMS4yQTI1LDI1LDAsMCwwLDI0NS4xOCw4MmEyMS43NCwyMS43NCwwLDAsMCw3LjUtMTYuNDZBMjIuNDEsMjIuNDEsMCwwLDAsMjQ1LDQ3LjYyWiIvPjxwYXRoIGNsYXNzPSJjbHMtMSIgZD0iTTMwNy42NSw1OS4zOEEyNS4yNywyNS4yNywwLDAsMCwyODguOTIsNjdhMjYuMjQsMjYuMjQsMCwwLDAtNy40NSwxOXYzMy40NWg5Vjg1LjI2YTE2LjMzLDE2LjMzLDAsMCwxLDUuMDgtMTIuMDksMTYuNTQsMTYuNTQsMCwwLDEsMTIuMDktNS4wNywxNi4xLDE2LjEsMCwwLDEsMTEuODgsNS4wNywxNi40MiwxNi40MiwwLDAsMSw1LjE4LDEyLjA5djM0LjI2aDlWODYuMDdhMjYuMjQsMjYuMjQsMCwwLDAtNy40NS0xOUEyNS4xNSwyNS4xNSwwLDAsMCwzMDcuNjUsNTkuMzhaIi8+PHJlY3QgY2xhc3M9ImNscy0xIiB3aWR0aD0iMTYwIiBoZWlnaHQ9IjE2MCIgcng9IjE2LjY3Ii8+PHJlY3QgY2xhc3M9ImNscy0yIiB4PSIyMCIgeT0iMjAiIHdpZHRoPSIxMjAiIGhlaWdodD0iMTIwIi8+PHBhdGggY2xhc3M9ImNscy0zIiBkPSJNOTIsNDgsMzkuMjYsMzMuMTRhNS43Miw1LjcyLDAsMCwwLTUsLjkyQTUuNTYsNS41NiwwLDAsMCwzMiwzOC41NHY5NS44NGE1LjU1LDUuNTUsMCwwLDAsMi4xNyw0LjQxQTUuNyw1LjcsMCwwLDAsMzcuNjgsMTQwYTUuNSw1LjUsMCwwLDAsMS4zMy0uMTZsNTIuNzUtMTIuMzloMEE1LjYxLDUuNjEsMCwwLDAsOTYuMTMsMTIyVjUzLjM3QTUuNjYsNS42NiwwLDAsMCw5Miw0OFoiLz48cGF0aCBjbGFzcz0iY2xzLTQiIGQ9Ik0xMjcuOTIsNDQuNTdhNS42NCw1LjY0LDAsMCwwLTQuMTItNS4zOWwtNjcuMTMtMTlhNS43Miw1LjcyLDAsMCwwLTUsLjkxLDUuNTUsNS41NSwwLDAsMC0yLjI2LDQuNDlWOTguMzRhNS41NSw1LjU1LDAsMCwwLDIuMTcsNC40MUE1LjcsNS43LDAsMCwwLDU1LjA5LDEwNGE1LjU4LDUuNTgsMCwwLDAsMS4zNC0uMTZsNjcuMjEtMTZBNS42MSw1LjYxLDAsMCwwLDEyOCw4Mi4zOFoiLz48cGF0aCBjbGFzcz0iY2xzLTUiIGQ9Ik05Miw0OCw0OS40MSwzNlY5OC4zNGE1LjU1LDUuNTUsMCwwLDAsMi4xNyw0LjQxQTUuNyw1LjcsMCwwLDAsNTUuMDksMTA0YTUuNTgsNS41OCwwLDAsMCwxLjM0LS4xNmwzOS43LTkuNDJ2LTQxQTUuNjYsNS42NiwwLDAsMCw5Miw0OFoiLz48L2c+PC9nPjwvc3ZnPg==" style="width:100px" alt="PingCAP logo"/></a></span><span class="index-module--mobileNavBarEnd--wJBf2"><a class="navbar-burger index-module--burger--JHKki" href="https://github.com/pingcap" target="_blank"><i class="iconfont icon-github index-module--icon--HqAmx"/></a><a role="button" class="navbar-burger index-module--burger--JHKki" aria-label="menu" aria-expanded="false"><i class="iconfont icon-menu index-module--icon--HqAmx"/></a></span></div><div class="navbar-menu index-module--desktopMenu--FioJ8"><div class="navbar-start"><div class="navbar-item px-5 index-module--menu--N9jNb"><a>产品</a></div><div class="navbar-item px-5 index-module--menu--N9jNb"><a>解决方案</a></div><div class="navbar-item px-5 index-module--menu--N9jNb"><a>文档</a></div><div class="navbar-item px-5 index-module--menu--N9jNb"><a>客户案例</a></div><div class="navbar-item px-5 index-module--menu--N9jNb"><a>合作伙伴</a></div><div class="navbar-item px-5 index-module--menu--N9jNb"><a>服务与支持</a></div><div class="navbar-item px-5 index-module--menu--N9jNb"><a>学习与社区</a></div></div><div class="navbar-end index-module--navbarEndContent--HqBKU"><div class="index-module--navbarEndItem--rYRre index-module--searchWrapper--JvFXI"><span class="index-module--icon--HqAmx index-module--navItem--ou3c9"><i class="iconfont icon-search"/><span class="index-module--iconLabel--GRGwr">搜索</span></span><div class="index-module--searchPanel--yTlLW"/></div><div class="navbar-item index-module--navItem--ou3c9 index-module--navbarEndItem--rYRre"><div class="dropdown is-center index-module--langSelector--mPyrj"><div class="dropdown-trigger"><div aria-haspopup="true" aria-controls="lang-menu" class="index-module--trigger--8EEgs"><i class="iconfont icon-language index-module--icon--HqAmx"/><span class="index-module--iconLabel--GRGwr">语言</span></div></div><div class="dropdown-menu index-module--menu--QgjOl" id="lang-menu" role="menu"><div class="dropdown-content index-module--dropdownContent--l+MWk"><a target="_blank" rel="noopener" href="https://en.pingcap.com/" class="dropdown-item index-module--item--Q3TbR">English</a><a target="_blank" rel="noopener" href="https://pingcap.co.jp/" class="dropdown-item index-module--item--Q3TbR">日本語</a></div></div></div></div><div class="navbar-item index-module--navbarEndItem--rYRre"><a class="index-module--icon--HqAmx index-module--navItem--ou3c9" href="https://github.com/pingcap" target="_blank"><i class="iconfont icon-github"/></a></div><div class="navbar-item"><a class="button is-white index-module--useFree--DEvR+" href="/product#SelectProduct">免费试用</a></div></div></div></nav><div class="index-module--layout--pDdDW"><main><div class="blog-header-module--container--EsMbA"><div class="container px-4 blog-header-module--fixedContainer--7ndgE"><div class="blog-detail-module--wrapper--esMKp"><h1 class="blog-detail-module--h1--Q3T+9">TiDB 源码阅读系列文章（七）基于规则的优化</h1><a class="index-module--blogReturnBtn--igugB"><i class="iconfont icon-arrow-right"/><label>返回全部</label></a></div></div></div><div class="blog-detail-module--container--88yCh"><div class="container px-4 "><div class="blog-detail-module--row--BOEUq"><span>毛康力</span><span><a href="/blog/categories/产品技术解读">产品技术解读</a></span><span>2018-04-10</span></div><div class="columns"><div class="column is-8 px-4"><div class="index-module--markdown--RI+u5"><p>在 TiDB 里面，SQL 优化的过程可以分为逻辑优化和物理优化两个部分。逻辑优化主要是基于规则的优化，简称 RBO（rule based optimization）。物理优化会为逻辑查询计划中的算子选择某个具体的实现，需要用到一些统计信息，决定哪一种方式代价最低，所以是基于代价的优化 CBO（cost based optimization）。</p> <p>本篇将主要关注逻辑优化。先介绍 TiDB 中的逻辑算子，然后介绍 TiDB 的逻辑优化规则，包括列裁剪、最大最小消除、投影消除、谓词下推等等。</p> <h2 id="逻辑算子介绍">逻辑算子介绍</h2><p>在写具体的优化规则之前，先简单介绍查询计划里面的一些逻辑算子。</p> <li><p>DataSource 这个就是数据源，也就是表，<code>select * from t</code> 里面的 t。</p> <li><p>Selection 选择，例如 <code>select xxx from t where xx = 5</code> 里面的 where 过滤条件。</p> <li><p>Projection 投影， <code>select c from t</code> 里面的取 c 列是投影操作。</p> <li><p>Join 连接， <code>select xx from t1, t2 where t1.c = t2.c</code> 就是把 t1 t2 两个表做 Join。</p> <p>选择，投影，连接（简称 SPJ）是最基本的算子。其中 Join 有内连接，左外右外连接等多种连接方式。</p> <pre><code class="language-sql"><span class="hljs-keyword">select</span> b <span class="hljs-keyword">from</span> t1, t2 <span class="hljs-keyword">where</span> t1.c <span class="hljs-operator">=</span> t2.c <span class="hljs-keyword">and</span> t1.a <span class="hljs-operator">&gt;</span> <span class="hljs-number">5</span> <p>变成逻辑查询计划之后，t1 t2 对应的 DataSource，负责将数据捞上来。上面接个 Join 算子，将两个表的结果按 <code>t1.c = t2.c</code>连接，再按 <code>t1.a &gt; 5</code> 做一个 Selection 过滤，最后将 b 列投影。下图是未经优化的表示：</p> <li><p>Sort 就是 <code>select xx from xx order by</code> 里面的 <code>order by</code>。</p> <li><p>Aggregation，在 <code>select sum(xx) from xx group by yy</code> 中的 <code>group by</code> 操作，按某些列分组。分组之后，可能带一些聚合函数，比如 Max/Min/Sum/Count/Average 等，这个例子里面是一个 sum。</p> <li><p>Apply 这个是用来做子查询的。</p> <h2 id="列裁剪">列裁剪</h2><p>列裁剪的思想是这样的：对于用不上的列，没有必要读取它们的数据，无谓的浪费 IO 资源。比如说表 t 里面有 a b c d 四列。</p> <pre><code class="language-sql"><span class="hljs-keyword">select</span> a <span class="hljs-keyword">from</span> t <span class="hljs-keyword">where</span> b <span class="hljs-operator">&gt;</span> <span class="hljs-number">5</span> <p>这个查询里面明显只有 a b 两列被用到了，所以 c d 的数据是不需要读取的。在查询计划里面，Selection 算子用到 b 列，下面接一个 DataSource 用到了 a b 两列，剩下 c 和 d 都可以裁剪掉，DataSource 读数据时不需要将它们读进来。</p> <p>列裁剪的算法实现是自顶向下地把算子过一遍。某个节点需要用到的列，等于它自己需要用到的列，加上它的父节点需要用到的列。可以发现，由上往下的节点，需要用到的列将越来越多。代码是在 <code>plan/column_pruning.go</code> 文件里面。</p> <p>列裁剪主要影响的算子是 Projection，DataSource，Aggregation，因为它们跟列直接相关。Projection 里面会裁掉用不上的列，DataSource 里面也会裁剪掉不需要使用的列。 </p> <p>Aggregation 算子会涉及哪些列？<code>group by</code> 用到的列，以及聚合函数里面引用到的列。比如 <code>select avg(a), sum(b) from t group by c d</code>，这里面 <code>group by</code> 用到的 c 和 d 列，聚合函数用到的 a 和 b 列。所以这个 Aggregation 使用到的就是 a b c d 四列。</p> <p>Selection 做列裁剪时，要看它父节点要哪些列，然后它自己的条件里面要用到哪些列。Sort 就看 <code>order by</code> 里面用到了哪些列。Join 则要把连接条件中用到的各种列都算进去。具体的代码里面，各个算子都是实现 PruneColumns 接口：</p> <pre><code class="language-go"><span class="hljs-function"><span class="hljs-keyword">func</span> <span class="hljs-params">(p *LogicalPlan)</span> <span class="hljs-title">PruneColumns</span><span class="hljs-params">(parentUsedCols []*expression.Column)</span></span> <p>通过列裁剪这一步操作之后，查询计划里面各个算子，只会记录下它实际需要用到的那些列。</p> <h2 id="最大最小消除">最大最小消除</h2><p>最大最小消除，会对 Min/Max 语句进行改写。</p> <pre><code class="language-sql"><span class="hljs-keyword">select</span> <span class="hljs-built_in">min</span>(id) <span class="hljs-keyword">from</span> t <p>我们用另一种写法，可以做到类似的效果：</p> <pre><code class="language-sql"><span class="hljs-keyword">select</span> id <span class="hljs-keyword">from</span> t <span class="hljs-keyword">order</span> <span class="hljs-keyword">by</span> id <span class="hljs-keyword">asc</span> limit <span class="hljs-number">1</span> <p>这个写法有什么好处呢？前一个语句，生成的执行计划，是一个 TableScan 上面接一个 Aggregation，也就是说这是一个全表扫描的操作。后一个语句，生成执行计划是 TableScan + Sort + Limit。</p> <p>在某些情况，比如 id 是主键或者是存在索引，数据本身有序， Sort 就可以消除，最终变成 TableScan 或者 IndexLookUp 接一个 Limit，这样子就不需要全表扫了，只需要读到第一条数据就得到结果！全表扫操作跟只查一条数据，性能上可是天壤之别。</p> <p>最大最小消除，做的事情就是由 SQL 优化器“自动”地做这个变换。</p> <pre><code class="language-sql"><span class="hljs-keyword">select</span> <span class="hljs-built_in">max</span>(id) <span class="hljs-keyword">from</span> t <p>生成的查询树会被转换成下面这种：</p> <pre><code class="language-sql"><span class="hljs-keyword">select</span> <span class="hljs-built_in">max</span>(id) <span class="hljs-keyword">from</span> (<span class="hljs-keyword">select</span> id <span class="hljs-keyword">from</span> t <span class="hljs-keyword">where</span> id <span class="hljs-keyword">is</span> <span class="hljs-keyword">not</span> <span class="hljs-keyword">null</span> <span class="hljs-keyword">order</span> <span class="hljs-keyword">by</span> id <span class="hljs-keyword">desc</span> limit <span class="hljs-number">1</span>) t <p>这个变换复杂一些是要处理 NULL 的情况。经过这步变换之后，还会执行其它变换。所以中间生成的额外的算子，可能在其它变换里面被继续修改掉。</p> <p>min 也是类似的语句替换。相应的代码是在 <code>max_min_eliminate.go</code> 文件里面。实现是一个纯粹的 AST 结构的修改。</p> <h2 id="投影消除">投影消除</h2><p>投影消除可以把不必要的 Projection 算子消除掉。那么，什么情况下，投影算子是可消除的呢？</p> <p>首先，如果 Projection 算子要投影的列，跟它的子节点的输出列，是一模一样的，那么投影步骤就是一个无用操作，可以消除。比如 <code>select a,b from t</code> 在表 t 里面就正好就是 a b 两列，那就没必要 TableScan 上面再做一次 Projection。</p> <p>然后，投影算子下面的子节点，又是另一个投影算子，那么子节点的投影操作就没有意义，可以消除。比如 <code>Projection(A) -&gt; Projection(A,B,C)</code> 只需要保留 <code>Projection(A)</code> 就够了。</p> <p>类似的，在投影消除规则里面，Aggregation 跟 Projection 操作很类似。因为从 Aggregation 节点出来的都是具体的列，所以 <code>Aggregation(A) -&gt; Projection(A,B,C)</code> 中，这个 Projection 也可以消除。</p> <p>代码是在 <code>eliminate_projection.go</code> 里面。</p> <pre><code class="language-go"><span class="hljs-function"><span class="hljs-keyword">func</span> <span class="hljs-title">eliminate</span><span class="hljs-params">(p Plan, canEliminate <span class="hljs-keyword">bool</span>)</span></span> { 对 p 的每个子节点，递归地调用 eliminate 如果 p 是 Project 如果 canEliminate 为真消除 p 如果 p 的子节点的输出列，跟 p 的输出列相同，消除 p <p>注意 <code>canEliminate</code> 参数，它是代表是否处于一个可被消除的“上下文”里面。比如 <code>Projection(A) -&gt; Projection(A, B, C)</code> 或者 <code>Aggregation -&gt; Projection</code> 递归调用到子节点 Projection 时，该 Projection 就处于一个 <code>canEliminate</code> 的上下文。</p> <p>简单解释就是，一个 Projection 节点是否可消除：</p> <li>一方面由它父节点告诉它，它是否是一个冗余的 Projection 操作。</li> <li>另一方面由它自己和子节点的输入列做比较，输出相同则可消除。</li> <h2 id="谓词下推">谓词下推</h2><p>谓词下推是非常重要的一个优化。比如</p> <pre><code class="language-sql"><span class="hljs-keyword">select</span> <span class="hljs-operator">*</span> <span class="hljs-keyword">from</span> t1, t2 <span class="hljs-keyword">where</span> t1.a <span class="hljs-operator">&gt;</span> <span class="hljs-number">3</span> <span class="hljs-keyword">and</span> t2.b <span class="hljs-operator">&gt;</span> <span class="hljs-number">5</span> <p>假设 t1 和 t2 都是 100 条数据。如果把 t1 和 t2 两个表做笛卡尔积了再过滤，我们要处理 10000 条数据，而如果能先做过滤条件，那么数据量就会大量减少。谓词下推会尽量把过滤条件，推到靠近叶子节点，从而减少数据访问，节省计算开销。这就是谓词下推的作用。</p> <p>谓词下推的接口函数类似是这样子的：</p> <pre><code class="language-go"><span class="hljs-function"><span class="hljs-keyword">func</span> <span class="hljs-params">(p *baseLogicalPlan)</span> <span class="hljs-title">PredicatePushDown</span><span class="hljs-params">(predicates []expression.Expression)</span> <span class="hljs-params">([]expression.Expression, LogicalPlan)</span></span> <p>PredicatePushDown 函数处理当前的查询计划 p，参数 predicates 表示要添加的过滤条件。函数返回值是无法下推的条件，以及生成的新 plan。</p> <p>这个函数会把能推的条件尽量往下推，推不下去的条件，做到一个 Selection 算子里面，然后连接在节点 p 上面，形成新的 plan。比如说现在有条件 <code>a &gt; 3 AND b = 5 AND c &lt; d</code>，其中 a &gt; 3 和 b = 5 都推下去了，那剩下就接一个 c &lt; d 的 Selection。</p> <p>我们看一下 Join 算子是如何做谓词下推的。代码是在 <code>plan/predicate_push_down.go</code> 文件。</p> <p>首先会做一个简化，将左外连接和右外连接转化为内连接。</p> <p>什么情况下外连接可以转内连接？左向外连接的结果集包括左表的所有行，而不仅仅是连接列所匹配的行。如果左表的某行在右表中没有匹配的行，则在结果集右边补 NULL。做谓词下推时，如果我们知道接下来的的谓词条件一定会把包含 NULL 的行全部都过滤掉，那么做外连接就没意义了，可以直接改写成内连接。</p> <p>什么情况会过滤掉 NULL 呢？比如，某个谓词的表达式用 NULL 计算后会得到 false 或者 NULL；或者多个谓词用 AND 条件连接，其中一个会过滤 NULL；又或者用 OR 条件连接，其中每个都是过滤 NULL 的。术语里面 OR 条件连接叫做析取范式 DNF (disjunctive normal form)。对应的还有合取范式 CNF (conjunctive normal form)。TiDB 的代码里面用到这种缩写。</p> <p>能转成 inner join 的例子:</p> <pre><code class="language-sql"> <span class="hljs-keyword">select</span> <span class="hljs-operator">*</span> <span class="hljs-keyword">from</span> t1 <span class="hljs-keyword">left</span> <span class="hljs-keyword">outer</span> <span class="hljs-keyword">join</span> t2 <span class="hljs-keyword">on</span> t1.id <span class="hljs-operator">=</span> t2.id <span class="hljs-keyword">where</span> t2.id <span class="hljs-keyword">is</span> <span class="hljs-keyword">not</span> <span class="hljs-keyword">null</span>; <span class="hljs-keyword">select</span> <span class="hljs-operator">*</span> <span class="hljs-keyword">from</span> t1 <span class="hljs-keyword">left</span> <span class="hljs-keyword">outer</span> <span class="hljs-keyword">join</span> t2 <span class="hljs-keyword">on</span> t1.id <span class="hljs-operator">=</span> t2.id <span class="hljs-keyword">where</span> t2.value <span class="hljs-operator">&gt;</span> <span class="hljs-number">3</span>; <span class="hljs-keyword">select</span> <span class="hljs-operator">*</span> <span class="hljs-keyword">from</span> t1 <span class="hljs-keyword">left</span> <span class="hljs-keyword">outer</span> <span class="hljs-keyword">join</span> t2 <span class="hljs-keyword">on</span> t1.id <span class="hljs-operator">=</span> t2.id <span class="hljs-keyword">where</span> t2.id <span class="hljs-keyword">is</span> <span class="hljs-keyword">null</span> <span class="hljs-keyword">and</span> t2.value <span class="hljs-operator">&gt;</span> <span class="hljs-number">3</span>; <p>不能转成 inner join 的例子:</p> <pre><code class="language-sql"> <span class="hljs-keyword">select</span> <span class="hljs-operator">*</span> <span class="hljs-keyword">from</span> t1 <span class="hljs-keyword">left</span> <span class="hljs-keyword">outer</span> <span class="hljs-keyword">join</span> t2 <span class="hljs-keyword">on</span> t1.id <span class="hljs-operator">=</span> t2.id <span class="hljs-keyword">where</span> t2.id <span class="hljs-keyword">is</span> <span class="hljs-keyword">null</span> <span class="hljs-keyword">or</span> t2.value <span class="hljs-operator">&gt;</span> <span class="hljs-number">3</span>; <p>接下来，把所有条件全收集起来，然后区分哪些是 Join 的等值条件，哪些是 Join 需要用到的条件，哪些全部来自于左子节点，哪些全部来自于右子节点。</p> <p>区分之后，对于内连接，可以把左条件，和右条件，分别向左右子节点下推。等值条件和其它条件保留在当前的 Join 算子中，剩下的返回。</p> <p>谓词下推不能推过 MaxOneRow 和 Limit 节点。因为先 Limit N 行，然后再做 Selection 操作，跟先做 Selection 操作，再 Limit N 行得到的结果是不一样的。比如数据是 1 到 100，先 Limit 10 再 Select 大于 5，得到的是 5 到 10，而先做 Selection 再做 Limit 得到的是 5 到 15。MaxOneRow 也是同理，跟 Limit 1 效果一样。</p> <p>DataSource 算子很简单，会直接把过滤条件加入到 CopTask 里面。最后会通过 coprocessor 推给 TiKV 去做。</p> <h2 id="构建节点属性">构建节点属性</h2><p>在 <code>build_key_info.go</code> 文件里面，会构建 unique key 和 MaxOneRow 属性。这一步不是在做优化，但它是在构建优化过程需要用到的一些信息。</p> <p><code>build_key_info</code> 是在收集关于唯一索引的信息。我们知道某些列是主键或者唯一索引列，这种情况该列不会存在多个相同的值。只有叶子节点记录这个信息。<code>build_key_info</code> 就是要将这个信息，从叶子节点，传递到 LogicalPlan 树上的所有节点，让每个节点都知道这些属性。对于 DataSource，对于主键列，和唯一索引列，都是 unique key。注意处理 NULL，需要列是带有 NotNull 标记的。对于 Projection，它的子节点中的唯一索引列信息，跟它的投影表达式的列取交集。比如 a b c 列都是唯一索引，投影其中的 b 列，输出的 b 列仍然具有值唯一的属性。</p> <p>如果一个节点输出肯定只有一行，这个节点会设置一个 MaxOneRow 属性。哪些情况节点输出只有一行呢？</p> <li><p>如果一个算子的子节点是 MaxOneRow 算子。</p> <li><p>如果是 Limit 1，可以设置 MaxOneRow。</p> <li><p>如果是 Selection，并且过滤条件是一个唯一索引列等于某常量。</p> <li><p>Join 算子，如果它的左右子节点都是 MaxOneRow 属性。</p> <h2 id="总结">总结</h2><p>这是基于规则优化（RBO）的上篇。介绍了逻辑查询计划里面基本的算子，以及一部分的优化规则。后续我们还将介绍更多的优化规则，以及基于代价的优化（CBO）。</p>