Re: Proposal for Merge Join for Non '=' Operators

On 09 April 2014 19:14, Tom Lane Wrote:
>
> I'm not following how this would help much. Consider "a.x < b.y" where
> we know that the inputs are sorted by x/y. I think you are saying that
> for a given b row, we could scan forward from the beginning of a, but
> stop as soon as we find a row with a.x >= b.y. Great ... but instead
> of comparing M*N rows, we are comparing M*N/2 rows. So it's still
> O(N^2), though with a slightly smaller constant. Is this going to be
> worth the added time to sort the inputs?
>
> It's slightly more promising for range constraints (that is, "a.x
> between b.y and b.z") but even then you have to assume that the ranges
> are narrow, at which point a nestloop join using an inner indexscan on
> a.x might do about as well.
>
> So personally, I suspect there's a reason why this isn't a standard
> join algorithm already. If you want to try it, I'd suggest that you
> focus on getting to where you can do some performance testing ASAP,
> without doing much code polishing or worrying about teaching the
> planner how to cost it.

As per your suggestion have done quick hack and done the performance testing for one specific scenario.

I shall perform some more test, for that I need to do some more hack in the code and I will post them soon..

Test Scenario:
Create table t1 (a int, b int);
Create table t2 (a int, b int);

Random record inserted in t1 and t2, as per attached files. (10K records are inserted in both the tables)

Performance is taken for the query : select count(*) from t1,t2 where t1.b < t2.b;

Test Result:
Nest Loop Join : Time: 36038.842 ms
Merge Join : Time: 19774.975 ms

Number of record selected: 42291979

Thanks & Regards,
Dilip