You are viewing a plain text version of this content. The canonical link for it is here.
Posted to reviews@impala.apache.org by "Zoltan Borok-Nagy (Code Review)" <ge...@cloudera.org> on 2024/06/26 13:42:21 UTC
[Impala-ASF-CR] IMPALA-13088: Use RoaringBitmap instead of sorted vector of int64s
Zoltan Borok-Nagy has uploaded this change for review. ( http://gerrit.cloudera.org:8080/21557
Change subject: IMPALA-13088: Use RoaringBitmap instead of sorted vector of int64s
......................................................................
IMPALA-13088: Use RoaringBitmap instead of sorted vector of int64s
This patch substitutes the sorted 64-bit integer vectors that we
use in IcebergDeleteNode to 64-bit roaring bitmaps. We use the
CRoaring library, but this patch also adds a thin C++ wrapper around
the C functions to get the best performance.
Performance
I used an extended version of the "One Trillion Row" challenge. This
means after inserting 1 Trillion records to a table I also deleted /
updated lots of records. So at the end I had 1 Trillion data records
and ~68.5 Billion delete records in the table.
For the measurements I used clusters with 10 and 40 executors, and
executed the following query:
SELECT station, min(measure), max(measure), avg(measure)
FROM measurements_extra_1trc_partitioned
GROUP BY 1
ORDER BY 1;
JOIN BUILD times:
+----------------+--------------+--------------+
| Implementation | 10 executors | 40 executors |
+----------------+--------------+--------------+
| Sorted vectors | CRASH | 2m3s |
| Roaring bitmap | 6m35s | 1m51s |
+----------------+--------------+--------------+
10 executors cluster with sorted vectors failed to run the query because
executors crashed due to out-of-memory.
Memory usage (VmRSS) for 10 executors:
+----------------+------------------------+
| Implementation | 10 executors |
+----------------+------------------------+
| Sorted vectors | 54.4 GB (before CRASH) |
| Roaring bitmap | 7.4 GB |
+----------------+------------------------+
Testing:
* TODO: unit tests for RoaringBitmap64
Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
---
M be/src/exec/iceberg-delete-builder.cc
M be/src/exec/iceberg-delete-builder.h
M be/src/exec/iceberg-delete-node.cc
M be/src/exec/iceberg-delete-node.h
A be/src/thirdparty/roaring/LICENSE
A be/src/thirdparty/roaring/README.md
A be/src/thirdparty/roaring/roaring.c
A be/src/thirdparty/roaring/roaring.h
M be/src/util/CMakeLists.txt
A be/src/util/roaring-bitmap-test.cc
A be/src/util/roaring-bitmap.h
11 files changed, 29,336 insertions(+), 274 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/Impala-ASF refs/changes/57/21557/1
--
To view, visit http://gerrit.cloudera.org:8080/21557
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: newchange
Gerrit-Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
Gerrit-Change-Number: 21557
Gerrit-PatchSet: 1
Gerrit-Owner: Zoltan Borok-Nagy <bo...@cloudera.com>
[Impala-ASF-CR] IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
Posted by "Daniel Becker (Code Review)" <ge...@cloudera.org>.
Daniel Becker has posted comments on this change. ( http://gerrit.cloudera.org:8080/21557 )
Change subject: IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
......................................................................
Patch Set 7: Code-Review+1
--
To view, visit http://gerrit.cloudera.org:8080/21557
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
Gerrit-Change-Number: 21557
Gerrit-PatchSet: 7
Gerrit-Owner: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Reviewer: Daniel Becker <da...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Kurt Deschler <kd...@cloudera.com>
Gerrit-Reviewer: Michael Smith <mi...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Wed, 03 Jul 2024 08:47:23 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
Posted by "Zoltan Borok-Nagy (Code Review)" <ge...@cloudera.org>.
Hello Daniel Becker, Kurt Deschler, Michael Smith, Csaba Ringhofer, Impala Public Jenkins,
I'd like you to reexamine a change. Please visit
http://gerrit.cloudera.org:8080/21557
to look at the new patch set (#9).
Change subject: IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
......................................................................
IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
This patch substitutes the sorted 64-bit integer vectors that we
use in IcebergDeleteNode to 64-bit roaring bitmaps. We use the
CRoaring library (version 4.0.0). CRoaring also offers C++ classes,
but this patch adds its own thin C++ wrapper class around the C
functions to get the best performance.
Toolchain Clang 5.0.1 was not able to compile CRoaring due to a
bug which is tracked by IMPALA-13190, this patch also fixes it
with a new toolchain.
Performance
I used an extended version of the "One Trillion Row" challenge. This
means after inserting 1 Trillion records to a table I also deleted /
updated lots of records (see statements at the end). So at the end
I had 1 Trillion data records and ~68.5 Billion delete records in
the table.
For the measurements I used clusters with 10 and 40 executors, and
executed the following query:
SELECT station, min(measure), max(measure), avg(measure)
FROM measurements_extra_1trc_partitioned
GROUP BY 1
ORDER BY 1;
JOIN BUILD times:
+----------------+--------------+--------------+
| Implementation | 10 executors | 40 executors |
+----------------+--------------+--------------+
| Sorted vectors | CRASH | 4m15s |
| Roaring bitmap | 6m35s | 1m51s |
+----------------+--------------+--------------+
10 executors cluster with sorted vectors failed to run the query because
executors crashed due to out-of-memory.
Memory usage (VmRSS) for 10 executors:
+----------------+------------------------+
| Implementation | 10 executors |
+----------------+------------------------+
| Sorted vectors | 54.4 GB (before CRASH) |
| Roaring bitmap | 7.4 GB |
+----------------+------------------------+
The resource estimations were wrong when MT_DOP was greater than 1. This
has been also fixed.
Testing:
* added tests for RoaringBitmap64
* added tests for resource estimations
Statements I used to delete / update the records for the One Trillion
Row challenge:
create table measurements_extra_1trc_partitioned(
station string, ts timestamp, sensor_type int, measure decimal(5,2))
partitioned by spec (bucket(11, station), day(ts), truncate(10, sensor_type))
stored as iceberg;
The original challenge didn't have any row-level modifications, columns 'ts'
and 'sensor_type' are new:
'ts': timestamps that span a year
'sensor_type': integer between 0 and 100
Both 'ts' and 'sensor_type' has uniform distribution.
Ingested data with the help of the original table One Trillion Row
challenge, then issued the following DML statements:
-- DELETE ~10 Billion
delete from measurements_extra_1trc_partitioned
where sensor_type = 13;
-- UPDATE ~220 Million
update measurements_extra_1trc_partitioned set measure = cast(measure - 2 as decimal(5,2))
where station in ('Budapest', 'Paris', 'Zurich', 'Kuala Lumpur')
and sensor_type in (7, 17, 77);
-- DELETE ~7.1 Billion
delete from measurements_extra_1trc_partitioned
where ts between '2024-01-15 11:30:00' and '2024-09-10 11:30:00'
and sensor_type between 45 and 51
and station regexp '[ATZ].*';
-- UPDATE ~334 Million
update measurements_extra_1trc_partitioned set measure = cast(measure + 5 as decimal(5,2))
where station in ('Accra', 'Addis Ababa', 'Entebbe', 'Helsinki', 'Hong Kong', 'Nairobi', 'Ottawa', 'Tauranga', 'Yaounde', 'Zagreb', 'Zurich')
and ts > '2024-11-05 22:30:00'
and sensor_type > 90;
-- DELETE 50.6 Billion
delete from measurements_extra_1trc_partitioned
where
sensor_type between 65 and 77
and ts > '2024-08-11 12:00:00'
;
-- UPDATE ~200 Million
update measurements_extra_1trc_partitioned set measure = cast(measure + 3.5 as decimal(5,2))
where
sensor_type in (56, 66, 76, 86, 96)
and ts < '2024-03-17 01:00:00'
and (station like 'Z%' or station like 'Y%');
Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
---
M LICENSE.txt
M be/src/exec/iceberg-delete-builder.cc
M be/src/exec/iceberg-delete-builder.h
M be/src/exec/iceberg-delete-node.cc
M be/src/exec/iceberg-delete-node.h
A be/src/thirdparty/roaring/LICENSE
A be/src/thirdparty/roaring/README.md
A be/src/thirdparty/roaring/roaring.c
A be/src/thirdparty/roaring/roaring.h
M be/src/util/CMakeLists.txt
A be/src/util/roaring-bitmap-test.cc
A be/src/util/roaring-bitmap.h
M bin/impala-config.sh
M bin/rat_exclude_files.txt
M fe/src/main/java/org/apache/impala/planner/IcebergDeleteNode.java
M fe/src/test/java/org/apache/impala/planner/PlannerTest.java
A testdata/workloads/functional-planner/queries/PlannerTest/iceberg-v2-tables-resources.test
A testdata/workloads/functional-query/queries/QueryTest/iceberg-query-v2.test
M testdata/workloads/functional-query/queries/QueryTest/iceberg-query.test
M tests/query_test/test_scanners.py
20 files changed, 33,156 insertions(+), 252 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/Impala-ASF refs/changes/57/21557/9
--
To view, visit http://gerrit.cloudera.org:8080/21557
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
Gerrit-Change-Number: 21557
Gerrit-PatchSet: 9
Gerrit-Owner: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Reviewer: Csaba Ringhofer <cs...@cloudera.com>
Gerrit-Reviewer: Daniel Becker <da...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Kurt Deschler <kd...@cloudera.com>
Gerrit-Reviewer: Michael Smith <mi...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
[Impala-ASF-CR] IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/21557 )
Change subject: IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
......................................................................
Patch Set 11: Verified+1
--
To view, visit http://gerrit.cloudera.org:8080/21557
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
Gerrit-Change-Number: 21557
Gerrit-PatchSet: 11
Gerrit-Owner: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Reviewer: Csaba Ringhofer <cs...@cloudera.com>
Gerrit-Reviewer: Daniel Becker <da...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Kurt Deschler <kd...@cloudera.com>
Gerrit-Reviewer: Michael Smith <mi...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Tue, 16 Jul 2024 17:35:12 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/21557 )
Change subject: IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
......................................................................
Patch Set 10: Verified+1
--
To view, visit http://gerrit.cloudera.org:8080/21557
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
Gerrit-Change-Number: 21557
Gerrit-PatchSet: 10
Gerrit-Owner: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Reviewer: Csaba Ringhofer <cs...@cloudera.com>
Gerrit-Reviewer: Daniel Becker <da...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Kurt Deschler <kd...@cloudera.com>
Gerrit-Reviewer: Michael Smith <mi...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Thu, 11 Jul 2024 22:16:29 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/21557 )
Change subject: IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
......................................................................
Patch Set 6:
Build Failed
https://jenkins.impala.io/job/gerrit-code-review-checks/16460/ : Initial code review checks failed. See linked job for details on the failure.
--
To view, visit http://gerrit.cloudera.org:8080/21557
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
Gerrit-Change-Number: 21557
Gerrit-PatchSet: 6
Gerrit-Owner: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Reviewer: Daniel Becker <da...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Kurt Deschler <kd...@cloudera.com>
Gerrit-Reviewer: Michael Smith <mi...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Tue, 02 Jul 2024 17:12:55 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] IMPALA-13088: Use RoaringBitmap instead of sorted vector of int64s
Posted by "Zoltan Borok-Nagy (Code Review)" <ge...@cloudera.org>.
Zoltan Borok-Nagy has posted comments on this change. ( http://gerrit.cloudera.org:8080/21557 )
Change subject: IMPALA-13088: Use RoaringBitmap instead of sorted vector of int64s
......................................................................
Patch Set 4:
(1 comment)
http://gerrit.cloudera.org:8080/#/c/21557/2/bin/rat_exclude_files.txt
File bin/rat_exclude_files.txt:
http://gerrit.cloudera.org:8080/#/c/21557/2/bin/rat_exclude_files.txt@245
PS2, Line 245: be/src/thirdparty/roaring/LICENSE
> Shouldn't we add the licence to /LICENSE.txt, as the comment above writes?
Good catch, added a new section for roaring.
--
To view, visit http://gerrit.cloudera.org:8080/21557
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
Gerrit-Change-Number: 21557
Gerrit-PatchSet: 4
Gerrit-Owner: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Reviewer: Daniel Becker <da...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Kurt Deschler <kd...@cloudera.com>
Gerrit-Reviewer: Michael Smith <mi...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Mon, 01 Jul 2024 13:23:26 +0000
Gerrit-HasComments: Yes
[Impala-ASF-CR] IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/21557 )
Change subject: IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
......................................................................
Patch Set 5:
Build Failed
https://jenkins.impala.io/job/gerrit-code-review-checks/16459/ : Initial code review checks failed. See linked job for details on the failure.
--
To view, visit http://gerrit.cloudera.org:8080/21557
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
Gerrit-Change-Number: 21557
Gerrit-PatchSet: 5
Gerrit-Owner: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Reviewer: Daniel Becker <da...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Kurt Deschler <kd...@cloudera.com>
Gerrit-Reviewer: Michael Smith <mi...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Tue, 02 Jul 2024 17:09:51 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/21557 )
Change subject: IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
......................................................................
Patch Set 7:
Build started: https://jenkins.impala.io/job/gerrit-verify-dryrun/10773/ DRY_RUN=true
--
To view, visit http://gerrit.cloudera.org:8080/21557
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
Gerrit-Change-Number: 21557
Gerrit-PatchSet: 7
Gerrit-Owner: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Reviewer: Daniel Becker <da...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Kurt Deschler <kd...@cloudera.com>
Gerrit-Reviewer: Michael Smith <mi...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Tue, 02 Jul 2024 19:51:22 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
Posted by "Zoltan Borok-Nagy (Code Review)" <ge...@cloudera.org>.
Zoltan Borok-Nagy has posted comments on this change. ( http://gerrit.cloudera.org:8080/21557 )
Change subject: IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
......................................................................
Patch Set 9:
(3 comments)
Thanks for the comments!
http://gerrit.cloudera.org:8080/#/c/21557/8//COMMIT_MSG
Commit Message:
http://gerrit.cloudera.org:8080/#/c/21557/8//COMMIT_MSG@22
PS8, Line 22: lots of records
> It could be interesting how the deleted rows were selected, as roaring bitm
Added a section at the end.
http://gerrit.cloudera.org:8080/#/c/21557/8//COMMIT_MSG@41
PS8, Line 41:
: 10 executors cluster with sorted vector
> Can you add a bit more info on this? What should be clarified is whether th
You are right, we underestimated memory in case of MT_DOP > 1. It is also fixed now, and added planner tests.
http://gerrit.cloudera.org:8080/#/c/21557/8//COMMIT_MSG@44
PS8, Line 44:
> The memory estimations are not changed - this is intentional, as we assume
No, it was an overlook. Good catch, btw! With RoaringBitmaps, 8 bytes per position is too much I think, so I adjusted the memory estimations to 1.5 bytes per position, which is probably still safe (2 bytes per position is worst-case scenario, and when it switches from ordered integers to bitmaps it uses 1 bit per position, and it can be even less with RLE).
--
To view, visit http://gerrit.cloudera.org:8080/21557
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
Gerrit-Change-Number: 21557
Gerrit-PatchSet: 9
Gerrit-Owner: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Reviewer: Csaba Ringhofer <cs...@cloudera.com>
Gerrit-Reviewer: Daniel Becker <da...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Kurt Deschler <kd...@cloudera.com>
Gerrit-Reviewer: Michael Smith <mi...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Tue, 09 Jul 2024 17:31:59 +0000
Gerrit-HasComments: Yes
[Impala-ASF-CR] IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
Posted by "Zoltan Borok-Nagy (Code Review)" <ge...@cloudera.org>.
Hello Daniel Becker, Kurt Deschler, Michael Smith, Csaba Ringhofer, Impala Public Jenkins,
I'd like you to reexamine a change. Please visit
http://gerrit.cloudera.org:8080/21557
to look at the new patch set (#10).
Change subject: IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
......................................................................
IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
This patch substitutes the sorted 64-bit integer vectors that we
use in IcebergDeleteNode to 64-bit roaring bitmaps. We use the
CRoaring library (version 4.0.0). CRoaring also offers C++ classes,
but this patch adds its own thin C++ wrapper class around the C
functions to get the best performance.
Toolchain Clang 5.0.1 was not able to compile CRoaring due to a
bug which is tracked by IMPALA-13190, this patch also fixes it
with a new toolchain.
Performance
I used an extended version of the "One Trillion Row" challenge. This
means after inserting 1 Trillion records to a table I also deleted /
updated lots of records (see statements at the end). So at the end
I had 1 Trillion data records and ~68.5 Billion delete records in
the table.
For the measurements I used clusters with 10 and 40 executors, and
executed the following query:
SELECT station, min(measure), max(measure), avg(measure)
FROM measurements_extra_1trc_partitioned
GROUP BY 1
ORDER BY 1;
JOIN BUILD times:
+----------------+--------------+--------------+
| Implementation | 10 executors | 40 executors |
+----------------+--------------+--------------+
| Sorted vectors | CRASH | 4m15s |
| Roaring bitmap | 6m35s | 1m51s |
+----------------+--------------+--------------+
10 executors cluster with sorted vectors failed to run the query because
executors crashed due to out-of-memory.
Memory usage (VmRSS) for 10 executors:
+----------------+------------------------+
| Implementation | 10 executors |
+----------------+------------------------+
| Sorted vectors | 54.4 GB (before CRASH) |
| Roaring bitmap | 7.4 GB |
+----------------+------------------------+
The resource estimations were wrong when MT_DOP was greater than 1. This
has been also fixed.
Testing:
* added tests for RoaringBitmap64
* added tests for resource estimations
Statements I used to delete / update the records for the One Trillion
Row challenge:
create table measurements_extra_1trc_partitioned(
station string, ts timestamp, sensor_type int, measure decimal(5,2))
partitioned by spec (bucket(11, station), day(ts),
truncate(10, sensor_type))
stored as iceberg;
The original challenge didn't have any row-level modifications, columns
'ts' and 'sensor_type' are new:
'ts': timestamps that span a year
'sensor_type': integer between 0 and 100
Both 'ts' and 'sensor_type' has uniform distribution.
Ingested data with the help of the original table One Trillion Row
challenge, then issued the following DML statements:
-- DELETE ~10 Billion
delete from measurements_extra_1trc_partitioned
where sensor_type = 13;
-- UPDATE ~220 Million
update measurements_extra_1trc_partitioned
set measure = cast(measure - 2 as decimal(5,2))
where station in ('Budapest', 'Paris', 'Zurich', 'Kuala Lumpur')
and sensor_type in (7, 17, 77);
-- DELETE ~7.1 Billion
delete from measurements_extra_1trc_partitioned
where ts between '2024-01-15 11:30:00' and '2024-09-10 11:30:00'
and sensor_type between 45 and 51
and station regexp '[ATZ].*';
-- UPDATE ~334 Million
update measurements_extra_1trc_partitioned
set measure = cast(measure + 5 as decimal(5,2))
where station in ('Accra', 'Addis Ababa', 'Entebbe', 'Helsinki',
'Hong Kong', 'Nairobi', 'Ottawa', 'Tauranga', 'Yaounde', 'Zagreb',
'Zurich')
and ts > '2024-11-05 22:30:00'
and sensor_type > 90;
-- DELETE 50.6 Billion
delete from measurements_extra_1trc_partitioned
where
sensor_type between 65 and 77
and ts > '2024-08-11 12:00:00'
;
-- UPDATE ~200 Million
update measurements_extra_1trc_partitioned
set measure = cast(measure + 3.5 as decimal(5,2))
where
sensor_type in (56, 66, 76, 86, 96)
and ts < '2024-03-17 01:00:00'
and (station like 'Z%' or station like 'Y%');
Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
---
M LICENSE.txt
M be/src/exec/iceberg-delete-builder.cc
M be/src/exec/iceberg-delete-builder.h
M be/src/exec/iceberg-delete-node.cc
M be/src/exec/iceberg-delete-node.h
A be/src/thirdparty/roaring/LICENSE
A be/src/thirdparty/roaring/README.md
A be/src/thirdparty/roaring/roaring.c
A be/src/thirdparty/roaring/roaring.h
M be/src/util/CMakeLists.txt
A be/src/util/roaring-bitmap-test.cc
A be/src/util/roaring-bitmap.h
M bin/impala-config.sh
M bin/rat_exclude_files.txt
M fe/src/main/java/org/apache/impala/planner/IcebergDeleteNode.java
M fe/src/test/java/org/apache/impala/planner/PlannerTest.java
A testdata/workloads/functional-planner/queries/PlannerTest/iceberg-v2-tables-resources.test
A testdata/workloads/functional-query/queries/QueryTest/iceberg-query-v2.test
M testdata/workloads/functional-query/queries/QueryTest/iceberg-query.test
M tests/query_test/test_scanners.py
20 files changed, 33,182 insertions(+), 273 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/Impala-ASF refs/changes/57/21557/10
--
To view, visit http://gerrit.cloudera.org:8080/21557
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
Gerrit-Change-Number: 21557
Gerrit-PatchSet: 10
Gerrit-Owner: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Reviewer: Csaba Ringhofer <cs...@cloudera.com>
Gerrit-Reviewer: Daniel Becker <da...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Kurt Deschler <kd...@cloudera.com>
Gerrit-Reviewer: Michael Smith <mi...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
[Impala-ASF-CR] IMPALA-13088: Use RoaringBitmap instead of sorted vector of int64s
Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/21557 )
Change subject: IMPALA-13088: Use RoaringBitmap instead of sorted vector of int64s
......................................................................
Patch Set 1:
Build Failed
https://jenkins.impala.io/job/gerrit-code-review-checks/16435/ : Initial code review checks failed. See linked job for details on the failure.
--
To view, visit http://gerrit.cloudera.org:8080/21557
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
Gerrit-Change-Number: 21557
Gerrit-PatchSet: 1
Gerrit-Owner: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Kurt Deschler <kd...@cloudera.com>
Gerrit-Comment-Date: Wed, 26 Jun 2024 14:03:43 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
Posted by "Zoltan Borok-Nagy (Code Review)" <ge...@cloudera.org>.
Hello Daniel Becker, Kurt Deschler, Michael Smith, Impala Public Jenkins,
I'd like you to reexamine a change. Please visit
http://gerrit.cloudera.org:8080/21557
to look at the new patch set (#6).
Change subject: IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
......................................................................
IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
This patch substitutes the sorted 64-bit integer vectors that we
use in IcebergDeleteNode to 64-bit roaring bitmaps. We use the
CRoaring library (version 4.0.0). CRoaring also offers C++ classes,
but this patch adds its own thin C++ wrapper class around the C
functions to get the best performance.
Toolchain Clang 5.0.1 was not able to compile CRoaring due to a
bug which is tracked by IMPALA-13190, this patch also fixes it
with a new toolchain.
Performance
I used an extended version of the "One Trillion Row" challenge. This
means after inserting 1 Trillion records to a table I also deleted /
updated lots of records. So at the end I had 1 Trillion data records
and ~68.5 Billion delete records in the table.
For the measurements I used clusters with 10 and 40 executors, and
executed the following query:
SELECT station, min(measure), max(measure), avg(measure)
FROM measurements_extra_1trc_partitioned
GROUP BY 1
ORDER BY 1;
JOIN BUILD times:
+----------------+--------------+--------------+
| Implementation | 10 executors | 40 executors |
+----------------+--------------+--------------+
| Sorted vectors | CRASH | 4m15s |
| Roaring bitmap | 6m35s | 1m51s |
+----------------+--------------+--------------+
10 executors cluster with sorted vectors failed to run the query because
executors crashed due to out-of-memory.
Memory usage (VmRSS) for 10 executors:
+----------------+------------------------+
| Implementation | 10 executors |
+----------------+------------------------+
| Sorted vectors | 54.4 GB (before CRASH) |
| Roaring bitmap | 7.4 GB |
+----------------+------------------------+
Testing:
* added tests for RoaringBitmap64
Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
---
M LICENSE.txt
M be/src/exec/iceberg-delete-builder.cc
M be/src/exec/iceberg-delete-builder.h
M be/src/exec/iceberg-delete-node.cc
M be/src/exec/iceberg-delete-node.h
A be/src/thirdparty/roaring/LICENSE
A be/src/thirdparty/roaring/README.md
A be/src/thirdparty/roaring/roaring.c
A be/src/thirdparty/roaring/roaring.h
M be/src/util/CMakeLists.txt
A be/src/util/roaring-bitmap-test.cc
A be/src/util/roaring-bitmap.h
M bin/impala-config.sh
M bin/rat_exclude_files.txt
14 files changed, 29,409 insertions(+), 207 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/Impala-ASF refs/changes/57/21557/6
--
To view, visit http://gerrit.cloudera.org:8080/21557
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
Gerrit-Change-Number: 21557
Gerrit-PatchSet: 6
Gerrit-Owner: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Reviewer: Daniel Becker <da...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Kurt Deschler <kd...@cloudera.com>
Gerrit-Reviewer: Michael Smith <mi...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
[Impala-ASF-CR] IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
Posted by "Csaba Ringhofer (Code Review)" <ge...@cloudera.org>.
Csaba Ringhofer has posted comments on this change. ( http://gerrit.cloudera.org:8080/21557 )
Change subject: IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
......................................................................
Patch Set 8:
(3 comments)
looks great! few questions, mainly related to memory management
http://gerrit.cloudera.org:8080/#/c/21557/8//COMMIT_MSG
Commit Message:
http://gerrit.cloudera.org:8080/#/c/21557/8//COMMIT_MSG@22
PS8, Line 22: lots of records
It could be interesting how the deleted rows were selected, as roaring bitmap stores continuous runs in optimized way.
http://gerrit.cloudera.org:8080/#/c/21557/8//COMMIT_MSG@41
PS8, Line 41: 10 executors cluster with sorted vectors failed to run the query because
: executors crashed due to out-of-memory.
Can you add a bit more info on this? What should be clarified is whether there are known issues with IcebergDeleteNode that can lead to OOM crashes.
If I understand the memory management correctly then we have a fair estimation during planning about the memory consumption and set this as minimal reservation. If the cluster doesn't have that much memory then it shouldn't start running the query. Do you know what goes wrong?
I don't mean to fix existing memory issues in this commit, but there should be a Jira about this.
http://gerrit.cloudera.org:8080/#/c/21557/8//COMMIT_MSG@44
PS8, Line 44: Memory usage (VmRSS) for 10 executors:
The memory estimations are not changed - this is intentional, as we assume that in the worst case the roaring bitmap will still need 8 byte per position, right? https://github.com/apache/impala/blob/00d0b0dda1e215d8e91ff52688fe6654bee52282/fe/src/main/java/org/apache/impala/planner/IcebergDeleteNode.java#L200
--
To view, visit http://gerrit.cloudera.org:8080/21557
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
Gerrit-Change-Number: 21557
Gerrit-PatchSet: 8
Gerrit-Owner: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Reviewer: Csaba Ringhofer <cs...@cloudera.com>
Gerrit-Reviewer: Daniel Becker <da...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Kurt Deschler <kd...@cloudera.com>
Gerrit-Reviewer: Michael Smith <mi...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Mon, 08 Jul 2024 18:13:54 +0000
Gerrit-HasComments: Yes
[Impala-ASF-CR] IMPALA-13088: Use RoaringBitmap instead of sorted vector of int64s
Posted by "Zoltan Borok-Nagy (Code Review)" <ge...@cloudera.org>.
Zoltan Borok-Nagy has posted comments on this change. ( http://gerrit.cloudera.org:8080/21557 )
Change subject: IMPALA-13088: Use RoaringBitmap instead of sorted vector of int64s
......................................................................
Patch Set 3:
(1 comment)
PS3 is squashed with https://gerrit.cloudera.org/#/c/21435/
http://gerrit.cloudera.org:8080/#/c/21557/2/be/src/util/roaring-bitmap-test.cc
File be/src/util/roaring-bitmap-test.cc:
http://gerrit.cloudera.org:8080/#/c/21557/2/be/src/util/roaring-bitmap-test.cc@33
PS2, Line 33: ASSERT_TRUE(rbm.IsEmpty());
> nit: might as well check the upper bound (with e.g. 30).
Done
--
To view, visit http://gerrit.cloudera.org:8080/21557
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
Gerrit-Change-Number: 21557
Gerrit-PatchSet: 3
Gerrit-Owner: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Reviewer: Daniel Becker <da...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Kurt Deschler <kd...@cloudera.com>
Gerrit-Reviewer: Michael Smith <mi...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Mon, 01 Jul 2024 13:13:31 +0000
Gerrit-HasComments: Yes
[Impala-ASF-CR] IMPALA-13088: Use RoaringBitmap instead of sorted vector of int64s
Posted by "Daniel Becker (Code Review)" <ge...@cloudera.org>.
Daniel Becker has posted comments on this change. ( http://gerrit.cloudera.org:8080/21557 )
Change subject: IMPALA-13088: Use RoaringBitmap instead of sorted vector of int64s
......................................................................
Patch Set 1:
(4 comments)
http://gerrit.cloudera.org:8080/#/c/21557/1/be/src/exec/iceberg-delete-builder.cc
File be/src/exec/iceberg-delete-builder.cc:
http://gerrit.cloudera.org:8080/#/c/21557/1/be/src/exec/iceberg-delete-builder.cc@285
PS1, Line 285: std::make_unsigned_t<int64_t>
We could simply use 'uint64_t' for the cast or leave the conversion implicit.
We could also DCHECK that the original signed position is not negative.
See also L297.
http://gerrit.cloudera.org:8080/#/c/21557/1/be/src/thirdparty/roaring/README.md
File be/src/thirdparty/roaring/README.md:
http://gerrit.cloudera.org:8080/#/c/21557/1/be/src/thirdparty/roaring/README.md@29
PS1, Line 29: need
Nit: "needs".
http://gerrit.cloudera.org:8080/#/c/21557/1/be/src/util/roaring-bitmap-test.cc
File be/src/util/roaring-bitmap-test.cc:
http://gerrit.cloudera.org:8080/#/c/21557/1/be/src/util/roaring-bitmap-test.cc@29
PS1, Line 29: 33
If we inserted 11, why should 33 be in the bitmap?
http://gerrit.cloudera.org:8080/#/c/21557/1/be/src/util/roaring-bitmap.h
File be/src/util/roaring-bitmap.h:
http://gerrit.cloudera.org:8080/#/c/21557/1/be/src/util/roaring-bitmap.h@33
PS1, Line 33: BulkContext
Couldn't we use 'roaring64_bulk_context_t' directly? Or are you concerned about accidentally using the copy constructor/assignment operator?
--
To view, visit http://gerrit.cloudera.org:8080/21557
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
Gerrit-Change-Number: 21557
Gerrit-PatchSet: 1
Gerrit-Owner: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Reviewer: Daniel Becker <da...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Kurt Deschler <kd...@cloudera.com>
Gerrit-Reviewer: Michael Smith <mi...@cloudera.com>
Gerrit-Comment-Date: Fri, 28 Jun 2024 10:45:39 +0000
Gerrit-HasComments: Yes
[Impala-ASF-CR] IMPALA-13088: Use RoaringBitmap instead of sorted vector of int64s
Posted by "Zoltan Borok-Nagy (Code Review)" <ge...@cloudera.org>.
Zoltan Borok-Nagy has posted comments on this change. ( http://gerrit.cloudera.org:8080/21557 )
Change subject: IMPALA-13088: Use RoaringBitmap instead of sorted vector of int64s
......................................................................
Patch Set 2:
(8 comments)
Clang-tidy failed on a Clang issue, opened IMPALA-13190 for this and preparing a new toolchain build.
http://gerrit.cloudera.org:8080/#/c/21557/1//COMMIT_MSG
Commit Message:
http://gerrit.cloudera.org:8080/#/c/21557/1//COMMIT_MSG@11
PS1, Line 11: CRoaring library (version 4.0.0). CRoaring also offers C++ classes,
> Please mention what release we're using.
Done
http://gerrit.cloudera.org:8080/#/c/21557/1/be/src/exec/iceberg-delete-builder.cc
File be/src/exec/iceberg-delete-builder.cc:
http://gerrit.cloudera.org:8080/#/c/21557/1/be/src/exec/iceberg-delete-builder.cc@260
PS1, Line 260: deletes.AddElements(positions);
> CRoaring does not handle out-of-memory. We should maybe add some reserve ch
I was thinking about this a bit. If we add reserve checks, they might still return non-NULL pointers due to overcommit, and if we had test them we'd get SIGSEGV, just like we'd get from CRoaring.
Or let's assume the reserve checks pass. Since Impala is multi-threaded, we cannot guarantee that CRoaring will be able to use them when it needs memory. It's probably quite likely that some other thread will steal the reservation when there is already high memory pressure.
We also don't know exactly how many and how much allocations CRoaring will use.
It's possible to register a global malloc for CRoaring, but I don't think it would have too much value as we cannot assign the memory consumption to queries. Pre-allocating memory, and writing custom allocators wouldn't worth the extra effort IMO, as at the end, if we run out of pre-allocated memory, we face the same problem.
Also, probably the kernel would OOMKill the process anyway before allocation failures.
In general, I don't think we handle OOM situations in Impala, especially when it is untracked memory. We just let the process die, and I don't think it is too bad. And without CRoaring, the sorted vectors would allocate way too more memory, and Impala would be more prone to crash. With CRoaring, Impala survives more likely.
http://gerrit.cloudera.org:8080/#/c/21557/1/be/src/exec/iceberg-delete-builder.cc@285
PS1, Line 285: *first_row->GetTuple(0)->GetB
> We could simply use 'uint64_t' for the cast or leave the conversion implici
Yeah, initially 'pos' was a pointer and I had to add casts.
DCHECKs are not appropriate here as they are for catching programming errors, but here we get the input data outside from Impala.
http://gerrit.cloudera.org:8080/#/c/21557/1/be/src/exec/iceberg-delete-builder.cc@303
PS1, Line 303: pos_buffer.push_back(pos);
> Should sort pos_buffer here to guarantee performance of bitmap insert.
The delete positions are stored in ascending order in the position delete files. It's possible that an exchange receives position delete records from different executors for the same data file, but even in that case 'pos_buffer' will be mostly sorted.
I micro-benchmarked the CRoaring library, inserted 100 Million records:
Input is completely sorted = 337[ms]
Every 10th element is significantly out-of-order = 503[ms]
So I think out-of-order elements are handled quite efficiently. And in our case, they are extremely rare.
http://gerrit.cloudera.org:8080/#/c/21557/1/be/src/thirdparty/roaring/README.md
File be/src/thirdparty/roaring/README.md:
http://gerrit.cloudera.org:8080/#/c/21557/1/be/src/thirdparty/roaring/README.md@29
PS1, Line 29: So one just needs to download the amalgamated files and override the
> Can we include a link where to find the CRoaring library?
Done
http://gerrit.cloudera.org:8080/#/c/21557/1/be/src/thirdparty/roaring/README.md@29
PS1, Line 29: need
> Nit: "needs".
Done
http://gerrit.cloudera.org:8080/#/c/21557/1/be/src/util/roaring-bitmap-test.cc
File be/src/util/roaring-bitmap-test.cc:
http://gerrit.cloudera.org:8080/#/c/21557/1/be/src/util/roaring-bitmap-test.cc@29
PS1, Line 29: )
> If we inserted 11, why should 33 be in the bitmap?
It shouldn't, I was just uploaded this file very early.
http://gerrit.cloudera.org:8080/#/c/21557/1/be/src/util/roaring-bitmap.h
File be/src/util/roaring-bitmap.h:
http://gerrit.cloudera.org:8080/#/c/21557/1/be/src/util/roaring-bitmap.h@33
PS1, Line 33: BulkContext
> Couldn't we use 'roaring64_bulk_context_t' directly? Or are you concerned a
I think it's safer and cleaner this way. Safer, because we provide a constructor that initializes the roaring64_bulk_context_t object. And cleaner, because user code don't need to mix different libraries and objects of different programming languages.
--
To view, visit http://gerrit.cloudera.org:8080/21557
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
Gerrit-Change-Number: 21557
Gerrit-PatchSet: 2
Gerrit-Owner: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Reviewer: Daniel Becker <da...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Kurt Deschler <kd...@cloudera.com>
Gerrit-Reviewer: Michael Smith <mi...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Fri, 28 Jun 2024 17:06:39 +0000
Gerrit-HasComments: Yes
[Impala-ASF-CR] IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
Posted by "Csaba Ringhofer (Code Review)" <ge...@cloudera.org>.
Csaba Ringhofer has posted comments on this change. ( http://gerrit.cloudera.org:8080/21557 )
Change subject: IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
......................................................................
Patch Set 10: Code-Review+2
(3 comments)
http://gerrit.cloudera.org:8080/#/c/21557/8//COMMIT_MSG
Commit Message:
http://gerrit.cloudera.org:8080/#/c/21557/8//COMMIT_MSG@22
PS8, Line 22: lots of records
> Added a section at the end.
Thanks for adding these.
Maybe for these details the Jira would be actually a better place?
http://gerrit.cloudera.org:8080/#/c/21557/9/be/src/exec/iceberg-delete-builder.h
File be/src/exec/iceberg-delete-builder.h:
http://gerrit.cloudera.org:8080/#/c/21557/9/be/src/exec/iceberg-delete-builder.h@119
PS9, Line 119: RoaringBitmap64
> That's a great idea. Would you mind creating a Jira ticket for this?
Created a ticket: IMPALA-13217
http://gerrit.cloudera.org:8080/#/c/21557/9/fe/src/main/java/org/apache/impala/planner/IcebergDeleteNode.java
File fe/src/main/java/org/apache/impala/planner/IcebergDeleteNode.java:
http://gerrit.cloudera.org:8080/#/c/21557/9/fe/src/main/java/org/apache/impala/planner/IcebergDeleteNode.java@201
PS9, Line 201: // Let's calculate with some overhead per roaring bitmap.
> I updated the calculations to have 512 bytes overhead per roaring bitmap. A
Thanks, I guess it's safe enough now!
--
To view, visit http://gerrit.cloudera.org:8080/21557
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
Gerrit-Change-Number: 21557
Gerrit-PatchSet: 10
Gerrit-Owner: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Reviewer: Csaba Ringhofer <cs...@cloudera.com>
Gerrit-Reviewer: Daniel Becker <da...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Kurt Deschler <kd...@cloudera.com>
Gerrit-Reviewer: Michael Smith <mi...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Fri, 12 Jul 2024 10:40:28 +0000
Gerrit-HasComments: Yes
[Impala-ASF-CR] IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/21557 )
Change subject: IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
......................................................................
Patch Set 8:
Build Successful
https://jenkins.impala.io/job/gerrit-code-review-checks/16462/ : 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/21557
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
Gerrit-Change-Number: 21557
Gerrit-PatchSet: 8
Gerrit-Owner: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Reviewer: Daniel Becker <da...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Kurt Deschler <kd...@cloudera.com>
Gerrit-Reviewer: Michael Smith <mi...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Wed, 03 Jul 2024 14:29:50 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] IMPALA-13088: Use RoaringBitmap instead of sorted vector of int64s
Posted by "Zoltan Borok-Nagy (Code Review)" <ge...@cloudera.org>.
Hello Daniel Becker, Kurt Deschler, Michael Smith, Impala Public Jenkins,
I'd like you to reexamine a change. Please visit
http://gerrit.cloudera.org:8080/21557
to look at the new patch set (#4).
Change subject: IMPALA-13088: Use RoaringBitmap instead of sorted vector of int64s
......................................................................
IMPALA-13088: Use RoaringBitmap instead of sorted vector of int64s
This patch substitutes the sorted 64-bit integer vectors that we
use in IcebergDeleteNode to 64-bit roaring bitmaps. We use the
CRoaring library (version 4.0.0). CRoaring also offers C++ classes,
but this patch adds its own thin C++ wrapper class around the C
functions to get the best performance.
Performance
I used an extended version of the "One Trillion Row" challenge. This
means after inserting 1 Trillion records to a table I also deleted /
updated lots of records. So at the end I had 1 Trillion data records
and ~68.5 Billion delete records in the table.
For the measurements I used clusters with 10 and 40 executors, and
executed the following query:
SELECT station, min(measure), max(measure), avg(measure)
FROM measurements_extra_1trc_partitioned
GROUP BY 1
ORDER BY 1;
JOIN BUILD times:
+----------------+--------------+--------------+
| Implementation | 10 executors | 40 executors |
+----------------+--------------+--------------+
| Sorted vectors | CRASH | 4m15s |
| Roaring bitmap | 6m35s | 1m51s |
+----------------+--------------+--------------+
10 executors cluster with sorted vectors failed to run the query because
executors crashed due to out-of-memory.
Memory usage (VmRSS) for 10 executors:
+----------------+------------------------+
| Implementation | 10 executors |
+----------------+------------------------+
| Sorted vectors | 54.4 GB (before CRASH) |
| Roaring bitmap | 7.4 GB |
+----------------+------------------------+
Testing:
* added tests for RoaringBitmap64
Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
---
M LICENSE.txt
M be/src/exec/iceberg-delete-builder.cc
M be/src/exec/iceberg-delete-builder.h
M be/src/exec/iceberg-delete-node.cc
M be/src/exec/iceberg-delete-node.h
A be/src/thirdparty/roaring/LICENSE
A be/src/thirdparty/roaring/README.md
A be/src/thirdparty/roaring/roaring.c
A be/src/thirdparty/roaring/roaring.h
M be/src/util/CMakeLists.txt
A be/src/util/roaring-bitmap-test.cc
A be/src/util/roaring-bitmap.h
M bin/rat_exclude_files.txt
13 files changed, 29,406 insertions(+), 203 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/Impala-ASF refs/changes/57/21557/4
--
To view, visit http://gerrit.cloudera.org:8080/21557
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
Gerrit-Change-Number: 21557
Gerrit-PatchSet: 4
Gerrit-Owner: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Reviewer: Daniel Becker <da...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Kurt Deschler <kd...@cloudera.com>
Gerrit-Reviewer: Michael Smith <mi...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
[Impala-ASF-CR] IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/21557 )
Change subject: IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
......................................................................
Patch Set 11: Code-Review+2
--
To view, visit http://gerrit.cloudera.org:8080/21557
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
Gerrit-Change-Number: 21557
Gerrit-PatchSet: 11
Gerrit-Owner: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Reviewer: Csaba Ringhofer <cs...@cloudera.com>
Gerrit-Reviewer: Daniel Becker <da...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Kurt Deschler <kd...@cloudera.com>
Gerrit-Reviewer: Michael Smith <mi...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Tue, 16 Jul 2024 12:26:06 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/21557 )
Change subject: IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
......................................................................
Patch Set 11:
Build started: https://jenkins.impala.io/job/gerrit-verify-dryrun/10794/ DRY_RUN=false
--
To view, visit http://gerrit.cloudera.org:8080/21557
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
Gerrit-Change-Number: 21557
Gerrit-PatchSet: 11
Gerrit-Owner: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Reviewer: Csaba Ringhofer <cs...@cloudera.com>
Gerrit-Reviewer: Daniel Becker <da...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Kurt Deschler <kd...@cloudera.com>
Gerrit-Reviewer: Michael Smith <mi...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Tue, 16 Jul 2024 12:26:06 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
Posted by "Zoltan Borok-Nagy (Code Review)" <ge...@cloudera.org>.
Zoltan Borok-Nagy has posted comments on this change. ( http://gerrit.cloudera.org:8080/21557 )
Change subject: IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
......................................................................
Patch Set 6:
FYI the toolchain fix is still on review: https://gerrit.cloudera.org/#/c/21562/
--
To view, visit http://gerrit.cloudera.org:8080/21557
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
Gerrit-Change-Number: 21557
Gerrit-PatchSet: 6
Gerrit-Owner: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Reviewer: Daniel Becker <da...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Kurt Deschler <kd...@cloudera.com>
Gerrit-Reviewer: Michael Smith <mi...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Tue, 02 Jul 2024 17:12:30 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] IMPALA-13088: Use RoaringBitmap instead of sorted vector of int64s
Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/21557 )
Change subject: IMPALA-13088: Use RoaringBitmap instead of sorted vector of int64s
......................................................................
Patch Set 4:
Build Failed
https://jenkins.impala.io/job/gerrit-code-review-checks/16452/ : Initial code review checks failed. See linked job for details on the failure.
--
To view, visit http://gerrit.cloudera.org:8080/21557
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
Gerrit-Change-Number: 21557
Gerrit-PatchSet: 4
Gerrit-Owner: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Reviewer: Daniel Becker <da...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Kurt Deschler <kd...@cloudera.com>
Gerrit-Reviewer: Michael Smith <mi...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Mon, 01 Jul 2024 13:41:55 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] IMPALA-13088: Use RoaringBitmap instead of sorted vector of int64s
Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/21557 )
Change subject: IMPALA-13088: Use RoaringBitmap instead of sorted vector of int64s
......................................................................
Patch Set 1: Verified-1
Build failed: https://jenkins.impala.io/job/gerrit-verify-dryrun/10764/
--
To view, visit http://gerrit.cloudera.org:8080/21557
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
Gerrit-Change-Number: 21557
Gerrit-PatchSet: 1
Gerrit-Owner: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Kurt Deschler <kd...@cloudera.com>
Gerrit-Reviewer: Michael Smith <mi...@cloudera.com>
Gerrit-Comment-Date: Wed, 26 Jun 2024 18:59:16 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] IMPALA-13088: Use RoaringBitmap instead of sorted vector of int64s
Posted by "Daniel Becker (Code Review)" <ge...@cloudera.org>.
Daniel Becker has posted comments on this change. ( http://gerrit.cloudera.org:8080/21557 )
Change subject: IMPALA-13088: Use RoaringBitmap instead of sorted vector of int64s
......................................................................
Patch Set 2:
(1 comment)
http://gerrit.cloudera.org:8080/#/c/21557/2/bin/rat_exclude_files.txt
File bin/rat_exclude_files.txt:
http://gerrit.cloudera.org:8080/#/c/21557/2/bin/rat_exclude_files.txt@245
PS2, Line 245: be/src/thirdparty/roaring/LICENSE
Shouldn't we add the licence to /LICENSE.txt, as the comment above writes?
--
To view, visit http://gerrit.cloudera.org:8080/21557
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
Gerrit-Change-Number: 21557
Gerrit-PatchSet: 2
Gerrit-Owner: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Reviewer: Daniel Becker <da...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Kurt Deschler <kd...@cloudera.com>
Gerrit-Reviewer: Michael Smith <mi...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Mon, 01 Jul 2024 11:37:54 +0000
Gerrit-HasComments: Yes
[Impala-ASF-CR] IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
Posted by "Csaba Ringhofer (Code Review)" <ge...@cloudera.org>.
Csaba Ringhofer has posted comments on this change. ( http://gerrit.cloudera.org:8080/21557 )
Change subject: IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
......................................................................
Patch Set 9: Code-Review+1
(3 comments)
http://gerrit.cloudera.org:8080/#/c/21557/9/be/src/exec/iceberg-delete-builder.h
File be/src/exec/iceberg-delete-builder.h:
http://gerrit.cloudera.org:8080/#/c/21557/9/be/src/exec/iceberg-delete-builder.h@119
PS9, Line 119: RoaringBitmap64
As we discussed offline, memory used by roaring bitmap could be tracked the following way:
an allocator could be created that saves mem tracker to a thread local variable - as a thread only works for a specific fragment instance, this would be a clear mapping
roaring bitmap can use a global allocator that gets the thread local mem tracker and allocates memory through that
we could check before each batch whether the memory limit was exceeded - if yes, then it could try to increase reservation or fail the query if it can't get more memory
This mainly just a reminder, I don't mean to implement this in the current patch.
http://gerrit.cloudera.org:8080/#/c/21557/9/fe/src/main/java/org/apache/impala/planner/IcebergDeleteNode.java
File fe/src/main/java/org/apache/impala/planner/IcebergDeleteNode.java:
http://gerrit.cloudera.org:8080/#/c/21557/9/fe/src/main/java/org/apache/impala/planner/IcebergDeleteNode.java@177
PS9, Line 177: getChild(1).getCardinality() == -1
Is it possible for these to be unknown? If not, then this if could be replaced with a precondition.
http://gerrit.cloudera.org:8080/#/c/21557/9/fe/src/main/java/org/apache/impala/planner/IcebergDeleteNode.java@201
PS9, Line 201: long roaringBitmapSize = (long) Math.ceil(1.5 * rhsCard);
Can you move the 1.5 to a constant?
Also, I think that this can underestimate memory needs:
- if there are relatively few rows per file, then the per 64K block overhead can be significant
- the sorted vectors are likely to allocate more memory than needed to store elements (*1.5).
--
To view, visit http://gerrit.cloudera.org:8080/21557
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
Gerrit-Change-Number: 21557
Gerrit-PatchSet: 9
Gerrit-Owner: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Reviewer: Csaba Ringhofer <cs...@cloudera.com>
Gerrit-Reviewer: Daniel Becker <da...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Kurt Deschler <kd...@cloudera.com>
Gerrit-Reviewer: Michael Smith <mi...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Wed, 10 Jul 2024 15:50:43 +0000
Gerrit-HasComments: Yes
[Impala-ASF-CR] IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
Posted by "Zoltan Borok-Nagy (Code Review)" <ge...@cloudera.org>.
Hello Daniel Becker, Kurt Deschler, Michael Smith, Impala Public Jenkins,
I'd like you to reexamine a change. Please visit
http://gerrit.cloudera.org:8080/21557
to look at the new patch set (#5).
Change subject: IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
......................................................................
IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
This patch substitutes the sorted 64-bit integer vectors that we
use in IcebergDeleteNode to 64-bit roaring bitmaps. We use the
CRoaring library (version 4.0.0). CRoaring also offers C++ classes,
but this patch adds its own thin C++ wrapper class around the C
functions to get the best performance.
Toolchain Clang 5.0.1 was not able to compile CRoaring due to a
bug which is tracked by IMPALA-13190, this patch also fixes it
with a new toolchain.
Performance
I used an extended version of the "One Trillion Row" challenge. This
means after inserting 1 Trillion records to a table I also deleted /
updated lots of records. So at the end I had 1 Trillion data records
and ~68.5 Billion delete records in the table.
For the measurements I used clusters with 10 and 40 executors, and
executed the following query:
SELECT station, min(measure), max(measure), avg(measure)
FROM measurements_extra_1trc_partitioned
GROUP BY 1
ORDER BY 1;
JOIN BUILD times:
+----------------+--------------+--------------+
| Implementation | 10 executors | 40 executors |
+----------------+--------------+--------------+
| Sorted vectors | CRASH | 4m15s |
| Roaring bitmap | 6m35s | 1m51s |
+----------------+--------------+--------------+
10 executors cluster with sorted vectors failed to run the query because
executors crashed due to out-of-memory.
Memory usage (VmRSS) for 10 executors:
+----------------+------------------------+
| Implementation | 10 executors |
+----------------+------------------------+
| Sorted vectors | 54.4 GB (before CRASH) |
| Roaring bitmap | 7.4 GB |
+----------------+------------------------+
Testing:
* added tests for RoaringBitmap64
Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
---
M LICENSE.txt
M be/src/exec/iceberg-delete-builder.cc
M be/src/exec/iceberg-delete-builder.h
M be/src/exec/iceberg-delete-node.cc
M be/src/exec/iceberg-delete-node.h
A be/src/thirdparty/roaring/LICENSE
A be/src/thirdparty/roaring/README.md
A be/src/thirdparty/roaring/roaring.c
A be/src/thirdparty/roaring/roaring.h
M be/src/util/CMakeLists.txt
A be/src/util/roaring-bitmap-test.cc
A be/src/util/roaring-bitmap.h
M bin/impala-config.sh
M bin/rat_exclude_files.txt
14 files changed, 29,407 insertions(+), 205 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/Impala-ASF refs/changes/57/21557/5
--
To view, visit http://gerrit.cloudera.org:8080/21557
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
Gerrit-Change-Number: 21557
Gerrit-PatchSet: 5
Gerrit-Owner: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Reviewer: Daniel Becker <da...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Kurt Deschler <kd...@cloudera.com>
Gerrit-Reviewer: Michael Smith <mi...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
[Impala-ASF-CR] IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
Posted by "Zoltan Borok-Nagy (Code Review)" <ge...@cloudera.org>.
Zoltan Borok-Nagy has posted comments on this change. ( http://gerrit.cloudera.org:8080/21557 )
Change subject: IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
......................................................................
Patch Set 5:
(1 comment)
http://gerrit.cloudera.org:8080/#/c/21557/4/be/src/thirdparty/roaring/README.md
File be/src/thirdparty/roaring/README.md:
http://gerrit.cloudera.org:8080/#/c/21557/4/be/src/thirdparty/roaring/README.md@26
PS4, Line 26: - roaring.c
> Do we have this file?
CRoaring also generates this file which contains the C++ codes, but we don't use it. Removed this line to avoid confusion.
--
To view, visit http://gerrit.cloudera.org:8080/21557
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
Gerrit-Change-Number: 21557
Gerrit-PatchSet: 5
Gerrit-Owner: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Reviewer: Daniel Becker <da...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Kurt Deschler <kd...@cloudera.com>
Gerrit-Reviewer: Michael Smith <mi...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Tue, 02 Jul 2024 17:05:32 +0000
Gerrit-HasComments: Yes
[Impala-ASF-CR] IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
Posted by "Zoltan Borok-Nagy (Code Review)" <ge...@cloudera.org>.
Hello Daniel Becker, Kurt Deschler, Michael Smith, Impala Public Jenkins,
I'd like you to reexamine a change. Please visit
http://gerrit.cloudera.org:8080/21557
to look at the new patch set (#8).
Change subject: IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
......................................................................
IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
This patch substitutes the sorted 64-bit integer vectors that we
use in IcebergDeleteNode to 64-bit roaring bitmaps. We use the
CRoaring library (version 4.0.0). CRoaring also offers C++ classes,
but this patch adds its own thin C++ wrapper class around the C
functions to get the best performance.
Toolchain Clang 5.0.1 was not able to compile CRoaring due to a
bug which is tracked by IMPALA-13190, this patch also fixes it
with a new toolchain.
Performance
I used an extended version of the "One Trillion Row" challenge. This
means after inserting 1 Trillion records to a table I also deleted /
updated lots of records. So at the end I had 1 Trillion data records
and ~68.5 Billion delete records in the table.
For the measurements I used clusters with 10 and 40 executors, and
executed the following query:
SELECT station, min(measure), max(measure), avg(measure)
FROM measurements_extra_1trc_partitioned
GROUP BY 1
ORDER BY 1;
JOIN BUILD times:
+----------------+--------------+--------------+
| Implementation | 10 executors | 40 executors |
+----------------+--------------+--------------+
| Sorted vectors | CRASH | 4m15s |
| Roaring bitmap | 6m35s | 1m51s |
+----------------+--------------+--------------+
10 executors cluster with sorted vectors failed to run the query because
executors crashed due to out-of-memory.
Memory usage (VmRSS) for 10 executors:
+----------------+------------------------+
| Implementation | 10 executors |
+----------------+------------------------+
| Sorted vectors | 54.4 GB (before CRASH) |
| Roaring bitmap | 7.4 GB |
+----------------+------------------------+
Testing:
* added tests for RoaringBitmap64
Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
---
M LICENSE.txt
M be/src/exec/iceberg-delete-builder.cc
M be/src/exec/iceberg-delete-builder.h
M be/src/exec/iceberg-delete-node.cc
M be/src/exec/iceberg-delete-node.h
A be/src/thirdparty/roaring/LICENSE
A be/src/thirdparty/roaring/README.md
A be/src/thirdparty/roaring/roaring.c
A be/src/thirdparty/roaring/roaring.h
M be/src/util/CMakeLists.txt
A be/src/util/roaring-bitmap-test.cc
A be/src/util/roaring-bitmap.h
M bin/impala-config.sh
M bin/rat_exclude_files.txt
A testdata/workloads/functional-query/queries/QueryTest/iceberg-query-v2.test
M testdata/workloads/functional-query/queries/QueryTest/iceberg-query.test
M tests/query_test/test_scanners.py
17 files changed, 29,455 insertions(+), 243 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/Impala-ASF refs/changes/57/21557/8
--
To view, visit http://gerrit.cloudera.org:8080/21557
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
Gerrit-Change-Number: 21557
Gerrit-PatchSet: 8
Gerrit-Owner: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Reviewer: Daniel Becker <da...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Kurt Deschler <kd...@cloudera.com>
Gerrit-Reviewer: Michael Smith <mi...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
[Impala-ASF-CR] IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
Posted by "Zoltan Borok-Nagy (Code Review)" <ge...@cloudera.org>.
Zoltan Borok-Nagy has posted comments on this change. ( http://gerrit.cloudera.org:8080/21557 )
Change subject: IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
......................................................................
Patch Set 10:
(4 comments)
Thanks for the comments!
http://gerrit.cloudera.org:8080/#/c/21557/9//COMMIT_MSG
Commit Message:
http://gerrit.cloudera.org:8080/#/c/21557/9//COMMIT_MSG@68
PS9, Line 68:
> Some of the columns are too long.
Done
http://gerrit.cloudera.org:8080/#/c/21557/9/be/src/exec/iceberg-delete-builder.h
File be/src/exec/iceberg-delete-builder.h:
http://gerrit.cloudera.org:8080/#/c/21557/9/be/src/exec/iceberg-delete-builder.h@119
PS9, Line 119: RoaringBitmap64
> As we discussed offline, memory used by roaring bitmap could be tracked the
That's a great idea. Would you mind creating a Jira ticket for this?
http://gerrit.cloudera.org:8080/#/c/21557/9/fe/src/main/java/org/apache/impala/planner/IcebergDeleteNode.java
File fe/src/main/java/org/apache/impala/planner/IcebergDeleteNode.java:
http://gerrit.cloudera.org:8080/#/c/21557/9/fe/src/main/java/org/apache/impala/planner/IcebergDeleteNode.java@177
PS9, Line 177: onditions.checkState(fragment_.getN
> Is it possible for these to be unknown? If not, then this if could be repla
IcebergScanPlanner should always set these stats.
http://gerrit.cloudera.org:8080/#/c/21557/9/fe/src/main/java/org/apache/impala/planner/IcebergDeleteNode.java@201
PS9, Line 201: // Let's calculate with some overhead per roaring bitmap.
> Can you move the 1.5 to a constant?
I updated the calculations to have 512 bytes overhead per roaring bitmap. Also increased bytes per position to 2. I also don't want to overestimate with a too big margin as that would limit Impala too much to execute the query.
If there are few rows per file, then the whole roaring bitmap might consume a few hundred bytes of untracked memory at most, so it's probably won't be too critical anyway.
--
To view, visit http://gerrit.cloudera.org:8080/21557
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
Gerrit-Change-Number: 21557
Gerrit-PatchSet: 10
Gerrit-Owner: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Reviewer: Csaba Ringhofer <cs...@cloudera.com>
Gerrit-Reviewer: Daniel Becker <da...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Kurt Deschler <kd...@cloudera.com>
Gerrit-Reviewer: Michael Smith <mi...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Thu, 11 Jul 2024 16:59:31 +0000
Gerrit-HasComments: Yes
[Impala-ASF-CR] IMPALA-13088: Use RoaringBitmap instead of sorted vector of int64s
Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/21557 )
Change subject: IMPALA-13088: Use RoaringBitmap instead of sorted vector of int64s
......................................................................
Patch Set 2:
Build Failed
https://jenkins.impala.io/job/gerrit-code-review-checks/16445/ : Initial code review checks failed. See linked job for details on the failure.
--
To view, visit http://gerrit.cloudera.org:8080/21557
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
Gerrit-Change-Number: 21557
Gerrit-PatchSet: 2
Gerrit-Owner: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Reviewer: Daniel Becker <da...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Kurt Deschler <kd...@cloudera.com>
Gerrit-Reviewer: Michael Smith <mi...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Fri, 28 Jun 2024 17:23:41 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
Posted by "Zoltan Borok-Nagy (Code Review)" <ge...@cloudera.org>.
Hello Daniel Becker, Kurt Deschler, Michael Smith, Impala Public Jenkins,
I'd like you to reexamine a change. Please visit
http://gerrit.cloudera.org:8080/21557
to look at the new patch set (#7).
Change subject: IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
......................................................................
IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
This patch substitutes the sorted 64-bit integer vectors that we
use in IcebergDeleteNode to 64-bit roaring bitmaps. We use the
CRoaring library (version 4.0.0). CRoaring also offers C++ classes,
but this patch adds its own thin C++ wrapper class around the C
functions to get the best performance.
Toolchain Clang 5.0.1 was not able to compile CRoaring due to a
bug which is tracked by IMPALA-13190, this patch also fixes it
with a new toolchain.
Performance
I used an extended version of the "One Trillion Row" challenge. This
means after inserting 1 Trillion records to a table I also deleted /
updated lots of records. So at the end I had 1 Trillion data records
and ~68.5 Billion delete records in the table.
For the measurements I used clusters with 10 and 40 executors, and
executed the following query:
SELECT station, min(measure), max(measure), avg(measure)
FROM measurements_extra_1trc_partitioned
GROUP BY 1
ORDER BY 1;
JOIN BUILD times:
+----------------+--------------+--------------+
| Implementation | 10 executors | 40 executors |
+----------------+--------------+--------------+
| Sorted vectors | CRASH | 4m15s |
| Roaring bitmap | 6m35s | 1m51s |
+----------------+--------------+--------------+
10 executors cluster with sorted vectors failed to run the query because
executors crashed due to out-of-memory.
Memory usage (VmRSS) for 10 executors:
+----------------+------------------------+
| Implementation | 10 executors |
+----------------+------------------------+
| Sorted vectors | 54.4 GB (before CRASH) |
| Roaring bitmap | 7.4 GB |
+----------------+------------------------+
Testing:
* added tests for RoaringBitmap64
Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
---
M LICENSE.txt
M be/src/exec/iceberg-delete-builder.cc
M be/src/exec/iceberg-delete-builder.h
M be/src/exec/iceberg-delete-node.cc
M be/src/exec/iceberg-delete-node.h
A be/src/thirdparty/roaring/LICENSE
A be/src/thirdparty/roaring/README.md
A be/src/thirdparty/roaring/roaring.c
A be/src/thirdparty/roaring/roaring.h
M be/src/util/CMakeLists.txt
A be/src/util/roaring-bitmap-test.cc
A be/src/util/roaring-bitmap.h
M bin/impala-config.sh
M bin/rat_exclude_files.txt
14 files changed, 29,412 insertions(+), 210 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/Impala-ASF refs/changes/57/21557/7
--
To view, visit http://gerrit.cloudera.org:8080/21557
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
Gerrit-Change-Number: 21557
Gerrit-PatchSet: 7
Gerrit-Owner: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Reviewer: Daniel Becker <da...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Kurt Deschler <kd...@cloudera.com>
Gerrit-Reviewer: Michael Smith <mi...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
[Impala-ASF-CR] IMPALA-13088: Use RoaringBitmap instead of sorted vector of int64s
Posted by "Daniel Becker (Code Review)" <ge...@cloudera.org>.
Daniel Becker has posted comments on this change. ( http://gerrit.cloudera.org:8080/21557 )
Change subject: IMPALA-13088: Use RoaringBitmap instead of sorted vector of int64s
......................................................................
Patch Set 4:
(1 comment)
http://gerrit.cloudera.org:8080/#/c/21557/4/be/src/thirdparty/roaring/README.md
File be/src/thirdparty/roaring/README.md:
http://gerrit.cloudera.org:8080/#/c/21557/4/be/src/thirdparty/roaring/README.md@26
PS4, Line 26: - roaring.hh
Do we have this file?
--
To view, visit http://gerrit.cloudera.org:8080/21557
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
Gerrit-Change-Number: 21557
Gerrit-PatchSet: 4
Gerrit-Owner: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Reviewer: Daniel Becker <da...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Kurt Deschler <kd...@cloudera.com>
Gerrit-Reviewer: Michael Smith <mi...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Tue, 02 Jul 2024 10:56:33 +0000
Gerrit-HasComments: Yes
[Impala-ASF-CR] IMPALA-13088: Use RoaringBitmap instead of sorted vector of int64s
Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/21557 )
Change subject: IMPALA-13088: Use RoaringBitmap instead of sorted vector of int64s
......................................................................
Patch Set 1:
Build started: https://jenkins.impala.io/job/gerrit-verify-dryrun/10764/ DRY_RUN=true
--
To view, visit http://gerrit.cloudera.org:8080/21557
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
Gerrit-Change-Number: 21557
Gerrit-PatchSet: 1
Gerrit-Owner: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Comment-Date: Wed, 26 Jun 2024 13:51:29 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] IMPALA-13088: Use RoaringBitmap instead of sorted vector of int64s
Posted by "Kurt Deschler (Code Review)" <ge...@cloudera.org>.
Kurt Deschler has posted comments on this change. ( http://gerrit.cloudera.org:8080/21557 )
Change subject: IMPALA-13088: Use RoaringBitmap instead of sorted vector of int64s
......................................................................
Patch Set 1:
(2 comments)
http://gerrit.cloudera.org:8080/#/c/21557/1/be/src/exec/iceberg-delete-builder.cc
File be/src/exec/iceberg-delete-builder.cc:
http://gerrit.cloudera.org:8080/#/c/21557/1/be/src/exec/iceberg-delete-builder.cc@260
PS1, Line 260: deletes.AddElements(positions);
CRoaring does not handle out-of-memory. We should maybe add some reserve check here before calling it's functions.
http://gerrit.cloudera.org:8080/#/c/21557/1/be/src/exec/iceberg-delete-builder.cc@303
PS1, Line 303: RETURN_IF_ERROR(AddToDeletedRows(prev_file_path, pos_buffer));
Should sort pos_buffer here to guarantee performance of bitmap insert.
--
To view, visit http://gerrit.cloudera.org:8080/21557
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
Gerrit-Change-Number: 21557
Gerrit-PatchSet: 1
Gerrit-Owner: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Kurt Deschler <kd...@cloudera.com>
Gerrit-Comment-Date: Wed, 26 Jun 2024 13:58:07 +0000
Gerrit-HasComments: Yes
[Impala-ASF-CR] IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
Posted by "Daniel Becker (Code Review)" <ge...@cloudera.org>.
Daniel Becker has posted comments on this change. ( http://gerrit.cloudera.org:8080/21557 )
Change subject: IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
......................................................................
Patch Set 9: Code-Review+1
(1 comment)
http://gerrit.cloudera.org:8080/#/c/21557/9//COMMIT_MSG
Commit Message:
http://gerrit.cloudera.org:8080/#/c/21557/9//COMMIT_MSG@68
PS9, Line 68: The original challenge didn't have any row-level modifications, columns 'ts'
Some of the columns are too long.
--
To view, visit http://gerrit.cloudera.org:8080/21557
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
Gerrit-Change-Number: 21557
Gerrit-PatchSet: 9
Gerrit-Owner: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Reviewer: Csaba Ringhofer <cs...@cloudera.com>
Gerrit-Reviewer: Daniel Becker <da...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Kurt Deschler <kd...@cloudera.com>
Gerrit-Reviewer: Michael Smith <mi...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Wed, 10 Jul 2024 12:18:01 +0000
Gerrit-HasComments: Yes
[Impala-ASF-CR] IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
Posted by "Michael Smith (Code Review)" <ge...@cloudera.org>.
Michael Smith has posted comments on this change. ( http://gerrit.cloudera.org:8080/21557 )
Change subject: IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
......................................................................
Patch Set 10: Code-Review+1
--
To view, visit http://gerrit.cloudera.org:8080/21557
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
Gerrit-Change-Number: 21557
Gerrit-PatchSet: 10
Gerrit-Owner: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Reviewer: Csaba Ringhofer <cs...@cloudera.com>
Gerrit-Reviewer: Daniel Becker <da...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Kurt Deschler <kd...@cloudera.com>
Gerrit-Reviewer: Michael Smith <mi...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Thu, 11 Jul 2024 17:04:13 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] IMPALA-13088: Use RoaringBitmap instead of sorted vector of int64s
Posted by "Zoltan Borok-Nagy (Code Review)" <ge...@cloudera.org>.
Hello Daniel Becker, Kurt Deschler, Michael Smith, Impala Public Jenkins,
I'd like you to reexamine a change. Please visit
http://gerrit.cloudera.org:8080/21557
to look at the new patch set (#2).
Change subject: IMPALA-13088: Use RoaringBitmap instead of sorted vector of int64s
......................................................................
IMPALA-13088: Use RoaringBitmap instead of sorted vector of int64s
This patch substitutes the sorted 64-bit integer vectors that we
use in IcebergDeleteNode to 64-bit roaring bitmaps. We use the
CRoaring library (version 4.0.0). CRoaring also offers C++ classes,
but this patch adds its own thin C++ wrapper class around the C
functions to get the best performance.
Performance
I used an extended version of the "One Trillion Row" challenge. This
means after inserting 1 Trillion records to a table I also deleted /
updated lots of records. So at the end I had 1 Trillion data records
and ~68.5 Billion delete records in the table.
For the measurements I used clusters with 10 and 40 executors, and
executed the following query:
SELECT station, min(measure), max(measure), avg(measure)
FROM measurements_extra_1trc_partitioned
GROUP BY 1
ORDER BY 1;
JOIN BUILD times:
+----------------+--------------+--------------+
| Implementation | 10 executors | 40 executors |
+----------------+--------------+--------------+
| Sorted vectors | CRASH | 2m3s |
| Roaring bitmap | 6m35s | 1m51s |
+----------------+--------------+--------------+
10 executors cluster with sorted vectors failed to run the query because
executors crashed due to out-of-memory.
Memory usage (VmRSS) for 10 executors:
+----------------+------------------------+
| Implementation | 10 executors |
+----------------+------------------------+
| Sorted vectors | 54.4 GB (before CRASH) |
| Roaring bitmap | 7.4 GB |
+----------------+------------------------+
Testing:
* added tests for RoaringBitmap64
Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
---
M be/src/exec/iceberg-delete-builder.cc
M be/src/exec/iceberg-delete-builder.h
M be/src/exec/iceberg-delete-node.cc
M be/src/exec/iceberg-delete-node.h
A be/src/thirdparty/roaring/LICENSE
A be/src/thirdparty/roaring/README.md
A be/src/thirdparty/roaring/roaring.c
A be/src/thirdparty/roaring/roaring.h
M be/src/util/CMakeLists.txt
A be/src/util/roaring-bitmap-test.cc
A be/src/util/roaring-bitmap.h
M bin/rat_exclude_files.txt
12 files changed, 29,367 insertions(+), 274 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/Impala-ASF refs/changes/57/21557/2
--
To view, visit http://gerrit.cloudera.org:8080/21557
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
Gerrit-Change-Number: 21557
Gerrit-PatchSet: 2
Gerrit-Owner: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Reviewer: Daniel Becker <da...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Kurt Deschler <kd...@cloudera.com>
Gerrit-Reviewer: Michael Smith <mi...@cloudera.com>
[Impala-ASF-CR] IMPALA-13088: Use RoaringBitmap instead of sorted vector of int64s
Posted by "Michael Smith (Code Review)" <ge...@cloudera.org>.
Michael Smith has posted comments on this change. ( http://gerrit.cloudera.org:8080/21557 )
Change subject: IMPALA-13088: Use RoaringBitmap instead of sorted vector of int64s
......................................................................
Patch Set 2: Code-Review+1
(3 comments)
http://gerrit.cloudera.org:8080/#/c/21557/1//COMMIT_MSG
Commit Message:
http://gerrit.cloudera.org:8080/#/c/21557/1//COMMIT_MSG@11
PS1, Line 11: CRoaring library (version 4.0.0). CRoaring also offers C++ classes,
> Done
Ack
http://gerrit.cloudera.org:8080/#/c/21557/1/be/src/thirdparty/roaring/README.md
File be/src/thirdparty/roaring/README.md:
http://gerrit.cloudera.org:8080/#/c/21557/1/be/src/thirdparty/roaring/README.md@29
PS1, Line 29: So one just needs to download the amalgamated files and override the
> Done
Ack
http://gerrit.cloudera.org:8080/#/c/21557/2/be/src/util/roaring-bitmap-test.cc
File be/src/util/roaring-bitmap-test.cc:
http://gerrit.cloudera.org:8080/#/c/21557/2/be/src/util/roaring-bitmap-test.cc@33
PS2, Line 33: ASSERT_FALSE(rbm.ContainsBulk(1, &context));
nit: might as well check the upper bound (with e.g. 30).
--
To view, visit http://gerrit.cloudera.org:8080/21557
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
Gerrit-Change-Number: 21557
Gerrit-PatchSet: 2
Gerrit-Owner: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Reviewer: Daniel Becker <da...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Kurt Deschler <kd...@cloudera.com>
Gerrit-Reviewer: Michael Smith <mi...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Fri, 28 Jun 2024 21:43:12 +0000
Gerrit-HasComments: Yes
[Impala-ASF-CR] IMPALA-13088: Use RoaringBitmap instead of sorted vector of int64s
Posted by "Zoltan Borok-Nagy (Code Review)" <ge...@cloudera.org>.
Hello Daniel Becker, Kurt Deschler, Michael Smith, Impala Public Jenkins,
I'd like you to reexamine a change. Please visit
http://gerrit.cloudera.org:8080/21557
to look at the new patch set (#3).
Change subject: IMPALA-13088: Use RoaringBitmap instead of sorted vector of int64s
......................................................................
IMPALA-13088: Use RoaringBitmap instead of sorted vector of int64s
This patch substitutes the sorted 64-bit integer vectors that we
use in IcebergDeleteNode to 64-bit roaring bitmaps. We use the
CRoaring library (version 4.0.0). CRoaring also offers C++ classes,
but this patch adds its own thin C++ wrapper class around the C
functions to get the best performance.
Performance
I used an extended version of the "One Trillion Row" challenge. This
means after inserting 1 Trillion records to a table I also deleted /
updated lots of records. So at the end I had 1 Trillion data records
and ~68.5 Billion delete records in the table.
For the measurements I used clusters with 10 and 40 executors, and
executed the following query:
SELECT station, min(measure), max(measure), avg(measure)
FROM measurements_extra_1trc_partitioned
GROUP BY 1
ORDER BY 1;
JOIN BUILD times:
+----------------+--------------+--------------+
| Implementation | 10 executors | 40 executors |
+----------------+--------------+--------------+
| Sorted vectors | CRASH | 4m15s |
| Roaring bitmap | 6m35s | 1m51s |
+----------------+--------------+--------------+
10 executors cluster with sorted vectors failed to run the query because
executors crashed due to out-of-memory.
Memory usage (VmRSS) for 10 executors:
+----------------+------------------------+
| Implementation | 10 executors |
+----------------+------------------------+
| Sorted vectors | 54.4 GB (before CRASH) |
| Roaring bitmap | 7.4 GB |
+----------------+------------------------+
Testing:
* added tests for RoaringBitmap64
Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
---
M be/src/exec/iceberg-delete-builder.cc
M be/src/exec/iceberg-delete-builder.h
M be/src/exec/iceberg-delete-node.cc
M be/src/exec/iceberg-delete-node.h
A be/src/thirdparty/roaring/LICENSE
A be/src/thirdparty/roaring/README.md
A be/src/thirdparty/roaring/roaring.c
A be/src/thirdparty/roaring/roaring.h
M be/src/util/CMakeLists.txt
A be/src/util/roaring-bitmap-test.cc
A be/src/util/roaring-bitmap.h
M bin/rat_exclude_files.txt
12 files changed, 29,399 insertions(+), 203 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/Impala-ASF refs/changes/57/21557/3
--
To view, visit http://gerrit.cloudera.org:8080/21557
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
Gerrit-Change-Number: 21557
Gerrit-PatchSet: 3
Gerrit-Owner: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Reviewer: Daniel Becker <da...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Kurt Deschler <kd...@cloudera.com>
Gerrit-Reviewer: Michael Smith <mi...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
[Impala-ASF-CR] IMPALA-13088: Use RoaringBitmap instead of sorted vector of int64s
Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/21557 )
Change subject: IMPALA-13088: Use RoaringBitmap instead of sorted vector of int64s
......................................................................
Patch Set 3:
Build Failed
https://jenkins.impala.io/job/gerrit-code-review-checks/16451/ : Initial code review checks failed. See linked job for details on the failure.
--
To view, visit http://gerrit.cloudera.org:8080/21557
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
Gerrit-Change-Number: 21557
Gerrit-PatchSet: 3
Gerrit-Owner: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Reviewer: Daniel Becker <da...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Kurt Deschler <kd...@cloudera.com>
Gerrit-Reviewer: Michael Smith <mi...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Mon, 01 Jul 2024 13:16:20 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/21557 )
Change subject: IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
......................................................................
Patch Set 7: Verified-1
Build failed: https://jenkins.impala.io/job/gerrit-verify-dryrun/10773/
--
To view, visit http://gerrit.cloudera.org:8080/21557
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
Gerrit-Change-Number: 21557
Gerrit-PatchSet: 7
Gerrit-Owner: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Reviewer: Daniel Becker <da...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Kurt Deschler <kd...@cloudera.com>
Gerrit-Reviewer: Michael Smith <mi...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Wed, 03 Jul 2024 00:56:50 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/21557 )
Change subject: IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
......................................................................
Patch Set 8: Verified+1
--
To view, visit http://gerrit.cloudera.org:8080/21557
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
Gerrit-Change-Number: 21557
Gerrit-PatchSet: 8
Gerrit-Owner: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Reviewer: Daniel Becker <da...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Kurt Deschler <kd...@cloudera.com>
Gerrit-Reviewer: Michael Smith <mi...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Wed, 03 Jul 2024 19:16:27 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/21557 )
Change subject: IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
......................................................................
Patch Set 8:
Build started: https://jenkins.impala.io/job/gerrit-verify-dryrun/10776/ DRY_RUN=true
--
To view, visit http://gerrit.cloudera.org:8080/21557
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
Gerrit-Change-Number: 21557
Gerrit-PatchSet: 8
Gerrit-Owner: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Reviewer: Daniel Becker <da...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Kurt Deschler <kd...@cloudera.com>
Gerrit-Reviewer: Michael Smith <mi...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Wed, 03 Jul 2024 14:04:46 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
Posted by "Michael Smith (Code Review)" <ge...@cloudera.org>.
Michael Smith has posted comments on this change. ( http://gerrit.cloudera.org:8080/21557 )
Change subject: IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
......................................................................
Patch Set 9: Code-Review+1
(1 comment)
http://gerrit.cloudera.org:8080/#/c/21557/2/be/src/util/roaring-bitmap-test.cc
File be/src/util/roaring-bitmap-test.cc:
http://gerrit.cloudera.org:8080/#/c/21557/2/be/src/util/roaring-bitmap-test.cc@33
PS2, Line 33: ASSERT_TRUE(rbm.IsEmpty());
> Done
Ack
--
To view, visit http://gerrit.cloudera.org:8080/21557
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
Gerrit-Change-Number: 21557
Gerrit-PatchSet: 9
Gerrit-Owner: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Reviewer: Csaba Ringhofer <cs...@cloudera.com>
Gerrit-Reviewer: Daniel Becker <da...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Kurt Deschler <kd...@cloudera.com>
Gerrit-Reviewer: Michael Smith <mi...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Tue, 09 Jul 2024 17:36:10 +0000
Gerrit-HasComments: Yes
[Impala-ASF-CR] IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/21557 )
Change subject: IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
......................................................................
Patch Set 9:
Build Successful
https://jenkins.impala.io/job/gerrit-code-review-checks/16472/ : 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/21557
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
Gerrit-Change-Number: 21557
Gerrit-PatchSet: 9
Gerrit-Owner: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Reviewer: Csaba Ringhofer <cs...@cloudera.com>
Gerrit-Reviewer: Daniel Becker <da...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Kurt Deschler <kd...@cloudera.com>
Gerrit-Reviewer: Michael Smith <mi...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Tue, 09 Jul 2024 17:57:54 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/21557 )
Change subject: IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
......................................................................
Patch Set 10:
Build started: https://jenkins.impala.io/job/gerrit-verify-dryrun/10787/ DRY_RUN=true
--
To view, visit http://gerrit.cloudera.org:8080/21557
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
Gerrit-Change-Number: 21557
Gerrit-PatchSet: 10
Gerrit-Owner: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Reviewer: Csaba Ringhofer <cs...@cloudera.com>
Gerrit-Reviewer: Daniel Becker <da...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Kurt Deschler <kd...@cloudera.com>
Gerrit-Reviewer: Michael Smith <mi...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Thu, 11 Jul 2024 17:14:18 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
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/21557 )
Change subject: IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
......................................................................
IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
This patch substitutes the sorted 64-bit integer vectors that we
use in IcebergDeleteNode to 64-bit roaring bitmaps. We use the
CRoaring library (version 4.0.0). CRoaring also offers C++ classes,
but this patch adds its own thin C++ wrapper class around the C
functions to get the best performance.
Toolchain Clang 5.0.1 was not able to compile CRoaring due to a
bug which is tracked by IMPALA-13190, this patch also fixes it
with a new toolchain.
Performance
I used an extended version of the "One Trillion Row" challenge. This
means after inserting 1 Trillion records to a table I also deleted /
updated lots of records (see statements at the end). So at the end
I had 1 Trillion data records and ~68.5 Billion delete records in
the table.
For the measurements I used clusters with 10 and 40 executors, and
executed the following query:
SELECT station, min(measure), max(measure), avg(measure)
FROM measurements_extra_1trc_partitioned
GROUP BY 1
ORDER BY 1;
JOIN BUILD times:
+----------------+--------------+--------------+
| Implementation | 10 executors | 40 executors |
+----------------+--------------+--------------+
| Sorted vectors | CRASH | 4m15s |
| Roaring bitmap | 6m35s | 1m51s |
+----------------+--------------+--------------+
10 executors cluster with sorted vectors failed to run the query because
executors crashed due to out-of-memory.
Memory usage (VmRSS) for 10 executors:
+----------------+------------------------+
| Implementation | 10 executors |
+----------------+------------------------+
| Sorted vectors | 54.4 GB (before CRASH) |
| Roaring bitmap | 7.4 GB |
+----------------+------------------------+
The resource estimations were wrong when MT_DOP was greater than 1. This
has been also fixed.
Testing:
* added tests for RoaringBitmap64
* added tests for resource estimations
Statements I used to delete / update the records for the One Trillion
Row challenge:
create table measurements_extra_1trc_partitioned(
station string, ts timestamp, sensor_type int, measure decimal(5,2))
partitioned by spec (bucket(11, station), day(ts),
truncate(10, sensor_type))
stored as iceberg;
The original challenge didn't have any row-level modifications, columns
'ts' and 'sensor_type' are new:
'ts': timestamps that span a year
'sensor_type': integer between 0 and 100
Both 'ts' and 'sensor_type' has uniform distribution.
Ingested data with the help of the original table One Trillion Row
challenge, then issued the following DML statements:
-- DELETE ~10 Billion
delete from measurements_extra_1trc_partitioned
where sensor_type = 13;
-- UPDATE ~220 Million
update measurements_extra_1trc_partitioned
set measure = cast(measure - 2 as decimal(5,2))
where station in ('Budapest', 'Paris', 'Zurich', 'Kuala Lumpur')
and sensor_type in (7, 17, 77);
-- DELETE ~7.1 Billion
delete from measurements_extra_1trc_partitioned
where ts between '2024-01-15 11:30:00' and '2024-09-10 11:30:00'
and sensor_type between 45 and 51
and station regexp '[ATZ].*';
-- UPDATE ~334 Million
update measurements_extra_1trc_partitioned
set measure = cast(measure + 5 as decimal(5,2))
where station in ('Accra', 'Addis Ababa', 'Entebbe', 'Helsinki',
'Hong Kong', 'Nairobi', 'Ottawa', 'Tauranga', 'Yaounde', 'Zagreb',
'Zurich')
and ts > '2024-11-05 22:30:00'
and sensor_type > 90;
-- DELETE 50.6 Billion
delete from measurements_extra_1trc_partitioned
where
sensor_type between 65 and 77
and ts > '2024-08-11 12:00:00'
;
-- UPDATE ~200 Million
update measurements_extra_1trc_partitioned
set measure = cast(measure + 3.5 as decimal(5,2))
where
sensor_type in (56, 66, 76, 86, 96)
and ts < '2024-03-17 01:00:00'
and (station like 'Z%' or station like 'Y%');
Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
Reviewed-on: http://gerrit.cloudera.org:8080/21557
Reviewed-by: Impala Public Jenkins <im...@cloudera.com>
Tested-by: Impala Public Jenkins <im...@cloudera.com>
---
M LICENSE.txt
M be/src/exec/iceberg-delete-builder.cc
M be/src/exec/iceberg-delete-builder.h
M be/src/exec/iceberg-delete-node.cc
M be/src/exec/iceberg-delete-node.h
A be/src/thirdparty/roaring/LICENSE
A be/src/thirdparty/roaring/README.md
A be/src/thirdparty/roaring/roaring.c
A be/src/thirdparty/roaring/roaring.h
M be/src/util/CMakeLists.txt
A be/src/util/roaring-bitmap-test.cc
A be/src/util/roaring-bitmap.h
M bin/impala-config.sh
M bin/rat_exclude_files.txt
M fe/src/main/java/org/apache/impala/planner/IcebergDeleteNode.java
M fe/src/test/java/org/apache/impala/planner/PlannerTest.java
A testdata/workloads/functional-planner/queries/PlannerTest/iceberg-v2-tables-resources.test
A testdata/workloads/functional-query/queries/QueryTest/iceberg-query-v2.test
M testdata/workloads/functional-query/queries/QueryTest/iceberg-query.test
M tests/query_test/test_scanners.py
20 files changed, 33,182 insertions(+), 273 deletions(-)
Approvals:
Impala Public Jenkins: Looks good to me, approved; Verified
--
To view, visit http://gerrit.cloudera.org:8080/21557
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: merged
Gerrit-Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
Gerrit-Change-Number: 21557
Gerrit-PatchSet: 12
Gerrit-Owner: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Reviewer: Csaba Ringhofer <cs...@cloudera.com>
Gerrit-Reviewer: Daniel Becker <da...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Kurt Deschler <kd...@cloudera.com>
Gerrit-Reviewer: Michael Smith <mi...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
[Impala-ASF-CR] IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/21557 )
Change subject: IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
......................................................................
Patch Set 10:
Build Successful
https://jenkins.impala.io/job/gerrit-code-review-checks/16495/ : 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/21557
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
Gerrit-Change-Number: 21557
Gerrit-PatchSet: 10
Gerrit-Owner: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Reviewer: Csaba Ringhofer <cs...@cloudera.com>
Gerrit-Reviewer: Daniel Becker <da...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Kurt Deschler <kd...@cloudera.com>
Gerrit-Reviewer: Michael Smith <mi...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Thu, 11 Jul 2024 17:24:00 +0000
Gerrit-HasComments: No
[Impala-ASF-CR] IMPALA-13088: Use RoaringBitmap instead of sorted vector of int64s
Posted by "Michael Smith (Code Review)" <ge...@cloudera.org>.
Michael Smith has posted comments on this change. ( http://gerrit.cloudera.org:8080/21557 )
Change subject: IMPALA-13088: Use RoaringBitmap instead of sorted vector of int64s
......................................................................
Patch Set 1:
(2 comments)
http://gerrit.cloudera.org:8080/#/c/21557/1//COMMIT_MSG
Commit Message:
http://gerrit.cloudera.org:8080/#/c/21557/1//COMMIT_MSG@11
PS1, Line 11: CRoaring library, but this patch also adds a thin C++ wrapper around
Please mention what release we're using.
http://gerrit.cloudera.org:8080/#/c/21557/1/be/src/thirdparty/roaring/README.md
File be/src/thirdparty/roaring/README.md:
http://gerrit.cloudera.org:8080/#/c/21557/1/be/src/thirdparty/roaring/README.md@29
PS1, Line 29: So one just need to download the amalgamated files and override the
Can we include a link where to find the CRoaring library?
--
To view, visit http://gerrit.cloudera.org:8080/21557
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
Gerrit-Change-Number: 21557
Gerrit-PatchSet: 1
Gerrit-Owner: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Kurt Deschler <kd...@cloudera.com>
Gerrit-Reviewer: Michael Smith <mi...@cloudera.com>
Gerrit-Comment-Date: Wed, 26 Jun 2024 15:10:53 +0000
Gerrit-HasComments: Yes
[Impala-ASF-CR] IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/21557 )
Change subject: IMPALA-13088, IMPALA-13109: Use RoaringBitmap instead of sorted vector of int64s
......................................................................
Patch Set 7:
Build Successful
https://jenkins.impala.io/job/gerrit-code-review-checks/16461/ : 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/21557
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib769965d094149e99c43e0044914d9ecccc76107
Gerrit-Change-Number: 21557
Gerrit-PatchSet: 7
Gerrit-Owner: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Reviewer: Daniel Becker <da...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Kurt Deschler <kd...@cloudera.com>
Gerrit-Reviewer: Michael Smith <mi...@cloudera.com>
Gerrit-Reviewer: Zoltan Borok-Nagy <bo...@cloudera.com>
Gerrit-Comment-Date: Tue, 02 Jul 2024 17:45:46 +0000
Gerrit-HasComments: No