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
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.
Incremental sort takes effect only when all of the following hold:
ORDER BY, and at least one sort key is guaranteed to be ordered by the input plan.NULLS FIRST / NULLS LAST, and collation.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.
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=offalone does not turn off all vectorized incremental sort. For certain inputs, a regularMxVSortstill recognizes the sort prefix provided by the input below; see the “Limitations and Notes” section below.
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;
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.
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.
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;
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.
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.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.Incremental Sort.EXPLAIN show Optimizer: Postgres-based planner?ANALYZE), and did cost estimates prefer another path?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.
EXPLAIN shows Optimizer: Postgres-based plannerPresorted Key or Common Prefix Order KeySort Method of vectorized incremental sort is subkey sortNULLS position match the index or sort key definition in useANALYZE has been run, so statistics are not stale