Simplify redundant EXISTS

[sopel39]

Example query tpch/q21:

  AND EXISTS (
    SELECT 
      * 
    FROM 
      "lineitem" l2
    WHERE 
      l2.orderkey = l1.orderkey
      AND l2.suppkey <> l1.suppkey
  ) 
  AND NOT EXISTS (
    SELECT 
      * 
    FROM 
      "lineitem" l3
    WHERE 
      l3.orderkey = l1.orderkey 
      AND l3.suppkey <> l1.suppkey 
      AND l3.receiptdate > l3.commitdate
  ) 

With subquery canonicalisation and CommonSubqueryExtractor we can determine that first EXISTS is super set of the other. Let’s say A is represents:

SELECT 
      * 
    FROM 
      "lineitem" l2
    WHERE 
      l2.orderkey = l1.orderkey
      AND l2.suppkey <> l1.suppkey

and B represents:

SELECT 
      * 
    FROM 
      "lineitem" l3
    WHERE 
      l3.orderkey = l1.orderkey 
      AND l3.suppkey <> l1.suppkey 
      AND l3.receiptdate > l3.commitdate

with CommonSubqueryExtractor we can figure that adaptation predicate from A to B is l3.receiptdate > l3.commitdate. Therefore we can rewrite two EXISTS into single one with principle: C = A - B, which is A AND NOT (adaptation_predicate) which is

EXISTS (
    SELECT 
      * 
    FROM 
      "lineitem" l2
    WHERE 
      l2.orderkey = l1.orderkey
      AND l2.suppkey <> l1.suppkey
      AND NOT l3.receiptdate > l3.commitdate
  )

[sopel39]

Similarly we can eliminate overlapping IN-list predicates, e.g: tpch/q95:

AND ("ws1".ws_order_number IN (SELECT ws_order_number FROM ws_wh))
AND ("ws1".ws_order_number IN (SELECT wr_order_number FROM web_returns , ws_wh
WHERE (wr_order_number = ws_wh.ws_order_number)))

or simpler case:

AND col1 IN (SELECT col2 FROM table2) 
AND col1 IN (SELECT col2 FROM table2 WHERE col3 > 10) 

we could try to compute common subplan for such subplans and then it will be obvious that one subplan is superset of the other. In such case we can just remove one, redundant IN conjunct.

We can also extract common subplan for joins as in case of q95 common subquery can be LEFT JOIN with adaptation predicate on top.