You are viewing a plain text version of this content. The canonical link for it is here.
Posted to reviews@impala.apache.org by "Amogh Margoor (Code Review)" <ge...@cloudera.org> on 2021/06/14 09:50:10 UTC
[Impala-ASF-CR] WIP: Reducing HashTable size by packing it's buckets efficiently.
Amogh Margoor has uploaded this change for review. ( http://gerrit.cloudera.org:8080/17592
Change subject: WIP: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
WIP: Reducing HashTable size by packing it's buckets efficiently.
HashTable implementation comprises of contiguos
array of Buckets and each Bucket would either
have Data or will point to linked list of
duplicate entries named DuplicateNode. These
are the structures of Bucket and DuplicateNode:
struct DuplicateNode {
bool matched;
DuplicateNode* next;
HtData htdata;
};
struct Bucket {
bool filled;
bool matched;
bool hasDuplicates;
uint32_t hash;
union {
HtData htdata;
DuplicateNode* duplicates;
} bucketData;
};
Size of Bucket is currently 16 bytes and Size of Duplicate Node is
24 bytes. If we can remove the booleans from both struct size of
Bucket would reduce to 12 bytes and DuplicateNode will be 16 bytes.
One of the ways we can remove booleans is to fold it into pointers
already part of struct. Pointers store addresses and on
architectures like x86 and ARM the linear address is only 48 bits
long. With level 5 paging intel is planning to expand it to 57-bit
long which means we can use most significant 7 bits i.e., 58 to 64
bits to store these booleans. This patch reduces the size of Bucket
and DuplicateNode by implementing this folding.
New Classes:
------------
As a part of patch, TaggedPointer is introduced which is template
class to store pointers and tag together in 64 bit integer. This
structure contains the ownership of the pointer and will take care
of allocation and deallocation the the object being pointed to.
However derived classes can opt out of the ownership of the object
and let the client manage it. It's derived classes for Bucket and
DuplicateNode do the same. These classes are TaggedBucketData and
TaggedDuplicateNode.
Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
---
M be/src/exec/grouping-aggregator.h
M be/src/exec/hash-table.cc
M be/src/exec/hash-table.h
M be/src/exec/hash-table.inline.h
M be/src/runtime/buffered-tuple-stream.h
M be/src/util/CMakeLists.txt
A be/src/util/tagged-ptr-test.cc
A be/src/util/tagged-ptr.h
M fe/src/main/java/org/apache/impala/planner/PlannerContext.java
9 files changed, 452 insertions(+), 123 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/Impala-ASF refs/changes/92/17592/1
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: newchange
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 1
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
[Impala-ASF-CR] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Zoltan Borok-Nagy (Code Review)" <ge...@cloudera.org>.
Zoltan Borok-Nagy has posted comments on this change. ( http://gerrit.cloudera.org:8080/17592 )
Change subject: IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
Patch Set 5:
(12 comments)
Did a first round. The code looks really great, I mostly had comments about naming conventions.
http://gerrit.cloudera.org:8080/#/c/17592/5//COMMIT_MSG
Commit Message:
http://gerrit.cloudera.org:8080/#/c/17592/5//COMMIT_MSG@9
PS5, Line 9: contiguos
contiguous?
http://gerrit.cloudera.org:8080/#/c/17592/5//COMMIT_MSG@61
PS5, Line 61: the the
duplicated 'the'
http://gerrit.cloudera.org:8080/#/c/17592/5//COMMIT_MSG@69
PS5, Line 69: ofthis
of this
http://gerrit.cloudera.org:8080/#/c/17592/5//COMMIT_MSG@73
PS5, Line 73: This would help measuring the impact of changes to the HashTable's
: data structure and algorithm.
It would be nice to some results in the commit message
http://gerrit.cloudera.org:8080/#/c/17592/5/be/src/exec/hash-table-test.cc
File be/src/exec/hash-table-test.cc:
http://gerrit.cloudera.org:8080/#/c/17592/5/be/src/exec/hash-table-test.cc@744
PS5, Line 744: // Test to ensure the bucket size doesn't change accidentally.
Nice! It could be also a static_assert at the class scope, e.g.:
static_assert(HashTable::BUCKET_SIZE == 8, "size should be power of two");
http://gerrit.cloudera.org:8080/#/c/17592/5/be/src/exec/hash-table.h
File be/src/exec/hash-table.h:
http://gerrit.cloudera.org:8080/#/c/17592/5/be/src/exec/hash-table.h@653
PS5, Line 653: is_matched
The namings are inconsistent a bit in this file. Some functions use underscore, some use CamelCase.
We usually only use underscores if we return a reference to a data member.
So it'd be probably better to use UpperCamelCase for all the new member functions.
http://gerrit.cloudera.org:8080/#/c/17592/5/be/src/exec/hash-table.h@674
PS5, Line 674: dn
nit: probably name it 'tdn' to be more clear?
http://gerrit.cloudera.org:8080/#/c/17592/5/be/src/exec/hash-table.h@694
PS5, Line 694: uint8
Why it isn't BucketData?
http://gerrit.cloudera.org:8080/#/c/17592/5/be/src/exec/hash-table.h@711
PS5, Line 711: getBd
nit: we usually don't abbreviate, i.e. it should be 'getBucketData()'
http://gerrit.cloudera.org:8080/#/c/17592/5/be/src/exec/hash-table.h@712
PS5, Line 712: uint8* ptr = getPtr();
: BucketData * bdPtr = reinterpret_cast<BucketData *>(&ptr);
: return *bdPtr;
(&ptr) is the address of the local variable 'ptr'.
Why not just simply
return *reinterpret_cast<BucketData*>(getPtr());
http://gerrit.cloudera.org:8080/#/c/17592/5/be/src/util/tagged-ptr.h
File be/src/util/tagged-ptr.h:
http://gerrit.cloudera.org:8080/#/c/17592/5/be/src/util/tagged-ptr.h@66
PS5, Line 66: s
nit: 'S', i.e. we are using UpperCamelCase for functions.
http://gerrit.cloudera.org:8080/#/c/17592/5/be/src/util/tagged-ptr.h@103
PS5, Line 103: data
nit: data_, i.e. we postfix member variables with '_'
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 5
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Wed, 07 Jul 2021 16:49:38 +0000
Gerrit-HasComments: Yes
[Impala-ASF-CR] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Zoltan Borok-Nagy (Code Review)" <ge...@cloudera.org>.
Zoltan Borok-Nagy has posted comments on this change. ( http://gerrit.cloudera.org:8080/17592 )
Change subject: IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
Patch Set 14: Code-Review+2
LGTM, great work!
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 14
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Qifan Chen <qc...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Wed, 25 Aug 2021 13:46:21 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/17592 )
Change subject: IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
Patch Set 5:
(5 comments)
http://gerrit.cloudera.org:8080/#/c/17592/5/be/src/exec/hash-table.cc
File be/src/exec/hash-table.cc:
http://gerrit.cloudera.org:8080/#/c/17592/5/be/src/exec/hash-table.cc@579
PS5, Line 579: Status hash_allocation_status = allocator_->Allocate(new_hash_size, &new_hash_allocation);
line too long (92 > 90)
http://gerrit.cloudera.org:8080/#/c/17592/5/be/src/exec/hash-table.inline.h
File be/src/exec/hash-table.inline.h:
http://gerrit.cloudera.org:8080/#/c/17592/5/be/src/exec/hash-table.inline.h@70
PS5, Line 70: && ht_ctx->Equals<INCLUSIVE_EQUALITY>(GetRow(bucket, ht_ctx->scratch_row_, bd))) {
line too long (92 > 90)
http://gerrit.cloudera.org:8080/#/c/17592/5/be/src/exec/hash-table.inline.h@103
PS5, Line 103: int64_t bucket_idx = Probe<true, true>(buckets_, num_buckets_, ht_ctx, hash, &found, &bd);
line too long (92 > 90)
http://gerrit.cloudera.org:8080/#/c/17592/5/be/src/exec/hash-table.inline.h@155
PS5, Line 155: int64_t bucket_idx = Probe<false, true>(buckets_, num_buckets_, ht_ctx, hash, &found, &bd);
line too long (93 > 90)
http://gerrit.cloudera.org:8080/#/c/17592/5/be/src/exec/hash-table.inline.h@168
PS5, Line 168: int64_t bucket_idx = Probe<true, true>(buckets_, num_buckets_, ht_ctx, hash, found, &bd);
line too long (91 > 90)
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 5
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Sun, 04 Jul 2021 16:44:58 +0000
Gerrit-HasComments: Yes
[Impala-ASF-CR] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Amogh Margoor (Code Review)" <ge...@cloudera.org>.
Amogh Margoor has posted comments on this change. ( http://gerrit.cloudera.org:8080/17592 )
Change subject: IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
Patch Set 5:
(1 comment)
http://gerrit.cloudera.org:8080/#/c/17592/5/be/src/benchmarks/hash-table-benchmark.cc
File be/src/benchmarks/hash-table-benchmark.cc:
http://gerrit.cloudera.org:8080/#/c/17592/5/be/src/benchmarks/hash-table-benchmark.cc@332
PS5, Line 332: vector<int> num_tuples { 65536, 262144 };
> One area of performance testing is looking at what happens when the hash ta
Sure, that makes a lot of sense. I was planning to do single node check with few TPCDS queries. But synthetic benchmark on the lines you suggested makes more sense and would be easier to verify.
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 5
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Thu, 08 Jul 2021 17:08:10 +0000
Gerrit-HasComments: Yes
[Impala-ASF-CR] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Qifan Chen (Code Review)" <ge...@cloudera.org>.
Qifan Chen has posted comments on this change. ( http://gerrit.cloudera.org:8080/17592 )
Change subject: IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
Patch Set 13: Code-Review+1
Thanks for the update. The patch looks great to me!
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 13
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Qifan Chen <qc...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Wed, 25 Aug 2021 03:28:24 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Amogh Margoor (Code Review)" <ge...@cloudera.org>.
Amogh Margoor has posted comments on this change. ( http://gerrit.cloudera.org:8080/17592 )
Change subject: IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
Patch Set 9:
(1 comment)
http://gerrit.cloudera.org:8080/#/c/17592/5/be/src/benchmarks/hash-table-benchmark.cc
File be/src/benchmarks/hash-table-benchmark.cc:
http://gerrit.cloudera.org:8080/#/c/17592/5/be/src/benchmarks/hash-table-benchmark.cc@332
PS5, Line 332: vector<int> num_tuples { 65536, 262144 };
> Sure, that makes a lot of sense. I was planning to do single node check wit
I have benchmarked it on Billion rows table and TPCH-42 just on single node. Results are under sheets 'Billion-Row' and 'TPCH-42' here: https://docs.google.com/spreadsheets/d/1nPkfFG1DDossI8Q-F9ALzc2qJvDAQaHT1yaJzkOQZBs/edit#gid=1839253325. Perf looks almost same - Probe seems a little bit faster with change (2-3% faster on non-skewed data). Reduction of 17% PeakMemory usage seen in Grouping aggregate operator and 21% reduction in Cumulative allocation when running Build benchmark.
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 9
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Qifan Chen <qc...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Wed, 04 Aug 2021 21:54:58 +0000
Gerrit-HasComments: Yes
[Impala-ASF-CR] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/17592 )
Change subject: IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
Patch Set 10:
Build Successful
https://jenkins.impala.io/job/gerrit-code-review-checks/9317/ : Initial code review checks passed. Use gerrit-verify-dryrun-external or gerrit-verify-dryrun to run full precommit tests.
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 10
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Qifan Chen <qc...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Wed, 18 Aug 2021 14:34:43 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Amogh Margoor (Code Review)" <ge...@cloudera.org>.
Amogh Margoor has posted comments on this change. ( http://gerrit.cloudera.org:8080/17592 )
Change subject: IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
Patch Set 10:
(43 comments)
http://gerrit.cloudera.org:8080/#/c/17592/9//COMMIT_MSG
Commit Message:
http://gerrit.cloudera.org:8080/#/c/17592/9//COMMIT_MSG@9
PS9, Line 9: HashTable implementation in Impala comprises of contiguous array
> nit. in Impala
Done
http://gerrit.cloudera.org:8080/#/c/17592/9//COMMIT_MSG@10
PS9, Line 10: ns either data or pointer to
: linked list of du
> nit. "contains either data or a pointer to linked"
Done
http://gerrit.cloudera.org:8080/#/c/17592/9//COMMIT_MSG@15
PS9, Line 15: bool matched;
: DuplicateNode* next;
: HtData htdata;
: };
:
: struct Bucket {
: bool filled;
: bool matched;
: bool hasDuplicates;
: uint32_t hash;
: union {
: HtData htdata;
: DuplicateNode* duplicates;
: } bucketData;
: };
:
> nit. The commit message is nice with many details. I wonder if it can be si
It would be easier for reader to look at struct to digest the new and old size and where size reduction is coming from.
http://gerrit.cloudera.org:8080/#/c/17592/9//COMMIT_MSG@38
PS9, Line 38: e mos
> nit. Intel
Done
http://gerrit.cloudera.org:8080/#/c/17592/9//COMMIT_MSG@53
PS9, Line 53: sures siz
> separately
Done
http://gerrit.cloudera.org:8080/#/c/17592/9//COMMIT_MSG@58
PS9, Line 58: class to store a pointer and 7-bit tag together in 64 bit integer.
> nit: a template class
Done
http://gerrit.cloudera.org:8080/#/c/17592/9//COMMIT_MSG@59
PS9, Line 59: ownership of the pointer and w
> nit. "tags together in 64-bit integers".
i have instead changed 'pointers' to singular to avoid impression of containing multiple pointers at once.
http://gerrit.cloudera.org:8080/#/c/17592/9//COMMIT_MSG@71
PS9, Line 71: med after building the Table.
> nit. use lower cases.
Done
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/benchmarks/hash-table-benchmark.cc
File be/src/benchmarks/hash-table-benchmark.cc:
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/benchmarks/hash-table-benchmark.cc@47
PS9, Line 47: Hash Table Build: Function iters/ms 10%ile 50%ile 90%ile 10%ile 50%ile 90%ile
> nit. Formatting. The space under "HashT able Build" is wasted. Suggest to b
This is common format for all benchmarks and this output is generated by common benchmark code for all other benchmarks. Moreover line is not wasted - it is to accommodate '(relative)' below.
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/benchmarks/hash-table-benchmark.cc@50
PS9, Line 50: 65536_100
> nit. Add a comment on the meaning of these two numbers.
Line 40 outlines it already.
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/benchmarks/hash-table-benchmark.cc@254
PS9, Line 254: fo
> I think we should return bool here to indicate whether there are any troubl
I have converted it into CHECK now.
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/benchmarks/hash-table-benchmark.cc@261
PS9, Line 261:
> nit. This can be defined outside the for loop.
Status passed to 'insert' is not overwritten in all cases, hence a new one needs to be passed always.
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/benchmarks/hash-table-benchmark.cc@267
PS9, Line 267: // Clear old
> nit. can we use name space htbenchmark here?
They are now nested into htbenchmark namespace itself. There is separate namespace within htbenchmark for build and probe benchmarks to organise the methods they exclusively need.
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/benchmarks/hash-table-benchmark.cc@279
PS9, Line 279:
> nit. We should check the return status from Build().
its not needed now as Build has CHECK.
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/exec/grouping-aggregator-ir.cc
File be/src/exec/grouping-aggregator-ir.cc:
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/exec/grouping-aggregator-ir.cc@113
PS9, Line 113: e wil
> nit: I wonder if instead of true/false we had an enum, then the code could
Sure, Done.
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/exec/grouping-aggregator-ir.cc@240
PS9, Line 240: This is called from ProcessBatchStreaming() so the rows are not aggregated.
: Hash
> nit: we could keep the old 'else if' and formatting so it is easier to spot
Done
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/exec/grouping-aggregator-ir.cc@245
PS9, Line 245: se
> nit: +2 indent
Done
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/exec/grouping-aggregator-partition.cc
File be/src/exec/grouping-aggregator-partition.cc:
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/exec/grouping-aggregator-partition.cc@126
PS9, Line 126: ion =
> nit: can we use an enum here as well?
Done
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/exec/hash-table.h
File be/src/exec/hash-table.h:
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/exec/hash-table.h@661
PS9, Line 661:
> nit: this definition is not needed
Done
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/exec/hash-table.h@689
PS9, Line 689:
> nit: its
Done
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/exec/hash-table.h@692
PS9, Line 692: tes whether
> seems like it's not true anymore
right. removed it.
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/exec/hash-table.h@694
PS9, Line 694: it is ef
> nit. this does not match the code at line 704.
right. changed the comment.
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/exec/hash-table.h@698
PS9, Line 698:
> Tag bit 1?
yes. changed it.
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/exec/hash-table.h@713
PS9, Line 713: r
> I wonder if why this argument is needed. Is it true that all hash tables ha
No, hash tables don't have this tag. This tag is used to only set or update bucket data where client knows if data is tagged or not. it is required to reduce time complexity.
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/exec/hash-table.h@723
PS9, Line 723: / If struct Bucket is
> nit: this definition is not needed.
Removed.
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/exec/hash-table.h@732
PS9, Line 732: bucket_data.htdata.tuple = bd.GetTuple<TAGGED>();
: return buck
> Seems like it's not true anymore
Right, it's removed.
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/exec/hash-table.cc
File be/src/exec/hash-table.cc:
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/exec/hash-table.cc@579
PS9, Line 579: Status hash_allocation_status =
> line too long (92 > 90)
Done
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/util/benchmark.cc
File be/src/util/benchmark.cc:
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/util/benchmark.cc@143
PS9, Line 143: if (fn != NULL) fn(benchmarks_[0].args);
> nit. May run Clang-format. {} is not needed if the entire IF statement is i
Done
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/util/benchmark.cc@174
PS9, Line 174: if (fn != NULL) fn(benchmarks_[i].args);
> nit. same as above.
Done
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/util/tagged-ptr-test.cc
File be/src/util/tagged-ptr-test.cc:
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/util/tagged-ptr-test.cc@27
PS9, Line 27:
> nit const std::string&
Done
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/util/tagged-ptr-test.cc@42
PS9, Line 42:
> nit. const std::string&
Done
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/util/tagged-ptr-test.cc@59
PS9, Line 59:
> nit. I wonder if we use OWN=true version in BE. If so, you may test it well
We use OWN=false in backend too.
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/util/tagged-ptr-test.cc@92
PS9, Line 92: EXPECT_FALSE(ptr.IsTagBitSet<i>());
:
> nit. May include setting tag bit 3, 4,5 and 6.
Have added above.
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/util/tagged-ptr-test.cc@97
PS9, Line 97: ch
> nit. Please use 0x60 here to indicate which bits are set better.
Done
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/util/tagged-ptr-test.cc@102
PS9, Line 102: tS
> nit same as above.
Done
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/util/tagged-ptr-test.cc@144
PS9, Line 144:
> nit remove the space.
Done
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/util/tagged-ptr.h
File be/src/util/tagged-ptr.h:
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/util/tagged-ptr.h@47
PS9, Line 47: /// allocation/deallocation of the object to which pointer stored points to should be
> Instead of macros these could be template variables and template functions:
Makes sense. This simplifies things.
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/util/tagged-ptr.h@54
PS9, Line 54:
> nit. Unset
Done
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/util/tagged-ptr.h@46
PS9, Line 46: /// Derived class would be needed to define what each tag bit would mean or when
: /// allocation/deallocation of the object to which pointer stored points to should be
: /// the responsibility of client and not 'TaggedPtr'( check HashTable::TaggedBucketData).
:
: template <class T, bool OWNS = true>
: class TaggedPtr {
: public:
: TaggedPtr() = default;
:
: template <class... Args>
: static TaggedPtr make_tagptr(Args&&... args) {
: T* ptr = new T(std::forward<Args>(args)...);
: return TaggedPtr(ptr);
: }
:
> nit. May run ClangFormat on the entire macro to align '\' nicely.
Code Removed.
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/util/tagged-ptr.h@99
PS9, Line 99: return data_ & DATA_MASK<bit>;
> nit. tag bits 0-6.
Code Removed.
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/util/tagged-ptr.h@100
PS9, Line 100: }
:
: ALWAYS_INLINE bool IsNull() { return GetPtr() == 0; }
:
> nit. This can be moved to where the macro is defined (e.g. line 46).
Code Removed.
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/util/tagged-ptr.h@104
PS9, Line 104: ALWAYS_INLINE int GetTag() const { return data_ >> 57; }
:
: ALWAYS_INLINE T* GetPtr() const { return (T*)(data_ & MASK_0_56_BITS); }
:
: T& operator*() const noexcept { return *GetPtr(); }
:
> nit. remove?
Code Removed.
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/util/tagged-ptr.h@137
PS9, Line 137:
> This can be made a constant to avoid compute ~ every time SetPtr() is calle
Done
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 10
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Qifan Chen <qc...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Wed, 18 Aug 2021 14:09:18 +0000
Gerrit-HasComments: Yes
[Impala-ASF-CR] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/17592 )
Change subject: IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
Patch Set 7:
(1 comment)
http://gerrit.cloudera.org:8080/#/c/17592/7/be/src/exec/hash-table.cc
File be/src/exec/hash-table.cc:
http://gerrit.cloudera.org:8080/#/c/17592/7/be/src/exec/hash-table.cc@579
PS7, Line 579: Status hash_allocation_status = allocator_->Allocate(new_hash_size, &new_hash_allocation);
line too long (92 > 90)
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 7
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Mon, 19 Jul 2021 11:36:13 +0000
Gerrit-HasComments: Yes
[Impala-ASF-CR] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Qifan Chen (Code Review)" <ge...@cloudera.org>.
Qifan Chen has posted comments on this change. ( http://gerrit.cloudera.org:8080/17592 )
Change subject: IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
Patch Set 12:
(1 comment)
Looks great!
http://gerrit.cloudera.org:8080/#/c/17592/12/be/src/exec/hash-table.h
File be/src/exec/hash-table.h:
http://gerrit.cloudera.org:8080/#/c/17592/12/be/src/exec/hash-table.h@705
PS12, Line 705: If bucket doesn't have tag fields set, TAGGED can
: /// be set to 'false' to avoid extra bit operations.
nit. I think the following may describe the semantics better:
When 'data' may contain tagging bits, use TAGGED being equal true version of this method.
This comment probably should become item 3. of the description for this class (e.g., at line 697) as there are several methods with the TAGGED argument.
I also wonder if we can improve the performance a bit by splitting the method into two to avoid the IF test
1. SetBucketDataUnTagged() (untagged version)
2. SetBucketDataTagged() (tagged version)
Another option would be to add UNLIKELY() for untagged branch.
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 12
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Qifan Chen <qc...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Tue, 24 Aug 2021 13:37:33 +0000
Gerrit-HasComments: Yes
[Impala-ASF-CR] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/17592 )
Change subject: IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
Patch Set 12:
Build Successful
https://jenkins.impala.io/job/gerrit-code-review-checks/9347/ : Initial code review checks passed. Use gerrit-verify-dryrun-external or gerrit-verify-dryrun to run full precommit tests.
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 12
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Qifan Chen <qc...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Mon, 23 Aug 2021 14:48:24 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/17592 )
Change subject: IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
Patch Set 14: Verified+1
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 14
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Qifan Chen <qc...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Wed, 25 Aug 2021 20:05:45 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] [WIP] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Amogh Margoor (Code Review)" <ge...@cloudera.org>.
Amogh Margoor has uploaded a new patch set (#3). ( http://gerrit.cloudera.org:8080/17592 )
Change subject: [WIP] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
[WIP] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
HashTable implementation comprises of contiguos
array of Buckets and each Bucket would either
have Data or will point to linked list of
duplicate entries named DuplicateNode. These
are the structures of Bucket and DuplicateNode:
struct DuplicateNode {
bool matched;
DuplicateNode* next;
HtData htdata;
};
struct Bucket {
bool filled;
bool matched;
bool hasDuplicates;
uint32_t hash;
union {
HtData htdata;
DuplicateNode* duplicates;
} bucketData;
};
Size of Bucket is currently 16 bytes and Size of Duplicate Node is
24 bytes. If we can remove the booleans from both struct size of
Bucket would reduce to 12 bytes and DuplicateNode will be 16 bytes.
One of the ways we can remove booleans is to fold it into pointers
already part of struct. Pointers store addresses and on
architectures like x86 and ARM the linear address is only 48 bits
long. With level 5 paging intel is planning to expand it to 57-bit
long which means we can use most significant 7 bits i.e., 58 to 64
bits to store these booleans. This patch reduces the size of Bucket
and DuplicateNode by implementing this folding.
New Classes:
------------
As a part of patch, TaggedPointer is introduced which is template
class to store pointers and tag together in 64 bit integer. This
structure contains the ownership of the pointer and will take care
of allocation and deallocation the the object being pointed to.
However derived classes can opt out of the ownership of the object
and let the client manage it. It's derived classes for Bucket and
DuplicateNode do the same. These classes are TaggedBucketData and
TaggedDuplicateNode.
Benchmark:
----------
As a part ofthis patch a new Micro Benchmark for HashTable has
been introduced, which will help in measuring these:
1. Runtime for Building Hash Table and Probing the table.
2. Memory consumed after building the Table.
This would help measuring the impact of changes to the HashTable's
data structure and algorithm.
Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
---
M be/src/benchmarks/CMakeLists.txt
A be/src/benchmarks/hash-table-benchmark.cc
M be/src/exec/grouping-aggregator.h
M be/src/exec/hash-table-test.cc
M be/src/exec/hash-table.cc
M be/src/exec/hash-table.h
M be/src/exec/hash-table.inline.h
M be/src/runtime/buffered-tuple-stream.h
M be/src/util/CMakeLists.txt
A be/src/util/tagged-ptr-test.cc
A be/src/util/tagged-ptr.h
M fe/src/main/java/org/apache/impala/planner/PlannerContext.java
12 files changed, 909 insertions(+), 149 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/Impala-ASF refs/changes/92/17592/3
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 3
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
[Impala-ASF-CR] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Amogh Margoor (Code Review)" <ge...@cloudera.org>.
Amogh Margoor has uploaded a new patch set (#14). ( http://gerrit.cloudera.org:8080/17592 )
Change subject: IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
HashTable implementation in Impala comprises of contiguous array
of Buckets and each Bucket contains either data or pointer to
linked list of duplicate entries named DuplicateNode.
These are the structures of Bucket and DuplicateNode:
struct DuplicateNode {
bool matched;
DuplicateNode* next;
HtData htdata;
};
struct Bucket {
bool filled;
bool matched;
bool hasDuplicates;
uint32_t hash;
union {
HtData htdata;
DuplicateNode* duplicates;
} bucketData;
};
Size of Bucket is currently 16 bytes and size of DuplicateNode is
24 bytes. If we can remove the booleans from both struct size of
Bucket would reduce to 12 bytes and DuplicateNode will be 16 bytes.
One of the ways we can remove booleans is to fold it into pointers
already part of struct. Pointers store addresses and on
architectures like x86 and ARM the linear address is only 48 bits
long. With level 5 paging Intel is planning to expand it to 57-bit
long which means we can use most significant 7 bits i.e., 58 to 64
bits to store these booleans. This patch reduces the size of Bucket
and DuplicateNode by implementing this folding. However, there is
another requirement regarding Size of Bucket to be power of 2 and
also for the number of buckets in Hash table to be power of 2.
These requirements are for the following reasons:
1. Memory Allocator allocates memory in power of 2 to avoid
internal fragmentation. Hence, num of buckets * sizeof(Buckets)
should be power of 2.
2. Number of buckets being power of 2 enables faster modulo
operation i.e., instead of slow modulo: (hash % N), faster
(hash & (N-1)) can be used.
Due to this, 4 bytes 'hash' field from Bucket is removed and
stored separately in new array hash_array_ in HashTable.
This ensures sizeof(Bucket) is 8 which is power of 2.
New Classes:
------------
As a part of patch, TaggedPointer is introduced which is a template
class to store a pointer and 7-bit tag together in 64 bit integer.
This structure contains the ownership of the pointer and will take care
of allocation and deallocation of the object being pointed to.
However derived classes can opt out of the ownership of the object
and let the client manage it. It's derived classes for Bucket and
DuplicateNode do the same. These classes are TaggedBucketData and
TaggedDuplicateNode.
Benchmark:
----------
As a part of this patch a new Micro Benchmark for HashTable has
been introduced, which will help in measuring these:
1. Runtime for building hash table and probing it.
2. Memory consumed after building the Table.
This would help measuring the impact of changes to the HashTable's
data structure and algorithm.
Saw 25-30% reduction in memory consumed and no significant
difference in performance (0.91X-1.2X).
Other Benchmarks:
1. Billion row Synthetic benchmark on single node, single daemon:
a. 2-3% improvement in Join GEOMEAN for Probe benchmark.
b. 17% and 21% reduction in PeakMemoryUsage and
CumulativeBytes allocated respectively
2. TPCH-42: 0-1.5% improvement in GEOMEAN runtime
Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
---
M be/src/benchmarks/CMakeLists.txt
A be/src/benchmarks/hash-table-benchmark.cc
M be/src/exec/grouping-aggregator-ir.cc
M be/src/exec/grouping-aggregator-partition.cc
M be/src/exec/grouping-aggregator.cc
M be/src/exec/hash-table-test.cc
M be/src/exec/hash-table.cc
M be/src/exec/hash-table.h
M be/src/exec/hash-table.inline.h
M be/src/util/CMakeLists.txt
M be/src/util/benchmark.cc
M be/src/util/benchmark.h
A be/src/util/tagged-ptr-test.cc
A be/src/util/tagged-ptr.h
M fe/src/main/java/org/apache/impala/planner/PlannerContext.java
M fe/src/test/java/org/apache/impala/planner/CardinalityTest.java
M testdata/workloads/functional-planner/queries/PlannerTest/fk-pk-join-detection-hdfs-num-rows-est-enabled.test
M testdata/workloads/functional-planner/queries/PlannerTest/fk-pk-join-detection.test
M testdata/workloads/functional-planner/queries/PlannerTest/max-row-size.test
M testdata/workloads/functional-planner/queries/PlannerTest/resource-requirements.test
M testdata/workloads/functional-planner/queries/PlannerTest/spillable-buffer-sizing.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q01.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q04.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q05.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q06.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q07.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q11.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q12.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q14a.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q15.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q16.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q17.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q18.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q19.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q20.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q22.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q23a.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q23b.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q24a.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q24b.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q25.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q26.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q27.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q29.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q34.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q35a.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q38.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q39a.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q39b.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q45.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q46.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q47.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q48.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q50.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q51.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q56.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q57.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q58.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q60.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q61.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q64.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q66.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q67.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q68.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q72.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q73.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q74.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q78.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q80.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q82.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q83.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q85.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q87.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q95.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q97.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q98.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpch-all.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpch-kudu.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpch-nested.test
M testdata/workloads/functional-query/queries/QueryTest/spilling-broadcast-joins.test
M testdata/workloads/functional-query/queries/QueryTest/spilling.test
81 files changed, 1,975 insertions(+), 1,048 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/Impala-ASF refs/changes/92/17592/14
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 14
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Qifan Chen <qc...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
[Impala-ASF-CR] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/17592 )
Change subject: IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
Patch Set 11:
Build Successful
https://jenkins.impala.io/job/gerrit-code-review-checks/9344/ : Initial code review checks passed. Use gerrit-verify-dryrun-external or gerrit-verify-dryrun to run full precommit tests.
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 11
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Qifan Chen <qc...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Sat, 21 Aug 2021 07:27:32 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Amogh Margoor (Code Review)" <ge...@cloudera.org>.
Amogh Margoor has uploaded a new patch set (#12). ( http://gerrit.cloudera.org:8080/17592 )
Change subject: IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
HashTable implementation in Impala comprises of contiguous array
of Buckets and each Bucket contains either data or pointer to
linked list of duplicate entries named DuplicateNode.
These are the structures of Bucket and DuplicateNode:
struct DuplicateNode {
bool matched;
DuplicateNode* next;
HtData htdata;
};
struct Bucket {
bool filled;
bool matched;
bool hasDuplicates;
uint32_t hash;
union {
HtData htdata;
DuplicateNode* duplicates;
} bucketData;
};
Size of Bucket is currently 16 bytes and size of DuplicateNode is
24 bytes. If we can remove the booleans from both struct size of
Bucket would reduce to 12 bytes and DuplicateNode will be 16 bytes.
One of the ways we can remove booleans is to fold it into pointers
already part of struct. Pointers store addresses and on
architectures like x86 and ARM the linear address is only 48 bits
long. With level 5 paging Intel is planning to expand it to 57-bit
long which means we can use most significant 7 bits i.e., 58 to 64
bits to store these booleans. This patch reduces the size of Bucket
and DuplicateNode by implementing this folding. However, there is
another requirement regarding Size of Bucket to be power of 2 and
also for the number of buckets in Hash table to be power of 2.
These requirements are for the following reasons:
1. Memory Allocator allocates memory in power of 2 to avoid
internal fragmentation. Hence, num of buckets * sizeof(Buckets)
should be power of 2.
2. Number of buckets being power of 2 enables faster modulo
operation i.e., instead of slow modulo: (hash % N), faster
(hash & (N-1)) can be used.
Due to this, 4 bytes 'hash' field from Bucket is removed and
stored separately in new array hash_array_ in HashTable.
This ensures sizeof(Bucket) is 8 which is power of 2.
New Classes:
------------
As a part of patch, TaggedPointer is introduced which is a template
class to store a pointer and 7-bit tag together in 64 bit integer.
This structure contains the ownership of the pointer and will take care
of allocation and deallocation of the object being pointed to.
However derived classes can opt out of the ownership of the object
and let the client manage it. It's derived classes for Bucket and
DuplicateNode do the same. These classes are TaggedBucketData and
TaggedDuplicateNode.
Benchmark:
----------
As a part of this patch a new Micro Benchmark for HashTable has
been introduced, which will help in measuring these:
1. Runtime for building hash table and probing it.
2. Memory consumed after building the Table.
This would help measuring the impact of changes to the HashTable's
data structure and algorithm.
Saw 25-30% reduction in memory consumed and no significant
difference in performance (0.91X-1.2X).
Other Benchmarks:
1. Billion row Synthetic benchmark on single node, single daemon:
a. 2-3% improvement in Join GEOMEAN for Probe benchmark.
b. 17% and 21% reduction in PeakMemoryUsage and
CumulativeBytes allocated respectively
2. TPCH-42: 0-1.5% improvement in GEOMEAN runtime
Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
---
M be/src/benchmarks/CMakeLists.txt
A be/src/benchmarks/hash-table-benchmark.cc
M be/src/exec/grouping-aggregator-ir.cc
M be/src/exec/grouping-aggregator-partition.cc
M be/src/exec/grouping-aggregator.cc
M be/src/exec/hash-table-test.cc
M be/src/exec/hash-table.cc
M be/src/exec/hash-table.h
M be/src/exec/hash-table.inline.h
M be/src/util/CMakeLists.txt
M be/src/util/benchmark.cc
M be/src/util/benchmark.h
A be/src/util/tagged-ptr-test.cc
A be/src/util/tagged-ptr.h
M fe/src/main/java/org/apache/impala/planner/PlannerContext.java
M fe/src/test/java/org/apache/impala/planner/CardinalityTest.java
M testdata/workloads/functional-planner/queries/PlannerTest/fk-pk-join-detection-hdfs-num-rows-est-enabled.test
M testdata/workloads/functional-planner/queries/PlannerTest/fk-pk-join-detection.test
M testdata/workloads/functional-planner/queries/PlannerTest/max-row-size.test
M testdata/workloads/functional-planner/queries/PlannerTest/resource-requirements.test
M testdata/workloads/functional-planner/queries/PlannerTest/spillable-buffer-sizing.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q01.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q04.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q05.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q06.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q07.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q11.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q12.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q14a.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q15.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q16.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q17.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q18.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q19.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q20.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q22.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q23a.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q23b.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q24a.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q24b.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q25.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q26.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q27.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q29.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q34.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q35a.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q38.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q39a.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q39b.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q45.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q46.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q47.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q48.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q50.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q51.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q56.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q57.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q58.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q60.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q61.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q64.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q66.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q67.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q68.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q72.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q73.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q74.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q78.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q80.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q82.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q83.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q85.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q87.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q95.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q97.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q98.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpch-all.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpch-kudu.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpch-nested.test
M testdata/workloads/functional-query/queries/QueryTest/spilling-broadcast-joins.test
M testdata/workloads/functional-query/queries/QueryTest/spilling.test
81 files changed, 1,972 insertions(+), 1,048 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/Impala-ASF refs/changes/92/17592/12
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 12
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Qifan Chen <qc...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
[Impala-ASF-CR] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Amogh Margoor (Code Review)" <ge...@cloudera.org>.
Amogh Margoor has posted comments on this change. ( http://gerrit.cloudera.org:8080/17592 )
Change subject: IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
Patch Set 8:
(11 comments)
> (1 comment)
>
> I grabbed this change and was doing some local testing, and I ran
> into a scenario that crashes Impala.
>
> Here's what I did:
> 1. I loaded a larger TPC-H dataset in parquet (takes quite a while
> and will use up some disk space):
> bin/load-data.py -w tpch -s 42 --table_formats=text/none/none,parquet/none/none
> 2. Ran the following multiple times (it is intermittent):
> use tpch42_parquet;
> SELECT l_orderkey,
> count(*) AS cnt
> FROM lineitem
> GROUP BY l_orderkey
> HAVING count(*) > 9999999999999;
>
> That intermittently crashes with this stack:
> C [impalad+0x27e8546] long impala::HashTable::Probe<true,
> false>(impala::HashTable::Bucket*, long, impala::HashTableCtx*,
> unsigned int, bool*, impala::HashTable::BucketData*)+0x28c
> C [impalad+0x27e2141] impala::HashTable::ResizeBuckets(long,
> impala::HashTableCtx*, bool*)+0x7d1
> C [impalad+0x27e194d] impala::HashTable::CheckAndResize(unsigned
> long, impala::HashTableCtx*, bool*)+0xcb
> C [impalad+0x27c8a48] impala::GroupingAggregator::CheckAndResizeHashPartitions(bool,
> int, impala::HashTableCtx*)+0x176
>
> This may reproduce on smaller datasets.
This has been fixed now.
http://gerrit.cloudera.org:8080/#/c/17592/5/be/src/exec/hash-table-test.cc
File be/src/exec/hash-table-test.cc:
http://gerrit.cloudera.org:8080/#/c/17592/5/be/src/exec/hash-table-test.cc@744
PS5, Line 744: // Test to ensure the bucket size doesn't change accidentally.
> Nice! It could be also a static_assert at the class scope, e.g.:
Done.
http://gerrit.cloudera.org:8080/#/c/17592/7/be/src/exec/hash-table.h
File be/src/exec/hash-table.h:
http://gerrit.cloudera.org:8080/#/c/17592/7/be/src/exec/hash-table.h@653
PS7, Line 653: n
> nit. May define and use constant for MATCHED here.
This logic has been changed to reduce the runtime overhead to read these flags.
http://gerrit.cloudera.org:8080/#/c/17592/7/be/src/exec/hash-table.h@697
PS7, Line 697:
> nit. same as above. May use constants for FILLED, MATCHED and DUPLICATED, i
This logic has been changed to reduce the runtime overhead to read these flags.
http://gerrit.cloudera.org:8080/#/c/17592/5/be/src/exec/hash-table.h
File be/src/exec/hash-table.h:
http://gerrit.cloudera.org:8080/#/c/17592/5/be/src/exec/hash-table.h@694
PS5, Line 694:
> Why it isn't BucketData?
So it stores the pointer that union BucketData stores and not the pointer to the BucketData itself.
http://gerrit.cloudera.org:8080/#/c/17592/5/be/src/exec/hash-table.h@712
PS5, Line 712: ALWAYS_INLINE void UnsetMatched() { UnSetTagBit1(); }
: ALWAYS_INLINE void UnsetHasDuplicates() { UnSetTagBit2(); }
: ALWAYS_INLINE vo
> (&ptr) is the address of the local variable 'ptr'.
Have changed this logic. '*reinterpret_cast<BucketData*>(getPtr());' would not work as it getPtr() returns the pointer to tuple/duplicate node instead of returning pointer to BucketData.
http://gerrit.cloudera.org:8080/#/c/17592/7/be/src/util/tagged-ptr.h
File be/src/util/tagged-ptr.h:
http://gerrit.cloudera.org:8080/#/c/17592/7/be/src/util/tagged-ptr.h@71
PS7, Line 71: late<class T, bool
> nit. UNLIKELY()?
This conditional has been removed altogether.
http://gerrit.cloudera.org:8080/#/c/17592/7/be/src/util/tagged-ptr.h@78
PS7, Line 78: return TaggedPtr(ptr)
> same as above
This conditional has been removed altogether.
http://gerrit.cloudera.org:8080/#/c/17592/7/be/src/util/tagged-ptr.h@91
PS7, Line 91: if (OWNS) {
> nit. delete?
Done.
http://gerrit.cloudera.org:8080/#/c/17592/7/be/src/util/tagged-ptr.h@101
PS7, Line 101: // ALWAYS_INLINE void SetTagBit0() {
: // data_ = (data_ | DATA_MASK_0);
: // }
> nit. I found the implementation of these two operators counter intuitive as
These are comparison of the tagged pointers which includes tag. For comparison of just pointers getPtr() on both can be used.
http://gerrit.cloudera.org:8080/#/c/17592/7/be/src/util/tagged-ptr.h@115
PS7, Line 115:
> nit. remove?
Done.
http://gerrit.cloudera.org:8080/#/c/17592/7/fe/src/main/java/org/apache/impala/planner/PlannerContext.java
File fe/src/main/java/org/apache/impala/planner/PlannerContext.java:
http://gerrit.cloudera.org:8080/#/c/17592/7/fe/src/main/java/org/apache/impala/planner/PlannerContext.java@47
PS7, Line 47: public final static double SIZE_OF_HASH = 4;
> nit. I wonder if this value can be folded back into SIZE_OF_BUCKET and SIZE
Makes sense. Have made the change.
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 8
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Qifan Chen <qc...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Wed, 04 Aug 2021 20:34:08 +0000
Gerrit-HasComments: Yes
[Impala-ASF-CR] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Amogh Margoor (Code Review)" <ge...@cloudera.org>.
Amogh Margoor has posted comments on this change. ( http://gerrit.cloudera.org:8080/17592 )
Change subject: IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
Patch Set 6:
(8 comments)
http://gerrit.cloudera.org:8080/#/c/17592/5//COMMIT_MSG
Commit Message:
http://gerrit.cloudera.org:8080/#/c/17592/5//COMMIT_MSG@9
PS5, Line 9: contiguou
> contiguous?
Done
http://gerrit.cloudera.org:8080/#/c/17592/5//COMMIT_MSG@61
PS5, Line 61: of the
> duplicated 'the'
Done
http://gerrit.cloudera.org:8080/#/c/17592/5//COMMIT_MSG@69
PS5, Line 69: of thi
> of this
Done
http://gerrit.cloudera.org:8080/#/c/17592/5/be/src/exec/hash-table.h
File be/src/exec/hash-table.h:
http://gerrit.cloudera.org:8080/#/c/17592/5/be/src/exec/hash-table.h@653
PS5, Line 653: IsMatched(
> The namings are inconsistent a bit in this file. Some functions use undersc
Done. Changed all the names.
http://gerrit.cloudera.org:8080/#/c/17592/5/be/src/exec/hash-table.h@674
PS5, Line 674: td
> nit: probably name it 'tdn' to be more clear?
Done
http://gerrit.cloudera.org:8080/#/c/17592/5/be/src/exec/hash-table.h@711
PS5, Line 711: GetBu
> nit: we usually don't abbreviate, i.e. it should be 'getBucketData()'
Done
http://gerrit.cloudera.org:8080/#/c/17592/5/be/src/util/tagged-ptr.h
File be/src/util/tagged-ptr.h:
http://gerrit.cloudera.org:8080/#/c/17592/5/be/src/util/tagged-ptr.h@66
PS5, Line 66: S
> nit: 'S', i.e. we are using UpperCamelCase for functions.
Done. Changed it throughout the file.
http://gerrit.cloudera.org:8080/#/c/17592/5/be/src/util/tagged-ptr.h@103
PS5, Line 103: data
> nit: data_, i.e. we postfix member variables with '_'
Done
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 6
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Tue, 13 Jul 2021 11:18:05 +0000
Gerrit-HasComments: Yes
[Impala-ASF-CR] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/17592 )
Change subject: IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
Patch Set 6:
(1 comment)
http://gerrit.cloudera.org:8080/#/c/17592/6/be/src/exec/hash-table.cc
File be/src/exec/hash-table.cc:
http://gerrit.cloudera.org:8080/#/c/17592/6/be/src/exec/hash-table.cc@579
PS6, Line 579: Status hash_allocation_status = allocator_->Allocate(new_hash_size, &new_hash_allocation);
line too long (92 > 90)
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 6
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Tue, 13 Jul 2021 11:18:45 +0000
Gerrit-HasComments: Yes
[Impala-ASF-CR] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/17592 )
Change subject: IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
Patch Set 9:
(1 comment)
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/exec/hash-table.cc
File be/src/exec/hash-table.cc:
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/exec/hash-table.cc@579
PS9, Line 579: Status hash_allocation_status = allocator_->Allocate(new_hash_size, &new_hash_allocation);
line too long (92 > 90)
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 9
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Qifan Chen <qc...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Wed, 04 Aug 2021 21:55:33 +0000
Gerrit-HasComments: Yes
[Impala-ASF-CR] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Amogh Margoor (Code Review)" <ge...@cloudera.org>.
Amogh Margoor has posted comments on this change. ( http://gerrit.cloudera.org:8080/17592 )
Change subject: IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
Patch Set 9:
(2 comments)
Benchmark Update:
SingleNode benchmarks done:
1. MicroBenchmark
2. Billion Rows Probe (join) and Build (groupby) Benchmark
3. TPCH-42 scale: 3 queries including groupby on lineitem (build benchmark).
https://docs.google.com/spreadsheets/d/1nPkfFG1DDossI8Q-F9ALzc2qJvDAQaHT1yaJzkOQZBs/edit#gid=0
TPCDS-3000 has been run once and few queries in that are being rerun.
http://gerrit.cloudera.org:8080/#/c/17592/5//COMMIT_MSG
Commit Message:
http://gerrit.cloudera.org:8080/#/c/17592/5//COMMIT_MSG@73
PS5, Line 73: This would help measuring the impact of changes to the HashTable's
: data structure and algorithm.
> It would be nice to some results in the commit message
Added results for microbenchmark, billion Row benchmark and TPCH-42 benchmark. TPCDS-3000 needs few queries to be rerun.
http://gerrit.cloudera.org:8080/#/c/17592/7//COMMIT_MSG
Commit Message:
http://gerrit.cloudera.org:8080/#/c/17592/7//COMMIT_MSG@69
PS7, Line 69: As a part of this patch a new Micro Benchmark for HashTable has
: been introduced, which will help in measuring these:
: 1. Runtime for Building Hash Table and Probing the table.
: 2. Memory consumed after building the Table.
: This would help measuring the impact of changes to the HashTable's
: data structure and algorithm.
> nit. Nice addition! May be useful to include some results here.
Done.
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 9
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Qifan Chen <qc...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Wed, 04 Aug 2021 22:01:47 +0000
Gerrit-HasComments: Yes
[Impala-ASF-CR] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/17592 )
Change subject: IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
Patch Set 8:
(2 comments)
http://gerrit.cloudera.org:8080/#/c/17592/8/be/src/exec/grouping-aggregator-ir.cc
File be/src/exec/grouping-aggregator-ir.cc:
http://gerrit.cloudera.org:8080/#/c/17592/8/be/src/exec/grouping-aggregator-ir.cc@240
PS8, Line 240:
line has trailing whitespace
http://gerrit.cloudera.org:8080/#/c/17592/8/be/src/exec/hash-table.cc
File be/src/exec/hash-table.cc:
http://gerrit.cloudera.org:8080/#/c/17592/8/be/src/exec/hash-table.cc@579
PS8, Line 579: Status hash_allocation_status = allocator_->Allocate(new_hash_size, &new_hash_allocation);
line too long (92 > 90)
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 8
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Qifan Chen <qc...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Thu, 29 Jul 2021 14:00:29 +0000
Gerrit-HasComments: Yes
[Impala-ASF-CR] [WIP] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/17592 )
Change subject: [WIP] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
Patch Set 3:
Build Successful
https://jenkins.impala.io/job/gerrit-code-review-checks/8973/ : Initial code review checks passed. Use gerrit-verify-dryrun-external or gerrit-verify-dryrun to run full precommit tests.
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 3
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Tue, 22 Jun 2021 18:07:58 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] [WIP] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/17592 )
Change subject: [WIP] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
Patch Set 4:
Build Successful
https://jenkins.impala.io/job/gerrit-code-review-checks/8998/ : Initial code review checks passed. Use gerrit-verify-dryrun-external or gerrit-verify-dryrun to run full precommit tests.
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 4
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Thu, 24 Jun 2021 10:04:29 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Amogh Margoor (Code Review)" <ge...@cloudera.org>.
Amogh Margoor has uploaded a new patch set (#9). ( http://gerrit.cloudera.org:8080/17592 )
Change subject: IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
HashTable implementation comprises of contiguous
array of Buckets and each Bucket would either
have Data or will point to linked list of
duplicate entries named DuplicateNode. These
are the structures of Bucket and DuplicateNode:
struct DuplicateNode {
bool matched;
DuplicateNode* next;
HtData htdata;
};
struct Bucket {
bool filled;
bool matched;
bool hasDuplicates;
uint32_t hash;
union {
HtData htdata;
DuplicateNode* duplicates;
} bucketData;
};
Size of Bucket is currently 16 bytes and Size of Duplicate Node is
24 bytes. If we can remove the booleans from both struct size of
Bucket would reduce to 12 bytes and DuplicateNode will be 16 bytes.
One of the ways we can remove booleans is to fold it into pointers
already part of struct. Pointers store addresses and on
architectures like x86 and ARM the linear address is only 48 bits
long. With level 5 paging intel is planning to expand it to 57-bit
long which means we can use most significant 7 bits i.e., 58 to 64
bits to store these booleans. This patch reduces the size of Bucket
and DuplicateNode by implementing this folding. However, there is
another requirement regarding Size of Bucket to be power of 2 and
also for the number of buckets in Hash table to be power of 2.
These requirements are for the following reasons:
1. Memory Allocator allocates memory in power of 2 to avoid
internal fragmentation. Hence, num of buckets * sizeof(Buckets)
should be power of 2.
2. Number of buckets being power of 2 enables faster modulo
operation i.e., instead of slow modulo: (hash % N), faster
(hash & (N-1)) can be used.
Due to this, 4 bytes 'hash' field from Bucket is removed and
stored sperately in new array hash_array_ in HashTable.
This ensures sizeof(Bucket) is 8 which is power of 2.
New Classes:
------------
As a part of patch, TaggedPointer is introduced which is template
class to store pointers and tag together in 64 bit integer. This
structure contains the ownership of the pointer and will take care
of allocation and deallocation of the object being pointed to.
However derived classes can opt out of the ownership of the object
and let the client manage it. It's derived classes for Bucket and
DuplicateNode do the same. These classes are TaggedBucketData and
TaggedDuplicateNode.
Benchmark:
----------
As a part of this patch a new Micro Benchmark for HashTable has
been introduced, which will help in measuring these:
1. Runtime for Building Hash Table and Probing the table.
2. Memory consumed after building the Table.
This would help measuring the impact of changes to the HashTable's
data structure and algorithm.
Saw 25-30% reduction in memory consumed and no significant
difference in performance (0.91X-1.2X).
Other Benchmarks:
1. Billion row Synthetic benchmark on single node, single daemon:
a. 2-3% improvement in Join GEOMEAN for Probe benchmark.
b. 17% and 21% reduction in PeakMemoryUsage and
CumulativeBytes allocated respectively
2. TPCH-42: 0-1.5% improvement in GEOMEAN runtime
Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
---
M be/src/benchmarks/CMakeLists.txt
A be/src/benchmarks/hash-table-benchmark.cc
M be/src/exec/grouping-aggregator-ir.cc
M be/src/exec/grouping-aggregator-partition.cc
M be/src/exec/grouping-aggregator.cc
M be/src/exec/hash-table-test.cc
M be/src/exec/hash-table.cc
M be/src/exec/hash-table.h
M be/src/exec/hash-table.inline.h
M be/src/util/CMakeLists.txt
M be/src/util/benchmark.cc
M be/src/util/benchmark.h
A be/src/util/tagged-ptr-test.cc
A be/src/util/tagged-ptr.h
M fe/src/main/java/org/apache/impala/planner/PlannerContext.java
15 files changed, 1,082 insertions(+), 170 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/Impala-ASF refs/changes/92/17592/9
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 9
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Qifan Chen <qc...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
[Impala-ASF-CR] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Amogh Margoor (Code Review)" <ge...@cloudera.org>.
Amogh Margoor has uploaded a new patch set (#7). ( http://gerrit.cloudera.org:8080/17592 )
Change subject: IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
HashTable implementation comprises of contiguous
array of Buckets and each Bucket would either
have Data or will point to linked list of
duplicate entries named DuplicateNode. These
are the structures of Bucket and DuplicateNode:
struct DuplicateNode {
bool matched;
DuplicateNode* next;
HtData htdata;
};
struct Bucket {
bool filled;
bool matched;
bool hasDuplicates;
uint32_t hash;
union {
HtData htdata;
DuplicateNode* duplicates;
} bucketData;
};
Size of Bucket is currently 16 bytes and Size of Duplicate Node is
24 bytes. If we can remove the booleans from both struct size of
Bucket would reduce to 12 bytes and DuplicateNode will be 16 bytes.
One of the ways we can remove booleans is to fold it into pointers
already part of struct. Pointers store addresses and on
architectures like x86 and ARM the linear address is only 48 bits
long. With level 5 paging intel is planning to expand it to 57-bit
long which means we can use most significant 7 bits i.e., 58 to 64
bits to store these booleans. This patch reduces the size of Bucket
and DuplicateNode by implementing this folding. However, there is
another requirement regarding Size of Bucket to be power of 2 and
also for the number of buckets in Hash table to be power of 2.
These requirements are for the following reasons:
1. Memory Allocator allocates memory in power of 2 to avoid
internal fragmentation. Hence, num of buckets * sizeof(Buckets)
should be power of 2.
2. Number of buckets being power of 2 enables faster modulo
operation i.e., instead of slow modulo: (hash % N), faster
(hash & (N-1)) can be used.
Due to this, 4 bytes 'hash' field from Bucket is removed and
stored sperately in new array hash_array_ in HashTable.
This ensures sizeof(Bucket) is 8 which is power of 2.
New Classes:
------------
As a part of patch, TaggedPointer is introduced which is template
class to store pointers and tag together in 64 bit integer. This
structure contains the ownership of the pointer and will take care
of allocation and deallocation of the object being pointed to.
However derived classes can opt out of the ownership of the object
and let the client manage it. It's derived classes for Bucket and
DuplicateNode do the same. These classes are TaggedBucketData and
TaggedDuplicateNode.
Benchmark:
----------
As a part of this patch a new Micro Benchmark for HashTable has
been introduced, which will help in measuring these:
1. Runtime for Building Hash Table and Probing the table.
2. Memory consumed after building the Table.
This would help measuring the impact of changes to the HashTable's
data structure and algorithm.
Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
---
M be/src/benchmarks/CMakeLists.txt
A be/src/benchmarks/hash-table-benchmark.cc
M be/src/exec/hash-table-test.cc
M be/src/exec/hash-table.cc
M be/src/exec/hash-table.h
M be/src/exec/hash-table.inline.h
M be/src/util/CMakeLists.txt
M be/src/util/benchmark.cc
M be/src/util/benchmark.h
A be/src/util/tagged-ptr-test.cc
A be/src/util/tagged-ptr.h
M fe/src/main/java/org/apache/impala/planner/AggregationNode.java
M fe/src/main/java/org/apache/impala/planner/HashJoinNode.java
M fe/src/main/java/org/apache/impala/planner/PlannerContext.java
14 files changed, 1,001 insertions(+), 144 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/Impala-ASF refs/changes/92/17592/7
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 7
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
[Impala-ASF-CR] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/17592 )
Change subject: IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
Patch Set 7:
Build Successful
https://jenkins.impala.io/job/gerrit-code-review-checks/9113/ : Initial code review checks passed. Use gerrit-verify-dryrun-external or gerrit-verify-dryrun to run full precommit tests.
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 7
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Mon, 19 Jul 2021 12:03:12 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Amogh Margoor (Code Review)" <ge...@cloudera.org>.
Amogh Margoor has posted comments on this change. ( http://gerrit.cloudera.org:8080/17592 )
Change subject: IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
Patch Set 5:
Benchmark Result: https://docs.google.com/spreadsheets/d/1nPkfFG1DDossI8Q-F9ALzc2qJvDAQaHT1yaJzkOQZBs/edit?usp=sharing
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 5
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Sun, 04 Jul 2021 22:06:54 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] [WIP] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/17592 )
Change subject: [WIP] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
Patch Set 3:
(2 comments)
http://gerrit.cloudera.org:8080/#/c/17592/3/be/src/exec/hash-table.h
File be/src/exec/hash-table.h:
http://gerrit.cloudera.org:8080/#/c/17592/3/be/src/exec/hash-table.h@709
PS3, Line 709: setPtr((uint8*) flat_row);
line has trailing whitespace
http://gerrit.cloudera.org:8080/#/c/17592/3/be/src/exec/hash-table.h@725
PS3, Line 725: /// stored.
line has trailing whitespace
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 3
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Tue, 22 Jun 2021 17:48:05 +0000
Gerrit-HasComments: Yes
[Impala-ASF-CR] [WIP] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/17592 )
Change subject: [WIP] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
Patch Set 2:
Build Failed
https://jenkins.impala.io/job/gerrit-code-review-checks/8929/ : Initial code review checks failed. See linked job for details on the failure.
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 2
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Tue, 15 Jun 2021 23:06:21 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Amogh Margoor (Code Review)" <ge...@cloudera.org>.
Amogh Margoor has uploaded a new patch set (#6). ( http://gerrit.cloudera.org:8080/17592 )
Change subject: IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
HashTable implementation comprises of contiguous
array of Buckets and each Bucket would either
have Data or will point to linked list of
duplicate entries named DuplicateNode. These
are the structures of Bucket and DuplicateNode:
struct DuplicateNode {
bool matched;
DuplicateNode* next;
HtData htdata;
};
struct Bucket {
bool filled;
bool matched;
bool hasDuplicates;
uint32_t hash;
union {
HtData htdata;
DuplicateNode* duplicates;
} bucketData;
};
Size of Bucket is currently 16 bytes and Size of Duplicate Node is
24 bytes. If we can remove the booleans from both struct size of
Bucket would reduce to 12 bytes and DuplicateNode will be 16 bytes.
One of the ways we can remove booleans is to fold it into pointers
already part of struct. Pointers store addresses and on
architectures like x86 and ARM the linear address is only 48 bits
long. With level 5 paging intel is planning to expand it to 57-bit
long which means we can use most significant 7 bits i.e., 58 to 64
bits to store these booleans. This patch reduces the size of Bucket
and DuplicateNode by implementing this folding. However, there is
another requirement regarding Size of Bucket to be power of 2 and
also for the number of buckets in Hash table to be power of 2.
These requirements are for the following reasons:
1. Memory Allocator allocates memory in power of 2 to avoid
internal fragmentation. Hence, num of buckets * sizeof(Buckets)
should be power of 2.
2. Number of buckets being power of 2 enables faster modulo
operation i.e., instead of slow modulo: (hash % N), faster
(hash & (N-1)) can be used.
Due to this, 4 bytes 'hash' field from Bucket is removed and
stored sperately in new array hash_array_ in HashTable.
This ensures sizeof(Bucket) is 8 which is power of 2.
New Classes:
------------
As a part of patch, TaggedPointer is introduced which is template
class to store pointers and tag together in 64 bit integer. This
structure contains the ownership of the pointer and will take care
of allocation and deallocation of the object being pointed to.
However derived classes can opt out of the ownership of the object
and let the client manage it. It's derived classes for Bucket and
DuplicateNode do the same. These classes are TaggedBucketData and
TaggedDuplicateNode.
Benchmark:
----------
As a part of this patch a new Micro Benchmark for HashTable has
been introduced, which will help in measuring these:
1. Runtime for Building Hash Table and Probing the table.
2. Memory consumed after building the Table.
This would help measuring the impact of changes to the HashTable's
data structure and algorithm.
Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
---
M be/src/benchmarks/CMakeLists.txt
A be/src/benchmarks/hash-table-benchmark.cc
M be/src/exec/hash-table-test.cc
M be/src/exec/hash-table.cc
M be/src/exec/hash-table.h
M be/src/exec/hash-table.inline.h
M be/src/util/CMakeLists.txt
M be/src/util/benchmark.cc
M be/src/util/benchmark.h
A be/src/util/tagged-ptr-test.cc
A be/src/util/tagged-ptr.h
M fe/src/main/java/org/apache/impala/planner/AggregationNode.java
M fe/src/main/java/org/apache/impala/planner/HashJoinNode.java
M fe/src/main/java/org/apache/impala/planner/PlannerContext.java
14 files changed, 994 insertions(+), 144 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/Impala-ASF refs/changes/92/17592/6
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 6
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
[Impala-ASF-CR] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Amogh Margoor (Code Review)" <ge...@cloudera.org>.
Amogh Margoor has posted comments on this change. ( http://gerrit.cloudera.org:8080/17592 )
Change subject: IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
Patch Set 13:
(1 comment)
http://gerrit.cloudera.org:8080/#/c/17592/12/be/src/exec/hash-table.h
File be/src/exec/hash-table.h:
http://gerrit.cloudera.org:8080/#/c/17592/12/be/src/exec/hash-table.h@705
PS12, Line 705: { return IsTagBitSet<0>(); }
: ALWAYS_INLINE bool HasDuplicates() { return IsTagBit
> Okay on dead branch elimination.
Ok to avoid duplication, I have added it to class description along with redirections from method so that readers can locate it.
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 13
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Qifan Chen <qc...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Tue, 24 Aug 2021 17:29:00 +0000
Gerrit-HasComments: Yes
[Impala-ASF-CR] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Amogh Margoor (Code Review)" <ge...@cloudera.org>.
Amogh Margoor has posted comments on this change. ( http://gerrit.cloudera.org:8080/17592 )
Change subject: IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
Patch Set 5:
> (1 comment)
>
> I grabbed this change and was doing some local testing, and I ran
> into a scenario that crashes Impala.
>
> Here's what I did:
> 1. I loaded a larger TPC-H dataset in parquet (takes quite a while
> and will use up some disk space):
> bin/load-data.py -w tpch -s 42 --table_formats=text/none/none,parquet/none/none
> 2. Ran the following multiple times (it is intermittent):
> use tpch42_parquet;
> SELECT l_orderkey,
> count(*) AS cnt
> FROM lineitem
> GROUP BY l_orderkey
> HAVING count(*) > 9999999999999;
>
> That intermittently crashes with this stack:
> C [impalad+0x27e8546] long impala::HashTable::Probe<true,
> false>(impala::HashTable::Bucket*, long, impala::HashTableCtx*,
> unsigned int, bool*, impala::HashTable::BucketData*)+0x28c
> C [impalad+0x27e2141] impala::HashTable::ResizeBuckets(long,
> impala::HashTableCtx*, bool*)+0x7d1
> C [impalad+0x27e194d] impala::HashTable::CheckAndResize(unsigned
> long, impala::HashTableCtx*, bool*)+0xcb
> C [impalad+0x27c8a48] impala::GroupingAggregator::CheckAndResizeHashPartitions(bool,
> int, impala::HashTableCtx*)+0x176
>
> This may reproduce on smaller datasets.
Thanks for checking this out. I will check it and revert back.
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 5
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Thu, 08 Jul 2021 17:06:11 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Qifan Chen (Code Review)" <ge...@cloudera.org>.
Qifan Chen has posted comments on this change. ( http://gerrit.cloudera.org:8080/17592 )
Change subject: IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
Patch Set 10: Code-Review+1
(2 comments)
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/exec/hash-table.h
File be/src/exec/hash-table.h:
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/exec/hash-table.h@713
PS9, Line 713: r
> No, hash tables don't have this tag. This tag is used to only set or update
Okay. Maybe move this to a comment to explain TAGGED.
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/util/tagged-ptr-test.cc
File be/src/util/tagged-ptr-test.cc:
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/util/tagged-ptr-test.cc@59
PS9, Line 59:
> We use OWN=false in backend too.
Done
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 10
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Qifan Chen <qc...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Wed, 18 Aug 2021 15:11:50 +0000
Gerrit-HasComments: Yes
[Impala-ASF-CR] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Zoltan Borok-Nagy (Code Review)" <ge...@cloudera.org>.
Zoltan Borok-Nagy has posted comments on this change. ( http://gerrit.cloudera.org:8080/17592 )
Change subject: IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
Patch Set 9:
(5 comments)
Looks really good! Left some minor comments, will do another round tomorrow.
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/exec/grouping-aggregator-ir.cc
File be/src/exec/grouping-aggregator-ir.cc:
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/exec/grouping-aggregator-ir.cc@113
PS9, Line 113: false
nit: I wonder if instead of true/false we had an enum, then the code could be a bit more self explaining.
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/exec/grouping-aggregator-ir.cc@240
PS9, Line 240: else {
: if
nit: we could keep the old 'else if' and formatting so it is easier to spot what have changed.
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/exec/grouping-aggregator-ir.cc@245
PS9, Line 245:
nit: +2 indent
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/exec/grouping-aggregator-partition.cc
File be/src/exec/grouping-aggregator-partition.cc:
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/exec/grouping-aggregator-partition.cc@126
PS9, Line 126: false
nit: can we use an enum here as well?
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/util/tagged-ptr.h
File be/src/util/tagged-ptr.h:
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/util/tagged-ptr.h@47
PS9, Line 47: #define SET_UNSET_IS_TAG(bit) \
Instead of macros these could be template variables and template functions:
template <int bit>
static constexpr uintptr_t DATA_MASK = 1ULL << (63 - bit);
template <int bit>
static constexpr uintptr_t DATA_MASK_INVERSE = ~DATA_MASK<bit>;
template <int bit>
void SetTagBit() {
data_ = (data_ | DATA_MASK<bit>);
}
...
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 9
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Qifan Chen <qc...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Mon, 09 Aug 2021 18:01:34 +0000
Gerrit-HasComments: Yes
[Impala-ASF-CR] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Amogh Margoor (Code Review)" <ge...@cloudera.org>.
Amogh Margoor has posted comments on this change. ( http://gerrit.cloudera.org:8080/17592 )
Change subject: IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
Patch Set 12:
(1 comment)
http://gerrit.cloudera.org:8080/#/c/17592/12/be/src/exec/hash-table.h
File be/src/exec/hash-table.h:
http://gerrit.cloudera.org:8080/#/c/17592/12/be/src/exec/hash-table.h@705
PS12, Line 705: If bucket doesn't have tag fields set, TAGGED can
: /// be set to 'false' to avoid extra bit operations.
> nit. I think the following may describe the semantics better:
'IF' is upon boolean template parameter, so compiler will do dead branch elimination at compile time and it will not be a branch statement anymore after compilation. It's the same reason why LIKELY or UNLIKELY is not needed.
Reg comment, it describes 'false' value on purpose rather than 'true'. The reason is class definition and description in comment clearly depicts that that data is expected to be tagged and that is the default state (all it's clients even define this parameter as 'true' by default). Data being un-taggged is the special case and <TAGGED> exists to handle that special case itself.
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 12
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Qifan Chen <qc...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Tue, 24 Aug 2021 14:51:37 +0000
Gerrit-HasComments: Yes
[Impala-ASF-CR] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/17592 )
Change subject: IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
Patch Set 6:
Build Successful
https://jenkins.impala.io/job/gerrit-code-review-checks/9082/ : Initial code review checks passed. Use gerrit-verify-dryrun-external or gerrit-verify-dryrun to run full precommit tests.
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 6
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Tue, 13 Jul 2021 11:39:15 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Amogh Margoor (Code Review)" <ge...@cloudera.org>.
Amogh Margoor has uploaded a new patch set (#13). ( http://gerrit.cloudera.org:8080/17592 )
Change subject: IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
HashTable implementation in Impala comprises of contiguous array
of Buckets and each Bucket contains either data or pointer to
linked list of duplicate entries named DuplicateNode.
These are the structures of Bucket and DuplicateNode:
struct DuplicateNode {
bool matched;
DuplicateNode* next;
HtData htdata;
};
struct Bucket {
bool filled;
bool matched;
bool hasDuplicates;
uint32_t hash;
union {
HtData htdata;
DuplicateNode* duplicates;
} bucketData;
};
Size of Bucket is currently 16 bytes and size of DuplicateNode is
24 bytes. If we can remove the booleans from both struct size of
Bucket would reduce to 12 bytes and DuplicateNode will be 16 bytes.
One of the ways we can remove booleans is to fold it into pointers
already part of struct. Pointers store addresses and on
architectures like x86 and ARM the linear address is only 48 bits
long. With level 5 paging Intel is planning to expand it to 57-bit
long which means we can use most significant 7 bits i.e., 58 to 64
bits to store these booleans. This patch reduces the size of Bucket
and DuplicateNode by implementing this folding. However, there is
another requirement regarding Size of Bucket to be power of 2 and
also for the number of buckets in Hash table to be power of 2.
These requirements are for the following reasons:
1. Memory Allocator allocates memory in power of 2 to avoid
internal fragmentation. Hence, num of buckets * sizeof(Buckets)
should be power of 2.
2. Number of buckets being power of 2 enables faster modulo
operation i.e., instead of slow modulo: (hash % N), faster
(hash & (N-1)) can be used.
Due to this, 4 bytes 'hash' field from Bucket is removed and
stored separately in new array hash_array_ in HashTable.
This ensures sizeof(Bucket) is 8 which is power of 2.
New Classes:
------------
As a part of patch, TaggedPointer is introduced which is a template
class to store a pointer and 7-bit tag together in 64 bit integer.
This structure contains the ownership of the pointer and will take care
of allocation and deallocation of the object being pointed to.
However derived classes can opt out of the ownership of the object
and let the client manage it. It's derived classes for Bucket and
DuplicateNode do the same. These classes are TaggedBucketData and
TaggedDuplicateNode.
Benchmark:
----------
As a part of this patch a new Micro Benchmark for HashTable has
been introduced, which will help in measuring these:
1. Runtime for building hash table and probing it.
2. Memory consumed after building the Table.
This would help measuring the impact of changes to the HashTable's
data structure and algorithm.
Saw 25-30% reduction in memory consumed and no significant
difference in performance (0.91X-1.2X).
Other Benchmarks:
1. Billion row Synthetic benchmark on single node, single daemon:
a. 2-3% improvement in Join GEOMEAN for Probe benchmark.
b. 17% and 21% reduction in PeakMemoryUsage and
CumulativeBytes allocated respectively
2. TPCH-42: 0-1.5% improvement in GEOMEAN runtime
Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
---
M be/src/benchmarks/CMakeLists.txt
A be/src/benchmarks/hash-table-benchmark.cc
M be/src/exec/grouping-aggregator-ir.cc
M be/src/exec/grouping-aggregator-partition.cc
M be/src/exec/grouping-aggregator.cc
M be/src/exec/hash-table-test.cc
M be/src/exec/hash-table.cc
M be/src/exec/hash-table.h
M be/src/exec/hash-table.inline.h
M be/src/util/CMakeLists.txt
M be/src/util/benchmark.cc
M be/src/util/benchmark.h
A be/src/util/tagged-ptr-test.cc
A be/src/util/tagged-ptr.h
M fe/src/main/java/org/apache/impala/planner/PlannerContext.java
M fe/src/test/java/org/apache/impala/planner/CardinalityTest.java
M testdata/workloads/functional-planner/queries/PlannerTest/fk-pk-join-detection-hdfs-num-rows-est-enabled.test
M testdata/workloads/functional-planner/queries/PlannerTest/fk-pk-join-detection.test
M testdata/workloads/functional-planner/queries/PlannerTest/max-row-size.test
M testdata/workloads/functional-planner/queries/PlannerTest/resource-requirements.test
M testdata/workloads/functional-planner/queries/PlannerTest/spillable-buffer-sizing.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q01.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q04.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q05.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q06.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q07.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q11.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q12.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q14a.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q15.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q16.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q17.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q18.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q19.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q20.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q22.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q23a.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q23b.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q24a.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q24b.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q25.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q26.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q27.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q29.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q34.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q35a.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q38.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q39a.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q39b.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q45.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q46.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q47.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q48.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q50.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q51.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q56.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q57.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q58.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q60.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q61.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q64.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q66.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q67.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q68.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q72.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q73.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q74.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q78.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q80.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q82.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q83.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q85.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q87.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q95.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q97.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q98.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpch-all.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpch-kudu.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpch-nested.test
M testdata/workloads/functional-query/queries/QueryTest/spilling-broadcast-joins.test
M testdata/workloads/functional-query/queries/QueryTest/spilling.test
81 files changed, 1,974 insertions(+), 1,048 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/Impala-ASF refs/changes/92/17592/13
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 13
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Qifan Chen <qc...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
[Impala-ASF-CR] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Amogh Margoor (Code Review)" <ge...@cloudera.org>.
Amogh Margoor has uploaded a new patch set (#10). ( http://gerrit.cloudera.org:8080/17592 )
Change subject: IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
HashTable implementation in Impala comprises of contiguous array
of Buckets and each Bucket contains either data or pointer to
linked list of duplicate entries named DuplicateNode.
These are the structures of Bucket and DuplicateNode:
struct DuplicateNode {
bool matched;
DuplicateNode* next;
HtData htdata;
};
struct Bucket {
bool filled;
bool matched;
bool hasDuplicates;
uint32_t hash;
union {
HtData htdata;
DuplicateNode* duplicates;
} bucketData;
};
Size of Bucket is currently 16 bytes and size of DuplicateNode is
24 bytes. If we can remove the booleans from both struct size of
Bucket would reduce to 12 bytes and DuplicateNode will be 16 bytes.
One of the ways we can remove booleans is to fold it into pointers
already part of struct. Pointers store addresses and on
architectures like x86 and ARM the linear address is only 48 bits
long. With level 5 paging Intel is planning to expand it to 57-bit
long which means we can use most significant 7 bits i.e., 58 to 64
bits to store these booleans. This patch reduces the size of Bucket
and DuplicateNode by implementing this folding. However, there is
another requirement regarding Size of Bucket to be power of 2 and
also for the number of buckets in Hash table to be power of 2.
These requirements are for the following reasons:
1. Memory Allocator allocates memory in power of 2 to avoid
internal fragmentation. Hence, num of buckets * sizeof(Buckets)
should be power of 2.
2. Number of buckets being power of 2 enables faster modulo
operation i.e., instead of slow modulo: (hash % N), faster
(hash & (N-1)) can be used.
Due to this, 4 bytes 'hash' field from Bucket is removed and
stored separately in new array hash_array_ in HashTable.
This ensures sizeof(Bucket) is 8 which is power of 2.
New Classes:
------------
As a part of patch, TaggedPointer is introduced which is a template
class to store a pointer and 7-bit tag together in 64 bit integer.
This structure contains the ownership of the pointer and will take care
of allocation and deallocation of the object being pointed to.
However derived classes can opt out of the ownership of the object
and let the client manage it. It's derived classes for Bucket and
DuplicateNode do the same. These classes are TaggedBucketData and
TaggedDuplicateNode.
Benchmark:
----------
As a part of this patch a new Micro Benchmark for HashTable has
been introduced, which will help in measuring these:
1. Runtime for building hash table and probing it.
2. Memory consumed after building the Table.
This would help measuring the impact of changes to the HashTable's
data structure and algorithm.
Saw 25-30% reduction in memory consumed and no significant
difference in performance (0.91X-1.2X).
Other Benchmarks:
1. Billion row Synthetic benchmark on single node, single daemon:
a. 2-3% improvement in Join GEOMEAN for Probe benchmark.
b. 17% and 21% reduction in PeakMemoryUsage and
CumulativeBytes allocated respectively
2. TPCH-42: 0-1.5% improvement in GEOMEAN runtime
Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
---
M be/src/benchmarks/CMakeLists.txt
A be/src/benchmarks/hash-table-benchmark.cc
M be/src/exec/grouping-aggregator-ir.cc
M be/src/exec/grouping-aggregator-partition.cc
M be/src/exec/grouping-aggregator.cc
M be/src/exec/hash-table-test.cc
M be/src/exec/hash-table.cc
M be/src/exec/hash-table.h
M be/src/exec/hash-table.inline.h
M be/src/util/CMakeLists.txt
M be/src/util/benchmark.cc
M be/src/util/benchmark.h
A be/src/util/tagged-ptr-test.cc
A be/src/util/tagged-ptr.h
M fe/src/main/java/org/apache/impala/planner/PlannerContext.java
15 files changed, 1,072 insertions(+), 159 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/Impala-ASF refs/changes/92/17592/10
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 10
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Qifan Chen <qc...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
[Impala-ASF-CR] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has submitted this change and it was merged. ( http://gerrit.cloudera.org:8080/17592 )
Change subject: IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
HashTable implementation in Impala comprises of contiguous array
of Buckets and each Bucket contains either data or pointer to
linked list of duplicate entries named DuplicateNode.
These are the structures of Bucket and DuplicateNode:
struct DuplicateNode {
bool matched;
DuplicateNode* next;
HtData htdata;
};
struct Bucket {
bool filled;
bool matched;
bool hasDuplicates;
uint32_t hash;
union {
HtData htdata;
DuplicateNode* duplicates;
} bucketData;
};
Size of Bucket is currently 16 bytes and size of DuplicateNode is
24 bytes. If we can remove the booleans from both struct size of
Bucket would reduce to 12 bytes and DuplicateNode will be 16 bytes.
One of the ways we can remove booleans is to fold it into pointers
already part of struct. Pointers store addresses and on
architectures like x86 and ARM the linear address is only 48 bits
long. With level 5 paging Intel is planning to expand it to 57-bit
long which means we can use most significant 7 bits i.e., 58 to 64
bits to store these booleans. This patch reduces the size of Bucket
and DuplicateNode by implementing this folding. However, there is
another requirement regarding Size of Bucket to be power of 2 and
also for the number of buckets in Hash table to be power of 2.
These requirements are for the following reasons:
1. Memory Allocator allocates memory in power of 2 to avoid
internal fragmentation. Hence, num of buckets * sizeof(Buckets)
should be power of 2.
2. Number of buckets being power of 2 enables faster modulo
operation i.e., instead of slow modulo: (hash % N), faster
(hash & (N-1)) can be used.
Due to this, 4 bytes 'hash' field from Bucket is removed and
stored separately in new array hash_array_ in HashTable.
This ensures sizeof(Bucket) is 8 which is power of 2.
New Classes:
------------
As a part of patch, TaggedPointer is introduced which is a template
class to store a pointer and 7-bit tag together in 64 bit integer.
This structure contains the ownership of the pointer and will take care
of allocation and deallocation of the object being pointed to.
However derived classes can opt out of the ownership of the object
and let the client manage it. It's derived classes for Bucket and
DuplicateNode do the same. These classes are TaggedBucketData and
TaggedDuplicateNode.
Benchmark:
----------
As a part of this patch a new Micro Benchmark for HashTable has
been introduced, which will help in measuring these:
1. Runtime for building hash table and probing it.
2. Memory consumed after building the Table.
This would help measuring the impact of changes to the HashTable's
data structure and algorithm.
Saw 25-30% reduction in memory consumed and no significant
difference in performance (0.91X-1.2X).
Other Benchmarks:
1. Billion row Synthetic benchmark on single node, single daemon:
a. 2-3% improvement in Join GEOMEAN for Probe benchmark.
b. 17% and 21% reduction in PeakMemoryUsage and
CumulativeBytes allocated respectively
2. TPCH-42: 0-1.5% improvement in GEOMEAN runtime
Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Reviewed-on: http://gerrit.cloudera.org:8080/17592
Reviewed-by: Zoltan Borok-Nagy <bo...@cloudera.com>
Tested-by: Impala Public Jenkins <im...@cloudera.com>
---
M be/src/benchmarks/CMakeLists.txt
A be/src/benchmarks/hash-table-benchmark.cc
M be/src/exec/grouping-aggregator-ir.cc
M be/src/exec/grouping-aggregator-partition.cc
M be/src/exec/grouping-aggregator.cc
M be/src/exec/hash-table-test.cc
M be/src/exec/hash-table.cc
M be/src/exec/hash-table.h
M be/src/exec/hash-table.inline.h
M be/src/util/CMakeLists.txt
M be/src/util/benchmark.cc
M be/src/util/benchmark.h
A be/src/util/tagged-ptr-test.cc
A be/src/util/tagged-ptr.h
M fe/src/main/java/org/apache/impala/planner/PlannerContext.java
M fe/src/test/java/org/apache/impala/planner/CardinalityTest.java
M testdata/workloads/functional-planner/queries/PlannerTest/fk-pk-join-detection-hdfs-num-rows-est-enabled.test
M testdata/workloads/functional-planner/queries/PlannerTest/fk-pk-join-detection.test
M testdata/workloads/functional-planner/queries/PlannerTest/max-row-size.test
M testdata/workloads/functional-planner/queries/PlannerTest/resource-requirements.test
M testdata/workloads/functional-planner/queries/PlannerTest/spillable-buffer-sizing.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q01.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q04.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q05.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q06.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q07.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q11.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q12.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q14a.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q15.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q16.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q17.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q18.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q19.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q20.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q22.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q23a.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q23b.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q24a.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q24b.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q25.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q26.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q27.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q29.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q34.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q35a.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q38.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q39a.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q39b.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q45.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q46.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q47.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q48.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q50.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q51.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q56.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q57.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q58.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q60.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q61.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q64.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q66.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q67.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q68.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q72.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q73.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q74.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q78.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q80.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q82.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q83.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q85.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q87.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q95.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q97.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q98.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpch-all.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpch-kudu.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpch-nested.test
M testdata/workloads/functional-query/queries/QueryTest/spilling-broadcast-joins.test
M testdata/workloads/functional-query/queries/QueryTest/spilling.test
81 files changed, 1,975 insertions(+), 1,048 deletions(-)
Approvals:
Zoltan Borok-Nagy: Looks good to me, approved
Impala Public Jenkins: Verified
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: merged
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 15
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Qifan Chen <qc...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
[Impala-ASF-CR] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Amogh Margoor (Code Review)" <ge...@cloudera.org>.
Amogh Margoor has posted comments on this change. ( http://gerrit.cloudera.org:8080/17592 )
Change subject: IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
Patch Set 11:
> Uploaded patch set 11.
Patch adjust estimated memories in testcases for Joins and aggregates, especially in Tpcds test plans.
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 11
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Qifan Chen <qc...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Sat, 21 Aug 2021 07:21:22 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Zoltan Borok-Nagy (Code Review)" <ge...@cloudera.org>.
Zoltan Borok-Nagy has posted comments on this change. ( http://gerrit.cloudera.org:8080/17592 )
Change subject: IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
Patch Set 9:
(7 comments)
This is really great work! I only found a few more nits.
http://gerrit.cloudera.org:8080/#/c/17592/9//COMMIT_MSG
Commit Message:
http://gerrit.cloudera.org:8080/#/c/17592/9//COMMIT_MSG@53
PS9, Line 53: sperately
separately
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/exec/hash-table.h
File be/src/exec/hash-table.h:
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/exec/hash-table.h@661
PS9, Line 661: ~TaggedDuplicateNode() {}
nit: this definition is not needed
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/exec/hash-table.h@689
PS9, Line 689: it's
nit: its
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/exec/hash-table.h@692
PS9, Line 692: (Tag bit 0)
seems like it's not true anymore
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/exec/hash-table.h@698
PS9, Line 698: Tag bit 2
Tag bit 1?
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/exec/hash-table.h@723
PS9, Line 723: ~TaggedBucketData() {}
nit: this definition is not needed.
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/exec/hash-table.h@732
PS9, Line 732: /// 2. Bucket is attributted as packed with alignment of 4 to ensure no padding
: /// is used.
Seems like it's not true anymore
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 9
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Qifan Chen <qc...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Tue, 10 Aug 2021 16:07:05 +0000
Gerrit-HasComments: Yes
[Impala-ASF-CR] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/17592 )
Change subject: IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
Patch Set 8:
Build Successful
https://jenkins.impala.io/job/gerrit-code-review-checks/9207/ : Initial code review checks passed. Use gerrit-verify-dryrun-external or gerrit-verify-dryrun to run full precommit tests.
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 8
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Qifan Chen <qc...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Thu, 29 Jul 2021 14:22:21 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Zoltan Borok-Nagy (Code Review)" <ge...@cloudera.org>.
Zoltan Borok-Nagy has posted comments on this change. ( http://gerrit.cloudera.org:8080/17592 )
Change subject: IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
Patch Set 13: Code-Review+1
(1 comment)
I had a small comment, otherwise the change looks awesome. It's good to see the decrease of memory consumption.
http://gerrit.cloudera.org:8080/#/c/17592/13/be/src/util/tagged-ptr.h
File be/src/util/tagged-ptr.h:
http://gerrit.cloudera.org:8080/#/c/17592/13/be/src/util/tagged-ptr.h@87
PS13, Line 87: DCHECK_IN_RANGE(bit, 0, 6);
This could be a compile-time check with static_assert.
Same in L92 and L98.
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 13
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Qifan Chen <qc...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Wed, 25 Aug 2021 07:29:03 +0000
Gerrit-HasComments: Yes
[Impala-ASF-CR] WIP: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/17592 )
Change subject: WIP: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
Patch Set 1:
Build Failed
https://jenkins.impala.io/job/gerrit-code-review-checks/8902/ : Initial code review checks failed. See linked job for details on the failure.
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 1
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Comment-Date: Mon, 14 Jun 2021 10:11:29 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] [WIP] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Amogh Margoor (Code Review)" <ge...@cloudera.org>.
Amogh Margoor has uploaded a new patch set (#4). ( http://gerrit.cloudera.org:8080/17592 )
Change subject: [WIP] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
[WIP] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
HashTable implementation comprises of contiguos
array of Buckets and each Bucket would either
have Data or will point to linked list of
duplicate entries named DuplicateNode. These
are the structures of Bucket and DuplicateNode:
struct DuplicateNode {
bool matched;
DuplicateNode* next;
HtData htdata;
};
struct Bucket {
bool filled;
bool matched;
bool hasDuplicates;
uint32_t hash;
union {
HtData htdata;
DuplicateNode* duplicates;
} bucketData;
};
Size of Bucket is currently 16 bytes and Size of Duplicate Node is
24 bytes. If we can remove the booleans from both struct size of
Bucket would reduce to 12 bytes and DuplicateNode will be 16 bytes.
One of the ways we can remove booleans is to fold it into pointers
already part of struct. Pointers store addresses and on
architectures like x86 and ARM the linear address is only 48 bits
long. With level 5 paging intel is planning to expand it to 57-bit
long which means we can use most significant 7 bits i.e., 58 to 64
bits to store these booleans. This patch reduces the size of Bucket
and DuplicateNode by implementing this folding.
New Classes:
------------
As a part of patch, TaggedPointer is introduced which is template
class to store pointers and tag together in 64 bit integer. This
structure contains the ownership of the pointer and will take care
of allocation and deallocation the the object being pointed to.
However derived classes can opt out of the ownership of the object
and let the client manage it. It's derived classes for Bucket and
DuplicateNode do the same. These classes are TaggedBucketData and
TaggedDuplicateNode.
Benchmark:
----------
As a part ofthis patch a new Micro Benchmark for HashTable has
been introduced, which will help in measuring these:
1. Runtime for Building Hash Table and Probing the table.
2. Memory consumed after building the Table.
This would help measuring the impact of changes to the HashTable's
data structure and algorithm.
Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
---
M be/src/benchmarks/CMakeLists.txt
A be/src/benchmarks/hash-table-benchmark.cc
M be/src/exec/grouping-aggregator.h
M be/src/exec/hash-table-test.cc
M be/src/exec/hash-table.cc
M be/src/exec/hash-table.h
M be/src/exec/hash-table.inline.h
M be/src/runtime/buffered-tuple-stream.h
M be/src/util/CMakeLists.txt
A be/src/util/tagged-ptr-test.cc
A be/src/util/tagged-ptr.h
M fe/src/main/java/org/apache/impala/planner/PlannerContext.java
12 files changed, 941 insertions(+), 149 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/Impala-ASF refs/changes/92/17592/4
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 4
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
[Impala-ASF-CR] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Qifan Chen (Code Review)" <ge...@cloudera.org>.
Qifan Chen has posted comments on this change. ( http://gerrit.cloudera.org:8080/17592 )
Change subject: IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
Patch Set 12:
(1 comment)
http://gerrit.cloudera.org:8080/#/c/17592/12/be/src/exec/hash-table.h
File be/src/exec/hash-table.h:
http://gerrit.cloudera.org:8080/#/c/17592/12/be/src/exec/hash-table.h@705
PS12, Line 705: If bucket doesn't have tag fields set, TAGGED can
: /// be set to 'false' to avoid extra bit operations.
> 'IF' is upon boolean template parameter, so compiler will do dead branch e
Okay on dead branch elimination.
On comment for TAGGED, I think it is still a good idea to add it to the class level description, as I saw duplication of comments on the same topic.
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 12
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Qifan Chen <qc...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Tue, 24 Aug 2021 15:08:25 +0000
Gerrit-HasComments: Yes
[Impala-ASF-CR] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/17592 )
Change subject: IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
Patch Set 5:
Build Successful
https://jenkins.impala.io/job/gerrit-code-review-checks/9032/ : Initial code review checks passed. Use gerrit-verify-dryrun-external or gerrit-verify-dryrun to run full precommit tests.
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 5
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Sun, 04 Jul 2021 17:04:54 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] [WIP] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/17592 )
Change subject: [WIP] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
Patch Set 2:
(1 comment)
http://gerrit.cloudera.org:8080/#/c/17592/2/be/src/exec/hash-table.h
File be/src/exec/hash-table.h:
http://gerrit.cloudera.org:8080/#/c/17592/2/be/src/exec/hash-table.h@708
PS2, Line 708: void setFlatRow(BufferedTupleStream::FlatRowPtr flat_row) { setPtr((uint8*) flat_row); }
line too long (92 > 90)
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 2
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Tue, 15 Jun 2021 22:45:44 +0000
Gerrit-HasComments: Yes
[Impala-ASF-CR] WIP: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/17592 )
Change subject: WIP: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
Patch Set 1:
(3 comments)
http://gerrit.cloudera.org:8080/#/c/17592/1/be/src/exec/hash-table.inline.h
File be/src/exec/hash-table.inline.h:
http://gerrit.cloudera.org:8080/#/c/17592/1/be/src/exec/hash-table.inline.h@184
PS1, Line 184: if ((!has_duplicates && bucket->is_matched()) || (has_duplicates && node->is_matched())) {
line too long (92 > 90)
http://gerrit.cloudera.org:8080/#/c/17592/1/be/src/exec/hash-table.inline.h@194
PS1, Line 194: *node = stores_duplicates() ? buckets_[*bucket_idx].bucket_data()->duplicates : NULL;
line too long (91 > 90)
http://gerrit.cloudera.org:8080/#/c/17592/1/be/src/util/tagged-ptr.h
File be/src/util/tagged-ptr.h:
http://gerrit.cloudera.org:8080/#/c/17592/1/be/src/util/tagged-ptr.h@31
PS1, Line 31: /// canonical address is also 57-bit canonical. For 64-bit address
line has trailing whitespace
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 1
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Comment-Date: Mon, 14 Jun 2021 09:50:56 +0000
Gerrit-HasComments: Yes
[Impala-ASF-CR] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Amogh Margoor (Code Review)" <ge...@cloudera.org>.
Amogh Margoor has uploaded a new patch set (#11). ( http://gerrit.cloudera.org:8080/17592 )
Change subject: IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
HashTable implementation in Impala comprises of contiguous array
of Buckets and each Bucket contains either data or pointer to
linked list of duplicate entries named DuplicateNode.
These are the structures of Bucket and DuplicateNode:
struct DuplicateNode {
bool matched;
DuplicateNode* next;
HtData htdata;
};
struct Bucket {
bool filled;
bool matched;
bool hasDuplicates;
uint32_t hash;
union {
HtData htdata;
DuplicateNode* duplicates;
} bucketData;
};
Size of Bucket is currently 16 bytes and size of DuplicateNode is
24 bytes. If we can remove the booleans from both struct size of
Bucket would reduce to 12 bytes and DuplicateNode will be 16 bytes.
One of the ways we can remove booleans is to fold it into pointers
already part of struct. Pointers store addresses and on
architectures like x86 and ARM the linear address is only 48 bits
long. With level 5 paging Intel is planning to expand it to 57-bit
long which means we can use most significant 7 bits i.e., 58 to 64
bits to store these booleans. This patch reduces the size of Bucket
and DuplicateNode by implementing this folding. However, there is
another requirement regarding Size of Bucket to be power of 2 and
also for the number of buckets in Hash table to be power of 2.
These requirements are for the following reasons:
1. Memory Allocator allocates memory in power of 2 to avoid
internal fragmentation. Hence, num of buckets * sizeof(Buckets)
should be power of 2.
2. Number of buckets being power of 2 enables faster modulo
operation i.e., instead of slow modulo: (hash % N), faster
(hash & (N-1)) can be used.
Due to this, 4 bytes 'hash' field from Bucket is removed and
stored separately in new array hash_array_ in HashTable.
This ensures sizeof(Bucket) is 8 which is power of 2.
New Classes:
------------
As a part of patch, TaggedPointer is introduced which is a template
class to store a pointer and 7-bit tag together in 64 bit integer.
This structure contains the ownership of the pointer and will take care
of allocation and deallocation of the object being pointed to.
However derived classes can opt out of the ownership of the object
and let the client manage it. It's derived classes for Bucket and
DuplicateNode do the same. These classes are TaggedBucketData and
TaggedDuplicateNode.
Benchmark:
----------
As a part of this patch a new Micro Benchmark for HashTable has
been introduced, which will help in measuring these:
1. Runtime for building hash table and probing it.
2. Memory consumed after building the Table.
This would help measuring the impact of changes to the HashTable's
data structure and algorithm.
Saw 25-30% reduction in memory consumed and no significant
difference in performance (0.91X-1.2X).
Other Benchmarks:
1. Billion row Synthetic benchmark on single node, single daemon:
a. 2-3% improvement in Join GEOMEAN for Probe benchmark.
b. 17% and 21% reduction in PeakMemoryUsage and
CumulativeBytes allocated respectively
2. TPCH-42: 0-1.5% improvement in GEOMEAN runtime
Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
---
M be/src/benchmarks/CMakeLists.txt
A be/src/benchmarks/hash-table-benchmark.cc
M be/src/exec/grouping-aggregator-ir.cc
M be/src/exec/grouping-aggregator-partition.cc
M be/src/exec/grouping-aggregator.cc
M be/src/exec/hash-table-test.cc
M be/src/exec/hash-table.cc
M be/src/exec/hash-table.h
M be/src/exec/hash-table.inline.h
M be/src/util/CMakeLists.txt
M be/src/util/benchmark.cc
M be/src/util/benchmark.h
A be/src/util/tagged-ptr-test.cc
A be/src/util/tagged-ptr.h
M fe/src/main/java/org/apache/impala/planner/PlannerContext.java
M fe/src/test/java/org/apache/impala/planner/CardinalityTest.java
M testdata/workloads/functional-planner/queries/PlannerTest/fk-pk-join-detection-hdfs-num-rows-est-enabled.test
M testdata/workloads/functional-planner/queries/PlannerTest/fk-pk-join-detection.test
M testdata/workloads/functional-planner/queries/PlannerTest/max-row-size.test
M testdata/workloads/functional-planner/queries/PlannerTest/resource-requirements.test
M testdata/workloads/functional-planner/queries/PlannerTest/spillable-buffer-sizing.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q01.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q04.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q05.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q06.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q07.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q11.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q12.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q14a.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q15.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q16.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q17.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q18.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q19.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q20.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q22.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q23a.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q23b.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q24a.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q24b.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q25.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q26.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q27.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q29.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q34.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q35a.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q38.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q39a.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q39b.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q45.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q46.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q47.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q48.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q50.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q51.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q56.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q57.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q58.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q60.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q61.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q64.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q66.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q67.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q68.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q72.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q73.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q74.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q78.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q80.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q82.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q83.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q85.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q87.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q95.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q97.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpcds/tpcds-q98.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpch-all.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpch-kudu.test
M testdata/workloads/functional-planner/queries/PlannerTest/tpch-nested.test
M testdata/workloads/functional-query/queries/QueryTest/spilling-broadcast-joins.test
M testdata/workloads/functional-query/queries/QueryTest/spilling.test
81 files changed, 1,912 insertions(+), 988 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/Impala-ASF refs/changes/92/17592/11
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 11
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Qifan Chen <qc...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
[Impala-ASF-CR] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/17592 )
Change subject: IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
Patch Set 14:
Build started: https://jenkins.impala.io/job/gerrit-verify-dryrun/7419/ DRY_RUN=false
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 14
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Qifan Chen <qc...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Wed, 25 Aug 2021 13:46:49 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] [WIP] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Amogh Margoor (Code Review)" <ge...@cloudera.org>.
Amogh Margoor has uploaded a new patch set (#2). ( http://gerrit.cloudera.org:8080/17592 )
Change subject: [WIP] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
[WIP] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
HashTable implementation comprises of contiguos
array of Buckets and each Bucket would either
have Data or will point to linked list of
duplicate entries named DuplicateNode. These
are the structures of Bucket and DuplicateNode:
struct DuplicateNode {
bool matched;
DuplicateNode* next;
HtData htdata;
};
struct Bucket {
bool filled;
bool matched;
bool hasDuplicates;
uint32_t hash;
union {
HtData htdata;
DuplicateNode* duplicates;
} bucketData;
};
Size of Bucket is currently 16 bytes and Size of Duplicate Node is
24 bytes. If we can remove the booleans from both struct size of
Bucket would reduce to 12 bytes and DuplicateNode will be 16 bytes.
One of the ways we can remove booleans is to fold it into pointers
already part of struct. Pointers store addresses and on
architectures like x86 and ARM the linear address is only 48 bits
long. With level 5 paging intel is planning to expand it to 57-bit
long which means we can use most significant 7 bits i.e., 58 to 64
bits to store these booleans. This patch reduces the size of Bucket
and DuplicateNode by implementing this folding.
New Classes:
------------
As a part of patch, TaggedPointer is introduced which is template
class to store pointers and tag together in 64 bit integer. This
structure contains the ownership of the pointer and will take care
of allocation and deallocation the the object being pointed to.
However derived classes can opt out of the ownership of the object
and let the client manage it. It's derived classes for Bucket and
DuplicateNode do the same. These classes are TaggedBucketData and
TaggedDuplicateNode.
Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
---
M be/src/exec/grouping-aggregator.h
M be/src/exec/hash-table.cc
M be/src/exec/hash-table.h
M be/src/exec/hash-table.inline.h
M be/src/runtime/buffered-tuple-stream.h
M be/src/util/CMakeLists.txt
A be/src/util/tagged-ptr-test.cc
A be/src/util/tagged-ptr.h
M fe/src/main/java/org/apache/impala/planner/PlannerContext.java
9 files changed, 544 insertions(+), 146 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/Impala-ASF refs/changes/92/17592/2
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 2
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
[Impala-ASF-CR] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Amogh Margoor (Code Review)" <ge...@cloudera.org>.
Amogh Margoor has posted comments on this change. ( http://gerrit.cloudera.org:8080/17592 )
Change subject: IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
Patch Set 15:
Thanks Zoltan and Qifan for the reviews and Joe for the benchmark suggestion.
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 15
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Qifan Chen <qc...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Thu, 26 Aug 2021 12:29:46 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/17592 )
Change subject: IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
Patch Set 13:
Build Successful
https://jenkins.impala.io/job/gerrit-code-review-checks/9359/ : Initial code review checks passed. Use gerrit-verify-dryrun-external or gerrit-verify-dryrun to run full precommit tests.
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 13
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Qifan Chen <qc...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Tue, 24 Aug 2021 17:50:47 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Qifan Chen (Code Review)" <ge...@cloudera.org>.
Qifan Chen has posted comments on this change. ( http://gerrit.cloudera.org:8080/17592 )
Change subject: IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
Patch Set 7:
(10 comments)
Looks pretty good.
My only concern is whether there is a significant performance degradation, and how much.
http://gerrit.cloudera.org:8080/#/c/17592/7//COMMIT_MSG
Commit Message:
http://gerrit.cloudera.org:8080/#/c/17592/7//COMMIT_MSG@69
PS7, Line 69: As a part of this patch a new Micro Benchmark for HashTable has
: been introduced, which will help in measuring these:
: 1. Runtime for Building Hash Table and Probing the table.
: 2. Memory consumed after building the Table.
: This would help measuring the impact of changes to the HashTable's
: data structure and algorithm.
nit. Nice addition! May be useful to include some results here.
May also include some numbers from TPCDS here.
http://gerrit.cloudera.org:8080/#/c/17592/7/be/src/exec/hash-table.h
File be/src/exec/hash-table.h:
http://gerrit.cloudera.org:8080/#/c/17592/7/be/src/exec/hash-table.h@653
PS7, Line 653: 0
nit. May define and use constant for MATCHED here.
http://gerrit.cloudera.org:8080/#/c/17592/7/be/src/exec/hash-table.h@697
PS7, Line 697: 0
nit. same as above. May use constants for FILLED, MATCHED and DUPLICATED, instead of 0, 1 and 2 directly.
http://gerrit.cloudera.org:8080/#/c/17592/7/be/src/util/tagged-ptr.h
File be/src/util/tagged-ptr.h:
http://gerrit.cloudera.org:8080/#/c/17592/7/be/src/util/tagged-ptr.h@33
PS7, Line 33: /// bits. Tag bit 0 - corresponds to bit 63, bit 1 corresponds to 62 and so on.
nit: may add: To get the address stored together with extra information in canonical form, one must set/reset all bits from 57 to 63.
http://gerrit.cloudera.org:8080/#/c/17592/7/be/src/util/tagged-ptr.h@71
PS7, Line 71: if (i > 6 || i < 0)
nit. UNLIKELY()?
http://gerrit.cloudera.org:8080/#/c/17592/7/be/src/util/tagged-ptr.h@78
PS7, Line 78: if (i > 6 || i < 0) {
same as above
http://gerrit.cloudera.org:8080/#/c/17592/7/be/src/util/tagged-ptr.h@91
PS7, Line 91: //return (T*)((data_ & MASK_0_56_BITS) | ~((data_ & MASK_56_BIT) - 1));
nit. delete?
http://gerrit.cloudera.org:8080/#/c/17592/7/be/src/util/tagged-ptr.h@101
PS7, Line 101: bool operator==(const TaggedPtr<T> &a) noexcept { return data_ == a.data_; }
:
: bool operator!=(const TaggedPtr<T> &a) noexcept { return data_ != a.data_; }
nit. I found the implementation of these two operators counter intuitive as semantically, a comparison of two pointers means to compare the pointers, excluding any extra bits encoded within the pointers.
Maybe add two new methods
1. bool CompareTaggedPtrEqual()
2. bool compareTaggedPtrNotEqual()
http://gerrit.cloudera.org:8080/#/c/17592/7/be/src/util/tagged-ptr.h@115
PS7, Line 115: / data_ = (dat
nit. remove?
http://gerrit.cloudera.org:8080/#/c/17592/7/fe/src/main/java/org/apache/impala/planner/PlannerContext.java
File fe/src/main/java/org/apache/impala/planner/PlannerContext.java:
http://gerrit.cloudera.org:8080/#/c/17592/7/fe/src/main/java/org/apache/impala/planner/PlannerContext.java@47
PS7, Line 47: public final static double SIZE_OF_HASH = 4;
nit. I wonder if this value can be folded back into SIZE_OF_BUCKET and SIZE_OF_DUPLICATENODE. That is to define directly
SIZE_OF_BUCKET=12
SIZE_OF_DUPLICATENODE=20
as the separation of hash from bucket is an implementation optimization.
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 7
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Qifan Chen <qc...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Wed, 21 Jul 2021 15:55:17 +0000
Gerrit-HasComments: Yes
[Impala-ASF-CR] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/17592 )
Change subject: IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
Patch Set 9:
Build Successful
https://jenkins.impala.io/job/gerrit-code-review-checks/9240/ : Initial code review checks passed. Use gerrit-verify-dryrun-external or gerrit-verify-dryrun to run full precommit tests.
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 9
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Qifan Chen <qc...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Wed, 04 Aug 2021 22:18:13 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Qifan Chen (Code Review)" <ge...@cloudera.org>.
Qifan Chen has posted comments on this change. ( http://gerrit.cloudera.org:8080/17592 )
Change subject: IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
Patch Set 9:
(33 comments)
Looks pretty good. I have some additional comments, mostly nits.
http://gerrit.cloudera.org:8080/#/c/17592/9//COMMIT_MSG
Commit Message:
http://gerrit.cloudera.org:8080/#/c/17592/9//COMMIT_MSG@9
PS9, Line 9: HashTable implementation comprises of contiguous
nit. in Impala
http://gerrit.cloudera.org:8080/#/c/17592/9//COMMIT_MSG@10
PS9, Line 10: would either
: have Data or will
nit. "contains either data or a pointer to linked"
http://gerrit.cloudera.org:8080/#/c/17592/9//COMMIT_MSG@15
PS9, Line 15: struct DuplicateNode {
: bool matched;
: DuplicateNode* next;
: HtData htdata;
: };
:
: struct Bucket {
: bool filled;
: bool matched;
: bool hasDuplicates;
: uint32_t hash;
: union {
: HtData htdata;
: DuplicateNode* duplicates;
: } bucketData;
: };
nit. The commit message is nice with many details. I wonder if it can be simplified a little bit by omitting some details. For example we could just provide the definition on Bucket here.
http://gerrit.cloudera.org:8080/#/c/17592/9//COMMIT_MSG@38
PS9, Line 38: intel
nit. Intel
http://gerrit.cloudera.org:8080/#/c/17592/9//COMMIT_MSG@58
PS9, Line 58: As a part of patch, TaggedPointer is introduced which is template
nit: a template class
http://gerrit.cloudera.org:8080/#/c/17592/9//COMMIT_MSG@59
PS9, Line 59: tag together in 64 bit integer
nit. "tags together in 64-bit integers".
http://gerrit.cloudera.org:8080/#/c/17592/9//COMMIT_MSG@71
PS9, Line 71: Building Hash Table and Probing the table
nit. use lower cases.
http://gerrit.cloudera.org:8080/#/c/17592/9//COMMIT_MSG@81
PS9, Line 81: 17% and 21%
Nice.
http://gerrit.cloudera.org:8080/#/c/17592/9//COMMIT_MSG@83
PS9, Line 83: 0-1.5%
Nice.
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/benchmarks/hash-table-benchmark.cc
File be/src/benchmarks/hash-table-benchmark.cc:
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/benchmarks/hash-table-benchmark.cc@47
PS9, Line 47: Hash Table Build: Function iters/ms 10%ile 50%ile 90%ile 10%ile 50%ile 90%ile
nit. Formatting. The space under "HashT able Build" is wasted. Suggest to break the entire line into two:
Hash Table Build:
Function iters/ms 10%ile 50%ile 90%ile 10%ile 50%ile 90%ile
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/benchmarks/hash-table-benchmark.cc@50
PS9, Line 50: 65536_100
nit. Add a comment on the meaning of these two numbers.
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/benchmarks/hash-table-benchmark.cc@254
PS9, Line 254: void
I think we should return bool here to indicate whether there are any troubles with hashing or insertion.
DCHECK() is an no-op in non-debug build.
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/benchmarks/hash-table-benchmark.cc@261
PS9, Line 261: Status status;
nit. This can be defined outside the for loop.
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/benchmarks/hash-table-benchmark.cc@267
PS9, Line 267: amespace build
nit. can we use name space htbenchmark here?
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/benchmarks/hash-table-benchmark.cc@279
PS9, Line 279: Build
nit. We should check the return status from Build().
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/exec/hash-table.h
File be/src/exec/hash-table.h:
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/exec/hash-table.h@694
PS9, Line 694: Tag bit 1
nit. this does not match the code at line 704.
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/exec/hash-table.h@713
PS9, Line 713: TAGGED
I wonder if why this argument is needed. Is it true that all hash tables have been converted to tagged version?
It brings complexity.
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/util/benchmark.cc
File be/src/util/benchmark.cc:
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/util/benchmark.cc@143
PS9, Line 143: if (fn != NULL) { fn(benchmarks_[0].args); }
nit. May run Clang-format. {} is not needed if the entire IF statement is in one line.
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/util/benchmark.cc@174
PS9, Line 174: if (fn != NULL) { fn(benchmarks_[i].args); }
nit. same as above.
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/util/tagged-ptr-test.cc
File be/src/util/tagged-ptr-test.cc:
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/util/tagged-ptr-test.cc@27
PS9, Line 27: std::string
nit const std::string&
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/util/tagged-ptr-test.cc@42
PS9, Line 42: std::string
nit. const std::string&
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/util/tagged-ptr-test.cc@59
PS9, Line 59: false
nit. I wonder if we use OWN=true version in BE. If so, you may test it well.
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/util/tagged-ptr-test.cc@92
PS9, Line 92: ptr.SetTagBit0();
: ptr.SetTagBit1();
nit. May include setting tag bit 3, 4,5 and 6.
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/util/tagged-ptr-test.cc@97
PS9, Line 97: 96
nit. Please use 0x60 here to indicate which bits are set better.
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/util/tagged-ptr-test.cc@102
PS9, Line 102: 32
nit same as above.
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/util/tagged-ptr-test.cc@144
PS9, Line 144:
nit remove the space.
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/util/tagged-ptr.h
File be/src/util/tagged-ptr.h:
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/util/tagged-ptr.h@54
PS9, Line 54: UnSet
nit. Unset
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/util/tagged-ptr.h@46
PS9, Line 46: // Boiler Plate Code for Setting/Unsetting/Checking Tags
: #define SET_UNSET_IS_TAG(bit) \
: static const uintptr_t DATA_MASK_##bit = (1ULL << (63 - bit)); \
: static const uintptr_t DATA_MASK_INVERSE_##bit = ~(1ULL << (63 - bit)); \
: ALWAYS_INLINE void SetTagBit##bit() { \
: data_ = (data_ | DATA_MASK_##bit); \
: } \
: \
: ALWAYS_INLINE void UnSetTagBit##bit() { \
: data_ = (data_ & DATA_MASK_INVERSE_##bit); \
: } \
: \
: ALWAYS_INLINE bool IsTagBitSet##bit() const { \
: return (data_ & DATA_MASK_##bit); \
: }
nit. May run ClangFormat on the entire macro to align '\' nicely.
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/util/tagged-ptr.h@99
PS9, Line 99: // Member functions for Setting/Unsetting/Checking tags for 0-6
nit. tag bits 0-6.
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/util/tagged-ptr.h@100
PS9, Line 100: // E.g. for tag bit 0,
: // ALWAYS_INLINE void SetTagBit0() {
: // data_ = (data_ | DATA_MASK_0);
: // }
nit. This can be moved to where the macro is defined (e.g. line 46).
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/util/tagged-ptr.h@104
PS9, Line 104: // ALWAYS_INLINE void UnSetTagBit##bit() {
: // data_ = (data_ & DATA_MASK_INVERSE_##bit);
: // }
: // ALWAYS_INLINE bool IsTagBitSet##bit() const {
: // return (data_ & DATA_MASK_INVERSE_##bit);
: // }
nit. remove?
http://gerrit.cloudera.org:8080/#/c/17592/9/be/src/util/tagged-ptr.h@137
PS9, Line 137: ~MASK_0_56_BITS
This can be made a constant to avoid compute ~ every time SetPtr() is called. Not sure if C++ constant folds it.
http://gerrit.cloudera.org:8080/#/c/17592/7/be/src/util/tagged-ptr.h
File be/src/util/tagged-ptr.h:
http://gerrit.cloudera.org:8080/#/c/17592/7/be/src/util/tagged-ptr.h@101
PS7, Line 101: // ALWAYS_INLINE void SetTagBit0() {
: // data_ = (data_ | DATA_MASK_0);
: // }
> These are comparison of the tagged pointers which includes tag. For compari
Done
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 9
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Qifan Chen <qc...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Thu, 05 Aug 2021 15:33:41 +0000
Gerrit-HasComments: Yes
[Impala-ASF-CR] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/17592 )
Change subject: IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
Patch Set 14:
Build Successful
https://jenkins.impala.io/job/gerrit-code-review-checks/9365/ : Initial code review checks passed. Use gerrit-verify-dryrun-external or gerrit-verify-dryrun to run full precommit tests.
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 14
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Qifan Chen <qc...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Wed, 25 Aug 2021 10:13:46 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Amogh Margoor (Code Review)" <ge...@cloudera.org>.
Amogh Margoor has posted comments on this change. ( http://gerrit.cloudera.org:8080/17592 )
Change subject: IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
Patch Set 14:
(1 comment)
http://gerrit.cloudera.org:8080/#/c/17592/13/be/src/util/tagged-ptr.h
File be/src/util/tagged-ptr.h:
http://gerrit.cloudera.org:8080/#/c/17592/13/be/src/util/tagged-ptr.h@87
PS13, Line 87: static_assert(bit >= 0 && b
> This could be a compile-time check with static_assert.
yeah that makes sense. I have changed it.
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 14
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Qifan Chen <qc...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Wed, 25 Aug 2021 09:50:21 +0000
Gerrit-HasComments: Yes
[Impala-ASF-CR] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Joe McDonnell (Code Review)" <ge...@cloudera.org>.
Joe McDonnell has posted comments on this change. ( http://gerrit.cloudera.org:8080/17592 )
Change subject: IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
Patch Set 5:
(1 comment)
I grabbed this change and was doing some local testing, and I ran into a scenario that crashes Impala.
Here's what I did:
1. I loaded a larger TPC-H dataset in parquet (takes quite a while and will use up some disk space):
bin/load-data.py -w tpch -s 42 --table_formats=text/none/none,parquet/none/none
2. Ran the following multiple times (it is intermittent):
use tpch42_parquet;
SELECT l_orderkey,
count(*) AS cnt
FROM lineitem
GROUP BY l_orderkey
HAVING count(*) > 9999999999999;
That intermittently crashes with this stack:
C [impalad+0x27e8546] long impala::HashTable::Probe<true, false>(impala::HashTable::Bucket*, long, impala::HashTableCtx*, unsigned int, bool*, impala::HashTable::BucketData*)+0x28c
C [impalad+0x27e2141] impala::HashTable::ResizeBuckets(long, impala::HashTableCtx*, bool*)+0x7d1
C [impalad+0x27e194d] impala::HashTable::CheckAndResize(unsigned long, impala::HashTableCtx*, bool*)+0xcb
C [impalad+0x27c8a48] impala::GroupingAggregator::CheckAndResizeHashPartitions(bool, int, impala::HashTableCtx*)+0x176
This may reproduce on smaller datasets.
http://gerrit.cloudera.org:8080/#/c/17592/5/be/src/benchmarks/hash-table-benchmark.cc
File be/src/benchmarks/hash-table-benchmark.cc:
http://gerrit.cloudera.org:8080/#/c/17592/5/be/src/benchmarks/hash-table-benchmark.cc@332
PS5, Line 332: vector<int> num_tuples { 65536, 262144 };
One area of performance testing is looking at what happens when the hash table no longer fits in CPU cache and requires more accesses to main memory. This will interact heavily with the memory layout and prefetching.
That kind of testing requires a lot of care if we do it outside the usual Impala code, because it will be much more sensitive to the specific algorithms we use. In particular, we process tuples in batches and do a round of prefetching for the whole batch before the insert/probe. This hides the latency of fetching things from memory.
I'm commenting here because if this benchmark wants to handle that case, these values need to go much higher. 1 million, 5 million, 10 million, 100 million. Other aspects would also need to change.
Another approach for testing the hashtable is to write custom hashtable intensive queries. The general shape would be like this:
1. Run a single Impalad
2. Create tables with a single column with different data distributions (i.e. different number of distinct values, duplication). These are used for building hash tables.
3. Create tables with different data distributions for probing the hash table.
4. Testing hashtable build involves a groupby like this targeted perf query: https://github.com/apache/impala/blob/master/testdata/workloads/targeted-perf/queries/primitive_groupby_bigint_highndv.test
5. Testing hashtable probe involves writing SQLs with JOINs that stress the hashtable. The probe tables can be as big as we want, so that the probe is the dominant part of query execution. STRAIGHT_JOIN can override any join ordering optimizations to force a particular join order. We may have to disable runtime filters.
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 5
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Thu, 08 Jul 2021 02:40:10 +0000
Gerrit-HasComments: Yes
[Impala-ASF-CR] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Amogh Margoor (Code Review)" <ge...@cloudera.org>.
Amogh Margoor has uploaded a new patch set (#8). ( http://gerrit.cloudera.org:8080/17592 )
Change subject: IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
HashTable implementation comprises of contiguous
array of Buckets and each Bucket would either
have Data or will point to linked list of
duplicate entries named DuplicateNode. These
are the structures of Bucket and DuplicateNode:
struct DuplicateNode {
bool matched;
DuplicateNode* next;
HtData htdata;
};
struct Bucket {
bool filled;
bool matched;
bool hasDuplicates;
uint32_t hash;
union {
HtData htdata;
DuplicateNode* duplicates;
} bucketData;
};
Size of Bucket is currently 16 bytes and Size of Duplicate Node is
24 bytes. If we can remove the booleans from both struct size of
Bucket would reduce to 12 bytes and DuplicateNode will be 16 bytes.
One of the ways we can remove booleans is to fold it into pointers
already part of struct. Pointers store addresses and on
architectures like x86 and ARM the linear address is only 48 bits
long. With level 5 paging intel is planning to expand it to 57-bit
long which means we can use most significant 7 bits i.e., 58 to 64
bits to store these booleans. This patch reduces the size of Bucket
and DuplicateNode by implementing this folding. However, there is
another requirement regarding Size of Bucket to be power of 2 and
also for the number of buckets in Hash table to be power of 2.
These requirements are for the following reasons:
1. Memory Allocator allocates memory in power of 2 to avoid
internal fragmentation. Hence, num of buckets * sizeof(Buckets)
should be power of 2.
2. Number of buckets being power of 2 enables faster modulo
operation i.e., instead of slow modulo: (hash % N), faster
(hash & (N-1)) can be used.
Due to this, 4 bytes 'hash' field from Bucket is removed and
stored sperately in new array hash_array_ in HashTable.
This ensures sizeof(Bucket) is 8 which is power of 2.
New Classes:
------------
As a part of patch, TaggedPointer is introduced which is template
class to store pointers and tag together in 64 bit integer. This
structure contains the ownership of the pointer and will take care
of allocation and deallocation of the object being pointed to.
However derived classes can opt out of the ownership of the object
and let the client manage it. It's derived classes for Bucket and
DuplicateNode do the same. These classes are TaggedBucketData and
TaggedDuplicateNode.
Benchmark:
----------
As a part of this patch a new Micro Benchmark for HashTable has
been introduced, which will help in measuring these:
1. Runtime for Building Hash Table and Probing the table.
2. Memory consumed after building the Table.
This would help measuring the impact of changes to the HashTable's
data structure and algorithm.
Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
---
M be/src/benchmarks/CMakeLists.txt
A be/src/benchmarks/hash-table-benchmark.cc
M be/src/exec/grouping-aggregator-ir.cc
M be/src/exec/hash-table-test.cc
M be/src/exec/hash-table.cc
M be/src/exec/hash-table.h
M be/src/exec/hash-table.inline.h
M be/src/util/CMakeLists.txt
M be/src/util/benchmark.cc
M be/src/util/benchmark.h
A be/src/util/tagged-ptr-test.cc
A be/src/util/tagged-ptr.h
M fe/src/main/java/org/apache/impala/planner/AggregationNode.java
M fe/src/main/java/org/apache/impala/planner/HashJoinNode.java
M fe/src/main/java/org/apache/impala/planner/PlannerContext.java
15 files changed, 1,108 insertions(+), 171 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/Impala-ASF refs/changes/92/17592/8
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 8
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Qifan Chen <qc...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
[Impala-ASF-CR] IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
Posted by "Amogh Margoor (Code Review)" <ge...@cloudera.org>.
Amogh Margoor has uploaded a new patch set (#5). ( http://gerrit.cloudera.org:8080/17592 )
Change subject: IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
......................................................................
IMPALA-7635: Reducing HashTable size by packing it's buckets efficiently.
HashTable implementation comprises of contiguos
array of Buckets and each Bucket would either
have Data or will point to linked list of
duplicate entries named DuplicateNode. These
are the structures of Bucket and DuplicateNode:
struct DuplicateNode {
bool matched;
DuplicateNode* next;
HtData htdata;
};
struct Bucket {
bool filled;
bool matched;
bool hasDuplicates;
uint32_t hash;
union {
HtData htdata;
DuplicateNode* duplicates;
} bucketData;
};
Size of Bucket is currently 16 bytes and Size of Duplicate Node is
24 bytes. If we can remove the booleans from both struct size of
Bucket would reduce to 12 bytes and DuplicateNode will be 16 bytes.
One of the ways we can remove booleans is to fold it into pointers
already part of struct. Pointers store addresses and on
architectures like x86 and ARM the linear address is only 48 bits
long. With level 5 paging intel is planning to expand it to 57-bit
long which means we can use most significant 7 bits i.e., 58 to 64
bits to store these booleans. This patch reduces the size of Bucket
and DuplicateNode by implementing this folding. However, there is
another requirement regarding Size of Bucket to be power of 2 and
also for the number of buckets in Hash table to be power of 2.
These requirements are for the following reasons:
1. Memory Allocator allocates memory in power of 2 to avoid
internal fragmentation. Hence, num of buckets * sizeof(Buckets)
should be power of 2.
2. Number of buckets being power of 2 enables faster modulo
operation i.e., instead of slow modulo: (hash % N), faster
(hash & (N-1)) can be used.
Due to this, 4 bytes 'hash' field from Bucket is removed and
stored sperately in new array hash_array_ in HashTable.
This ensures sizeof(Bucket) is 8 which is power of 2.
New Classes:
------------
As a part of patch, TaggedPointer is introduced which is template
class to store pointers and tag together in 64 bit integer. This
structure contains the ownership of the pointer and will take care
of allocation and deallocation the the object being pointed to.
However derived classes can opt out of the ownership of the object
and let the client manage it. It's derived classes for Bucket and
DuplicateNode do the same. These classes are TaggedBucketData and
TaggedDuplicateNode.
Benchmark:
----------
As a part ofthis patch a new Micro Benchmark for HashTable has
been introduced, which will help in measuring these:
1. Runtime for Building Hash Table and Probing the table.
2. Memory consumed after building the Table.
This would help measuring the impact of changes to the HashTable's
data structure and algorithm.
Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
---
M be/src/benchmarks/CMakeLists.txt
A be/src/benchmarks/hash-table-benchmark.cc
M be/src/exec/hash-table-test.cc
M be/src/exec/hash-table.cc
M be/src/exec/hash-table.h
M be/src/exec/hash-table.inline.h
M be/src/util/CMakeLists.txt
M be/src/util/benchmark.cc
M be/src/util/benchmark.h
A be/src/util/tagged-ptr-test.cc
A be/src/util/tagged-ptr.h
M fe/src/main/java/org/apache/impala/planner/AggregationNode.java
M fe/src/main/java/org/apache/impala/planner/HashJoinNode.java
M fe/src/main/java/org/apache/impala/planner/PlannerContext.java
14 files changed, 980 insertions(+), 136 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/Impala-ASF refs/changes/92/17592/5
--
To view, visit http://gerrit.cloudera.org:8080/17592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: I72912ae9353b0d567a976ca712d2d193e035df9b
Gerrit-Change-Number: 17592
Gerrit-PatchSet: 5
Gerrit-Owner: Amogh Margoor <am...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>