Sorting optimization

Background information

When you create a table, you can define one or more columns as a sort key. After data is written to the table, you can physically reorder it based on this sort key.

Sorting a table speeds up range filter queries. The database stores the minimum and maximum values for each column within each data block. When a query includes a range filter, the AnalyticDB for PostgreSQL query engine uses these min/max values to skip blocks that do not meet the filter conditions during the scan.

For example, consider a table that stores seven years of data and is sorted by a date column. If you query for one month of data, the engine scans only about 1/84 of the total data, skipping 98.8% of the blocks. If the data were not sorted, the engine would have to scan every block on disk.

AnalyticDB for PostgreSQL supports two sorting methods:

• compound sorting: Best for queries where the filter conditions are a prefix of the sort key, such as queries that filter on the first column of the sort key.

• interleaved sorting: Assigns equal weight to each column in the sort key, making it more suitable for queries where filter conditions can apply to any subset of the sorted columns.

How to choose a sort key

• If your queries frequently use equality filters or range filters on a fixed set of columns, define these columns as a sort key. This enables the system to combine data sorting with a rough set index to accelerate these queries. In most cases, you should use compound sorting.

• If your queries use filter conditions on a variable set of columns, use interleaved sorting to improve performance. Because it involves additional data organization, interleaved sorting is generally slower than compound sorting.

  Note

  Interleaved sorting supports a maximum of eight columns.

• If your queries often use a fixed column as a JOIN condition, you can set that column as both the distribution key and the sort key. This enables the optimizer to use a merge join instead of a hash join. Because the underlying data is already sorted by the JOIN key, the system can skip the time-consuming sort phase of the merge join.

Performance comparison of compound and interleaved sorting

The following benchmark applies compound sorting and interleaved sorting to two identical tables and compares how each method affects query performance in different scenarios.

1. Create two test tables and set their sort keys. Each table contains four columns: id, num1, num2, and value. The sort key is (id, num1, num2). Run the following statements:

   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);

2. Insert 10 million rows of test data by running the following statements:

   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;

   Query the total number of rows in each table:

   • SELECT count(*) FROM test;

     The following information is returned:

       count
     ----------
      10000000
     (1 row)

   • SELECT count(*) FROM test_multi;

     The following information is returned:

       count
     ----------
      10000000
     (1 row)

3. Apply compound sorting and interleaved sorting to the two tables.

   Apply compound sorting to the test table:

   SORT test;

   Apply interleaved sorting to the test_multi table:

   MULTISORT test_multi;

4. The following is a performance comparison for equality queries:

   • Q1 query: The filter condition is on the first sort key column.

     SELECT * FROM test WHERE id = 100000;
     SELECT * FROM test_multi WHERE id = 100000;

   • Q2 query: The filter condition is on the second sort key column.

     SELECT * FROM test WHERE num1 = 8766963;
     SELECT * FROM test_multi WHERE num1 = 8766963;

   • Q3 query: The filter conditions are on the second and third sort key columns.

     SELECT * FROM test WHERE num1 = 100000 AND num2=2904114;
     SELECT * FROM test_multi WHERE num1 = 100000 AND num2=2904114;

   The performance comparison results are as follows:

   Sorting method	Q1	Q2	Q3
   compound sorting	0.026 s	3.95 s	4.21 s
   interleaved sorting	0.55 s	0.42 s	0.071 s

5. The following is a performance comparison for range queries:

   • Q1 query: The filter condition is on the first sort key column.

     SELECT count(*) FROM test WHERE id>5000 AND id < 100000;
     SELECT count(*) FROM test_multi WHERE id>5000 AND id < 100000;

   • Q2 query: The filter condition is on the second sort key column.

     SELECT count(*) FROM test WHERE num1 >5000 AND num1 <100000;
     SELECT count(*) FROM test_multi WHERE num1 >5000 AND num1 <100000;

   • Q3 query: The filter conditions are on the second and third sort key columns.

     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;

   The performance comparison results are as follows:

   Sorting method	Q1	Q2	Q3
   compound sorting	0.07 s	3.35 s	3.64 s
   interleaved sorting	0.44 s	0.28 s	0.047 s

Conclusions:

• For Q1 queries, which filter on the first column of the sort key, compound sorting performs better. In contrast, interleaved sorting is weaker in this scenario.

• For Q2 queries, which do not filter on the first column of the sort key, compound sorting is largely ineffective. Interleaved sorting, however, provides a stable performance improvement.

• Interleaved sorting performs better, as its effectiveness increases when more sorted columns are included in the filter conditions.

Sorting acceleration

After you execute SORT <tablename>, the system physically sorts the table data. AnalyticDB for PostgreSQL can then leverage this physical ordering by pushing down sort-aware operators to the storage layer to accelerate computation. SQL queries that can take advantage of the underlying data order will see performance gains. This feature can accelerate SORT, AGG, and JOIN operators based on the sort key.

The following example compares query times on a test table named far before and after sorting to demonstrate the effect of sorting acceleration.

1. Create the test table far.

   CREATE TABLE far(a int,  b int)
   WITH (APPENDONLY=TRUE, COMPRESSTYPE=ZSTD, COMPRESSLEVEL=5)
   DISTRIBUTED BY (a)  --distribution key
   ORDER BY (a);       --sort key

2. Insert one million rows of data.

   INSERT INTO far VALUES(generate_series(0, 1000000), 1);

3. After the data is imported, sort the data.

   SORT far;

The query performance comparison is as follows:

• ORDER BY acceleration

  • Before acceleration, the ORDER BY query takes 323.980 ms:

    postgres=# select * from far order by a limit 1;
     a | b
    ---+---
     0 | 1
    (1 row)
    Time: 323.980 ms

  • After acceleration, query performance is improved.

    postgres=# select * from far order by a limit 1;
     a | b
    ----+----
     0 | 1
    (1 row)
    Time: 6.971 ms

• GROUP BY acceleration

  • Before acceleration:

    postgres=# select a,count(*) from far  group by a limit 1;
        a    | count
    ---------+-------
     579229 |     1
    (1 row)
    Time: 779.368 ms

  • After acceleration:

    postgres=# select a, count(*) from far group by a limit 1;
     a | count
    ---+-------
     0 | 1
    (1 row)
    Time: 6.859 ms

• JOIN acceleration

  • Before acceleration:

    postgres=# select * from far t1, far t2 where t1.a = t2.a limit 1;
     a | b | a | b
    ---+---+---+---
     2 | 1 | 2 | 1
    (1 row)
    Time: 289.075 ms

  • After acceleration:

    Note

    To accelerate JOIN queries, you must disable the ORCA optimizer and enable the merge join feature by running the following statements:

    SET enable_mergejoin TO on;
    SET optimizer TO off;

    The JOIN query now takes 12.315 ms.

    postgres=# select * from far t1, far t2 where t1.a = t2.a limit 1;
     a | b | a | b
    ---+---+---+---
     2 | 1 | 2 | 1
    (1 row)
    Time: 12.315 ms