Optimization idea: merging multiple EXISTS(...) with constraint-based join removal - Mailing list pgsql-hackers

I've frequently encountered queries where the WHERE clause contains a lot of "EXISTS(...)" subqueries linked by logical ANDs. They are typically generated queries, and the "EXISTS(...)" fragments are composable pieces of SQL code acting as filters. Moreover, all those filters ends up being very similar: the joins used to navigate in the objects graph often involves the same tables.

Unfortunately, PostgreSQL doesn't seem to be smart enough to simplify them. In fact, according to my experiments, even dead-simple uncorrelated subqueries such as "SELECT * FROM t1 WHERE EXISTS(SELECT * FROM t2) AND EXISTS(SELECT * FROM t2)" are not simplified. (the execution plan is rather naive: t2 is checked twice for non-emptiness).

I've not seen anything related to that topic on the TODO list or in the mailing list. Consequently, I would like to propose a method which can be used to merge multiple EXISTS(...) semi-joins linked by logical ANDs.

For the sake of this example, the database schema is:

    create table t1(id int primary key, t2_id int, t6_id int)

    create table t2(id int primary key, t3_id int)

    create table t3(id int primary key, t4_id int, t5_id int)

    create table t4(id int primary key, val text)

    create table t5(id int primary key, val text)

    create table t6(id int primary key, val text)

Here is a machine-generated query. Notice that the path "t1->t2->t3" is used twice. 

    SELECT * FROM t1

    WHERE EXISTS(

        SELECT 1 FROM t2, t3, t4

        WHERE t2.id = t1.t2_id

        AND t3.id = t2.t3_id

        AND t4.id = t3.t4_id

        AND t4.val = 'XYZ'

    ) AND EXISTS(

        SELECT 1 FROM t2, t3, t5

        WHERE t2.id = t1.t2_id

        AND t3.id = t2.t3_id

        AND t5.id = t3.t5_id

        AND t5.val = 'Blablabla'

    ) AND EXISTS(

        SELECT 1 FROM t6

        WHERE t6.id = t1.t6_id

        AND t6.val = 'Hello'

    )

The following transformation can be applied:

    SELECT * FROM [...]

    WHERE

        EXISTS(SELECT 1 FROM [...tables_1...] WHERE [...conditions_1...])

    AND EXISTS(SELECT 1 FROM [...tables_2...] WHERE [...conditions_2...])

        <=>

    SELECT * FROM [...]

    WHERE

        EXISTS(

            SELECT 1 FROM

                (SELECT 1 FROM [...tables_1...] WHERE [...conditions_1...]) q1,

                (SELECT 1 FROM [...tables_2...] WHERE [...conditions_2...]) q2

        )

The resulting query is:

    SELECT * FROM t1

        WHERE EXISTS(

            SELECT 1 FROM t2 t2_a, t3 t3_a, t4 t4_a, t2 t2_b, t3 t3_b, t5, t6

            WHERE t2_a.id = t1.t2_id

            AND t3_a.id = t2_a.t3_id

            AND t4_a.id = t3_a.t4_id

            AND t4_a.val = 'XYZ'

            AND t2_b.id = t1.t2_id

            AND t3_b.id = t2_b.t3_id

            AND t5.id = t3_b.t5_id

            AND t5.val = 'Blablabla'

            AND t6.id = t1.t6_id

            AND t6.val = 'Hello'

        )

Given the constraints, it can be shown that t2_a = t2_b AND t3_a = t3_b :

    * t2_a.id = t1.t2_id AND t2_b.id = t1.t2_id => t2_a.id = t2_b.id

    * t2_a.id = t2_b.id AND t2(id) is a pkey => t2_a = t2_b

    * t2_a = t2_b => t2_a.t3_id = t2_b.t3_id

    * t2_a.t3_id = t2_b.t3_id AND t3_b.id = t2_b.t3_id AND t3_a.id = t2_a.t3_id => t3_b.id = t3_a.id

    * t3_b.id = t3_a.id AND t3(id) is a pkey => t3_a = t3_b

It is then safe to remove the joins "t2_b" and "t3_b" in the subquery, because they have been proved to be duplicates of "t2_a" and "t3_a".

    SELECT * FROM t1

        WHERE EXISTS(

            SELECT 1 FROM t2, t3, t4, t2, t3, t5, t6

            WHERE t2.id = t1.t2_id

            AND t3.id = t2.t3_id

            AND t4.id = t3.t4_id

            AND t5.id = t3.t5_id

            AND t4.val = 'XYZ'

            AND t5.val = 'Blablabla'

            AND t6.id = t1.t6_id

            AND t6.val = 'Hello'

        )

Using a connected component analysis on join predicates, joined tables can be separated and we get back our original query with the first two EXISTS(...) semi-joins merged.

    SELECT * FROM t1

        WHERE EXISTS(

            SELECT 1 FROM t2, t3, t4, t2, t3, t5

            WHERE t2.id = t1.t2_id

            AND t3.id = t2.t3_id

            AND t4.id = t3.t4_id

            AND t5.id = t3.t5_id

            AND t4.val = 'XYZ'

            AND t5.val = 'Blablabla'

        ) AND EXISTS(

            SELECT 1 FROM t6

            WHERE t6.id = t1.t6_id

            AND t6.val = 'Hello'

        )

My questions are:

- Does PostgreSQL already supports this optimization ? Maybe it's not enabled in my case only?

- If yes, is my reasoning incorrect ? Can you point me my mistake ?

- Otherwise is there any plan to add this optimization to PostgreSQL ?

Thank you !

Frédéric Terrazzoni