[PATCH] Equivalence Class Filters

We can see that a qual was added to filter t2.id=1.

As of today these Equivalence Classes only incorporate expressions which use the equality operator, but what if the above query had been written as:

                                  QUERY PLAN

------------------------------------------------------------------------------

 Merge Join  (cost=0.56..5.68 rows=1 width=12)

   Merge Cond: (t1.id = t2.id)

   ->  Index Scan using t1_pkey on t1  (cost=0.29..8.44 rows=9 width=8)

         Index Cond: (id <= 10)

   ->  Index Only Scan using t2_pkey on t2  (cost=0.28..4.45 rows=10 width=4)

         Index Cond: (id <= 10)

Now, it may not be that common to perform range filters on an id column, but it can be fairly common for date values to be join conditions and have date range filters too. For example in [1] Alexandre claimed a 1100 to 2200 performance improvement after manually pushing the date filter into the subquery. This patch allows this to become automatic.

This all works by simply just collecting OpExprs during building the EquivalanceClasses which have previously been rejected for the eqclass because they don't use an equality operator. OpExprs in the form of "Expr op Const" and "Const op Expr" are collected, and then once the EquivalanceClasses have been build the "Expr" is searched for in the built classes to see if we can find that Expr as a member of a class, if so this then becomes an EquivalenceFilter and gets tagged onto to the EquivalenceClass.

Patch Status - I'm a bit uncertain as to how far we can go with this and if we deem this as a good idea, then we'd need to be careful not to cause any performance regression. For example if the filter was "somestaticfunc(col) < 1234", then we might not want to push that down as somestaticfunc() might be so costly, that it might be better to perform the join with all the rows instead.  For this reason I've limited the current patch to only using Operators which are members of a btree op class. Perhaps we could do more, but likely there's less of a win to be had due to less chance of that qual being useful for an index scan.

Writing this patch has been on my "interesting" list for a while now. I got some time last weekend to finally write it, but due to that happening at the weekend rather than in work time it's a low priority for me to. However there's no sense in it gathering dust, so I'm posting it today.

Is this something that we might want?

[1] http://www.postgresql.org/message-id/CAGewt-tbqRW5NLAzKDCvP_ztEN_LMMyGugQ1iVVEzB+p2XpefQ@mail.gmail.com