How to make this SQL query reasonably fast

Question 1

I could make it work with the following query:

WITH relevant_a AS (
    SELECT * FROM A 
        WHERE
            foo BETWEEN foo_min AND foo_max 
            AND
            bar BETWEEN bar_min AND bar_max
),
relevant_c AS (
    SELECT * FROM C
        WHERE l_id IN (
            SELECT l_id FROM B
                WHERE n1_id IN (
                    SELECT n_id FROM relevant_a
                )
            UNION
            SELECT l_id FROM B
                WHERE n2_id IN (
                    SELECT n_id FROM relevant_a
                )
        )
        AND
        (property1 = 'Y' OR property2= 'Y')
),
relevant_b AS (
    SELECT * FROM B WHERE l_id IN (
        SELECT l_id FROM relevant_c
    )
),
a1_data AS (
    SELECT A.n_id, A.foo, A.bar
    FROM A
    WHERE A.n_id IN (
        SELECT n1_id FROM relevant_b
    )
)
a2_data AS (
    SELECT A.n_id, A.foo, A.bar
    FROM A
    WHERE A.n_id IN (
        SELECT n2_id FROM relevant_b
    )
)

SELECT relevant_b.*, a1_data.foo,  a1_data.bar,  a2_data.foo,  a2_data.bar 
FROM relevant_b
LEFT JOIN a1_data ON relevant_b.n1_id = a1_data.n_id
LEFT JOIN a2_data ON relevant_b.n2_id = a2_data.n_id

I do not like this solution as it seems forced and redundant. However, it gets the job done in < 0.1 s.

I still refuse to believe that an SQL noob like me can (quite easily in retrospect) come up with a statement that forces the optimizer to use a strategy much better than the one it comes up with on its own. There has to be a better solution but I will not be looking for one anymore.

Regardless, thank you all for your suggestions, I definetely learned a few things on the way.

Question 2

Or something like this:

SELECT B.*, A1.foo, A2.bar 
FROM B 
     LEFT JOIN A as A1 on B.n1_id = A1.n_id 
     LEFT JOIN A as A2 on B.n2_id = A2.n_id 
     INNER JOIN C on (C.l_id = B.l_id)
where 
     A1.foo between A1.foo_min AND A1.foo_max AND 
     A2.bar BETWEEN A2.bar_min AND A2.bar_max and
     b.foo between b.foo_min AND b.foo_max AND 
     b.bar BETWEEN b.bar_min AND bar_max   AND
     (C.property1 = 'Y' OR C.property2 = 'Y')

Question 3

You could club both the Left joins on A (A1,A2) into 1 Left join and use a OR for the ON Clause
Change INs to Exists
Change the UNION into 1 query using a OR Clause

Try this...

    SELECT B.*
    , A1.foo
    , A2.bar
FROM B
LEFT JOIN A AS A1
    ON (
            B.n1_id = A1.n_id
            OR B.n2_id = A1.n_id
            )
WHERE EXISTS (
        SELECT l_id
        FROM C
        WHERE EXISTS (
                SELECT l_id
                FROM B
                WHERE EXISTS (
                        SELECT n_id
                        FROM A
                        WHERE foo BETWEEN foo_min
                                AND foo_max
                            AND bar BETWEEN bar_min
                                AND bar_max
                            AND (
                                A.n_id = B.n_id
                                OR A.n_id = B.n2_id
                                )
                        )
                    AND B.l_id = C.l_id
                )
        )

Question 4

There should be only one index for both columns foo and bar in Table A, so this would be optimal for both between clauses (find by your self witch would be the better columns order) Table B is not optimally designed for this query, you should traspose values n1_id and n2_id in 2 different rows with same key and column_id (crosstab).

The follwing query should return then same data with a huge perfomance improvement.

with b_norm(l_id, role, n_id) as (
        select l_id, unnest(Array['1','2']) as role, unnest(Array[n1_id, n2_id]) as n_id
        from b
    )
select *
from (
        select distinct l_id
        from a
            join b_norm using (n_id)
            join c using (l_id)
        where bar between 0 and 10000
            and foo between 10000 and 20000
            and (c.property1 = 'Y' or c.property2 = 'Y')
    ) as driver
    join b using (l_id)
    join (
        select a.n_id as n1_id, foo as foo1, bar as bar1
        from a
    )  as a1 using (n1_id)
    join (
        select a.n_id as n2_id, foo as foo2, bar as bar2
        from a
    ) as a2 using (n2_id);

Question 5

As far as I see it, you select B where at least one of the two associated As is within the given ranges. Moreover you require there exists a C for the B. Then you show foo and bar of the two associated As with the B values.

SELECT B.*, A1.foo, A2.bar
FROM B 
LEFT JOIN A A1 ON A1.n_id = B.n1_id
LEFT JOIN A A2 ON A2.n_id = B.n2_id
WHERE 
(
  (A1.foo BETWEEN foo_min AND foo_max AND A1.bar BETWEEN bar_min AND bar_max)
  OR
  (A2.foo BETWEEN foo_min AND foo_max AND A2.bar BETWEEN bar_min AND bar_max)
)
AND EXISTS
(
  SELECT *
  FROM C
  WHERE C.l_id = B.l_id
  AND (property1 = 'Y' OR property2 = 'Y')
);

Can B.n1_id and B.n2_id be NULL? Then you need the left outer joins. Otherwise you can replace them with inner joins.

EDIT: Oops I missed the C criteria. I've altered the statement accordingly.

EDIT: Reacting to your comments, here is the same select with INNER JOINs and an IN clause:

SELECT B.*, A1.foo, A2.bar
FROM B 
INNER JOIN A A1 ON A1.n_id = B.n1_id
INNER JOIN A A2 ON A2.n_id = B.n2_id
WHERE 
(
  (A1.foo BETWEEN foo_min AND foo_max AND A1.bar BETWEEN bar_min AND bar_max)
  OR
  (A2.foo BETWEEN foo_min AND foo_max AND A2.bar BETWEEN bar_min AND bar_max)
)
AND B.l_id IN
(
  SELECT l_id
  FROM C
  WHERE property1 = 'Y' OR property2 = 'Y'
);