> 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

Attachment: 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

Reply via email to