Sorting Operator Optimization

Availability

This feature is available since MogDB 3.1.0.

Introduction

This feature improves the performance of the sorting operator in several ways. First, it is optimized for sorting individual columns, using more efficient algorithms and data structures that reduce the computational and storage resources required for sorting. Second, a specialized fast sort function is introduced, which is a commonly used and efficient sorting algorithm capable of achieving high sorting performance in the average case. In addition, incremental sorting is supported, which can utilize a portion of the data that has already been sorted and quickly insert it into the sorted dataset when new data arrives.

Benefits

Compared to the traditional way of comparing function calls, the fast sort function can reduce overhead and thus improve performance. Typically, a performance improvement of 2% to 5% can be obtained by using the quick sort function.

The incremental sort method utilizes the ordered arrangement of indexes to incrementally sort other fields, which can reduce the number of sorted fields and thus improve performance. Depending on the specific situation, this method can bring 10 to 100 times performance improvement.

Both optimization methods can be used in query and sort operations to improve performance and reduce overhead. The specific performance improvement will be affected by the amount of data, index design, query conditions, and other factors. Overall, however, these optimization methods are designed to improve the performance of query and sort operations so that your business can process data more efficiently.

Description

This feature optimizes the sorting of individual columns and reduces overhead by saving only one Datum structure, avoiding the operation of copying the tuple into sort memory.

When sorting with Quick Sort in MogDB, each data type has its own comparison function. To avoid the overhead of calling the compare function multiple times, this feature introduces a new set of fast sort functions. The comparison functions of these functions are inlined, which improves performance by eliminating the overhead required by a large number of comparison function calls.

In addition, this feature introduces an incremental sorting method that utilizes the ordered arrangement of indexes on which other fields are incrementally sorted to reduce the number of sorted fields, thereby improving performance.

All of these optimizations are very helpful in improving the performance of the sort operation, reducing the overhead and making the sort more efficient and faster.

Constraints

This feature supports the following sorting modes except ORDER BY LIMIT: integer, date, timestamp, uuid, text, varchar, and char.

Example

Create a table, insert data, and turn on incremental sorting.

 -- Create a table and insert test data
 drop table if exists MogDB_incresort_1;
 create table MogDB_incresort_1 (id int, pname name, match text);
 
 create index on MogDB_incresort_1(id);
 
 insert into MogDB_incresort_1
 values (
         generate_series(1, 20000),
         'player# ' || generate_series(1, 20000),
         'match# ' || generate_series(1, 11)
     );
 
 vacuum analyze MogDB_incresort_1;
 
 -- Turn on incremental sorting
 set enable_incremental_sort = on;

Incremental sorting operators are typically generated in partially ordered scenarios with a LIMIT, such as the Index Scan + LIMIT scenario.

 -- Incremental sorting using index scanning
 MogDB=# explain (costs off) select id, pname from MogDB_incresort_1 where id < 20 order by id, pname limit 20;
                                  QUERY PLAN
 ----------------------------------------------------------------------------
  Limit
    ->  Incremental Sort
          Sort Key: id, pname
          Presorted Key: id
          ->  Index Scan using mogdb_incresort_1_id_idx on mogdb_incresort_1
                Index Cond: (id < 20)
 (6 rows)

Replacing the index scan of step 2 with an ordered subquery also allows for incremental sorting.

 -- Incremental sorting using ordered subqueries
  MogDB=# explain (costs off)
 select players.pname,
     random() as lottery_number
 from (
         select distinct pname
         from MogDB_incresort_1
         group by pname
         order by pname
     ) as players
 order by players.pname,
     lottery_number
 limit 20;
                               QUERY PLAN
 -----------------------------------------------------------------------
  Limit
    ->  Incremental Sort
          Sort Key: players.pname, (random())
          Presorted Key: players.pname
          ->  Subquery Scan on players
                ->  Unique
                      ->  Sort
                            Sort Key: mogdb_incresort_1.pname
                            ->  HashAggregate
                                  Group By Key: mogdb_incresort_1.pname
                                  ->  Seq Scan on mogdb_incresort_1
 (11 rows)

enable_incremental_sort