Incremental Sort

This topic describes incremental sort in YMatrix: when it applies, how to configure it, how to identify it in an execution plan, and how to troubleshoot it when it does not take effect.

Applies to: YMatrix 6.8.6 and later

What Is Incremental Sort

A regular sort reads the entire input before sorting it. When the input is already ordered by part of the sort keys the query needs, incremental sort splits the input into groups by that presorted prefix and sorts only the remaining keys within each group, which reduces both the number of comparisons and the memory the sort needs.

In YMatrix, incremental sort works at two levels:

Level Role
PostgreSQL Planner Decides whether the input provides a usable presorted prefix and whether to generate an Incremental Sort node
Vectorized executor Converts an eligible incremental sort into the SubKeySorter implementation of MxVSort and processes data in batches

The planner decides whether to use incremental sort; the vectorized executor decides which implementation to use. Both must agree for vectorized incremental sort to appear.

Requirements

Incremental sort takes effect only when all of the following hold:

  1. The query has an ORDER BY, and at least one sort key is guaranteed to be ordered by the input plan.
  2. The order of that prefix satisfies the query, including sort direction, NULLS FIRST / NULLS LAST, and collation.
  3. The PostgreSQL planner is used. With ORCA, rely on the actual plan.
  4. The relevant switches are on and the cost estimate considers incremental sort cheaper than a regular sort.

Common sources of an ordered prefix are the index order, the physical sort keys of a MARS3 table, and the order produced by a lower sort node. Having an index on the table does not mean the upper sort will use that index order; always check the actual execution plan.

Configuration

Two parameters control incremental sort, and both are on by default:

Parameter Default Role
enable_incremental_sort on Whether the planner may generate Incremental Sort plans
matrix.enable_mxv_subkey_sort on Whether MxVSort may use SubKeySorter, and whether a native incremental sort may be converted into a vectorized one

matrix.enable_mxv_subkey_sort already exists in 6.8 and is on by default. What 6.8.6 adds is the planner's ability to generate incremental sort plans (enable_incremental_sort) and the conversion of the generated native incremental sort into a vectorized one.

Common combinations (the first three assume vectorized execution and vectorized sort are already on):

Goal enable_incremental_sort matrix.enable_mxv_subkey_sort Expected behavior
Allow vectorized incremental sort on on Uses vectorized incremental sort when eligible; keeps the native incremental sort when vectorization is not possible
Use native incremental sort, keep vectorized scans on off The sort node stays a native Incremental Sort; scans below can still be vectorized
Turn incremental sort off off off No Incremental Sort is generated; regular sorts can still be vectorized

Before daily use, make sure the PostgreSQL planner is in use and vectorization is on:

SET optimizer = off;
SET matrix.enable_mxvector = on;
SET matrix.enable_mxv_sort = on;

Then choose one combination from the table above. You can also use SET LOCAL, which restores the setting automatically at the end of the transaction.

Note!
enable_incremental_sort=off alone does not turn off all vectorized incremental sort. For certain inputs, a regular MxVSort still recognizes the sort prefix provided by the input below; see the “Limitations and Notes” section below.

Example

The example below creates a MARS3 table, uses a mars3_btree index to provide a sort prefix, and then compares the execution plans under different configurations. It runs inside a transaction; run ROLLBACK at the end to undo the objects and settings.

BEGIN;
CREATE SCHEMA incremental_sort_demo;
SET LOCAL search_path = incremental_sort_demo, public;
SET LOCAL optimizer = off;
SET LOCAL matrix.enable_mxvector = on;
SET LOCAL matrix.enable_mxv_sort = on;
SET LOCAL statement_timeout = '60s';

CREATE TABLE events(id int, a int, b int) USING mars3
WITH (compress_threshold=65535, mars3options='prefer_load_mode=normal')
DISTRIBUTED BY(id);

INSERT INTO events
SELECT g, (g-1)/100, 12001-g FROM generate_series(1,12000) g;
CREATE INDEX events_a ON events USING mars3_btree(a);
ANALYZE events;

a takes a new value every 100 rows, for 120 distinct values; b decreases as id grows. The index provides the order of a, and the query asks for ORDER BY a, b, id, so a can serve as the prefix.

mars3.enable_btree_inorderscan controls whether mars3_btree provides an ordered index path and is off by default; without it, the index scan carries no ordering information and incremental sort cannot use it. To make the behavior easier to observe, the example temporarily lowers the attractiveness of other paths. These settings are not part of a normal configuration:

SET LOCAL enable_seqscan = off;
SET LOCAL enable_bitmapscan = off;
SET LOCAL enable_sort = off;
SET LOCAL mars3.enable_btree_inorderscan = on;

Vectorized Incremental Sort

SET LOCAL enable_incremental_sort = on;
SET LOCAL matrix.enable_mxv_subkey_sort = on;
EXPLAIN (ANALYZE, COSTS OFF, TIMING OFF, SUMMARY OFF)
SELECT id, a, b FROM events ORDER BY a, b, id LIMIT 50;
Custom Scan (MxVLimit)
  ->  Custom Scan (MxVMotion) Gather Motion 3:1  (slice1; segments: 3)
        Merge Key: a, b, id
        ->  Custom Scan (MxVLimit)
              ->  Custom Scan (MxVSort)
                    Sort Key: a, b, id
                    Common Prefix Order Key: a
                    Sort Method: subkey sort
                    ->  Custom Scan (MxVIndexScan) using events_a on events
Optimizer: Postgres-based planner

Common Prefix Order Key and Sort Method: subkey sort are the markers of vectorized incremental sort.

Native Incremental Sort with Vectorized Scans

SET LOCAL enable_incremental_sort = on;
SET LOCAL matrix.enable_mxv_subkey_sort = off;
EXPLAIN (ANALYZE, COSTS OFF, TIMING OFF, SUMMARY OFF)
SELECT id, a, b FROM events ORDER BY a, b, id LIMIT 50;
Limit
  ->  Gather Motion 3:1  (slice1; segments: 3)
        Merge Key: a, b, id
        ->  Limit
              ->  Incremental Sort
                    Sort Key: a, b, id
                    Presorted Key: a
                    ->  Custom Scan (MxVIndexScan) using events_a on events
Optimizer: Postgres-based planner

The sort node stays a native Incremental Sort, and its input is still a vectorized index scan. Only the vectorized implementation of incremental sort is disabled, not vectorized scanning.

Incremental Sort Turned Off

SET LOCAL enable_incremental_sort = off;
SET LOCAL matrix.enable_mxv_subkey_sort = off;
EXPLAIN (ANALYZE, COSTS OFF, TIMING OFF, SUMMARY OFF)
SELECT id, a, b FROM events ORDER BY a, b, id LIMIT 50;
Custom Scan (MxVLimit)
  ->  Custom Scan (MxVMotion) Gather Motion 3:1  (slice1; segments: 3)
        Merge Key: a, b, id
        ->  Custom Scan (MxVLimit)
              ->  Custom Scan (MxVSort)
                    Sort Key: a, b, id
                    Sort Method: top-k sort
                    ->  Custom Scan (MxVIndexScan) using events_a on events
Optimizer: Postgres-based planner

MxVSort still appears, but Sort Method is top-k sort or quicksort and there is no Common Prefix Order Key, which means a regular sort is used. Using an index for the scan does not mean the upper sort uses the index order.

Clean up after the example:

ROLLBACK;

How to Tell Whether It Works

Use the following markers in the EXPLAIN output:

Implementation Key marker
Native incremental sort Incremental Sort node with Presorted Key
Vectorized incremental sort MxVSort node with Common Prefix Order Key and Sort Method: subkey sort
Regular vectorized sort MxVSort node with Sort Method of top-k sort or quicksort

Node names alone are not enough: MxVSort appears for both regular sort and vectorized incremental sort.

The outputs above come from a test environment; row counts vary with data distribution, statistics, cost estimates, and version. The table above spreads about 12,000 rows over 3 segments, and a per-segment scan count of around 4,000 is normal. Do not use the row counts in the examples to infer performance ratios.

Limitations and Notes

  • The ordered prefix must come from the order actually reported by a plan node. A regular MxVSort does not currently take the index-provided sort prefix directly from MxVIndexScan. To use the index order, the planner must generate an Incremental Sort node and pass the prefix to the vectorized sort. Turning on SubKeySorter without generating an incremental sort plan therefore does not make the MxVIndexScan → MxVSort path use the index prefix.
  • enable_incremental_sort=off does not disable all vectorized incremental sort. When the input below is an MxVSort that can report order, the upper regular MxVSort may still recognize that prefix and use SubKeySorter.
  • Turning the switches on does not guarantee use. The cost estimate decides; usually the input must really provide an ordered prefix and the prefix groups must be small enough.
  • Prefix group size directly affects the benefit. If prefix values are almost unique (only one or two rows per group), the benefit approaches that of a regular sort, and the extra grouping overhead may make execution slower.
  • In a distributed plan, ordering is guaranteed only within a segment. Each segment completes its incremental sort and a Gather Motion with a Merge Key merges the results. The actual rows shown on a segment node is the amount for that segment, not the whole table.
  • LIMIT is not a requirement. It may let the scan stop early, but the actual amount read also depends on prefix group size, filters, vector batch size, and distributed execution, so it is not guaranteed to read less every time.
  • The native implementation is kept when conversion is not possible. The current vectorized conversion requires a matching DeltaFilter, a supported default sort operator, and a deterministic collation. When these conditions are not met, no error is raised and the plan falls back to the native Incremental Sort.

Troubleshooting Order

  1. Does EXPLAIN show Optimizer: Postgres-based planner?
  2. Does the input path really provide the sort prefix the query needs, rather than just a related index existing on the table?
  3. Are statistics up to date (ANALYZE), and did cost estimates prefer another path?
  4. Are the vectorization master switch, the vectorized sort switch, and the SubKeySorter switch all on, and is the subplan vectorizable?
  5. Does the prefix comparison meet the conversion requirements: DeltaFilter, sort operator, and deterministic collation?

When comparing the two implementations, use the "vectorized incremental sort" and "native incremental sort" configurations on the same query and confirm Sort Method before comparing execution time. Comparing "incremental sort off" with "incremental sort on" gives the difference between regular sort and incremental sort, not between the two incremental sort implementations.

Checklist

  • [ ] EXPLAIN shows Optimizer: Postgres-based planner
  • [ ] The incremental sort node has Presorted Key or Common Prefix Order Key
  • [ ] The Sort Method of vectorized incremental sort is subkey sort
  • [ ] The sort direction and NULLS position match the index or sort key definition in use
  • [ ] ANALYZE has been run, so statistics are not stale
  • [ ] Execution time with the feature on and off has been compared on real data volumes, not just the plans