Recursive/iterative reduce in PostgreSQL

Question

I'm battling with recursive CTEs at the moment as I need to reference the resulting output of the CTE so far in each loop.

What I'm trying to do is take a table like this:

| suggestions |
| ----------- |
| id | label  |
| ----------- |
|  1 | item-1 |
|  1 | item-2 |
|  2 | item-1 |
|  2 | item-2 |
|  3 | item-1 |
|  3 | item-2 |

And reduce it to one selected row per id:

| selected_suggestions |
| -------------------- |
| id |  label  | taken |
| -------------------- |
|  1 | item-1  | false |
|  2 | item-2  | false | (item-1 was taken by id=1, but item-2 was available)
|  3 | item-1  | true  | (item-1 and item-2 both taken)

So for each id, it selects one of the suggestions that ideally hasn't already been taken by a prior id.

This is my attempt so far:

with recursive suggestions (id, label) as (
  values
    (1, 'item-1'),
    (1, 'item-2'),
    (2, 'item-1'),
    (2, 'item-2'),
    (3, 'item-1'),
    (3, 'item-2')
),

chosen_suggestions as (
  -- these are the rows we're iterating over
  -- they are all set to selected = false so they can be filtered out at the end
  (
    select
      *,
      false as taken,
      false as selected
    from
      suggestions
    order by
      id asc,
      label asc
  )

  union

  -- for each of the rows above, Postgres calls this section
  (
    select
      suggestions.*,
      count(already_chosen_suggestions) > 0 as taken,
      true as selected

    from
      suggestions

    -- join any suggestions already selected with the same label
    left join chosen_suggestions already_chosen_suggestions on
      already_chosen_suggestions.label = suggestions.label and
      already_chosen_suggestions.selected = true

    -- select all the suggestions for this row, where we don't already have a suggestion for this item (so we don't select multiple selections for a given `id`)
    where
      suggestions.id = chosen_suggestions.id and
      suggestions.id not in (select id from chosen_suggestions where selected = true)

    -- favour unused suggestions, then default to alphabetical
    order by
      case when count(already_chosen_suggestions) = 0 then 0 else 1 end asc,
      label asc

    -- we only want one suggestion per original row
    limit 1
  )
)

-- filter out all the unselected suggestions
select id, label, taken from chosen_suggestions where selected = true;

Unfortunately, this gives me a syntax error:

recursive reference to query "chosen_suggestions" must not appear within an outer join

I've tried replacing with subqueries, but this also is not allowed by PostgreSQL. At this point, I'm wondering if there's a wholly different approach I should be considering that I'm simply not aware of?

Answer 1

I've solved the problem with pgplsql:

create type suggestion as (id int, label text, selected boolean);

create function select_suggestions(suggestions suggestion[]) returns setof suggestion as $$
  declare
    current_record suggestion;
    chosen_suggestion suggestion;
    chosen_suggestions suggestion[];
  begin
    chosen_suggestions := array[]::suggestion[];
  
    <<input_selections>>
    foreach current_record in array suggestions     
    loop 
      foreach chosen_suggestion in array chosen_suggestions
      loop
        if chosen_suggestion.id = current_record.id or chosen_suggestion.label = current_record.label then
          continue input_selections;
        end if;
      end loop;
      
      chosen_suggestions := array_append(chosen_suggestions, current_record);
    end loop;

    return query
      select
        suggestions.id,
        suggestions.label,
        chosen_suggestions.label is not null as selected
      from
        unnest(suggestions) as suggestions(id, label)
      left join
        unnest(chosen_suggestions) as chosen_suggestions(id, label) on
          chosen_suggestions.id = suggestions.id and
          chosen_suggestions.label = suggestions.label;
  end;
$$ language plpgsql;

with suggestions (id, label) as (
  values
    (1, 'item-1'),
    (1, 'item-2'),
    (2, 'item-1'),
    (2, 'item-2'),
    (3, 'item-1'),
    (3, 'item-2'),
    (4, 'item-4')
)

select distinct on (id)
  id,
  case
    when selected = true then label
    else null
  end as label
from
  select_suggestions(array(select (id, label, false)::suggestion from suggestions))
order by
  id asc,
  selected desc;

This outputs the rows as expected:

id | label 
---+-------
 1 | item-1
 2 | item-2
 3 | (null)