Re: [HACKERS] Proposal for Merge Join for Non '=' Operators
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_salarytb.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 ab 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.atb.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.atb.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 merge_join_nonequal.patch Description: merge_join_nonequal.patch -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Proposal for Merge Join for Non '=' Operators
Hello Dilip, Query: select count(*) from t1,t2 where t1.bt2.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
Re: [HACKERS] Proposal for Merge Join for Non '=' Operators
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.bt2.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
Re: [HACKERS] Proposal for Merge Join for Non '=' Operators
2014-04-09 Dilip kumar dilip.ku...@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
Re: [HACKERS] Proposal for Merge Join for Non '=' Operators
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
Re: [HACKERS] Proposal for Merge Join for Non '=' Operators
Dilip kumar dilip.ku...@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
[HACKERS] Proposal for Merge Join for Non '=' Operators
I would like to propose a New merge join algorithm for optimizing non '='
operators. ('', '=', '', '=')
- Currently Merge join is only supported for '=' operator. For '' or
'' operator it chooses Nest Loop Join, or Nest loop with materialization.
- I think when tuple from lower node is sorted or sorting cost is very
less, then we can use Merge Join for Non Equal operator also and which will
give better performance than NLJ (for selecting this new cost calculation can
be implemented in planner).
Example for using merge Join for operator.
T1T2
3 1
4 2
5 4
Outer tuple (3) need to be compared with inner tuple one by one, so it will
satisfy condition at third inner tuple (as 34). So here we can save this point
of inner tuple so that next outer tuple can directly start comparison from this
tuple.
1. In this algorithm we can put one more optimization: Once outer tuple
satisfies the Merge QUAL it can skip the Merge QUAL test with remaining inner
tuple and directly apply Other QUALs, as merge QUAL will always satisfy for
remaining tuples.
Implementation Detail:
1. Need to add new cost calculation mechanism for this. I still have to
work on this part.
2. Implementing in Executor
a. This algorithm is almost same as normal merge Join with some changes.
b. Both Inner and Outer Data Sources should be sorted, same as normal
merge Join.
ALGORITHM:
Merge Qual (R.A Q.A)
r = first tuple from R (Outer Relation)
q = first tuple in Q( Inner Relation)
save_pos = q; /* Position to start scanning in relation Q*/
While (fetch tuple r from R till relation end)
{
for each tuple q in Q starting from save_pos
{
Merge Qual Satisfy
{
save_pos = q;
Consume all subsequent tuples
and project(just need to match Other Quals if any.)
}
Else
Fetch Next tuple from Q;
}
}
- Performance Comparison:
Suppose tuples of inner and outer is already sorted or Index scan on inner and
outer.
* Then cost of NLJ is always O (r*q).
* The cost of this MJ will be b/w: O (n) to O (r*q).
Where r is number of tuple in R (outer relation) and q is number of tuple in Q
(inner Relation).
Please provide your feedback/suggestions.
Thanks Regards,
Dilip Kumar
