Re: The testing of multi-batch hash joins with skewed data sets patch - Mailing list pgsql-hackers

> The idea I came up with for benchmarking was a little similar to what
I
> remember from the original tests. I have a sales orders table and a
> products
> table. My version of the sales orders table contains a customer
column.
> Data
> for 10 customers is populated into the sales orders table, customer 1
has
> a
> totally non-skewed set of orders, where customer 10 has the most skew.
> I've
> done this by creating 10000 products each with a product code that has
> been
> cast into a varchar and padded up to 5 chars in length with '0's. Each
> customer has the same number of rows in the sales orders table,
customer
> 10
> mostly orders products that when cast as INT are evenly divisible by
10,
> where customer 2 mostly orders products that are evenly divisible by
2.
> You
> get the idea.
> Currently I'm unsure the best way to ensure that the hash join goes
into
> more than one batch apart from just making the dataset very large.
>
> Does anyone have any thoughts about the way I plan to go about
> benchmarking?

Thank you for testing the patch - it is very much appreciated.  If you
use the test version of the patch, it will print out statistics that
will be helpful.

I think your approach should work.  I have two comments:

1) You will need to scale the data set larger to go multi-batch.  Even a
minimum work_mem of 1 MB may be enough to keep the product table in
memory unless each tuple is large.  For the TPC-H tests, the size of
product was 200,000 for 1 GB tests and 2 million tuples for 10 GB tests.

2) The current formula may not generate the skew you expect on
sales.productcode.  To simplify the discussion, I will only consider
customer 1 (c1) and customer 10 (c10) and a total of 100,000 sales
(50,000 for each customer).

If I look at product 10 for instance, it will be ordered 50,000/1,000 =
50 times by c10 and 50,000/10,000 = 5 times by c1 for a total of 55
times. Product 10 represents only 0.055% of all sales.  For all mod 10
products combined, they represent 55% of sales, which is significant BUT
requires us to store 10% of product in memory (1000 tuples all of which
need to be in the stats record).

This two customer test would be interesting.  There should be no benefit
for customer 1. In fact, you would see the worst case as you would plan
for skew but not get any benefit.  For customer 10 you should see a
benefit if your stats have 1000 tuples.  The issue is that you cannot
scale this test easily.  Increasing by a factor of 10 would require
stats of 10,000, and increasing by a factor of 100 is not possible.

The Zipfian distribution used in the previous experiments causes the top
few values to be exponentially better than the average value.  For
instance, the top 100 products may represent 10 to 50% of total sales
even for 1 million products.  In the previous case, the top 100 products
represent only 0.0055% of total sales for 1 million products.  This
level of skew would be ignored by the algorithm which has a cutoff value
that at least 1% of the probe relation must match with the skew values
buffered in memory.

To test higher values of skew, you could setup the experiment like this
(may scale down by a factor of 10 depending on your hardware):

products - 1 million
sales - 10 million
customers - 5  - Each customer has 2 million orders.  - Customer 1 orders each product equally.  - Customer 2 orders
eachproduct mod 10^2 equally.  - Customer 5 orders each product mod 10^5 equally. 

It is customer 5's orders that result in most of the skew as every
100,000th product will be ordered 200,000 times (customer 5 only orders
10 products).  Then, there is a huge benefit for customer 5 for keeping
these 10 products in memory during the join.  The benefit decreases for
each customer all the way down to customer 1 which will see no benefit.

--
Ramon Lawrence