How to hierarchical query in PostgreSQL with language-dependent data

Question

I am trying to retrieve a hierarchical ordered result from a query on an auto referenced table like this:

create table category (
  id          serial,
  
  -- parent category, 
  parent_id   integer default null, -- null for root category
  
  -- tree control
  tree_depth  smallint not null, -- calculated

  primary key (id),
  unique (parent_id, id),
  foreign key (parent_id) references category (id)
);

This is a common approach to store a tree of categories except for the need for supporting multiple languages. To that aim, we join a language-dependent table like this:

create table category_lang (
  id            serial,
  
  -- natural primary key
  category_id   integer not null,
  lang_code     char(2) not null,
  
  -- language-dependent data
  title         varchar(128) not null,
  
  primary key (id),
  unique (category_id, lang_code)
);

The tree_depth column is calculated in a before insert trigger like this:

create or replace function fn_category__bins () returns trigger as $$
begin
  -- calculate tree_depth as parent tree_depth + 1
  if new.parent_id is null then
    new.tree_depth = 0;
  else
    new.tree_depth = (select tree_depth from category where id = new.parent_id limit 1) + 1;
  end if;

  return new;
end;
$$ language plpgsql;

create trigger tg_category__bins before insert on category for each row
execute procedure fn_category__bins();

We populate the tables with easy to read texts in two languages:

insert into category (parent_id, id) values 
(null, 1),
(null, 2),
(null, 3),

(1, 11),
(1, 12),
(1, 13),

(2, 21),
(2, 22),
(3, 31),

(21, 211),
(21, 212),
(21, 213);

-- lang_code = 'EN'
insert into category_lang (category_id, title, lang_code) values 
(1, 'One',   'EN'),
(2, 'Two',   'EN'),
(3, 'Three', 'EN'),

(11, 'One.One',   'EN'),
(12, 'One.Two',   'EN'),
(13, 'One.Three', 'EN'),

(21, 'Two.One',   'EN'),
(22, 'Two.Two',   'EN'),
(31, 'Three.One', 'EN'),

(211, 'Two.One.One',   'EN'),
(212, 'Two.One.Two',   'EN'),
(213, 'Two.One.Three', 'EN');

-- lang_code = 'ES'
insert into category_lang (category_id, title, lang_code) values 
(1, 'Uno',  'ES'),
(2, 'Dos',  'ES'),
(3, 'Tres', 'ES'),

(11, 'Uno.Uno',  'ES'),
(12, 'Uno.Dos',  'ES'),
(13, 'Uno.Tres', 'ES'),

(21, 'Dos.Uno',  'ES'),
(22, 'Dos.Dos',  'ES'),
(31, 'Tres.Uno', 'ES'),

(211, 'Dos.Uno.Uno',  'ES'),
(212, 'Dos.Uno.Dos',  'ES'),
(213, 'Dos.Uno.Tres', 'ES');

A plain query produces a natural result like this:

select * from category tc 
left outer join category_lang tl on tl.category_id = tc.id and tl.lang_code = 'EN';

id |parent_id|tree_depth|id|category_id|lang_code|title        |
---|---------|----------|--|-----------|---------|-------------|
  1|         |         0| 1|          1|EN       |One          |
  2|         |         0| 2|          2|EN       |Two          |
  3|         |         0| 3|          3|EN       |Three        |
 11|        1|         1| 4|         11|EN       |One.One      |
 12|        1|         1| 5|         12|EN       |One.Two      |
 13|        1|         1| 6|         13|EN       |One.Three    |
 21|        2|         1| 7|         21|EN       |Two.One      |
 22|        2|         1| 8|         22|EN       |Two.Two      |
 31|        3|         1| 9|         31|EN       |Three.One    |
211|       21|         2|10|        211|EN       |Two.One.One  |
212|       21|         2|11|        212|EN       |Two.One.Two  |
213|       21|         2|12|        213|EN       |Two.One.Three|

when the expected order should be compliant with tree hierarchy and alphabetical order in English (at every depth level), like this:
[Edited to fix the error identified by Erwin]

id |parent_id|tree_depth|id|category_id|lang_code|title        |
---|---------|----------|--|-----------|---------|-------------|
  1|         |         0| 1|          1|EN       |One          |
 11|        1|         1| 4|         11|EN       |One.One      |
 13|        1|         1| 6|         13|EN       |One.Three    |
 12|        1|         1| 5|         12|EN       |One.Two      |
  3|         |         0| 3|          3|EN       |Three        |
 31|        3|         1| 9|         31|EN       |Three.One    |
  2|         |         0| 2|          2|EN       |Two          |
 21|        2|         1| 7|         21|EN       |Two.One      |
211|       21|         2|10|        211|EN       |Two.One.One  |
213|       21|         2|12|        213|EN       |Two.One.Three|
212|       21|         2|11|        212|EN       |Two.One.Two  |
 22|        2|         1| 8|         22|EN       |Two.Two      |

Note that the alphabetical order at every depth forces a different result for Spanish:
[Edited to fix the error identified by Erwin]

id |parent_id|tree_depth|id|category_id|lang_code|title       |
---|---------|----------|--|-----------|---------|------------|
  2|         |         0|14|          2|ES       |Dos         |
 22|        2|         1|20|         22|ES       |Dos.Dos     |
 21|        2|         1|19|         21|ES       |Dos.Uno     |
212|       21|         2|23|        212|ES       |Dos.Uno.Dos |
213|       21|         2|24|        213|ES       |Dos.Uno.Tres|
211|       21|         2|22|        211|ES       |Dos.Uno.Uno |
  1|         |         0|13|          1|ES       |Uno         |
 12|        1|         1|17|         12|ES       |Uno.Dos     |
 13|        1|         1|18|         13|ES       |Uno.Tres    |
 11|        1|         1|16|         11|ES       |Uno.Uno     |
  3|         |         0|15|          3|ES       |Tres        |
 31|        3|         1|21|         31|ES       |Tres.Uno    |

I have tried a number of approaches, including a recursive CTE as in https://www.postgresql.org/docs/12/queries-with.html, but none seems to cope with the problem of different orders for different languages.

Any ideas?

Answer 1

... the expected order should be compliant with tree hierarchy and alphabetical order in English (at every depth level),

The additional difficulty is that category_lang(title, lang_code) is not defined UNIQUE, so we need to sort by title and category_id (as tiebreaker) on every level - which is hard to implement for a dynamic number of levels. An array of composite type can solve the conundrum.

Your displayed results do not currently comply with your requirement. 'Three' should sort before 'Two' according to English sorting rules. The result of the following query implements your requirement:

Create once per database:

CREATE TYPE title_id AS (title varchar(128), id int);

Then use a recursive CTE to generate an array of this composite type according to its path.

WITH RECURSIVE tree AS (
   SELECT c.id AS cat_id, c.parent_id, c.tree_depth
        , l.id AS lang_id, l.title, l.lang_code
        , ARRAY[(l.title, l.category_id)::title_id] AS sort_arr
   FROM   category      c 
   JOIN   category_lang l ON l.category_id = c.id
                         AND l.lang_code = 'EN'
   WHERE  c.parent_id IS NULL  -- root cat

   UNION ALL
   SELECT c.id AS cat_id, c.parent_id, c.tree_depth
        , l.id AS lang_id, l.title, l.lang_code
        , sort_arr || (l.title, l.category_id)::title_id
   FROM   tree          t
   JOIN   category      c ON c.parent_id = t.cat_id
   JOIN   category_lang l ON l.category_id = c.id
                         AND l.lang_code = t.lang_code
    )
SELECT cat_id, parent_id, tree_depth, lang_id, title 
FROM   tree
ORDER  BY sort_arr;

db<>fiddle here

Closely related with more explanation and details:

• Retrieving full hierarchy sorted by a column under PostgreSQL's Ltree module

COLLATE?

But that's not all. The simple solution sorts by the default collation of your database, which seems inappropriate for different languages.

Every language has its own collation rules, or typically several of them, depending on the region of the world and other political / cultural rules. The "language" is not enough to specify exact rules for sorting. The precise locale matters. Postgres implements collation-aware sorting with the COLLATE keyword. You would have to store the actual precise collation in addition to the language, and use it to sort properly.

Also, indexes depend on the exact COLLATION. You might consider multiple partial indexes with different collation. Lots of tricky stuff that goes beyond the scope of this question. See:

• How to choose a collation for international database?
• PostgreSQL 9.1 using collate in select statements

Asides

• Your trigger is not safe against race conditions between concurrent writes. For the purpose of this query we do not need a persisted tree_depth at all. We could easily generate it in the rCTE. Consider dropping the column tree_depth and the trigger.

• A FK constraint seems to be missing in table category_lang:

   , FOREIGN KEY (category_id) REFERENCES category (id)
  

• Consider text instead of varchar(n) and char(n). See:

  • Any downsides of using data type "text" for storing strings?
  • Should I add an arbitrary length limit to VARCHAR columns?

• Consider an IDENTITY column instead of serial:

  • Auto increment table column

Answer 2

Before Erwin answered with a much simpler solution, I made this recursive approach by myself. It works better inserting a virtual root category, which allow us to retrive the whole tree from a single entry point.

create or replace function list_category_tree (
    _category_id integer,
    _lang_code char(2)
)
returns setof category
as $$
declare
    _child_category category;
begin
    -- return the passed category
    return query
    select * from category where id = _category_id;

    -- loop over the passed category children
    for _child_category in 
        select tc.* 
        from category tc
        join category_lang tl on tl.category_id = tc.id and tl.lang_code = _lang_code
        where tc.parent_id = _category_id
        order by tl.title asc
    loop
        -- recursively look for every children childrens
        return query 
        select * from list_category_tree(_child_category.id, _lang_code);
    end loop;
end;
$$ language plpgsql;

A simple test could be

select * 
from list_category_tree (0, 'EN') as tc
join category_lang tl on tl.category_id = tc.id and tl.lang_code = 'EN';

id |parent_id|tree_depth|id|category_id|lang_code|title        |
---|---------|----------|--|-----------|---------|-------------|
  1|         |         0| 1|          1|EN       |One          |
 11|        1|         1| 4|         11|EN       |One.One      |
 13|        1|         1| 6|         13|EN       |One.Three    |
 12|        1|         1| 5|         12|EN       |One.Two      |
  2|         |         0| 2|          2|EN       |Two          |
 21|        2|         1| 7|         21|EN       |Two.One      |
211|       21|         2|10|        211|EN       |Two.One.One  |
213|       21|         2|12|        213|EN       |Two.One.Three|
212|       21|         2|11|        212|EN       |Two.One.Two  |
 22|        2|         1| 8|         22|EN       |Two.Two      |
  3|         |         0| 3|          3|EN       |Three        |
 31|        3|         1| 9|         31|EN       |Three.One    |


select * 
from list_category_tree (0, 'ES') as tc
join of_category_lang tl on tl.category_id = tc.id and tl.lang_code = 'ES';

id |parent_id|tree_depth|id|category_id|lang_code|title       |
---|---------|----------|--|-----------|---------|------------|
  2|        0|         1|14|          2|ES       |Dos         |
 22|        2|         2|20|         22|ES       |Dos.Dos     |
 21|        2|         2|19|         21|ES       |Dos.Uno     |
212|       21|         3|23|        212|ES       |Dos.Uno.Dos |
213|       21|         3|24|        213|ES       |Dos.Uno.Tres|
211|       21|         3|22|        211|ES       |Dos.Uno.Uno |
  3|        0|         1|15|          3|ES       |Tres        |
 31|        3|         2|21|         31|ES       |Tres.Uno    |
  1|        0|         1|13|          1|ES       |Uno         |
 12|        1|         2|17|         12|ES       |Uno.Dos     |
 13|        1|         2|18|         13|ES       |Uno.Tres    |
 11|        1|         2|16|         11|ES       |Uno.Uno     |

having inserted the root node as

insert into of_category (parent_id, id) values 
(null, 0),

(null, 1),
(null, 2),
(null, 3),

(1, 11),
(1, 12),
(1, 13),

(2, 21),
(2, 22),
(3, 31),

(21, 211),
(21, 212),
(21, 213);

-- lang_code = 'EN'
insert into of_category_lang (category_id, title, lang_code) values 
(0, 'Root', 'EN'),

(1, 'One',   'EN'),
(2, 'Two',   'EN'),
(3, 'Three', 'EN'),

(11, 'One.One',   'EN'),
(12, 'One.Two',   'EN'),
(13, 'One.Three', 'EN'),

(21, 'Two.One',   'EN'),
(22, 'Two.Two',   'EN'),
(31, 'Three.One', 'EN'),

(211, 'Two.One.One',   'EN'),
(212, 'Two.One.Two',   'EN'),
(213, 'Two.One.Three', 'EN');

-- lang_code = 'ES'
insert into of_category_lang (category_id, title, lang_code) values 
(0, 'Raíz', 'ES'),

(1, 'Uno',  'ES'),
(2, 'Dos',  'ES'),
(3, 'Tres', 'ES'),

(11, 'Uno.Uno',  'ES'),
(12, 'Uno.Dos',  'ES'),
(13, 'Uno.Tres', 'ES'),

(21, 'Dos.Uno',  'ES'),
(22, 'Dos.Dos',  'ES'),
(31, 'Tres.Uno', 'ES'),

(211, 'Dos.Uno.Uno',  'ES'),
(212, 'Dos.Uno.Dos',  'ES'),
(213, 'Dos.Uno.Tres', 'ES');