CODEWITHSUNDEEP
postgresql
German
German

Reputation: 126

how to sort rows according to multiple dependencies

The table has many columns, but for the problematic part let's assume only two, [ID] and [dependency].

[Dependency] means which [ID]s should be listed before this [ID].

Each row has its unique [ID] but it might have none, one or more dependencies in the [Dependency] column

ID Dependency
1 4
2 null
3 1,2
4 2
5 1,2,4

Expected Result

ID Dependency
2 null
4 2
1 4
3 1,2
5 1,2,4

I have no prior experience in Postgres, I found this very useful:

SELECT aa.dep_id::integer FROM unnest(string_to_array(ss.dependency, ',')) aa(dep_id)

But still, I can't make it right.

EDIT: Added one row with 3 dependencies'

http://sqlfiddle.com/#!15/894c3/4

Upvotes: 1

Views: 268

Answers (2)

Laurenz Albe
Laurenz Albe

Reputation: 247215

Use a recursive CTE:

WITH RECURSIVE o AS (
      SELECT ss.id, ss.dependency,
             1 AS level
      FROM ss
      WHERE dependency IS NULL
   UNION ALL
      SELECT ss.id, ss.dependency,
             o.level + 1
      FROM ss
         JOIN o
            ON o.id IN (SELECT x
                        FROM unnest(ss.dependency) AS x(x)
                       )
)
SELECT o.id, o.dependency
FROM o
GROUP BY o.id, o.dependency
ORDER BY max(o.level);

Upvotes: 3

German
German

Reputation: 126

My working solution, I hope it can be improved

DO $do$
DECLARE v_RowCountInt  Int;
--copy all values to temp table
begin
--This is the origin table, all rows to sort
drop table if exists _tempAll;
create temp table _tempAll as select id, dependency from XXXXX;

-- create temp table for results
drop table if exists _tempSort;
create temp table _tempSort (
id integer
,dependency varchar
,pos serial primary key);

  -- move all IDs with no depencencies
WITH tmp AS (DELETE FROM _tempAll where dependency is null RETURNING id, dependency)
    INSERT INTO _tempSort ( id, dependency) 
    SELECT id, dependency FROM tmp;


GET DIAGNOSTICS v_RowCountInt = ROW_COUNT;

 while v_RowCountInt>0 loop

    -- move rows with all dependencies met     
 
    WITH tmp AS (DELETE FROM _tempAll a   
        where a.id in(SELECT  a.id FROM _tempSort s inner join _tempAll a on
                    s.id in (select split.dep_sid::integer  from unnest(string_to_array(a.dependency, ',')) split(dep_sid))
                    group by a.id, a.dependency
                    -- verify all dependencies are already sorted
                    having count(*)=(CHAR_LENGTH(a.dependency) - CHAR_LENGTH(REPLACE(a.dependency, ',', ''))+1))
        RETURNING a.id, a.dependency)
        INSERT INTO _tempSort (id, dependency) 
        SELECT id, dependency FROM tmp;

    GET DIAGNOSTICS v_RowCountInt = ROW_COUNT;

end loop;

end;
$do$

Upvotes: 0

Related Questions