Add `hilbertEncode` and `hilbertDecode` functions by Artemmm91 · Pull Request #60156 · ClickHouse/ClickHouse

Artemmm91 · 2024-02-19T20:30:54Z

Changelog category (leave one):

New Feature

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

Add Hilbert Curve encode and decode functions

https://en.wikipedia.org/wiki/Hilbert_curve
Closes #55520.

Documentation entry for user-facing changes

Documentation is written (mandatory for new features)

Information about CI checks: https://clickhouse.com/docs/en/development/continuous-integration/

CLAassistant · 2024-02-19T20:31:00Z

All committers have signed the CLA.

robot-clickhouse · 2024-02-19T21:35:21Z

This is an automated comment for commit 7977de9 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
CI running	A meta-check that indicates the running CI. Normally, it's in success or pending state. The failed status indicates some problems with the PR	❌ failure
Integration tests	The integration tests report. In parenthesis the package type is given, and in square brackets are the optional part/total tests	❌ failure
Stateless tests	Runs stateless functional tests for ClickHouse binaries built in various configurations -- release, debug, with sanitizers, etc	❌ failure

Successful checks

Check name	Description	Status
A Sync	If it fails, ask a maintainer for help	✅ success
AST fuzzer	Runs randomly generated queries to catch program errors. The build type is optionally given in parenthesis. If it fails, ask a maintainer for help	✅ success
ClickBench	Runs [ClickBench](https://github.com/ClickHouse/ClickBench/) with instant-attach table	✅ success
ClickHouse build check	Builds ClickHouse in various configurations for use in further steps. You have to fix the builds that fail. Build logs often has enough information to fix the error, but you might have to reproduce the failure locally. The cmake options can be found in the build log, grepping for cmake. Use these options and follow the general build process	✅ success
Compatibility check	Checks that clickhouse binary runs on distributions with old libc versions. If it fails, ask a maintainer for help	✅ success
Docker keeper image	The check to build and optionally push the mentioned image to docker hub	✅ success
Docker server image	The check to build and optionally push the mentioned image to docker hub	✅ success
Docs check	Builds and tests the documentation	✅ success
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	✅ success
Flaky tests	Checks if new added or modified tests are flaky by running them repeatedly, in parallel, with more randomization. Functional tests are run 100 times with address sanitizer, and additional randomization of thread scheduling. Integration tests are run up to 10 times. If at least once a new test has failed, or was too long, this check will be red. We don't allow flaky tests, read the doc	✅ success
Install packages	Checks that the built packages are installable in a clear environment	✅ success
Mergeable Check	Checks if all other necessary checks are successful	✅ success
PR Check	There's no description for the check yet, please add it to tests/ci/ci_config.py:CHECK_DESCRIPTIONS	✅ success
Performance Comparison	Measure changes in query performance. The performance test report is described in detail here. In square brackets are the optional part/total tests	✅ success
Stateful tests	Runs stateful functional tests for ClickHouse binaries built in various configurations -- release, debug, with sanitizers, etc	✅ success
Stress test	Runs stateless functional tests concurrently from several clients to detect concurrency-related errors	✅ success
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	✅ success
Unit tests	Runs the unit tests for different release types	✅ success
Upgrade check	Runs stress tests on server version from last release and then tries to upgrade it to the version from the PR. It checks if the new server can successfully startup without any errors, crashes or sanitizer asserts	✅ success

yariks5s · 2024-02-20T13:13:38Z

Hello! Thanks for the pull request! Could you please sign the CLA?

Artemmm91 · 2024-02-22T12:11:56Z

Hello! Thanks for the pull request! Could you please sign the CLA?

Sure, just signed it. And i'm still working on it, think that will finish in the end of this week

…to hilbert-function

Blargian · 2024-03-05T18:10:55Z

@Artemmm91 the documentation team has a project to document all functions. mortonEncode and mortonDecode documentation were missing from the docs but will hopefully be added with 60868. It will be nice to also have it there for your functions as they are closely related :)

Artemmm91 · 2024-03-11T16:50:04Z

@Artemmm91 the documentation team has a project to document all functions. mortonEncode and mortonDecode documentation were missing from the docs but will hopefully be added with 60868. It will be nice to also have it there for your functions as they are closely related :)

Okay, no problem)

yariks5s

For now, it will be good to have some stateless tests that check if we encode and decode values right (examples of tests can be found in /0_stateless/.. as .sql files).

src/Functions/FunctionSpaceFillingCurve.h

yariks5s · 2024-03-19T16:43:08Z

src/Functions/hilbertDecode.h

+namespace DB
+{
+
+namespace HilbertDetails


any specific reason to use HilbertDetails namespace instead of anonymous namespace? (Also in hilbertEncode)

AFAIC it is not recommended to make anonymous namespace in header files

src/Functions/hilbertDecode.h

…to hilbert-function

Artemmm91 · 2024-05-29T09:56:33Z

@yariks5s there are some problems with linking with gtest_hilbert_curve, so i'll make header in which i'll store implementations for 2D and lookup tables and will include it to test and to hilbertEncode.cpp file

Artemmm91 · 2024-05-30T08:08:37Z

@yariks5s Hi! i think i'm ready with PR.

i see that there are some failed checks, but seems they are not correlated with my PR:

Stateful tests failed - 00159_parallel_formatting_json_and_friends_2
Stress test (asan) - DB::Exception: Unknown disk 03008_local_plain_rewritable - some problems with disks
Upgrade check - some problem with settings that i didn't add

Artemmm91 · 2024-05-30T19:47:52Z

Also i'm currently working on index analysis of hilbert function - did this on my local branch, and will make other PR after merging this one

src/Functions/hilbertDecode.cpp

src/Functions/hilbertEncode.cpp

src/Functions/hilbertDecode.cpp

yariks5s · 2024-05-31T17:37:40Z

docs/en/sql-reference/functions/encoding-functions.md

+
+**Example**
+
+If a single argument is provided with a tuple specifying bit shifts, the function shifts the argument left by the specified number of bits.


Generally, the Hilbert curve does not apply to a single argument (because it's generally used for coordinates). We can also mention here that the second argument is considered as zero (please correct me if I'm wrong)

didn't quiet get you, but if you mean that we can state that hilbertEncode(N, 0) = hilbertEncode(N) that's not true

currently i'm adding the case with num_dimensions = 2, but i'm looking forward to also add the case of num_dimensions in [3, 8]. so for the completeness, i think it's good to also have the case num_dimemnsions = 1 (and mathematically speaking, it is a valid case)

UnamedRus · 2025-02-24T14:40:34Z

src/Functions/hilbertEncode2DLUT.h

+        const auto leading_zeros_count = getLeadingZeroBits(x | y);
+        const auto used_bits = std::numeric_limits<UInt64>::digits - leading_zeros_count;
+        if (used_bits > 32)
+            return 0; // hilbert code will be overflowed in this case


Basically, it does mean that it will always return 0 as code, if we will try to use numbers which fit only in UInt64 and not in UInt32 ?

Artemmm91 added 2 commits February 18, 2024 23:07

initial file of hilbertEncode + separate common functions code

99b8999

hilbert encode function added

c13dd9d

qoega added the can be tested Allows running workflows for external contributors label Feb 19, 2024

robot-clickhouse added the pr-feature Pull request with new product feature label Feb 19, 2024

code style + renaming

46e81da

yariks5s self-assigned this Feb 20, 2024

restart CI

9a65f9a

Artemmm91 added 2 commits February 22, 2024 11:14

fixed algorithm + template for steps sizes

1f9b4a7

add unit test

bf6bfcf

Artemmm91 and others added 6 commits February 22, 2024 12:12

Merge branch 'hilbert-function' of github.com:Artemmm91/ClickHouse in…

1a98fd8

…to hilbert-function

refactoring + ut + description + ratio

96f763b

style check

e63e7a4

Merge branch 'hilbert-function' of github.com:Artemmm91/ClickHouse in…

b66c2dd

…to hilbert-function

add hilbert decode

c21d849

style

5fc6020

Artemmm91 changed the title ~~[WIP] Add Hilbert Curve encode and decode functions~~ [WIP] Add hilbertEncode and hilbertDecode functions Feb 23, 2024

reload ci

695ea5f

yariks5s reviewed Mar 19, 2024

View reviewed changes

yariks5s and others added 6 commits March 19, 2024 19:39

"of function" -> "for function"

cf489bd

add bit_step=2 and some tests

6ab2e08

Merge branch 'hilbert-function' of github.com:Artemmm91/ClickHouse in…

0380c67

…to hilbert-function

fix style

3d1074c

Merge remote-tracking branch 'upstream/master'

9f9e2e4

initial file of hilbertEncode + separate common functions code

b2b9f5e

yariks5s and others added 6 commits May 24, 2024 17:28

add explicit conversion for UInt8 in exceptions

ca91a42

Merge branch 'hilbert-function' of github.com:Artemmm91/ClickHouse in…

18c586b

…to hilbert-function

review

ffa0f88

docs added

3f1941d

errors tests added

76898b9

docs upd

d630f34

Artemmm91 changed the title ~~[WIP] Add hilbertEncode and hilbertDecode functions~~ Add hilbertEncode and hilbertDecode functions May 28, 2024

Artemmm91 marked this pull request as ready for review May 28, 2024 18:39

Artemmm91 added 3 commits May 28, 2024 18:47

spellcheck

755a953

fix tests

d215e06

fix tests

4c93898

Artemmm91 added 6 commits May 29, 2024 09:58

fix gtest by adding header with Impl

7897348

hilbert

29c362d

style

d6a1197

fix test

2c4b559

reload ci

c63a010

reload ci

51cdc03

Artemmm91 mentioned this pull request May 30, 2024

Index analysis using Hilbert space-filling curve #64662

Merged

30 tasks

yariks5s approved these changes May 31, 2024

View reviewed changes

Artemmm91 added 2 commits June 1, 2024 09:49

review fixes

789bf13

reload-ci

7977de9

yariks5s added this pull request to the merge queue Jun 3, 2024

Merged via the queue into ClickHouse:master with commit 230fbf7 Jun 3, 2024

robot-clickhouse-ci-2 added the pr-synced-to-cloud The PR is synced to the cloud repo label Jun 3, 2024

alexey-milovidov mentioned this pull request Jun 12, 2024

Try Hilbert curve instead of Morton ClickHouse/reversedns.space#7

Open

UnamedRus reviewed Feb 24, 2025

View reviewed changes


		Example

		If a single argument is provided with a tuple specifying bit shifts, the function shifts the argument left by the specified number of bits.

Conversation

Artemmm91 commented Feb 19, 2024 • edited by Algunenano 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 Feb 19, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

robot-clickhouse commented Feb 19, 2024 • edited by robot-ch-test-poll2 Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

yariks5s commented Feb 20, 2024

Uh oh!

Artemmm91 commented Feb 22, 2024

Uh oh!

Blargian commented Mar 5, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Artemmm91 commented Mar 11, 2024

Uh oh!

yariks5s left a comment • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

yariks5s Mar 19, 2024

Choose a reason for hiding this comment

Uh oh!

Artemmm91 Apr 24, 2024

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Artemmm91 commented May 29, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Artemmm91 commented May 30, 2024

Uh oh!

Artemmm91 commented May 30, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

yariks5s May 31, 2024

Choose a reason for hiding this comment

Uh oh!

Artemmm91 Jun 1, 2024

Choose a reason for hiding this comment

Uh oh!

UnamedRus Feb 24, 2025

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

11 participants

Artemmm91 commented Feb 19, 2024 •

edited by Algunenano

Loading

CLAassistant commented Feb 19, 2024 •

edited

Loading

robot-clickhouse commented Feb 19, 2024 •

edited by robot-ch-test-poll2

Loading

Blargian commented Mar 5, 2024 •

edited

Loading

yariks5s left a comment •

edited

Loading

Artemmm91 commented May 29, 2024 •

edited

Loading

Artemmm91 commented May 30, 2024 •

edited

Loading