NumericIndexedVector: compressed aggregations & point-wise operations on sparse vectors by FriendLey · Pull Request #74193 · ClickHouse/ClickHouse

FriendLey · 2025-01-05T08:01:16Z

Changelog category (leave one):

New Feature

Changelog entry (a user-readable short description of the changes that goes to CHANGELOG.md):

NumericIndexedVector: new vector data-structure backed by bit-sliced, Roaring-bitmap compression, together with more than 20 functions for building, analysing and point-wise arithmetic. Can cut storage and speed up joins, filters and aggregations on sparse data. Implements #70582 and “Large-Scale Metric Computation in Online Controlled Experiment Platform” paper by T. Xiong and Y. Wang from VLDB 2024

Documentation entry for user-facing changes

Documentation is written (mandatory for new features)

CLAassistant · 2025-01-05T08:01:22Z

All committers have signed the CLA.

robot-ch-test-poll2 · 2025-01-05T15:29:38Z

This is an automated comment for commit 44daf19 with description of existing statuses. It's updated for the latest CI running

❌ Click here to open a full report in a separate page

Check name	Description	Status
Fast test	Normally this is the first check that is ran for a PR. It builds ClickHouse and runs most of stateless functional tests, omitting some. If it fails, further checks are not started until it is fixed. Look at the report to see which tests fail, then reproduce the failure locally as described here	❌ failure
Style check	Runs a set of checks to keep the code style clean. If some of tests failed, see the related log from the report	❌ failure

Successful checks

Check name	Description	Status
Docs check	Builds and tests the documentation	✅ success

clickhouse-gh · 2025-02-07T09:35:02Z

Workflow [PR], commit [285a187]

rschu1ze · 2025-02-11T13:14:28Z

Asked @rienath for a review.

rienath · 2025-02-26T16:22:20Z

@FriendLey thanks for the PR! I am currently reading the paper that you linked in the issue. It might take some time to review this, but be sure – I'm on it!

FriendLey · 2025-02-27T07:23:18Z

@FriendLey thanks for the PR! I am currently reading the paper that you linked in the issue. It might take some time to review this, but be sure – I'm on it!

Thanks for the update! I appreciate you taking the time to review it.

clickhouse-gh · 2025-04-01T13:16:21Z

Dear @rienath, this PR hasn't been updated for a while. You will be unassigned. Will you continue working on it? If so, please feel free to reassign yourself.

rienath

Thanks for the great PR! Impressive work overall, and the performance improvements highlighted in the paper are especially exciting!

I’ve reviewed the code thoroughly. Most suggestions focus on improving consistency, clarity, maintainability, and alignment with existing conventions in the codebase. The core logic looks solid, and it's clear a lot of thought went into the implementation.

A few higher-level points to consider:

Performance tests: Since your paper includes benchmarks, it would be fantastic to have those integrated under tests/performance as well. This would help us to quantify the speed ups and track the speed going forward. You can refer to this guide for details.
Documentation: The headers could benefit from additional comments or brief design notes. The PR is quite complicated and the logic isn't always immediately obvious. That will make it easier for others to understand and build on this work.
CI: Looks like a few checks are failing. Could you take a look when you have a moment?

docs/en/sql-reference/functions/numeric-indexed-vector-functions.md

src/AggregateFunctions/AggregateFunctionGroupNumericIndexedVectorData.h

src/AggregateFunctions/AggregateFunctionGroupBitmapData.h

src/AggregateFunctions/AggregateFunctionGroupNumericIndexedVectorData.h

docs/en/sql-reference/functions/numeric-indexed-vector-functions.md

src/AggregateFunctions/AggregateFunctionGroupBitmapData.h

rienath · 2025-04-16T12:02:40Z

Hi @FriendLey @ucasfl! Just a quick check-in, this PR is still on our radar. Are you planning to continue working on it? Let us know if you need any help!

ucasfl · 2025-04-16T16:09:20Z

Hi @FriendLey @ucasfl! Just a quick check-in, this PR is still on our radar. Are you planning to continue working on it? Let us know if you need any help!

Yes, @FriendLey is working on it.

rienath · 2025-05-19T15:41:58Z

Thanks for all the updates so far! Could you please avoid rebasing or force-pushing this branch once review has started? When you rewrite commits mid-review, my comments go stale and I have to review everything again. I really appreciate your help in keeping the review efficient @FriendLey

…ns.md Co-authored-by: Raufs Dunamalijevs <[email protected]>

Co-authored-by: Raufs Dunamalijevs <[email protected]>

… bugfix.

FriendLey · 2025-06-10T12:53:37Z

@rienath I have processed all the new comments. Please review them again when you are free.

src/AggregateFunctions/AggregateFunctionGroupNumericIndexedVector.cpp

rienath · 2025-06-13T09:19:00Z

@FriendLey could you have a look at this converstation?

FriendLey · 2025-06-16T02:46:26Z

@FriendLey could you have a look at this converstation?

@rienath I have corrected the description in the document, please review it when you are free.

rienath · 2025-06-16T09:52:08Z

@FriendLey there is a failing test in CI (03458_numeric_indexed_vector_operations_bit_promote). It looks like the result of numericIndexedVectorToMap(numericIndexedVectorPointwiseDivide(vec_1, 2)) may be undeterministic as the test produces correct result in other runs

FriendLey · 2025-06-16T11:37:50Z

@FriendLey there is a failing test in CI (03458_numeric_indexed_vector_operations_bit_promote). It looks like the result of numericIndexedVectorToMap(numericIndexedVectorPointwiseDivide(vec_1, 2)) may be undeterministic as the test produces correct result in other runs

I am working on this. I guess it is because fraction_bit_num is lost when transferring data from the replica node to the coordinator node in cloud scenario.

clickhouse-gh · 2025-06-17T08:32:48Z

Workflow [PR], commit [1cb079c]

Summary: ❌

job_name	test_name	status
Stateless tests (amd_tsan, 3/3)		failure
	01507_clickhouse_server_start_with_embedded_config	FAIL
Stateless tests (amd_tsan, s3 storage, 1/3)		failure
	02922_server_exit_code	FAIL

FriendLey · 2025-06-17T10:44:40Z

@rienath The failed test has been fixed, please review this pr when you are free.

rienath · 2025-06-17T12:11:24Z

@FriendLey thanks. Indeed, the test is green now. For my interest: how did rhs.isEmpty() check in pointwiseAddInplace(...) fix the issue with the numericIndexedVectorPointwiseDivide(...) function, which does not call the former

FriendLey · 2025-06-17T12:37:52Z

@FriendLey thanks. Indeed, the test is green now. For my interest: how did rhs.isEmpty() check in pointwiseAddInplace(...) fix the issue with the numericIndexedVectorPointwiseDivide(...) function, which does not call the former

@rienath The reason for the test failure is not the division operation, but the process of reading data in the ParallelReplicas scenario. In ParallelReplicas, the original data will be read by multiple replicas and then merged at the coordinator node.

In the default constructor of BSINumericIndexedVector, integer_bit_num and fraction_bit_num are set to 40 and 24 respectively when ValueType is Float64.

When read with ParallelReplicas, assume there are 2 replicas. If the result of one replica is empty, the data transmitted to the coordinator node is:

d1: empty with integer_bit_num = 40 and fraction_bit_num = 24
d2: non-empty, integer_bit_num = 32, fraction_bit_num = 0 (set via parameters)

The problem lies in the order of merge. Because the bit position has promote operation (promoteBitPrecisionInplace
) before merge(actually call pointwiseAddInplace), the result vector fraction_bit_num of d1.merge(d2) and d2.merge(d1) will be different:

d1.merge(d2): fraction_bit_num = 0
d2.merge(d1): fraction_bit_num = 24 (old version)

Different fraction_bit_num results in different results of subsequent operations.

rienath · 2025-06-17T13:40:48Z

Stateless tests (amd_tsan, 3/3) — Failed: 1, Passed: 2627, Skipped: 56

01507_clickhouse_server_start_with_embedded_config

Stateless tests (amd_tsan, s3 storage, 1/3) — Failed: 1, Passed: 2590, Skipped: 123

02922_server_exit_code

Both fail for reasons not related to this PR

@FriendLey thank you for all the work!

hanfei1991 added pr-feature Pull request with new product feature can be tested Allows running workflows for external contributors labels Jan 5, 2025

FriendLey force-pushed the numeric_index_vector branch from 57838ae to 8cfe289 Compare February 7, 2025 09:56

FriendLey marked this pull request as ready for review February 7, 2025 09:57

FriendLey force-pushed the numeric_index_vector branch 4 times, most recently from 52c4f88 to dfbe3e9 Compare February 11, 2025 07:43

ucasfl requested a review from rschu1ze February 11, 2025 12:22

rschu1ze assigned rschu1ze and rienath and unassigned rschu1ze Feb 11, 2025

FriendLey force-pushed the numeric_index_vector branch from 45de950 to 9ba9178 Compare February 17, 2025 07:18

clickhouse-gh bot unassigned rienath Apr 1, 2025

rienath self-assigned this Apr 1, 2025

rienath requested changes Apr 3, 2025

View reviewed changes

FriendLey force-pushed the numeric_index_vector branch 3 times, most recently from 6509696 to a19deda Compare May 17, 2025 03:26

FriendLey force-pushed the numeric_index_vector branch from 15d6cd5 to 09f4e93 Compare May 19, 2025 11:52

FriendLey and others added 4 commits June 9, 2025 16:33

Update docs/en/sql-reference/functions/numeric-indexed-vector-functio…

6722268

…ns.md Co-authored-by: Raufs Dunamalijevs <[email protected]>

Update docs/en/sql-reference/functions/numeric-indexed-vector-functio…

7746d20

…ns.md Co-authored-by: Raufs Dunamalijevs <[email protected]>

Update tests/performance/numeric_indexed_vector.xml

256b401

Co-authored-by: Raufs Dunamalijevs <[email protected]>

update docs & split test to multiple files & remove unused includes &…

88364e6

… bugfix.

FriendLey requested a review from rienath June 10, 2025 12:54

fix check failed.

25ce898

rienath requested changes Jun 11, 2025

View reviewed changes

src/AggregateFunctions/AggregateFunctionGroupNumericIndexedVector.cpp Show resolved Hide resolved

FriendLey requested a review from rienath June 12, 2025 02:30

update doc.

ae9da28

FriendLey added 2 commits June 16, 2025 19:39

add more test for debug.

285a187

fix test error in ParallelReplicas.

1cb079c

rienath enabled auto-merge June 17, 2025 13:41

rienath approved these changes Jun 17, 2025

View reviewed changes

rienath added this pull request to the merge queue Jun 17, 2025

Merged via the queue into ClickHouse:master with commit 8b78e12 Jun 17, 2025
118 of 123 checks passed

robot-ch-test-poll2 added the pr-synced-to-cloud The PR is synced to the cloud repo label Jun 17, 2025

arthurpassos mentioned this pull request Jun 17, 2025

Bug fix + changes in extractKeyValuePairs parsing logic #80657

Merged

1 task

rienath mentioned this pull request Jun 19, 2025

Fix float-to-long conversion overflow in AggregateFunctionGroupNumericIndexedVector.h #82165

Merged

rienath changed the title ~~add logic of numeric index vector, implemented by bsi and bitmap. --issue=#70582~~ NumericIndexedVector: compressed aggregations & point-wise operations on sparse vectors Jun 26, 2025

Conversation

FriendLey commented Jan 5, 2025 • edited by rienath Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Changelog category (leave one):

Changelog entry (a user-readable short description of the changes that goes to CHANGELOG.md):

Documentation entry for user-facing changes

Uh oh!

CLAassistant commented Jan 5, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

robot-ch-test-poll2 commented Jan 5, 2025 • edited by robot-ch-test-poll3 Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

clickhouse-gh bot commented Feb 7, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

rschu1ze commented Feb 11, 2025

Uh oh!

rienath commented Feb 26, 2025

Uh oh!

FriendLey commented Feb 27, 2025

Uh oh!

clickhouse-gh bot commented Apr 1, 2025

Uh oh!

rienath left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

rienath commented Apr 16, 2025

Uh oh!

ucasfl commented Apr 16, 2025

Uh oh!

rienath commented May 19, 2025

Uh oh!

FriendLey commented Jun 10, 2025

Uh oh!

Uh oh!

rienath commented Jun 13, 2025

Uh oh!

FriendLey commented Jun 16, 2025

Uh oh!

rienath commented Jun 16, 2025

Uh oh!

FriendLey commented Jun 16, 2025

Uh oh!

clickhouse-gh bot commented Jun 17, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

FriendLey commented Jun 17, 2025

Uh oh!

rienath commented Jun 17, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

FriendLey commented Jun 17, 2025

Uh oh!

rienath commented Jun 17, 2025

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

7 participants

FriendLey commented Jan 5, 2025 •

edited by rienath

Loading

CLAassistant commented Jan 5, 2025 •

edited

Loading

robot-ch-test-poll2 commented Jan 5, 2025 •

edited by robot-ch-test-poll3

Loading

clickhouse-gh bot commented Feb 7, 2025 •

edited

Loading

clickhouse-gh bot commented Jun 17, 2025 •

edited

Loading

rienath commented Jun 17, 2025 •

edited

Loading