执行计划的最佳索引，永远不会错过
#sql #database #yugabytedb #optimizer

使用完美的查询计划器（又称优化器），您可以提供尽可能多的索引，所有加入方法，并且可以找出最佳执行计划。这篇博客文章与加入和过滤器的查询相反，是否有一组索引，即使优化器的估计是错误的，执行计划也可以接受可以接受？

最佳计划是什么？查询计划者或优化器具有一个目标：评估所有可能的执行计划的成本，并选择具有最便宜的估计成本的。如果计划（来自选择性和Ressource访问时间的估计）很容易，这将有效。但是SQL查询是复杂的，并且具有变量值执行，选择性可以通过几个数量级来差异。执行对几行最佳的JOIN算法可能会造成灾难性的灾难性。由于数据的增长并添加了新的用例，因此这将发生一天并阻止应用程序。

优化器总是试图找到完美的计划，但是这不是用户想要的。完美是善良的敌人。用户不是赌徒期望的计划，如果所有的神与他们在一起，都会迅速执行。他们只想在验证软件时永远保持自己接受的性能。

用户想要的是重要的：

  1. 一致的性能：响应时间应与已测试和接受的响应时间在同一球场上
  2. 可以理解的性能：时间与用户对查询复杂性的感知成正比
  3. 更快的响应时间，但这取决于另外两个。没有两个先前的可预测性能，就不可能设定任何调整目标

未能提供上述属性是NOSQL的原因之一。如果没有一个缓存，没有一个访问路径，没有连接，就没有等待一致性，则性能变得更加可预测。但是，如果要删除优化器的选择，也可以在SQL数据库中使用计划器参数和优化器提示。

这是一个很小的例子，可以更好地了解联接方法（嵌套循环，哈希加入，合并加入）效率时，它们不是最佳计划。

两个表

i在yugabytedb上创建以下表格（postgresql兼容）：

create table a ( id int, filter int );
create table b ( id int, filter int );
insert into  a select n, sign(mod(n,1e5))
 from generate_series(1,1e6) n;
insert into  b select n, sign(mod(n,1e5))
 from generate_series(1,1e6) n;

我的目标是使用filter列在每个表上过滤，然后在id上加入。我已经构建了filter值以测试不同的选择性：

  • where filter=0返回10行
  • where filter=1返回999990行

这将使我能够测试每种连接方法的极端情况。

两个索引

我不想给优化器给更多选择，我创建了唯一适合所有加入方法的索引：

create index a_filter_id on a ( filter, id asc);
create index b_filter_id on b ( filter, id asc);

这些索引可以有效：

  • 过滤（filter = ?），因为索引从过滤列开始。然后，索引扫描可以直接寻求感兴趣的数据范围。这对于必须扫描两组行的哈希连接或合并连接非常完美。
  • 以相同的顺序检索连接列（id）的行，因为一旦在索引范围内过滤它们，就将输出在此列上排序。这将为合并加入的其他分类节省。
  • 覆盖所有列，尤其是连接列（id）无需访问表即可允许索引扫描。

我可以通过为每张表运行一个explain及其列表的谓词来检查所有这些，我将用于加入：

yugabyte=# explain select id, filter from a where filter=0 order by id;

                                 QUERY PLAN
-----------------------------------------------------------------------------
 Index Only Scan using a_filter_id on a  (cost=0.00..15.25 rows=100 width=8)
   Index Cond: (filter = 0)
(2 rows)

这是我可以做的最快的，以最大程度地减少我必须阅读的行。即使在某种情况下，在选择性较低的情况下，SEQ扫描可能会更快，我也会强制使用提示（IndexOnlyScan(a) IndexOnlyScan(b)）使用索引，因为我的目标是验证具有不同选择性的一个执行计划的性能。这是许多应用程序想要可预测的执行计划时所做的事情：用提示，基于规则的优化器强制索引，或者强迫索引访问的成本非常低（您可以查看SAP推荐的Oracle的配置，禁用索引，基于规则的优化器之后出现的所有优化器功能）。

我想在温暖的缓存上进行比较，但在这里只显示一个问题，我会多次运行查询。如果需要，可以复制它。

我没有分析表，也没有启用yb_enable_optimizer_statistics，因为我的目标是强制计划并查看执行时间。

内部和外部桌子

我从两侧的最高选择性开始：filter=0返回3行。

explain (costs off, analyze, summary off)
/*+ Leading((a b)) IndexOnlyScan(a) IndexOnlyScan(b) */
select id, filter from a join b using (id)
 where a.filter=0 and b.filter=0;

                                          QUERY PLAN
-----------------------------------------------------------------------------------------------
 Merge Join (actual time=1.137..1.153 rows=10 loops=1)
   Merge Cond: (a.id = b.id)
   ->  Index Only Scan using a_filter_id on a (actual time=0.733..0.738 rows=10 loops=1)
         Index Cond: (filter = 0)
         Heap Fetches: 0
   ->  Materialize (actual time=0.400..0.406 rows=10 loops=1)
         ->  Index Only Scan using b_filter_id on b (actual time=0.392..0.397 rows=10 loops=1)
               Index Cond: (filter = 0)
               Heap Fetches: 0
(9 rows)

多次运行它，合并加入需要1到2毫秒。这是一个很好的单位数字，可以返回几行。让我们看看如果选择其他执行计划会发生什么。我禁用合并加入：

explain (costs off, analyze, summary off)
/*+ Set(enable_mergejoin off) Leading((a b)) IndexOnlyScan(a) IndexOnlyScan(b) */
select id, filter from a join b using (id)
 where a.filter=0 and b.filter=0;

                                          QUERY PLAN
-----------------------------------------------------------------------------------------------
 Hash Join (actual time=1.046..1.053 rows=10 loops=1)
   Hash Cond: (a.id = b.id)
   ->  Index Only Scan using a_filter_id on a (actual time=0.558..0.563 rows=10 loops=1)
         Index Cond: (filter = 0)
         Heap Fetches: 0
   ->  Hash (actual time=0.468..0.468 rows=10 loops=1)
         Buckets: 1024  Batches: 1  Memory Usage: 9kB
         ->  Index Only Scan using b_filter_id on b (actual time=0.454..0.459 rows=10 loops=1)
               Index Cond: (filter = 0)
               Heap Fetches: 0
(10 rows)

随着哈希的加入，时间相似。即使已经针对较大的系列发明了这些联接方法，只要有3行即可进行哈希或实现，只要扫描时进行高选择性过滤，它们仍然对小型行列有好处。

让我们也禁用合并加入，看看嵌套循环发生了什么：

explain (costs off, analyze, summary off)
/*+ Set(enable_hashjoin off) Set(enable_mergejoin off) Leading((a b)) IndexOnlyScan(a) IndexOnlyScan(b) */
select id, filter from a join b using (id)
 where a.filter=0 and b.filter=0;

                                       QUERY PLAN
-----------------------------------------------------------------------------------------
 Nested Loop (actual time=1.189..4.098 rows=10 loops=1)
   ->  Index Only Scan using a_filter_id on a (actual time=0.675..0.684 rows=10 loops=1)
         Index Cond: (filter = 0)
         Heap Fetches: 0
   ->  Index Only Scan using b_filter_id on b (actual time=0.329..0.330 rows=1 loops=10)
         Index Cond: ((filter = 0) AND (id = a.id))
         Heap Fetches: 0
(7 rows)

执行时间为4毫秒。这仍然可以接受。特别是考虑到性能与行数成正比。您可以看到第一行连接成一毫秒。

从外表连接到几行从内表连接到几行时，任何联接方法都可以接受可接受的性能，并且对哈希或合并略有偏好。我对“最好的人”的资格不会在1毫米与4ms中，而是在红衣主教变化时仍然可以接受的资格。

较大的内表

让我们看看不同的选择性会发生什么。我更改内表上的过滤器：返回999990行的b.filter=1。

explain (costs off, analyze, summary off)
/*+ Leading((a b)) IndexOnlyScan(a) IndexOnlyScan(b) */
select id, filter from a join b using (id)
 where a.filter=0 and b.filter=1;

                                              QUERY PLAN
------------------------------------------------------------------------------------------------------
 Merge Join (actual time=3965.831..3965.831 rows=0 loops=1)
   Merge Cond: (a.id = b.id)
   ->  Index Only Scan using a_filter_id on a (actual time=0.538..0.561 rows=10 loops=1)
         Index Cond: (filter = 0)
         Heap Fetches: 0
   ->  Materialize (actual time=4.141..3857.054 rows=999990 loops=1)
         ->  Index Only Scan using b_filter_id on b (actual time=4.133..3676.393 rows=999990 loops=1)
               Index Cond: (filter = 1)
               Heap Fetches: 0

这需要4秒钟，因为从此内表中读取了将近100万行。当知道这一点时，这是可以接受的。但是连接很小的结果（即使在那里也是一个空的结果），用户将不了解这个漫长的响应时间。

通过禁用合并加入来检查另一个执行计划：

explain (costs off, analyze, summary off)
/*+ Set(enable_mergejoin off) Leading((a b)) IndexOnlyScan(a) IndexOnlyScan(b) */
select id, filter from a join b using (id)
 where a.filter=0 and b.filter=1;

                                              QUERY PLAN
------------------------------------------------------------------------------------------------------
 Hash Join (actual time=4059.080..4059.080 rows=0 loops=1)
   Hash Cond: (a.id = b.id)
   ->  Index Only Scan using a_filter_id on a (actual time=0.665..0.677 rows=10 loops=1)
         Index Cond: (filter = 0)
         Heap Fetches: 0
   ->  Hash (actual time=3966.577..3966.577 rows=999990 loops=1)
         Buckets: 131072 (originally 1024)  Batches: 16 (originally 1)  Memory Usage: 3471kB
         ->  Index Only Scan using b_filter_id on b (actual time=4.050..3725.402 rows=999990 loops=1)
               Index Cond: (filter = 1)
               Heap Fetches: 0
(10 rows)

哈希连接需要同一时间。我禁用它并得到一个嵌套的循环：

explain (costs off, analyze, summary off)
/*+ Set(enable_mergejoin off) Set(enable_hashjoin off) Leading((a b)) IndexOnlyScan(a) IndexOnlyScan(b) */
select id, filter from a join b using (id)
 where a.filter=0 and b.filter=1;

                                       QUERY PLAN
-----------------------------------------------------------------------------------------
 Nested Loop (actual time=5.743..5.743 rows=0 loops=1)
   ->  Index Only Scan using a_filter_id on a (actual time=0.722..0.748 rows=10 loops=1)
         Index Cond: (filter = 0)
         Heap Fetches: 0
   ->  Index Only Scan using b_filter_id on b (actual time=0.489..0.489 rows=0 loops=10)
         Index Cond: ((filter = 1) AND (id = a.id))
         Heap Fetches: 0
(7 rows)

这个快速：5毫秒。该计划更好，并且可能更接近用户对小结果的期望。这是嵌套环的优点：扫描内表（Index Cond: ((filter = 1) AND (id = a.id))）时可以应用联接条件，而其他方法不是这种情况。

对于每种情况，我知道最好的计划是什么。但是接受查询计划者估计的不正确，您将在以下内容之间选择什么？

  • 合并加入的基数低2毫秒，但可以达到4秒
  • 嵌套环在所有情况下都需要4毫秒

优化器通常会选择第一个，因为估计成本最低。数据库供应商还将更喜欢第一个供应商，并发布避免误容的基准。应用程序用户会更喜欢第二个数字毫秒。可预测的性能是目标。

我们应该总是强迫嵌套环吗？让我们看看当不正确的外表中会发生什么。

较大的外表

a.filter=1的外排更大，但带有a.filter=0的内表几行。我对领先的提示Leading((a b))强迫的加入方向（a to b）并不是这里最好的，但请记住，我的目标是测试不良估计的情况，然后使用不良的执行计划来测试。

explain (costs off, analyze, summary off)
/*+ Leading((a b)) IndexOnlyScan(a) IndexOnlyScan(b) */
select id, filter from a join b using (id)
 where a.filter=1 and b.filter=0;

                                           QUERY PLAN
------------------------------------------------------------------------------------------------
 Merge Join (actual time=3994.370..3994.370 rows=0 loops=1)
   Merge Cond: (a.id = b.id)
   ->  Index Only Scan using a_filter_id on a (actual time=4.460..3893.289 rows=999990 loops=1)
         Index Cond: (filter = 1)
         Heap Fetches: 0
   ->  Materialize (actual time=0.572..0.605 rows=10 loops=1)
         ->  Index Only Scan using b_filter_id on b (actual time=0.561..0.585 rows=10 loops=1)
               Index Cond: (filter = 0)
               Heap Fetches: 0
(9 rows)

这需要4秒钟，是时候为外表读取近一百万行。加入本身仅添加100毫秒。

哈希连接几乎相同：

explain (costs off, analyze, summary off)
/*+ Set(enable_mergejoin off) Leading((a b)) IndexOnlyScan(a) IndexOnlyScan(b) */
select id, filter from a join b using (id)
  where a.filter=1 and b.filter=0;

                                           QUERY PLAN
------------------------------------------------------------------------------------------------
 Hash Join (actual time=3977.997..3977.998 rows=0 loops=1)
   Hash Cond: (a.id = b.id)
   ->  Index Only Scan using a_filter_id on a (actual time=4.234..3865.260 rows=999990 loops=1)
         Index Cond: (filter = 1)
         Heap Fetches: 0
   ->  Hash (actual time=2.518..2.518 rows=10 loops=1)
         Buckets: 1024  Batches: 1  Memory Usage: 9kB
         ->  Index Only Scan using b_filter_id on b (actual time=2.487..2.497 rows=10 loops=1)
               Index Cond: (filter = 0)
               Heap Fetches: 0
(10 rows)

如果选择了嵌套环，因为它是以前情况的首选方法，这意味着999990循环：

explain (costs off, analyze, summary off)
/*+ Set(enable_mergejoin off) Set(enable_hashjoin off) Leading((a b)) IndexOnlyScan(a) IndexOnlyScan(b) */
select id, filter from a join b using (id)
  where a.filter=1 and b.filter=0;

                                           QUERY PLAN
------------------------------------------------------------------------------------------------
 Nested Loop (actual time=264337.144..264337.144 rows=0 loops=1)
   ->  Index Only Scan using a_filter_id on a (actual time=4.381..2290.456 rows=999990 loops=1)
         Index Cond: (filter = 1)
         Heap Fetches: 0
   ->  Index Only Scan using b_filter_id on b (actual time=0.252..0.252 rows=0 loops=999990)
         Index Cond: ((filter = 0) AND (id = a.id))
         Heap Fetches: 0
(7 rows)

这是嵌套循环可能会变得非常糟糕的地方，这里5分钟。这并不奇怪，因为有99990循环，在分布式数据库中，这意味着远程调用。

这是基数误会可能非常糟糕的地方。我们需要让优化器找到正确的加入方法，并希望它不会失败。一些数据库使用自适应加入，因此，在执行时，当检测到这可以切换到哈希。

。

yugabytedb具有另一种积极主动的解决方案，可以降低嵌套不良环的后果：在一批行上运行外环，而不是一个一个。可以用高于1的id来定义：

set yb_bnl_batch_size=10;
explain (costs off, analyze, summary off)
/*+ Set(enable_mergejoin off) Set(enable_hashjoin off) Leading((a b)) IndexOnlyScan(a) IndexOnlyScan(b) */
select id, filter from a join b using (id)
  where a.filter=1 and b.filter=0;

                                             QUERY PLAN
-----------------------------------------------------------------------------------------------------
 YB Batched Nested Loop Join (actual time=32608.808..32608.808 rows=0 loops=1)
   Join Filter: (a.id = b.id)
   ->  Index Only Scan using a_filter_id on a (actual time=4.305..659.195 rows=999990 loops=1)
         Index Cond: (filter = 1)
         Heap Fetches: 0
   ->  Index Only Scan using b_filter_id on b (actual time=0.301..0.301 rows=0 loops=99999)
         Index Cond: ((filter = 0) AND (id = ANY (ARRAY[a.id, $1, $2, $3, $4, $5, $6, $7, $8, $9])))
         Heap Fetches: 0
(8 rows)

您可以理解Index Cond中的实现详细信息：传递一个值数组以进行过滤。在带有B树的传统数据库中，这通常会阻止该索引的使用情况，因为我们没有单个范围可以从中读取索引。在Yugabytedb中，所有表和索引存储在LSM-Tree中，这是通过寻找排序结构来优化的。

批次每循环10行，5分钟减少到32秒。批量较大，这甚至更好：

set yb_bnl_batch_size=100;
explain (costs off, analyze, summary off)
/*+ Set(enable_mergejoin off) Set(enable_hashjoin off) Leading((a b)) IndexOnlyScan(a) IndexOnlyScan(b) */
select id, filter from a join b using (id)
  where a.filter=1 and b.filter=0;

                          QUERY PLAN


--------------------------------------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------------------------------------
---------------------------------------------------------------
 YB Batched Nested Loop Join (actual time=7038.942..7038.942 rows=0 loops=1)
   Join Filter: (a.id = b.id)
   ->  Index Only Scan using a_filter_id on a (actual time=4.186..475.601 rows=999990 loops=1)
         Index Cond: (filter = 1)
         Heap Fetches: 0
   ->  Index Only Scan using b_filter_id on b (actual time=0.578..0.578 rows=0 loops=10000)
         Index Cond: ((filter = 0) AND (id = ANY (ARRAY[a.id, $1, $2, $3, $4, $5, $6, $7, $8, $9, $10, $11, $12, $13, $14,
 $15, $16, $17, $18, $19, $20, $21, $22, $23, $24, $25, $26, $27, $28, $29, $30, $31, $32, $33, $34, $35, $36, $37, $38, $
39, $40, $41, $42, $43, $44, $45, $46, $47, $48, $49, $50, $51, $52, $53, $54, $55, $56, $57, $58, $59, $60, $61, $62, $63
, $64, $65, $66, $67, $68, $69, $70, $71, $72, $73, $74, $75, $76, $77, $78, $79, $80, $81, $82, $83, $84, $85, $86, $87,
$88, $89, $90, $91, $92, $93, $94, $95, $96, $97, $98, $99])))
         Heap Fetches: 0
(8 rows)

有100行的批次，我只有10000行的循环，来自外表中的百万行，这需要7秒。

现在，由于批处理的嵌套循环，我有一种加入方法，即使并非总是最好的方法，也可以接受所有情况。请注意，我在这里测试了一个极端情况，当另一个行只有10行时，优化器将选择以100万行表启动其连接。

较大的外部和内部

让我们尝试最坏的情况，两侧的选择性都低，以使联接方向无关紧要。

explain (costs off, analyze, summary off)
/*+ Leading((a b)) IndexOnlyScan(a) IndexOnlyScan(b) */
select id, filter from a join b using (id)
 where a.filter=1 and b.filter=1;

                                              QUERY PLAN
------------------------------------------------------------------------------------------------------
 Merge Join (actual time=8.494..4758.582 rows=999990 loops=1)
   Merge Cond: (a.id = b.id)
   ->  Index Only Scan using a_filter_id on a (actual time=4.226..1521.561 rows=999990 loops=1)
         Index Cond: (filter = 1)
         Heap Fetches: 0
   ->  Materialize (actual time=4.263..2715.448 rows=999990 loops=1)
         ->  Index Only Scan using b_filter_id on b (actual time=4.252..2493.512 rows=999990 loops=1)
               Index Cond: (filter = 1)
               Heap Fetches: 0

合并加入，这再次需要5秒。请注意，如果没有我的索引在过滤器上排序，然后在联接列上排序，则需要其他分类。我正在使用最佳索引来运行此操作。您可以看到时间与结果集成正比，第一行加入了8毫秒。

如果无法合并加入：

explain (costs off, analyze, summary off)
/*+ Set(enable_mergejoin off) Leading((a b)) IndexOnlyScan(a) IndexOnlyScan(b) */
select id, filter from a join b using (id)
 where a.filter=1 and b.filter=1;

                                              QUERY PLAN
------------------------------------------------------------------------------------------------------
 Hash Join (actual time=3995.393..8273.822 rows=999990 loops=1)
   Hash Cond: (a.id = b.id)
   ->  Index Only Scan using a_filter_id on a (actual time=4.274..3693.205 rows=999990 loops=1)
         Index Cond: (filter = 1)
         Heap Fetches: 0
   ->  Hash (actual time=3990.359..3990.360 rows=999990 loops=1)
         Buckets: 131072 (originally 1024)  Batches: 16 (originally 1)  Memory Usage: 3471kB
         ->  Index Only Scan using b_filter_id on b (actual time=4.282..3733.138 rows=999990 loops=1)
               Index Cond: (filter = 1)
               Heap Fetches: 0
(10 rows)

哈希连接需要更长的时间，因为它必须哈希一个大行列，需要8秒钟。除此之外，在整个内表被哈希之前无法连接第一行。

现在强迫嵌套环（批处理仍设置为100）：

explain (costs off, analyze, summary off)
/*+ Set(enable_mergejoin off) Set(enable_hashjoin off) Leading((a b)) IndexOnlyScan(a) IndexOnlyScan(b) */
select id, filter from a join b using (id)
 where a.filter=1 and b.filter=1;

                          QUERY PLAN

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 YB Batched Nested Loop Join (actual time=8.074..18138.524 rows=999990 loops=1)
   Join Filter: (a.id = b.id)
   ->  Index Only Scan using a_filter_id on a (actual time=4.299..467.477 rows=999990 loops=1)
         Index Cond: (filter = 1)
         Heap Fetches: 0
   ->  Index Only Scan using b_filter_id on b (actual time=1.453..1.637 rows=100 loops=10000)
         Index Cond: ((filter = 1) AND (id = ANY (ARRAY[a.id, $1, $2, $3, $4, $5, $6, $7, $8, $9, $10, $11, $12, $13, $14, $15, $16, $17, $18, $19, $20, $21, $22, $23, $24, $25, $26, $27, $28, $29, $30, $31, $32, $33, $34, $35, $36, $37, $38, $39, $40, $41, $42, $43, $44, $45, $46, $47, $48, $49, $50, $51, $52, $53, $54, $55, $56, $57, $58, $59, $60, $61, $62, $63, $64, $65, $66, $67, $68, $69, $70, $71, $72, $73, $74, $75, $76, $77, $78, $79, $80, $81, $82, $83, $84, $85, $86, $87,$88, $89, $90, $91, $92, $93, $94, $95, $96, $97, $98, $99])))
         Heap Fetches: 0
(8 rows)

这需要18s。不是最好的，但也不是其他联接方法。请记住，这是最糟糕的情况。
这意味着即使选择了最坏的联接方法，查询仍然运行。

概括

我创建了针对我的访问模式进行了优化的索引：过滤条件，然后连接条件，并使用范围sharding来保留订单。这是我观察到的响应时间：

外表 内表 合并加入 哈希加入 yb嵌套环
10行 10行 2ms 2ms 4ms
10行 100万 4S 4S 4ms
100万 10行 4S 4S 7S
100万 100万 4S 8S 18S

如果您希望最大的执行计划稳定性，则只有一种加入方法可以强制使用，批处理的嵌套循环可能是适合用户要求的循环。当它比其他联接方法更昂贵时，差异仅为5倍，用户可以很容易地理解，因为结果是一百万行。

如果我们让查询计划者决定执行计划，那么我们仍然可以保证在所有情况下都有可接受的响应时间。通过定义正确的索引，统计信息以及简单的查询，查询计划者应选择最佳计划。但是，错误不会致命，因为所有基本都可以接受所有计划（启用了批处理的嵌套循环）。

这取决于最佳，覆盖，索引，您将不会为每个用例创建完美的索引。但是至少关键的应该遵循这种模式以进行可预测的性能。