Proposal for Merge Join for Non '=' Operators

2014-04-09 Dilip kumar <dilip.kumar@huawei.com>:

I would like to propose a New merge join algorithm for optimizing non ‘=’
operators. (‘<’, ‘<=’, ‘>’, ‘>=’)

Do you have a real-world example use case of such joins, to offset the
extra planner time that will likely have to be paid (even for queries
for which the functionality ends up not being used)?

I guess there might be queries that join on “values that are not too
far apart” or something, but as those cases (there typically not being
a lot of “inner” rows that join with each “outer” row) are probably
executed efficiently using a nested loop + index scan, I don’t see the
point (yet). Are you aiming for the case where the inner relation is
difficult to compute and cannot be accessed using an index scan?

selecting this new cost calculation can be implemented in planner

Hmm. Of course, the difficult part will be adding support for this in
the planner, but you don’t seem to have any plans for implementing
that?

Nicolas

--
A. Because it breaks the logical sequence of discussion.
Q. Why is top posting bad?

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On 09 April 2014 13:31, Nicolas Barbier Wrote

Do you have a real-world example use case of such joins, to offset the
extra planner time that will likely have to be paid (even for queries
for which the functionality ends up not being used)?

I guess there might be queries that join on “values that are not too
far apart” or something, but as those cases (there typically not being
a lot of “inner” rows that join with each “outer” row) are probably
executed efficiently using a nested loop + index scan, I don’t see the
point (yet). Are you aiming for the case where the inner relation is
difficult to compute and cannot be accessed using an index scan?

I think this will be more useful when Both the relation are Big and are of almost equal size.

Here we can compare the cost of existing methods and new approach..

For such case planner can select
Either (1). NLJ [Outer(seq scan) JOIN Inner (Materialize))
OR (2). NLJ [Outer(seq scan) JOIN Inner (Index)) As you mentioned.

In approach (1), cost will be:
NLJ Cost : Outer Tuple * Inner Tuple
+ I/O cost : Seq Page Cost (Inner rel pages + outer rel pages).

* And relation can be too big for materialization.

In approach (2), Cost will be:
NLJ Cost : OuterTuple * Inner Tuple in Path { Inner Tuple in Path -> Join selectivity * Number of inner tuple}
+ I/O Cost : OuterTuple * Index Rescan Cost { Index Rescan Cost will depend upon (how many pages fetched in scan)}

* This will be costly because I/O cost will increase for doing multiple index rescan(for each outer).

In New Approach(3) Cost will be:
(since here for each outer tuple we need not to scan complete Inner Tuple.)
MJ Cost : Outer Tuple * Inner Tuple in Path + (every outer tuple need to scan some tuple before reach to qualifying tuple)
+ I/O Cost : Index Scan Cost {Only one scan}

So for This Best case cost will be : MJ Cost : Outer Tuple * Inner Tuple in Path + I/O Cost : Index Scan Cost
Worst case cost will be: MJ Cost : Outer Tuple * Inner Tuple + I/O Cost : Index Scan Cost

So for many case approach(3) can be cheaper, that can be detected by planner cost calculation.

selecting this new cost calculation can be implemented in planner

Hmm. Of course, the difficult part will be adding support for this in
the planner, but you don’t seem to have any plans for implementing that?

Yes, I have plan to implement this part, but it's not completed yet.

Thanks & Regards,
Dilip

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Dilip kumar <dilip.kumar@huawei.com> writes:

On 09 April 2014 13:31, Nicolas Barbier Wrote

Do you have a real-world example use case of such joins, to offset the
extra planner time that will likely have to be paid (even for queries
for which the functionality ends up not being used)?

I think this will be more useful when Both the relation are Big and are of almost equal size.

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.

regards, tom lane

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

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

On 10 April 2014 14:21, I wrote

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

I have some more testing with index and multiple conditions..
Test Scenario:
Create table t1 (a int, b int);
Create table t2 (a int, b int);

Create index t1_idx t1(b);
Create index t1_idx t1(b);

Query: select count(*) from t1,t2 where t1.b<t2.b and t1.b > 12000;

Test Result:
Nest Loop Join with Index Scan : 1653.506 ms
Sort Merge Join for (seq scan) : 610.257ms

From above both the scenario Sort merge join for < operator is faster than NLJ (using seq scan or index scan).

Any suggestion for other performance scenarios are welcome..

Thanks & Regards,
Dilip Kumar

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Hello Dilip,

Query: select count(*) from t1,t2 where t1.b<t2.b and t1.b > 12000;

Test Result:
Nest Loop Join with Index Scan : 1653.506 ms
Sort Merge Join for (seq scan) : 610.257ms

This looks like a great improvement. Repeating Nicolas's question, do you
have a real-world example of such joins?

In my experience, I see more queries like "self-join table A and table B
where A.time BETWEEN B.time - '1 week' and B.time", similar to
what Nicolas and Tom mentioned. As an example, "count users who placed an
order in the week following their registration".

Can you send a patch so we can also try it?

Thanks,
-- Hadi

On 29 April 2014 13:28, Hadi Moshayedi Wrote,

This looks like a great improvement. Repeating Nicolas's question, do you have a real-world example of such joins?

I can think of some scenario where, user need to self-join and find the comparison with other tuples, For example, list down all the employee which has less salary compare to others employees and count of the employees who are earning more than that emp. Like query given below

“select ta.emp_name, count(*) from t1 as ta, t1 as tb where ta.emp_salary<tb.emp_salary group by ta.emp_name;”

In my experience, I see more queries like "self-join table A and table B where A.time BETWEEN B.time - '1 week' and B.time", similar to what Nicolas and Tom mentioned. As an example, "count users who placed an order in the week following their registration".

Currently I have implemented very basic POC which can work only for a < b query, I think actual patch can be enhanced for these type of queries also.

Can you send a patch so we can also try it?

Patch is attached in the mail, but for testing we need to take care of some points

1. Patch is implemented only for a<b type of queries (only for table with one integer field, this can be modified in create_nestloop_plan if needed, I have written for basic test with integer).

2. What changes are done

There is no changes done in planner cost calculation, so hack is put while generating the plan.

IF planner has selected NLJ plan, and enable material is set to off (this is the hint to select special Merge Join)

Then add sort node above left and right tree for NLJ.

3. So if you want to test with normal NLJ no need to change anything, and if you want to test using this merge join just run ‘set enable_material=off’;

postgres=# explain select count(*) from t1 as ta, t1 as tb where ta.a<tb.a;
QUERY PLAN
---------------------------------------------------------------------------
Aggregate (cost=396625.51..396625.52 rows=1 width=0)
-> Nested Loop (cost=0.00..375758.83 rows=8346672 width=0)
Join Filter: (ta.a < tb.a)
-> Seq Scan on t1 ta (cost=0.00..73.04 rows=5004 width=4)
-> Materialize (cost=0.00..98.06 rows=5004 width=4)
-> Seq Scan on t1 tb (cost=0.00..73.04 rows=5004 width=4)
Planning time: 0.291 ms
(7 rows)

Now For enabling this merge Join
postgres=# set enable_material=off;
SET
postgres=# explain select count(*) from t1 as ta, t1 as tb where ta.a<tb.a;
QUERY PLAN
---------------------------------------------------------------------------
Aggregate (cost=699432.08..699432.09 rows=1 width=0)
-> Nested Loop (cost=0.00..678565.40 rows=8346672 width=0)
Join Filter: (ta.a < tb.a)
-> Sort (cost=380.51..393.02 rows=5004 width=4)
Sort Key: ta.a
-> Seq Scan on t1 ta (cost=0.00..73.04 rows=5004 width=4)
-> Sort (cost=380.51..393.02 rows=5004 width=4)
Sort Key: tb.a
-> Seq Scan on t1 tb (cost=0.00..73.04 rows=5004 width=4)
Planning time: 0.286 ms
(10 rows)

Thanks & Regards,
Dilip Kumar