Yingchun Lai has submitted this change and it was merged. ( http://gerrit.cloudera.org:8080/19794 )
Change subject: [cpp-client] KUDU-3455 Reduce space complexity and speed up hash partition pruning for in-list predicate ...................................................................... [cpp-client] KUDU-3455 Reduce space complexity and speed up hash partition pruning for in-list predicate This patch comes from a committed patch, its committed id is 'b69dbeb'. As that patch said, logic of pruning hash partitions for in-list predicate in Kudu cpp client has also a high space complexity and slow. Old algorithm must keep all intermedium objects because they are incomplete until they are completed and can be computed hash. This patch fixes the problems and provides a recursive algorithm the same as the one used by java client. Compared with java client, the cpp client is less likely to cause the OOM condition because it does not keep too many intermediate results. This optimization has good benefits too. The benefits are related to the in-list length and the number of primary keys, the performance would be better if in-list length is longer. For example, PartitionPrunerTest::TestMultiColumnInListHashPruningManyValues, using 10 key columns and kMaxInListLength=50, old algorithm memory cost may reach 600MB, while new algorithm's memory cost can be ignored (it only need one objects and a few stacks for contexts). At the same time, new algorithm has a good speedup, some effect as below: combination_count: 5554006920000, old cost: 428238us, new cost: 713us, speedup: 600.6x combination_count: 89083783664568, old cost: 2764924us, new cost: 1145us, speedup: 2414.7x combination_count: 27194091724800, old cost: 1610475us, new cost: 1151us, speedup: 1399.2x combination_count: 7116622216704, old cost: 34544289us, new cost: 375us, speedup: 92118.1x combination_count: 37570734489600, old cost: 1733205us, new cost: 901us, speedup: 1923.6x Change-Id: Ie4bea5c10b4ac2c62b85625fe9d2a33ceb4fb2e9 Reviewed-on: http://gerrit.cloudera.org:8080/19794 Reviewed-by: Yingchun Lai <[email protected]> Tested-by: Yingchun Lai <[email protected]> Reviewed-by: Yuqi Du <[email protected]> --- M src/kudu/common/partition_pruner-test.cc M src/kudu/common/partition_pruner.cc M src/kudu/common/partition_pruner.h 3 files changed, 240 insertions(+), 19 deletions(-) Approvals: Yingchun Lai: Looks good to me, approved; Verified Yuqi Du: Looks good to me, but someone else must approve -- To view, visit http://gerrit.cloudera.org:8080/19794 To unsubscribe, visit http://gerrit.cloudera.org:8080/settings Gerrit-Project: kudu Gerrit-Branch: master Gerrit-MessageType: merged Gerrit-Change-Id: Ie4bea5c10b4ac2c62b85625fe9d2a33ceb4fb2e9 Gerrit-Change-Number: 19794 Gerrit-PatchSet: 15 Gerrit-Owner: Yuqi Du <[email protected]> Gerrit-Reviewer: Abhishek Chennaka <[email protected]> Gerrit-Reviewer: Alexey Serbin <[email protected]> Gerrit-Reviewer: Ashwani Raina <[email protected]> Gerrit-Reviewer: KeDeng <[email protected]> Gerrit-Reviewer: Kudu Jenkins (120) Gerrit-Reviewer: Tidy Bot (241) Gerrit-Reviewer: Wang Xixu <[email protected]> Gerrit-Reviewer: Yifan Zhang <[email protected]> Gerrit-Reviewer: Yingchun Lai <[email protected]> Gerrit-Reviewer: Yuqi Du <[email protected]>
