列存表使用排序键和粗糙集索引加速查询

背景信息

当您创建表的时候，可以定义一个或者多个列为排序键（SORTKEY）。数据写入到表中之后，您可以对该表按照排序键进行排序重组。

表排序后可以加速范围限定查询，数据库会对每固定行记录每一列的min、max值。如果在查询时使用范围限定条件，ADBPG的查询引擎可以根据min、max值在对表进行扫描（SCAN）时快速跳过不满足限定条件的数据块（Block）。

例如，假设一张表存储了7年的数据，并且这张表的数据是按照时间字段排序存储的，如果我们需要查询一个月的数据，那么只需要扫描 1/(7*12) 的数据，也就是说有98.8%的数据块在扫描（SCAN）时可以被过滤掉。但是如果数据没有按照时间排序的话，可能所有的磁盘上的数据块都要被扫描到。

• 性能对比

  • 本节以组合排序给粗糙集索引带来的性能提升为例，展示粗糙集索引相比全表扫描的性能提升。

    以TPCH Lineitem表为例，表中存储了7年的数据，我们比较数据未按照l_shipdate字段排序和用l_shipdate字段作为排序键并进行排序的限定条件查询的性能。

    说明 本文的TPC的实现基于官方TPC的基准测试，并不能与已发布的TPC基准测试结果相比较，本文中的测试并不符合TPC基准测试的所有要求。
    测试步骤：

    1. 创建一个32节点的实例。
    2. 对Lineitem写入130亿行记录。
    3. 查询1997-09-01到1997-09-30的数据。
       • 数据未按照l_shipdate排序。执行范围查询，耗时约 34.6 秒：

         adbpgadmin=# select count(*) from lineitem where l_shipdate between '1997-09-01' and '1997-09-30';
            count
         -----------
          149619638
         (1 row)
         Time: 34651.793 ms

       • 数据按照l_shipdate排序。

         adbpgadmin=# select count(*) from lineitem where l_shipdate between '1997-09-01' and '1997-09-30';
            count
         -----------
          149619638
         (1 row)
         Time: 1661.046 ms

创建表时定义排序键

样例

create table test(date text, time text, open float, high float, low float, volume int) with(APPENDONLY=true,ORIENTATION=column) ORDER BY (volume);

语法

CREATE [[GLOBAL | LOCAL] {TEMPORARY | TEMP}] TABLE table_name (
[ { column_name data_type  ...} ]
)
[ DISTRIBUTED BY (column, [ ... ] ) | DISTRIBUTED RANDOMLY ]
[ ORDER BY (column, [ ... ] )]

数据库内核版本20210326之前，指定排序键语法为SORTKEY (column, [ ... ])

对表进行排序

• 对数据进行组合排序

  • SORT [tablename]

  • 数据库内核版本20210326之前可以使用以下语法的语句：

    VACUUM SORT ONLY [tablename]

• 对数据进行多维排序

  • MULTISORT [tablename]

  • 数据库内核版本20210326之前可以使用以下语法的语句：

    VACUUM REINDEX [tablename]

当您对一张表执行过SORT或者MULTISORT之后，当前的数据会组织为按照排序键全表有序，但随着表中不断写入新数据，未排序的部分就会不断增加，这将有可能影响粗糙集过滤的性能。因此您需要周期性地执行SORT或者VACUUM REINDEXMULTISORT操作来对表进行重排序，从而保证粗糙集过滤的性能。

修改排序键

您可以根据业务的变化修改已经创建的列存表的排序键，命令语法如下：

ALTER [[GLOBAL | LOCAL] {TEMPORARY | TEMP}] TABLE table_name SET ORDER BY (column, [ ... ] )

这个命令只会修改catalog，不会对数据立即排序，需要重新执行SORT table_name命令排序。

样例

ALTER TABLE test SET ORDER BY(high,low);

数据库内核版本20210326之前可以使用以下语法的语句：

ALTER TABLE test SET SORTKEY(high,low);

如何选择排序键和排序方式

当您的查询SQL经常包含某一个列或者某几个列的等值或者范围限定条件查询时，比如时间列等，可以考虑使用这些列作为排序键，从而利用数据排序并结合粗糙索引，加速这类SQL的查询速度。

一般情况下建议使用组合排序，因为多维排序在排序过程中还需要做一些额外的数据组织工作，多维排序VACUUM REINDEX的时间会长于组合排序VACUUM SORT ONLY的时间。

如果您的查询SQL包含的限定条件经常不是总是包含某些列的，可以使用多维排序来加速查询。多维排序最多支持8列。

组合排序和多维排序的性能对比

我们会对同一张表分别做组合排序和多维排序，从而比较两种排序方式在不同的场景下，对不同查询的性能影响。

在这个场景中，我们创建一张表test，其包含4列（id, num1, num2, value）。使用（id,num1,num2）作为排序键。这张表一共包含一千万条记录。对于ADBPG来说并不算是一张特别大的表，但是其可以显示出组合排序和多维排序的性能差异，在更大的数据集中，两者的性能差异也会更明显。

• 创建测试表并设置表的排序键

  • CREATE TABLE test(id int, num1 int, num2 int, value varchar) 
    with(APPENDONLY=TRUE, ORIENTATION=column)
    DISTRIBUTED BY(id)
    ORDER BY(id, num1, num2);
    CREATE TABLE test_multi(id int, num1 int, num2 int, value varchar) 
    with(APPENDONLY=TRUE, ORIENTATION=column)
    DISTRIBUTED BY(id)
    ORDER BY(id, num1, num2);

• 写入一千万行数据

  • INSERT INTO test(id, num1, num2, value) select g, 
    (random()*10000000)::int, 
    (random()*10000000)::int,
    (array['foo', 'bar', 'baz', 'quux', 'boy', 'girl', 'mouse', 'child', 'phone'])[floor(random() * 10 +1)]
    FROM generate_series(1, 10000000) as g;
    INSERT INTO test_multi SELECT * FROM test;
    adbpgadmin=# SELECT count(*) FROM test;
      count
    ----------
     10000000
    (1 row)
    adbpgadmin=# SELECT count(*) FROM test_multi;
      count
    ----------
     10000000
    (1 row)

• 对两张表分别进行组合排序和多维排序

  • SORT test;
    MULTISORT test_multi;

• 点查询比较性能

  • • 包含首列排序键限定条件。

      -- Q1 包含首列限定条件
      select * from test where id = 100000;
      select * from test_multi where id = 100000;

    • 包含第二列限定条件。

      -- Q2 包含第二列限定条件
      select * from test where num1 = 8766963;
      select * from test_multi where num1 = 8766963;

    • 包含二三列限定条件。

      -- Q3 包含二三列限定条件
      select * from test where num1 = 100000 and num2=2904114;
      select * from test_multi where num1 = 100000 and num2=2904114;

    表 1. 性能对比结果

    排序方式	Q1	Q2	Q3
    组合排序	0.026s	3.95s	4.21s
    多维排序	0.55s	0.42s	0.071s

• 范围查询比较性能

  • • 包含首列排序键限定条件。

      -- Q1 包含首列限定条件
      select count(*) from test where id>5000 and id < 100000;
      select count(*) from test_multi where id>5000 and id < 100000;

    • 包含第二列限定条件。

      -- Q2 包含第二列限定条件
      select count(*) from test where num1 >5000 and num1 <100000;
      select count(*) from test_multi where num1 >5000 and num1 <100000;

    • 包含二三列限定条件。

      -- Q3 包含二三列限定条件
      select count(*) from test where num1 >5000 and num1 <100000; and num2 < 100000;
      select count(*) from test_multi where num1 >5000 and num1 <100000 and num2 < 100000;

    表 2. 性能对比结果

    排序方式	Q1	Q2	Q3
    组合排序	0.07s	3.35s	3.64s
    多维排序	0.44s	0.28s	0.047s

• 结论

  • • 对于Q1场景，由于包含排序键的首列，所以组合排序的效果非常好，而多维排序则会相对性能弱一些。
    • 对于Q2场景，由于不包含排序键的首列，组合排序基本上失效了，而多维排序依然能维持比较稳定的性能提升。
    • 对于Q3场景，由于不包含排序键的首列，组合排序依然起不到很好的效果，并且由于比较条件的增加，需要额外的比较开销，时间更长，而多维排序表现出更好的性能，这是因为在查询时，限定条件包含的多维排序键越多，性能越好。