Re: Planner chose a much slower plan in hashjoin, using a large table as the inner table.

On Thu, Nov 28, 2019 at 7:19 PM Jinbao Chen <jinchen(at)pivotal(dot)io> wrote:

> Hi Andy,
>
> I just test the query on 12.1. But pg use big_table as inner.
>
> demo=# explain (costs off) select * from t_small, t_big where a = b;
> QUERY PLAN
> ------------------------------------
> Hash Join
> Hash Cond: (t_small.a = t_big.b)
> -> Seq Scan on t_small
> -> Hash
> -> Seq Scan on t_big
>
> Do you insert data and set max_parallel_workers_per_gather to 0 like
> above?
>

Sorry for the noise.. you are right. I thought I load the data but and
run the query immediately without running the analyzing.

now it is using big table as inner table.

> create table t_small(a int);
> create table t_big(b int);
> insert into t_small select i%100 from generate_series(0, 3000)i;
> insert into t_big select i%100000 from generate_series(1, 100000000)i ;
> analyze t_small;
> analyze t_big;
> set max_parallel_workers_per_gather = 0;
>
> On Thu, Nov 28, 2019 at 5:46 PM Andy Fan <zhihui(dot)fan1213(at)gmail(dot)com> wrote:
>
>>
>>
>> On Fri, Nov 22, 2019 at 6:51 PM Jinbao Chen <jinchen(at)pivotal(dot)io> wrote:
>>
>>> Hi hackers,
>>>
>>> I have made a patch to fix the problem.
>>>
>>> Added the selection rate of the inner table non-empty bucket
>>>
>>> The planner will use big table as inner table in hash join
>>> if small table have fewer unique values. But this plan is
>>> much slower than using small table as inner table.
>>>
>>> In general, the cost of creating a hash table is higher
>>> than the cost of querying a hash table. So we tend to use
>>> small tables as internal tables. But if the average chain
>>> length of the bucket is large, the situation is just the
>>> opposite.
>>>
>>> If virtualbuckets is much larger than innerndistinct, and
>>> outerndistinct is much larger than innerndistinct. Then most
>>> tuples of the outer table will match the empty bucket. So when
>>> we calculate the cost of traversing the bucket, we need to
>>> ignore the tuple matching empty bucket.
>>>
>>> So we add the selection rate of the inner table non-empty
>>> bucket. The formula is:
>>> (1 - ((outerndistinct - innerndistinct)/outerndistinct)*
>>> ((virtualbuckets - innerndistinct)/virtualbuckets))
>>>
>>>
>>> On Tue, Nov 19, 2019 at 5:56 PM Jinbao Chen <jinchen(at)pivotal(dot)io> wrote:
>>>
>>>> I think we have the same understanding of this issue.
>>>>
>>>> Sometimes use smaller costs on scanning the chain in bucket like below
>>>> would
>>>> be better.
>>>> run_cost += outer_path_rows * some_small_probe_cost;
>>>> run_cost += hash_qual_cost.per_tuple * approximate_tuple_count();
>>>> In some version of GreenPlum(a database based on postgres), we just
>>>> disabled
>>>> the cost on scanning the bucket chain. In most cases, this can get a
>>>> better query
>>>> plan. But I am worried that it will be worse in some cases.
>>>>
>>>> Now only the small table's distinct value is much smaller than the
>>>> bucket number,
>>>> and much smaller than the distinct value of the large table, the
>>>> planner will get the
>>>> wrong plan.
>>>>
>>>> For example, if inner table has 100 distinct values, and 3000 rows.
>>>> Hash table
>>>> has 1000 buckets. Outer table has 10000 distinct values.
>>>> We can assume that all the 100 distinct values of the inner table are
>>>> included in the
>>>> 10000 distinct values of the outer table. So (100/10000)*outer_rows
>>>> tuples will
>>>> probe the buckets has chain. And (9900/10000)*outer_rows tuples will
>>>> probe
>>>> all the 1000 buckets randomly. So (9900/10000)*outer_rows*(900/1000)
>>>> tuples will
>>>> probe empty buckets. So the costs on scanning bucket chain is
>>>>
>>>> hash_qual_cost.per_tuple*innerbucketsize*outer_rows*
>>>> (1 - ((outer_distinct - inner_distinct)/outer_distinct)*((buckets_num -
>>>> inner_disttinct)/buckets_num))
>>>>
>>>> Do you think this assumption is reasonable?
>>>>
>>>>
>>>> On Tue, Nov 19, 2019 at 3:46 PM Thomas Munro <thomas(dot)munro(at)gmail(dot)com>
>>>> wrote:
>>>>
>>>>> On Mon, Nov 18, 2019 at 7:48 PM Jinbao Chen <jinchen(at)pivotal(dot)io>
>>>>> wrote:
>>>>> > In the test case above, the small table has 3000 tuples and 100
>>>>> distinct values on column ‘a’.
>>>>> > If we use small table as inner table. The chan length of the bucket
>>>>> is 30. And we need to
>>>>> > search the whole chain on probing the hash table. So the cost of
>>>>> probing is bigger than build
>>>>> > hash table, and we need to use big table as inner.
>>>>> >
>>>>> > But in fact this is not true. We initialized 620,000 buckets in
>>>>> hashtable. But only 100 buckets
>>>>> > has chains with length 30. Other buckets are empty. Only hash values
>>>>> need to be compared.
>>>>> > Its costs are very small. We have 100,000 distinct key and
>>>>> 100,000,000 tuple on outer table.
>>>>> > Only (100/100000)* tuple_num tuples will search the whole chain. The
>>>>> other tuples
>>>>> > (number = (98900/100000)*tuple_num*) in outer
>>>>> > table just compare with the hash value. So the actual cost is much
>>>>> smaller than the planner
>>>>> > calculated. This is the reason why using a small table as inner is
>>>>> faster.
>>>>>
>>>>> So basically we think that if t_big is on the outer side, we'll do
>>>>> 100,000,000 probes and each one is going to scan a t_small bucket with
>>>>> chain length 30, so that looks really expensive. Actually only a
>>>>> small percentage of its probes find tuples with the right hash value,
>>>>> but final_cost_hash_join() doesn't know that. So we hash t_big
>>>>> instead, which we estimated pretty well and it finishes up with
>>>>> buckets of length 1,000 (which is actually fine in this case, they're
>>>>> not unwanted hash collisions, they're duplicate keys that we need to
>>>>> emit) and we probe them 3,000 times (which is also fine in this case),
>>>>> but we had to do a bunch of memory allocation and/or batch file IO and
>>>>> that turns out to be slower.
>>>>>
>>>>> I am not at all sure about this but I wonder if it would be better to
>>>>> use something like:
>>>>>
>>>>> run_cost += outer_path_rows * some_small_probe_cost;
>>>>> run_cost += hash_qual_cost.per_tuple * approximate_tuple_count();
>>>>>
>>>>> If we can estimate how many tuples will actually match accurately,
>>>>> that should also be the number of times we have to run the quals,
>>>>> since we don't usually expect hash collisions (bucket collisions, yes,
>>>>> but hash collisions where the key doesn't turn out to be equal, no*).
>>>>>
>>>>> * ... but also yes as you approach various limits, so you could also
>>>>> factor in bucket chain length that is due to being prevented from
>>>>> expanding the number of buckets by arbitrary constraints, and perhaps
>>>>> also birthday_problem(hash size, key space) to factor in unwanted hash
>>>>> collisions that start to matter once you get to billions of keys and
>>>>> expect collisions with short hashes.
>>>>>
>>>>
>> FYI: I tried this on 12.1, and find it use small_table as inner table
>> already. I didn't look into the details so far.
>>
>> postgres=# explain (costs off) select * from join_hash_t_small,
>> join_hash_t_big where a = b;
>> QUERY PLAN
>> --------------------------------------------------------
>> Hash Join
>> Hash Cond: (join_hash_t_big.b = join_hash_t_small.a)
>> -> Seq Scan on join_hash_t_big
>> -> Hash
>> -> Seq Scan on join_hash_t_small
>> (5 rows)
>>
>> postgres=# select version();
>> version
>>
>> -----------------------------------------------------------------------------------------------------------------
>> PostgreSQL 12.1 on x86_64-apple-darwin18.7.0, compiled by Apple LLVM
>> version 10.0.1 (clang-1001.0.46.4), 64-bit
>> (1 row)
>>
>