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_salaryIn 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 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 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.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.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
Dilip kumar 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
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
2014-04-09 Dilip kumar : > 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