[YSQL] Support Mixed Sort Order in YSQL using LSM Indexes

[pao214]

Jira Link: DB-11293

Description

Mixed Sort Order

One of the primary advantages of having a multi-dimensional index with skip style access is support for more flexible sort orders. Consider the following query for example for the same table as above

EXPLAIN (COSTS OFF, TIMING OFF, SUMMARY OFF)
  SELECT r1, r2 FROM t
  ORDER BY r1 ASC, r2 DESC;

produces a plan

       QUERY PLAN
-------------------------
 Sort
   Sort Key: r1, r2 DESC
   ->  Seq Scan on t
(3 rows)

However, skip scan allows us to backwards scan on r2 for each distinct key of r1 thus avoiding a sort completely. Implementing this for a single tablet server is simply not sufficient. Instead, the PgGate layer needs to merge outputs from multiple tablets at the boundaries appropriately. Take the same example as above,

we receive output (1,500), ..., (1,1) from tablet 1 and we receive output (1,1000), (1,501) from tablet 2. In the straightforward ordering case, we could have appended output from tablet 2 to tablet 1, but now we need to output the top elements from tablet 2 before the bottom elements in tablet 1 during the merge.

Issue Type

kind/bug

Warning: Please confirm that this issue does not contain any sensitive information

• I confirm this issue does not contain any sensitive information.

[tanujnay112]

Instead, the PgGate layer needs to merge outputs from multiple tablets at the boundaries appropriately.

This work is needed for vector index support as well.