PolarDB:Configure sort keys for IMCIs

Overview

IMCIs are arranged by columns. By default, a single column can contain a maximum of 64,000 rows. Each column is separated into parallel data blocks organized based on the primary key of the original row-oriented data. The data is unsorted, and updated data is appended to the existing data.

IMCIs support sparse indexes, where the metadata for each data block includes the largest and smallest values in that data block. When the IMCI pruner is not enabled, the system scans all data blocks of a column during a query. When the IMCI pruner is enabled, the system uses the query conditions and metadata to categorize all data blocks into three types based on their relevance to the query: relevant, fairly relevant, and irrelevant. Only relevant and fairly relevant data blocks are scanned. If sorted in different orders, the same set of data can be separated into different data blocks. Therefore, you can sort the data based on the query conditions to improve query performance.

As shown in the preceding figure, when the system executes the following SQL statement on the unsorted data blocks, both data blocks in that column must be scanned. However, for the sorted data blocks, the system can skip the first data block based on the largest and smallest values of the data block, and thus scans only the second data block.

SELECT * FROM t WHERE c >= 8;

Prerequisites

• A PolarDB cluster of Enterprise Edition that meets one of the following requirements is created to use the IMCI sorting feature:

  • PolarDB for MySQL 8.0.1 whose revision version is 8.0.1.1.32 or later.

  • PolarDB for MySQL 8.0.2 whose revision version is 8.0.2.2.12 or later.

• A PolarDB cluster of Enterprise Edition that meets one of the following requirements is created to use the incremental sorting feature:

  • PolarDB for MySQL 8.0.1 whose revision version is 8.0.1.1.39.1 or later.

  • PolarDB for MySQL 8.0.2 whose revision version is 8.0.2.2.20.1 or later.

For information about how to check the cluster version, see Query the engine version.

Precautions

• Columns of the BLOB, JSON, or GEOMETRY type cannot be used as sort keys.

• For the incremental sorting feature, columns of the unsigned integer or decimal type cannot be used as sort keys.

• The incremental sorting feature only sorts data based on the first column in the sort key.

• The incremental sorting feature occupies system resources. However, when your cluster is handling heavy write workloads, the speed of incremental sorting is controlled to make more resources available for data writes.

Sorting procedures

• Procedure for sorting data during IMCI creation

  When creating an IMCI, the system sorts data in a similar way as when using secondary indexes during a DDL operation. The sorting can be performed in single-thread or multi-thread mode. When performed in single-thread mode, the sorting is a standard two-way merge sort. When performed in multi-thread mode, the sorting is a k-way external merge sort that uses loser trees and supports sampling. Procedure:

  1. The system traverses all data based on the primary key index and stores the data in a data file. Then, the column to be sorted is added to the sort cache. The system uses a separate data file for each thread and writes the data after a specific amount of data is accumulated.

  2. The system continuously traverses the data and adds data to the sort cache. When the sort cache is full, the system sorts the data in cache based on the sort key and saves the sorted data to a combined file.

  3. After the system finishes the traversing of the data, it merges the combined files pairwise based on the sort key, stores the sorted data in a temporary file, and replaces the combined files with the temporary file.

  4. The system repeats Step c until all combined files are sorted. Then, the system reads all rows in the combined files, compares the data in the data file and the combined files, and appends the data in the data file to the IMCI based on the offset values.

• Procedure for sorting incremental data

  Incremental sorting does not ensure that all data is properly sorted. Procedure:

  1. Groups all data blocks in pairs and find the groups whose data highly overlaps.

  2. Performs merge sort for each group and generates two sorted data blocks.

  3. Repeats Step b until all data blocks are sorted.

Parameters

You must configure the cluster parameters described in the following table to enable or disable the IMCI sorting feature, and adjust the configurations such as the number of threads.

Usage notes

To use the IMCI sorting feature, perform the following steps:

1. Enable the IMCI sorting feature.

   Set imci_enable_pack_order_key to ON.

2. Add the order_key option to the COMMENT clause of the following SQL statement to create a sorted IMCI:

   ALTER TABLE table_name COMMENT 'columnar=1 order_key=column_name[,column_name]';

   The following table describes the required parameters.

   Parameter	Description
   table_name	The table name.
   column_name	The column name. You can specify multiple column names. Separate the column names with commas (,).

   You can view the progress of IMCI creation in the INFORMATION_SCHEMA.IMCI_ASYNC_DDL_STATS table. For more information about the INFORMATION_SCHEMA.IMCI_ASYNC_DDL_STATS table, see View DDL execution speed and build progress for IMCIs.

SELECT * FROM INFORMATION_SCHEMA.IMCI_ASYNC_DDL_STATS;

Differences between IMCI sorting and DDL sorting

IMCI sorting is based on specific columns, which is similar to the sorting performed on secondary indexes during DDL operations. However, they are different in the following aspects:

• IMCIs are not sorted by the index key. Instead, you can specify any columns as sort keys.

• After the sorting for an IMCI is complete, all data needs to be read. However, for a secondary index, only the indexed data needs to be read. For example, for the data of the VARCHAR type, only prefixes are saved for the index.

Time consumption

In this example, 100 GB of TPC-H data is used to test the time required to create a sorted IMCI and to execute queries with a sorted IMCI.

• Time required to create a sorted IMCI

  In this example, a sorted IMCI is created for the lineitem table with 16 threads. Sample code:

  ALTER TABLE lineitem COMMENT='columnar=1 order_key=l_receiptdate,l_shipmode';

  The following table describes the creation time.

  Unordered dataset	Ordered dataset	Ordered dataset (with parallel_build_use_parallel_load set to OFF)
  6 minutes	35 minutes	4 hours

• Time required to execute queries with a sorted IMCI

  In this example, a sorted IMCI is used to execute the TPC-H Q12 with both the LRU cache and executor memory set to 10 GB.

  SELECT
      l_shipmode,
      SUM(CASE
          WHEN o_orderpriority = '1-URGENT' OR o_orderpriority = '2-HIGH'
          THEN 1
          ELSE 0
          END) AS high_line_count,
      SUM(CASE
          WHEN o_orderpriority <> '1-URGENT' AND o_orderpriority <> '2-HIGH'
          THEN 1
          ELSE 0
          END) AS low_line_count
      FROM
          orders,
          lineitem
      WHERE
          o_orderkey = l_orderkey
          AND l_shipmode in ('MAIL', 'SHIP')
          AND l_commitdate < l_receiptdate
          AND l_shipdate < l_commitdate
          AND l_receiptdate >= date '1994-01-01'
          AND l_receiptdate < date '1994-01-01' + interval '1' year
      GROUP BY
          l_shipmode
      ORDER BY
          l_shipmode;

  The following table describes the execution time.

  Unordered dataset	Ordered dataset	Ordered dataset (with parallel_build_use_parallel_load set to OFF)
  7.47s	1.25s	1.26s

Execution time when sort keys and partitioned tables are used

This section tests the query performance when sort keys and partitioned tables are used. 1 TB of TPC-H data is queried, and the cluster has 32 CPU cores and 256 GB of memory.

The following statements for creating tables are used in the test:

CREATE TABLE region ( r_regionkey  BIGINT NOT NULL,
                      r_name       CHAR(25) NOT NULL,
                      r_comment    VARCHAR(152)) COMMENT 'COLUMNAR=1';

CREATE TABLE nation ( n_nationkey  BIGINT NOT NULL,
                      n_name       CHAR(25) NOT NULL,
                      n_regionkey  BIGINT NOT NULL,
                      n_comment    VARCHAR(152)) COMMENT 'COLUMNAR=1';

CREATE TABLE part ( p_partkey     BIGINT NOT NULL,
                    p_name        VARCHAR(55) NOT NULL,
                    p_mfgr        CHAR(25) NOT NULL,
                    p_brand       CHAR(10) NOT NULL,
                    p_type        VARCHAR(25) NOT NULL,
                    p_size        BIGINT NOT NULL,
                    p_container   CHAR(10) NOT NULL,
                    p_retailprice DECIMAL(15,2) NOT NULL,
                    p_comment     VARCHAR(23) NOT NULL) COMMENT 'COLUMNAR=1';

CREATE TABLE supplier ( s_suppkey     BIGINT NOT NULL,
                        s_name        CHAR(25) NOT NULL,
                        s_address     VARCHAR(40) NOT NULL,
                        s_nationkey   BIGINT NOT NULL,
                        s_phone       CHAR(15) NOT NULL,
                        s_acctbal     DECIMAL(15,2) NOT NULL,
                        s_comment     VARCHAR(101) NOT NULL) COMMENT 'COLUMNAR=1';

CREATE TABLE partsupp ( ps_partkey     BIGINT NOT NULL,
                        ps_suppkey     BIGINT NOT NULL,
                        ps_availqty    BIGINT NOT NULL,
                        ps_supplycost  DECIMAL(15,2)  NOT NULL,
                        ps_comment     VARCHAR(199) NOT NULL) COMMENT 'COLUMNAR=1';

CREATE TABLE customer ( c_custkey     BIGINT NOT NULL,
                        c_name        VARCHAR(25) NOT NULL,
                        c_address     VARCHAR(40) NOT NULL,
                        c_nationkey   BIGINT NOT NULL,
                        c_phone       CHAR(15) NOT NULL,
                        c_acctbal     DECIMAL(15,2)   NOT NULL,
                        c_mktsegment  CHAR(10) NOT NULL,
                        c_comment     VARCHAR(117) NOT NULL) COMMENT 'COLUMNAR=1';

CREATE TABLE orders ( o_orderkey       BIGINT NOT NULL,
                      o_custkey        BIGINT NOT NULL,
                      o_orderstatus    CHAR(1) NOT NULL,
                      o_totalprice     DECIMAL(15,2) NOT NULL,
                      o_orderdate      DATE NOT NULL,
                      o_orderpriority  CHAR(15) NOT NULL,
                      o_clerk          CHAR(15) NOT NULL,
                      o_shippriority   BIGINT NOT NULL,
                      o_comment        VARCHAR(79) NOT NULL) COMMENT 'COLUMNAR=1'
                      PARTITION BY RANGE (year(`o_orderdate`))
                      (PARTITION p0 VALUES LESS THAN (1992) ENGINE = InnoDB,
                       PARTITION p1 VALUES LESS THAN (1993) ENGINE = InnoDB,
                       PARTITION p2 VALUES LESS THAN (1994) ENGINE = InnoDB,
                       PARTITION p3 VALUES LESS THAN (1995) ENGINE = InnoDB,
                       PARTITION p4 VALUES LESS THAN (1996) ENGINE = InnoDB,
                       PARTITION p5 VALUES LESS THAN (1997) ENGINE = InnoDB,
                       PARTITION p6 VALUES LESS THAN (1998) ENGINE = InnoDB,
                       PARTITION p7 VALUES LESS THAN (1999) ENGINE = InnoDB);

CREATE TABLE lineitem ( l_orderkey       BIGINT NOT NULL,
                        l_partkey        BIGINT NOT NULL,
                        l_suppkey        BIGINT NOT NULL,
                        l_linenumber     BIGINT NOT NULL,
                        l_quantity       DECIMAL(15,2) NOT NULL,
                        l_extendedprice  DECIMAL(15,2) NOT NULL,
                        l_discount       DECIMAL(15,2) NOT NULL,
                        l_tax            DECIMAL(15,2) NOT NULL,
                        l_returnflag     CHAR(1) NOT NULL,
                        l_linestatus     CHAR(1) NOT NULL,
                        l_shipdate       DATE NOT NULL,
                        l_commitdate     DATE NOT NULL,
                        l_receiptdate    DATE NOT NULL,
                        l_shipinstruct   CHAR(25) NOT NULL,
                        l_shipmode       CHAR(10) NOT NULL,
                        l_comment        VARCHAR(44) NOT NULL) COMMENT 'COLUMNAR=1'
                        PARTITION BY RANGE (year(`l_shipdate`))
                        (PARTITION p0 VALUES LESS THAN (1992) ENGINE = InnoDB,
                         PARTITION p1 VALUES LESS THAN (1993) ENGINE = InnoDB,
                         PARTITION p2 VALUES LESS THAN (1994) ENGINE = InnoDB,
                         PARTITION p3 VALUES LESS THAN (1995) ENGINE = InnoDB,
                         PARTITION p4 VALUES LESS THAN (1996) ENGINE = InnoDB,
                         PARTITION p5 VALUES LESS THAN (1997) ENGINE = InnoDB,
                         PARTITION p6 VALUES LESS THAN (1998) ENGINE = InnoDB,
                         PARTITION p7 VALUES LESS THAN (1999) ENGINE = InnoDB);

Sort keys are configured for the table after data is imported. For more information about how to configure sort keys, see Configure sort keys for IMCIs.

ALTER TABLE customer COMMENT='COLUMNAR=1 order_key=c_mktsegment';
ALTER TABLE nation COMMENT='COLUMNAR=1 order_key=n_name';
ALTER TABLE part COMMENT='COLUMNAR=1 order_key=p_brand,p_container,p_type';
ALTER TABLE region COMMENT='COLUMNAR=1 order_key=r_name';
ALTER TABLE orders COMMENT='COLUMNAR=1 order_key=o_orderkey,o_custkey,o_orderdate';
ALTER TABLE lineitem COMMENT='COLUMNAR=1 order_key=l_orderkey,l_linenumber,l_receiptdate,l_shipdate,l_partkey';

Some TPC-H queries are used for the test. The following table describes the execution time.