Ordering rows by repeating pattern

All we need is an easy explanation of the problem, so here it is.

Given a table in Postgres like

CREATE TABLE t1 (
  type text NOT NULL,
  value int NOT NULL
)

where type could be A, B or C and given an arbitrary, repeating pattern like

A B B C B B

how can I query the table so that the results are sorted first according to the pattern and then according to the value? In other words, the first row is the A with the lowest value, the second row is the B with the lowest value, the third row is the B with the second lowest value and so on. If we run out of particular type, we just move on to the next letter in the pattern (i.e. if we don’t have any more Cs to return, the pattern becomes ABBBB).

type value
A 1
B 1
B 2
C 1
B 3
B 4
A 2
B 5
B 6
B 7
B 8
A 3
B 9

The actual pattern is dynamic and has an arbitrary length, thought it will always be constrained to only the possible values for type.

Here is a fiddle with sample data.

How to solve :

I know you bored from this bug, So we are here to help you! Take a deep breath and look at the explanation of your problem. We have many solutions to this problem, But we recommend you to use the first method because it is tested & true method that will 100% work for you.

Method 1

Not easy with plain SQL, but still possible:

WITH pattern AS  (
   SELECT *, row_number() OVER (PARTITION BY type ORDER BY ord) AS pos
   FROM   unnest('{A,B,B,C,B,B}'::text[]) WITH ORDINALITY t(type, ord)
              -- provide pattern here
   ) 
 , type_frequency AS (
   SELECT type, count(*) AS freq
   FROM   pattern
   GROUP  BY 1
   )
SELECT type, t.value -- , t.epoch, p.ord, pos
FROM  (
   SELECT type, value
        , ceil(rn / freq::float) AS epoch
        , (rn - 1) % freq + 1    AS pos
   FROM  (
      SELECT *, row_number() OVER (PARTITION BY type ORDER BY value) AS rn
      FROM   t1  -- base table here
      JOIN   type_frequency tf USING (type)
      ) sub
   ) t
JOIN   pattern p USING (type, pos)
ORDER  BY t.epoch, p.ord;

db<>fiddle here

Produces exactly your desired result.

Would seem simpler with a procedural solution looping through the pattern and getting the next greater value per type from the table. But this query should still perform decently.

User instructions

Provide any pattern once in the first CTE pattern. Assuming base type text, but any type supporting equality works. Unnest using WITH ORDINALITY to preserve the original order of elements in the pattern (ord). Distill the position per type (pos) to match the same for table rows later. About WITH ORDINALITY:

The second CTE type_frequency computes distinct values and their respective frequency in the pattern.

In the outer query, in the subquery sub, join to type_frequency to filter only involved types while adding the frequency, and add a row number (rn) per type.

Dividing that rn by the value frequency freq produces an epoch, the principal order of rows. (Can’t use integer division here, that would truncate, so cast to float!)
rn modulo (%) freq produces the position pos per type. Shift back (- 1) and forth (+ 1) to fix an off-by-1 issue. We need an integer type for the modulo operation.

Finally, join to the pattern on (type, pos) to attach the original order (ord) in the pattern per epoch.

Note: Use and implement method 1 because this method fully tested our system.
Thank you 🙂

All methods was sourced from stackoverflow.com or stackexchange.com, is licensed under cc by-sa 2.5, cc by-sa 3.0 and cc by-sa 4.0

Leave a Reply