2

A while back I asked this question about efficiently selecting unique permutations of columns in Postgres. Now I have a follow-up question regarding how to do so, with the addition of being able to order any of the columns with any combination of ASC/DESC across the columns.

The table contains hundreds of millions of rows, and while the accepted answer to my previous question is orders of magnitude faster than traditional approaches, not being able to order the columns in an ad-hoc way prevents me from putting this query to good use (I really need it to 'paginate', with LIMIT/OFFSET in small chunks). Is there a way to do this? The author of the previous answer kindly suggested a workaround (changing the row comparison for an explicit where clause), which I tried, but it doesn't seem to work (or I misunderstand it).

Given the following generic query:

WITH RECURSIVE cte AS (
   (
   SELECT col1, col2, col3, col4
   FROM   tbl
   ORDER  BY 1,2,3,4
   LIMIT  1
   )
   UNION ALL
   SELECT l.*
   FROM   cte c
   CROSS  JOIN LATERAL (
      SELECT t.col1, t.col2, t.col3, t.col4
      FROM   tbl t
      WHERE (t.col1, t.col2, t.col3, t.col4) > (c.col1, c.col2, c.col3, c.col4)
      ORDER  BY 1,2,3,4
      LIMIT  1
      ) l
   )
SELECT * FROM cte

Is there a way to order the columns in an ad-hoc way, whilst maintaining the performance? For example:

ORDER BY by col1 DESC, col2 ASC, col3 ASC, col4 DESC

Assume an index on each column, as well as a combined index across all 4 columns.

Postgres version is 15.4.
The table is read-only in the sense that the data can't / won't be modified, however it will be added to. Following is a CREATE TABLE script to replicate my problematic table (more or less):

CREATE TABLE tbl (id SERIAL primary key, col1 integer NOT NULL, col2 integer NOT NULL, col3 integer NOT NULL, col4 integer NOT NULL);

INSERT INTO tbl (col1, col2, col3, col4) SELECT (random()*1000)::int AS col1, (random()*1000)::int AS col2, (random()*1000)::int AS col3, (random()*1000)::int AS col4 FROM generate_series(1,10000000);

CREATE INDEX ON tbl (col1);
CREATE INDEX ON tbl (col2);
CREATE INDEX ON tbl (col3);
CREATE INDEX ON tbl (col4);
CREATE INDEX ON tbl (col1, col2, col3, col4);
0

1 Answer 1

3

Basically: No.
Row value comparison works with ASCENDNG or DESCENDING sort order, but not for a mix of directions among nested fields. See:

However ...

Workaround for numerical types

Emulating index-skip scan

Note, emulating an index-skip scan only makes sense for big tables with many duplicates for your set of columns. But then it can make orders of magnitude difference.

Basics:

For alternating sort order, there are workarounds for numeric data types (or any type that can be "inverted") with a multicolumn expression index. Basically, instead of col1 DESC, you operate on (col1 * -1) ASC - ASC being the default direction.

For your example:

ORDER BY col1 DESC, col2 ASC, col3 ASC, col4 DESC

CREATE INDEX tbl_1d2a3a4d_idx ON tbl ((col1 * -1), col2, col3, (col4 * -1));  -- !!!

The query then becomes:

WITH RECURSIVE cte AS (
   (
   SELECT col1, col2, col3, col4
   FROM   tbl
   ORDER  BY (col1 * -1), col2, col3, (col4 * -1)              -- !
   LIMIT  1
   )
   UNION ALL
   SELECT l.*
   FROM   cte c
   CROSS  JOIN LATERAL (
      SELECT t.col1, t.col2, t.col3, t.col4
      FROM   tbl t
      WHERE    ((t.col1 * -1), t.col2, t.col3, (t.col4 * -1))  -- !
             > ((c.col1 * -1), c.col2, c.col3, (c.col4 * -1))  -- !
      ORDER  BY (t.col1 * -1), t.col2, t.col3, (t.col4 * -1)   -- !
      LIMIT  1
      ) l
   )
SELECT *
FROM   cte

fiddle

Postgres cannot make do with an index-only scan, since col1 and col4 are hidden behind an expression. Depending on a number of storage and RAM factors, it may pay to use a covering index instead. See:

CREATE INDEX tbl_1d2a3a4d_covering_idx
ON tbl ((col1 * -1), col2, col3, (col4 * -1)) INCLUDE (col1, col4);  -- !

Same query.

But that's all still on the topic of "efficiently selecting unique permutations of columns".

Pagination

You mentioned pagination (with LIMIT / OFFSET). You can base it on above query. Like:

-- query from above
OFFSET 10000
LIMIT  10;

Should perform OK-ish. Makes limited sense for ad-hoc use.
If the table is not read-only or when OFFSET + LIMIT gets big, keyset-pagination makes more sense. See:

Materialize unique rows with a row number

For repeated use on a big, read-only table, consider a materialized view with a row number. May or may not make sense if, in your case, "rows will be added". You can use the query from above to create the MV:

CREATE MATERIALIZED VIEW mv_tbl AS
WITH RECURSIVE cte AS (
   (
   SELECT col1, col2, col3, col4
   FROM   tbl
   ORDER  BY (col1 * -1), col2, col3, (col4 * -1)
   LIMIT  1
   )
   UNION ALL
   SELECT l.*
   FROM   cte c
   CROSS  JOIN LATERAL (
      SELECT t.col1, t.col2, t.col3, t.col4
      FROM   tbl t
      WHERE  ((t.col1 * -1), t.col2, t.col3, (t.col4 * -1))
           > ((c.col1 * -1), c.col2, c.col3, (c.col4 * -1))
      ORDER  BY (t.col1 * -1), t.col2, t.col3, (t.col4 * -1)
      LIMIT  1
      ) l
   )
SELECT row_number() OVER () AS rn, *  -- !
FROM   cte;

Then, index & query are simple:

CREATE INDEX mv_tbl_idx ON mv_tbl (rn);  -- !

SELECT rn, col1, col2, col3, col4
FROM   mv_tbl
WHERE  rn > 10000
ORDER  BY rn
LIMIT  10;

fiddle

There are many nuances to all of this ...

2
  • 1
    I can't thank you enough for this answer - I had no idea expression indexes even existed, let alone how powerful they can be. I tried your solution and the performance is excellent! The only caveat is that (as far as I understand) an index will need to be created for every possible combination of order-by for the given columns, is that correct? And likewise for changing columns order (ie, order by col2, col1 instead of col1, col2). Even with it's limitations, you've provided a solution to what I understood was an unsolvable problem - many thanks!
    – hunter
    Commented May 4 at 14:03
  • 1
    @hunter The index tbl_1d2a3a4d_idx is also close to perfect for all leading subsets (1d2a3a, 1d2a, 1d) and their inversions (1a2d3d, 1a2d, 1a). And you should be able to adjust column order to an existing index as far as I understand the task. Other than that, you may need to create various indexes to support various combinations. With many duplicates, index size is considerably reduced since Postgres 13. See: dba.stackexchange.com/a/27493/3684 And index creation is remarkable performant. Set maintenance_work_mem high in the creating session. Commented May 5 at 2:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.