> Here is a cleaned-up version. I fixed a number of whitespace issues, > improved a few comments, and rearranged one set of nested if-else > statements (hopefully without breaking anything in the process). > > Josh / eggyknap - > > Can you rerun your performance tests with this version of the patch?
To help with testing, we have constructed a patch specifically for testing. The patch is the same as Robert's version except that it tracks and prints out statistics during the join on how many tuples are affected and has the enable_hashjoin_usestatmcvs variable defined so that it is easy to turn on/off skew handling. This is useful as although the patch reduces the number of I/Os performed, this improvement may not be seen in some queries which are dominated by other cost factors (non-skew joins, CPU time, time to scan input relations, etc.). The sample output looks like this: LI-P Values: 100 Skew: 0.27 Est. tuples: 59986052.00 Batches: 512 Est. Save: 16114709.99 Total Inner Tuples: 2000000 IM Inner Tuples: 83 Batch Zero Inner Tuples: 3941 Batch Zero Potential Inner Tuples: 3941 Total Outer Tuples: 59986052 IM Outer Tuples: 16074146 Batch Zero Outer Tuples: 98778 Batch Zero Potential Outer Tuples: 98778 Total Output Tuples: 59986052 IM Output Tuples: 16074146 Batch Zero Output Tuples: 98778 Batch Zero Potential Output Tuples: 98778 Percentage less tuple IOs than HHJ: 25.98 The other change is that the system calculates the skew and will not use the in-memory skew partition if the skew is less than 1%. Finally, we have attached some performance results for the TPCH 10G data set (skew factors z=1 and z=2). For the Customer-Orders-Lineitem-Part query that Josh was testing, we see no overall time difference that is significant compared to experimental error (although there is I/O benefit for the Lineitem-Part join). This query cost is dominated by the non-skew joins of Customer-Orders and Orders-Lineitem and output tuple construction. The joins with skew, Lineitem-Supplier and Lineitem-Part, show significantly improved performance. Note how the statistics show that the percentage I/O savings is directly proportional to the skew. However, the overall query time savings is always less than this as there are other costs such as reading the relations, performing the hash comparisons, building the output tuples, etc. that are unaffected by the optimization. At this point, we await further feedback on what is necessary to get this patch accepted. We would also like to thank Josh and Robert again for their review time. Sincerely, Ramon Lawrence and Bryce Cutt
histojoin_testing.patch
Description: histojoin_testing.patch
TPC-H 10G Skew Factor Z=1 results --------------------------------- LI-P Regular HJ: (time in milliseconds) 990344 1022562 1071250 1003219 1049000 989953 Average: 1021054.667 LI-P Skew-enabled HJ: (time in milliseconds) 883593 960860 934906 1007282 937406 948078 Average: 945354.1667 % Difference: 7.4% LI-P Values: 100 Skew: 0.27 Est. tuples: 59986052.00 Batches: 512 Est. Save: 16114709.99 Total Inner Tuples: 2000000 IM Inner Tuples: 83 Batch Zero Inner Tuples: 3941 Batch Zero Potential Inner Tuples: 3941 Total Outer Tuples: 59986052 IM Outer Tuples: 16074146 Batch Zero Outer Tuples: 98778 Batch Zero Potential Outer Tuples: 98778 Total Output Tuples: 59986052 IM Output Tuples: 16074146 Batch Zero Output Tuples: 98778 Batch Zero Potential Output Tuples: 98778 Percentage less tuple IOs than HHJ: 25.98 LI-P-S Regular HJ: (time in milliseconds) 1833016 1567515 1504625 Average: 1635052 LI-P-S Skew-enabled HJ: (time in milliseconds) 883593 1280297 1423984 Average: 1195958 % Difference: 27% LI-S Values: 100 Skew: 0.19 Est. tuples: 59986052.00 Batches: 32 Est. Save: 11097357.16 Total Inner Tuples: 100000 IM Inner Tuples: 78 Batch Zero Inner Tuples: 3123 Batch Zero Potential Inner Tuples: 3125 Total Outer Tuples: 59986052 IM Outer Tuples: 11563695 Batch Zero Outer Tuples: 1577432 Batch Zero Potential Outer Tuples: 1693632 Total Output Tuples: 59986052 IM Output Tuples: 11563695 Batch Zero Output Tuples: 1577432 Batch Zero Potential Output Tuples: 1693632 Percentage less tuple IOs than HHJ: 19.61 (LI-S)-P Values: 100 Skew: 0.27 Est. tuples: 59986052.00 Batches: 512 Est. Save: 16114709.99 Total Inner Tuples: 2000000 IM Inner Tuples: 83 Batch Zero Inner Tuples: 3941 Batch Zero Potential Inner Tuples: 3941 Total Outer Tuples: 59986052 IM Outer Tuples: 16074146 Batch Zero Outer Tuples: 98778 Batch Zero Potential Outer Tuples: 98778 Total Output Tuples: 59986052 IM Output Tuples: 16074146 Batch Zero Output Tuples: 98778 Batch Zero Potential Output Tuples: 98778 Percentage less tuple IOs than HHJ: 25.98
TPC-H 10G Skew Factor Z=2 results --------------------------------- LI-P Regular HJ: (time in milliseconds) 505672 424922 303250 361610 358125 Average: 390715.8 LI-P Skew-enabled HJ: (time in milliseconds) 219078 210078 212938 210094 212500 Average: 212937.6 % difference: 45.5% LI-P Values: 9 Skew: 0.94 Est. tuples: 59986052.00 Batches: 512 Est. Save: 56174982.55 Total Inner Tuples: 2000000 IM Inner Tuples: 9 Batch Zero Inner Tuples: 3941 Batch Zero Potential Inner Tuples: 3941 Total Outer Tuples: 59986052 IM Outer Tuples: 56163835 Batch Zero Outer Tuples: 825 Batch Zero Potential Outer Tuples: 825 Total Output Tuples: 59986052 IM Output Tuples: 56163835 Batch Zero Output Tuples: 825 Batch Zero Potential Output Tuples: 825 Percentage less tuple IOs than HHJ: 90.61 This is the test query suggested by Josh: SELECT * FROM lineitem l LEFT JOIN part p ON (p.p_partkey = l.l_partkey) LEFT JOIN orders o ON (o.o_orderkey = l.l_orderkey) LEFT JOIN customer c ON (c.c_custkey = o.o_custkey); LI-P-O-C Regular HJ: (time in milliseconds) 8193906 7274906 Average: 7734406 LI-P-O-C Skew-enabled HJ: (time in milliseconds) 7965641 7656969 Average: 7811305 % difference: -0.99% (even the heavily skewed LI-P join cannot improve the time for this query that takes about 2 hours). There is no skew benefit for the C-O or O-LI parts of this query that dominate its cost. LI-P-S Regular HJ: (time in milliseconds) 1112515 981313 801281 761359 765734 1064282 938937 839906 Average: 861916.5 LI-P-S Skew-enabled HJ: (time in milliseconds) 303407 307375 410329 295047 296594 334375 294609 Average: 326190.8 % difference: 62% LI-S Values: 27 Skew: 0.92 Est. tuples: 59986052.00 Batches: 32 Est. Save: 53396708.76 Total Inner Tuples: 100000 IM Inner Tuples: 27 Batch Zero Inner Tuples: 3125 Batch Zero Potential Inner Tuples: 3125 Total Outer Tuples: 59986052 IM Outer Tuples: 54957282 Batch Zero Outer Tuples: 174737 Batch Zero Potential Outer Tuples: 174737 Total Output Tuples: 59986052 IM Output Tuples: 54957282 Batch Zero Output Tuples: 174737 Batch Zero Potential Output Tuples: 174737 Percentage less tuple IOs than HHJ: 91.74 (LI-S)-P Values: 9 Skew: 0.94 Est. tuples: 59986052.00 Batches: 512 Est. Save: 56174982.55 Total Inner Tuples: 2000000 IM Inner Tuples: 9 Batch Zero Inner Tuples: 3941 Batch Zero Potential Inner Tuples: 3941 Total Outer Tuples: 59986052 IM Outer Tuples: 56163835 Batch Zero Outer Tuples: 825 Batch Zero Potential Outer Tuples: 825 Total Output Tuples: 59986052 IM Output Tuples: 56163835 Batch Zero Output Tuples: 825 Batch Zero Potential Output Tuples: 825 Percentage less tuple IOs than HHJ: 90.61
-- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers