Postgresql – How to join two columns and find unique combinations

distinctjoin;postgresql

I have the following topological structure (topo) with their types:

id(string) |   id_from(string) | id_to(string) | type(string) 
 '111'     |    'aaa'          |   'bbb'       |   'type1'  
 '222'     |    'bbb'          |   'ccc'       |   'type2' 
 '333'     |    'ddd'          |   'bbb'       |   'type3'

Now I want to find all distinct connected type-combinations

id_from = id_to OR
id_to = id_to OR 
id_from = id_from

The result should look like this:

type_from(string) | type_to(string) 
    'type1'       |      'type2'    
    'type2'       |      'type3'   
    'type1'       |      'type3'

My first approach is to create an index on id , id_from , id_to. The SQL query i tried is:

WITH p AS
( 
   SELECT DISTINCT ON ( id ) id , from , to , type FROM topo 
)
SELECT DISTINCT ON( p.type , t.type ) 
p.type AS type_a , t.type AS type_b FROM p
JOIN topo t ON 
t.id_from = p.id_to OR 
t.id_to = p.id_to OR 
t.id_from = p.id_from

It works but it takes several minutes without an result. Any way to achieve this (faster)?

EDIT: I'm not even sure if this query can be done much faster for several million rows. My current best solution is to compute this query once and to store it as an combination table. Whenever I need this values, I just query the combination table.

Best Answer

Try something like

    SELECT LEAST(t1.type, t2.type), GREATEST(t1.type, t2.type)
    FROM topo t1, topo t2
    WHERE t1.id_from = t2.id_to
UNION
    SELECT LEAST(t1.type, t2.type), GREATEST(t1.type, t2.type)
    FROM topo t1, topo t2
    WHERE t1.id_from = t2.id_from
      AND t1.id > t2.id
UNION
    SELECT LEAST(t1.type, t2.type), GREATEST(t1.type, t2.type)
    FROM topo t1, topo t2
    WHERE t1.id_to = t2.id_to
      AND t1.id > t2.id
Related Question