You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@hudi.apache.org by "chrevanthreddy (via GitHub)" <gi...@apache.org> on 2026/07/17 16:12:49 UTC
[PR] feat(index): add RaBitQ encoder and multibit-aware scorer contract [hudi]
chrevanthreddy opened a new pull request, #19318:
URL: https://github.com/apache/hudi/pull/19318
### Describe the issue this Pull Request addresses
Resolves #19098 (umbrella: #19094, RFC-109)
Third slice of RFC-109 (Hudi Native Vector Index): the RaBitQ encoder and metric-aware scorer contract with multibit-aware support.
> **Stacked PR.** This branch is stacked on #19310 (options, #19096) and #19317 (schema/payload, #19097). Until those merge, the diff here shows their commits too; the only new commit in this PR is `feat(index): add RaBitQ encoder and multibit-aware scorer contract`. Review/merge order: #19310 β #19317 β this.
### Summary and Changelog
- **`RaBitQEncoder`**: 1-bit and multibit (extended-plane) encoding contract, residual and non-residual encoding, L2/IP query-state preparation, and packed-binary/multibit dot-term scoring primitives. Encoding-version-aware so readers dispatch on the metadata written per generation.
- **`VectorQuantizer`**: quantized-vector container (`QuantizedVector`) and quantizer contract shared by encoder and posting builders.
- **`MetricQueryState`**: metric-aware query rotation/normalization state; enforces metric compatibility explicitly.
- **`RaBitQPlaneKernel` / `VectorQueryPlanes`**: bit-plane scoring kernel (`Long.bitCount`-based inner products) and query-plane representation.
- **`RaBitQByteLutScorer`**: byte-LUT scorer for multibit codes.
- **`RaBitQNeutralFactors` / `RaBitQFactorConfig`**: neutral/rescale factor computation and configuration.
- **Tests (59, all passing)**: `TestRaBitQEncoder` (20), `MetricEstimatorIdentityTest` (14), `TestVectorDistanceMetric` (9), `TestRaBitQNeutralFactors` (6), `TestMetricQueryStateRotation` (5), `TestRaBitQPlaneKernel` (3), `TestRaBitQResidualHypothesis` (1), `TestRaBitQResidualRecall` (1).
### Impact
Additive: new engine-neutral encoder/scorer classes under `hudi-common`. No wiring into existing write/read paths in this PR (that happens in the bootstrap #19099 and read-path #19100 slices). No behavioral change to existing tables.
### Risk Level
low
Pure additive numeric/encoding logic with dedicated unit coverage; nothing references these classes from existing runtime paths yet.
### Documentation Update
Encoder/scorer contracts and the multibit decomposition are documented as class/method Javadoc. User-facing RFC document tracked in #19309.
### Contributor's checklist
- [x] Read through [contributor's guide](https://hudi.apache.org/contribute/how-to-contribute)
- [x] Change Logs and Impact described above
- [x] Necessary doc changes done or have another open PR
- [x] For large changes, please consider breaking it into sub-tasks under an umbrella issue (#19094)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@hudi.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat(index): add RaBitQ encoder and multibit-aware scorer contract [hudi]
Posted by "hudi-agent (via GitHub)" <gi...@apache.org>.
hudi-agent commented on code in PR #19318:
URL: https://github.com/apache/hudi/pull/19318#discussion_r3686694402
##########
hudi-common/src/main/java/org/apache/hudi/metadata/HoodieMetadataPayload.java:
##########
@@ -210,6 +254,7 @@ public class HoodieMetadataPayload implements HoodieRecordPayload<HoodieMetadata
protected HoodieMetadataColumnStats columnStatMetadata = null;
protected HoodieRecordIndexInfo recordIndexMetadata;
protected HoodieSecondaryIndexInfo secondaryIndexMetadata;
+ protected Object vectorIndexMetadata;
Review Comment:
π€ nit: every other metadata payload field has its specific Avro type (`HoodieMetadataBloomFilter`, `HoodieRecordIndexInfo`, `HoodieSecondaryIndexInfo`, β¦), but this one is `Object`. Could you introduce a marker interface (e.g. `HoodieVectorIndexEntry`) that the Avro-generated types implement, or at least use a common base type? As-is, readers have no way to know what concrete types can land here without searching all constructors.
<sub><i>β οΈ AI-generated; verify before applying. React π/π to flag quality.</i></sub>
##########
hudi-common/src/test/java/org/apache/hudi/common/index/vector/MetricEstimatorIdentityTest.java:
##########
@@ -0,0 +1,321 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file for details.
+ */
+
+package org.apache.hudi.common.index.vector;
+
+import org.junit.jupiter.api.Test;
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.EnumSource;
+
+import java.util.Random;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertThrows;
+import static org.junit.jupiter.api.Assertions.assertTrue;
+
+/**
+ * The metric certification suite. Three families:
+ *
+ * <p>IDENTITY: for random (x, c, q), the query-state composition over the NEUTRAL factors
+ * must equal the exact estimator composed in double precision, for both passes and every
+ * metric. This pins encoder and scorer to each other; every silent-recall bug this index
+ * has had (zero factors, folded conventions, sign drift) fails this test.
+ *
+ * <p>BOUND: optimisticRankingDistance must never exceed the estimator-composed distance, and the
+ * true distance must lie within the propagated bound at the calibrated rate. The direction
+ * (rip + errAbs for ALL metrics) is the designated sign-bug site.
+ *
+ * <p>DEGENERATE: the normative special cases compose to EXACT values.
+ *
+ * <p>Codes here are synthetic centered codes built directly from the residual (sign code
+ * c1_i = +-0.5; multibit codeEx from B-bit grid) so the suite tests the FACTOR/COMPOSITION
+ * contract independent of bit-packing; the golden round-trip test (separate) certifies
+ * packing. Together they certify the full path.
+ */
+public class MetricEstimatorIdentityTest {
+
+ private static final int DIM = 96;
+ private static final int TRIALS = 200;
+ private static final int BITS = 4;
Review Comment:
π€ nit: could you rename this to `TestMetricEstimatorIdentity`? Every other test class in this PR and the surrounding package uses the `Test*` prefix convention (`TestRaBitQEncoder`, `TestMetricQueryStateRotation`, etc.) β the `*Test` suffix stands out as an outlier.
<sub><i>β οΈ AI-generated; verify before applying. React π/π to flag quality.</i></sub>
##########
hudi-common/src/main/java/org/apache/hudi/metadata/VectorPostingPrefixRawKey.java:
##########
@@ -0,0 +1,40 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.hudi.metadata;
+
+import lombok.Value;
+
+/**
+ * Raw key prefix for vector posting scans.
+ */
+@Value
+public class VectorPostingPrefixRawKey implements RawKey {
+
+ int generationId;
+ int clusterId;
+ Integer shardId;
+
+ @Override
+ public String encode() {
+ return shardId == null
Review Comment:
π€ nit: the `substring(0, 9)` magic number is duplicated from `HoodieTableMetadataUtil.getVectorIndexPostingPrefix` β could this delegate to that helper, or at least reference a named constant for the cluster-prefix length? It's non-obvious why 9 bytes is the right cut-off here.
<sub><i>β οΈ AI-generated; verify before applying. React π/π to flag quality.</i></sub>
##########
hudi-common/src/main/java/org/apache/hudi/metadata/HoodieMetadataPayload.java:
##########
@@ -253,6 +298,442 @@ protected HoodieMetadataPayload(String key, HoodieSecondaryIndexInfo secondaryIn
this(key, MetadataPartitionType.SECONDARY_INDEX.getRecordType(), null, null, null, null, secondaryIndexMetadata, secondaryIndexMetadata.getIsDeleted());
}
+ protected HoodieMetadataPayload(String key, Object vectorIndexInfo) {
+ this.key = key;
+ this.type = MetadataPartitionType.VECTOR_INDEX.getRecordType();
+ this.vectorIndexMetadata = vectorIndexInfo;
+ this.isDeletedRecord = vectorIndexInfo instanceof HoodieVectorIndexTombstone;
+ }
+
+ /**
+ * Create the generation-one centroid record for the given index partition.
+ */
+ public static HoodieRecord<HoodieMetadataPayload> createVectorIndexCentroidsRecord(
+ ByteBuffer centroidBytes, String partitionPath) {
+ HoodieVectorIndexCentroids centroids = new HoodieVectorIndexCentroids(
+ 0L,
+ ByteBuffer.allocate(0),
+ centroidBytes,
+ ByteBuffer.allocate(0));
+ HoodieMetadataPayload payload = new HoodieMetadataPayload(VectorIndexMetadataKey.centroids(1, 0L, 0), centroids);
+ HoodieKey key = new HoodieKey(VectorIndexMetadataKey.centroids(1, 0L, 0), partitionPath);
+ return new HoodieAvroRecord<>(key, payload);
+ }
+
+ public static HoodieRecord<HoodieMetadataPayload> createVectorIndexCentroidsRecord(
+ int generation,
+ long centroidEpoch,
+ int chunk,
+ ByteBuffer clusterIds,
+ ByteBuffer centroidBytes,
+ ByteBuffer clusterRadii,
+ String partitionPath) {
+ String recordKey = VectorIndexMetadataKey.centroids(generation, centroidEpoch, chunk);
+ HoodieVectorIndexCentroids centroids = new HoodieVectorIndexCentroids(
+ centroidEpoch, clusterIds, centroidBytes, clusterRadii);
+ return new HoodieAvroRecord<>(
+ new HoodieKey(recordKey, partitionPath),
+ new HoodieMetadataPayload(recordKey, centroids));
+ }
+
+ /**
+ * Create the generation-one quantizer metadata record for the given index partition.
+ */
+ public static HoodieRecord<HoodieMetadataPayload> createVectorIndexQuantizerMetadataRecord(
+ String quantizerType,
+ int quantizedCodeBytes,
+ long randomSeed,
+ boolean assumeNormalized,
+ String partitionPath) {
+ return createVectorIndexQuantizerMetadataRecord(
+ quantizerType,
+ quantizedCodeBytes,
+ 1,
+ randomSeed,
+ assumeNormalized,
+ partitionPath);
Review Comment:
π€ nit: this overload accepts `quantizedCodeBytes`, `rabitqBits`, and `assumeNormalized` but silently drops all three when delegating to the lower overload. Could the unused parameters be removed from the signature, or have a comment explaining why they're intentionally ignored? A caller passing a non-default `rabitqBits` here would have no indication their value is discarded.
<sub><i>β οΈ AI-generated; verify before applying. React π/π to flag quality.</i></sub>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@hudi.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat(index): add RaBitQ encoder and multibit-aware scorer contract [hudi]
Posted by "hudi-agent (via GitHub)" <gi...@apache.org>.
hudi-agent commented on code in PR #19318:
URL: https://github.com/apache/hudi/pull/19318#discussion_r3716246606
##########
hudi-common/src/main/java/org/apache/hudi/metadata/VectorPostingPrefixRawKey.java:
##########
@@ -0,0 +1,40 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.hudi.metadata;
+
+import lombok.Value;
+
+/**
+ * Raw key prefix for vector posting scans.
+ */
+@Value
+public class VectorPostingPrefixRawKey implements RawKey {
+
+ int generationId;
+ int clusterId;
+ Integer shardId;
+
+ @Override
+ public String encode() {
+ return shardId == null
+ ? VectorIndexMetadataKey.postingPrefix(generationId, clusterId, 0).substring(0, 9)
Review Comment:
π€ nit: the literal `9` in `.substring(0, 9)` is opaque β could you extract a named constant (e.g. `POSTING_PREFIX_SCAN_LENGTH`) or add a short comment explaining what those 9 bytes cover (generation + cluster id, no shard)? A future developer changing the key layout will have no signal that this number needs updating.
<sub><i>β οΈ AI-generated; verify before applying. React π/π to flag quality.</i></sub>
##########
hudi-common/src/test/java/org/apache/hudi/common/index/vector/TestRaBitQResidualRecall.java:
##########
@@ -0,0 +1,156 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file for details.
+ */
+
+package org.apache.hudi.common.index.vector;
+
+import org.junit.jupiter.api.Test;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+import java.util.Random;
+
+import static org.junit.jupiter.api.Assertions.assertTrue;
+
+/**
+ * End-to-end recall validation of the corrected math path (RFC-109 Β§3 + Β§3), simulating a
+ * re-bootstrap: encodes an IVF-residual multibit index with the new {@link RaBitQNeutralFactors}
+ * (posting-block format 1), scores queries through the rotate-once {@link MetricQueryState} +
+ * {@link RaBitQEncoder#multibitDotTerm} estimator, and measures recall@10 against brute-force exact
+ * L2 truth.
+ *
+ * <p>This is deliberately non-circular: the pass/fail comparison is against exact L2, not against
+ * the estimator itself. It confirms the rotate-once query math and the corrected factors do not
+ * regress candidate-set recall on SIFT-like clustered data.
+ */
+public class TestRaBitQResidualRecall {
+
+ private static final int DIM = 128;
+ private static final int NUM_CLUSTERS = 50;
+ private static final int PER_CLUSTER = 200;
+ private static final int N = NUM_CLUSTERS * PER_CLUSTER; // 10k base vectors
+ private static final int NUM_QUERIES = 100;
+ private static final int K = 10;
+ private static final int BITS = 4;
+ private static final long SEED = 7L;
+
+ @Test
+ public void residualMultibitRecallMeetsFloorOnCorrectedPath() {
+ Random rng = new Random(SEED);
+
+ // SIFT-like clustered, non-negative, large-norm data.
+ float[][] centers = new float[NUM_CLUSTERS][DIM];
+ for (int c = 0; c < NUM_CLUSTERS; c++) {
+ for (int d = 0; d < DIM; d++) {
+ centers[c][d] = 20f + rng.nextFloat() * 160f;
+ }
+ }
+ float[][] data = new float[N][DIM];
+ int[] assign = new int[N];
+ int idx = 0;
+ for (int c = 0; c < NUM_CLUSTERS; c++) {
+ for (int p = 0; p < PER_CLUSTER; p++) {
+ float[] v = new float[DIM];
+ for (int d = 0; d < DIM; d++) {
+ v[d] = Math.max(0f, centers[c][d] + (float) (rng.nextGaussian() * 15.0));
+ }
+ data[idx] = v;
+ assign[idx] = c;
+ idx++;
+ }
+ }
+
+ // Re-bootstrap the residual multibit index with the corrected factors.
+ RaBitQEncoder enc = new RaBitQEncoder(DIM, BITS, 42L, false);
+ QuantizedVector[] codes = new QuantizedVector[N];
+ for (int i = 0; i < N; i++) {
+ codes[i] = enc.encodeResidual(data[i], centers[assign[i]]);
+ }
+ // Confirm the new factor layout is actually being produced.
+ assertTrue(codes[0].rescaleFactor != null && codes[0].additiveFactor != null,
+ "residual multibit encoding must produce neutral factors");
+
+ double recallSum = 0;
+ for (int qi = 0; qi < NUM_QUERIES; qi++) {
+ int c = rng.nextInt(NUM_CLUSTERS);
+ float[] q = new float[DIM];
+ for (int d = 0; d < DIM; d++) {
+ q[d] = Math.max(0f, centers[c][d] + (float) (rng.nextGaussian() * 15.0));
+ }
+ int[] truth = exactTopK(q, data, K);
+
+ // Rotate-once query state; rotate each centroid once (corrected Β§2 path).
+ MetricQueryState state =
+ MetricQueryState.create(VectorDistanceMetric.L2, enc::rotateVector, q, false);
+ MetricQueryState.ClusterQuery[] cqByCluster = new MetricQueryState.ClusterQuery[NUM_CLUSTERS];
+ for (int cc = 0; cc < NUM_CLUSTERS; cc++) {
+ cqByCluster[cc] = state.forRotatedCentroid(state.rotateCentroid(centers[cc]));
+ }
+
+ float[] approx = new float[N];
+ for (int i = 0; i < N; i++) {
+ MetricQueryState.ClusterQuery cq = cqByCluster[assign[i]];
+ float dotTerm = RaBitQEncoder.multibitDotTerm(
+ cq.rotatedQuery, cq.querySum, codes[i].code, codes[i].extendedCode, DIM, BITS);
+ double rip = (codes[i].rescaleFactor == null ? 0.0 : codes[i].rescaleFactor) * (double) dotTerm;
+ float centerRip = codes[i].additiveFactor == null ? 0f : codes[i].additiveFactor;
+ float residualNorm = codes[i].scalar;
+ float vectorNorm = codes[i].vectorNorm == null ? Float.NaN : codes[i].vectorNorm;
+ approx[i] = (float) state.rankingDistance(rip, centerRip, residualNorm, vectorNorm, cq);
+ }
+ recallSum += recall(topKByDist(approx, K), truth);
+ }
+ double recall = recallSum / NUM_QUERIES;
+ System.out.printf("[RFC-109] residual multibit recall@%d (B=%d) = %.3f%n", K, BITS, recall);
+
+ // Floor for 4-bit residual multibit on this easy synthetic corpus (all clusters probed).
+ assertTrue(recall >= 0.85,
+ "corrected-path recall@" + K + " regressed below floor: " + recall);
+ }
+
+ private static float l2sq(float[] a, float[] b) {
+ float s = 0;
+ for (int i = 0; i < a.length; i++) {
+ float d = a[i] - b[i];
+ s += d * d;
+ }
+ return s;
+ }
+
+ private static int[] exactTopK(float[] q, float[][] data, int k) {
+ float[] d = new float[data.length];
Review Comment:
π€ nit: `System.out.printf` in a unit test gets lost or interleaved in CI logs and is inconsistent with how Hudi surfaces diagnostics β have you considered `LOG.debug(...)` or just dropping this line?
<sub><i>β οΈ AI-generated; verify before applying. React π/π to flag quality.</i></sub>
##########
hudi-common/src/main/java/org/apache/hudi/common/index/vector/RaBitQByteLutScorer.java:
##########
@@ -0,0 +1,169 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.hudi.common.index.vector;
+
+import java.nio.ByteBuffer;
+
+/**
+ * Byte-lookup-table posting scorer (RFC-109 Β§3A, fixes 1 and 2).
+ *
+ * <p><b>Exact float-query semantics.</b> This scorer scores the same float rotated (residual)
+ * query used by {@link RaBitQEncoder#dotPackedBinary} and {@link RaBitQEncoder#multibitDotTerm}.
+ * It introduces <em>no</em> query quantization (unlike {@link RaBitQPlaneKernel}, which quantizes
+ * the query to {@code Bq} planes and therefore changes recall math). It only re-associates the
+ * per-dimension sum {@code dot(q, code)} into per-byte partial sums precomputed once per probed
+ * cluster, which lets the scan replace:
+ * <ul>
+ * <li>the pass-1 per-dimension sign loop ({@code dotSignRow}); and</li>
+ * <li>the pass-2 per-survivor {@code copyBuffer(signRow)} + {@code repackExtendedLevels} +
+ * {@code multibitDotTerm} allocation dance</li>
+ * </ul>
+ * with table lookups and zero per-survivor allocation. Results match the scalar path up to
+ * floating-point re-association (byte grouping), never a semantic (quantization) change.
+ *
+ * <p><b>LUT layout.</b> {@code lut[bytePos][pattern]} holds the sum of {@code query[bytePos*8 + b]}
+ * over the set bits {@code b} of {@code pattern}, with padding dimensions ({@code >= dimension})
+ * contributing zero so the byte-grouped sum equals the {@code [0, dimension)} scalar sum. A packed
+ * plane dot is then {@code sum(lut[bytePos][planeByte])} over byte positions β {@code codeRowBytes}
+ * lookups instead of {@code dimension} branchy bit tests (an ~8x op reduction at any dimension).
+ */
+public final class RaBitQByteLutScorer {
+
+ private final double[][] lut; // [codeRowBytes][256]
+ private final int codeRowBytes;
+ private final float querySum;
+
+ private RaBitQByteLutScorer(double[][] lut, int codeRowBytes, float querySum) {
+ this.lut = lut;
+ this.codeRowBytes = codeRowBytes;
+ this.querySum = querySum;
+ }
+
+ /**
+ * Build the per-cluster LUT from the (residual) rotated query. Called at most once per distinct
+ * probed cluster; build cost is {@code codeRowBytes * 256} adds, amortized over the cluster's
+ * posting scan.
+ *
+ * @param rotatedQuery the rotated residual query {@code wRot} (length {@code >= dimension})
+ * @param querySum {@code sum(wRot)}; folded into the pass-1/pass-2 centering terms
+ * @param dimension raw dimension scored (padding dims contribute zero)
+ * @param codeRowBytes long-aligned per-plane row width from the block layout
+ */
+ public static RaBitQByteLutScorer forQuery(float[] rotatedQuery, float querySum,
+ int dimension, int codeRowBytes) {
+ if (rotatedQuery == null || dimension <= 0 || rotatedQuery.length < dimension) {
+ throw new IllegalArgumentException("rotatedQuery must contain every scored dimension");
+ }
+ if (!Float.isFinite(querySum) || codeRowBytes < (dimension + Byte.SIZE - 1) / Byte.SIZE) {
+ throw new IllegalArgumentException("querySum and codeRowBytes must match the scored query");
+ }
+ for (int i = 0; i < dimension; i++) {
+ if (!Float.isFinite(rotatedQuery[i])) {
+ throw new IllegalArgumentException("rotatedQuery contains a non-finite value at dimension " + i);
+ }
+ }
+ double[][] lut = new double[codeRowBytes][256];
+ for (int bytePos = 0; bytePos < codeRowBytes; bytePos++) {
+ int baseDim = bytePos << 3;
+ double[] bitContribution = new double[8];
+ for (int b = 0; b < 8; b++) {
+ int dim = baseDim + b;
+ bitContribution[b] = dim < dimension ? rotatedQuery[dim] : 0.0;
+ }
+ double[] table = lut[bytePos];
+ for (int pattern = 0; pattern < 256; pattern++) {
+ double sum = 0.0;
+ // Ascending bit order mirrors dotSignRow's ascending-dimension accumulation.
+ for (int b = 0; b < 8; b++) {
+ if ((pattern & (1 << b)) != 0) {
+ sum += bitContribution[b];
+ }
+ }
+ table[pattern] = sum;
+ }
+ }
+ return new RaBitQByteLutScorer(lut, codeRowBytes, querySum);
+ }
+
+ /**
+ * Raw packed-plane inner product {@code dot(query, plane)} read directly from a plane buffer at an
+ * absolute byte offset. Equivalent to {@link RaBitQEncoder#dotPackedBinary} for the sign plane.
+ */
+ public double planeDot(ByteBuffer planeBuffer, int offset) {
+ if (planeBuffer == null || offset < 0 || offset > planeBuffer.limit() - codeRowBytes) {
+ throw new IllegalArgumentException("Plane row exceeds the supplied buffer");
+ }
+ double sum = 0.0;
+ for (int bytePos = 0; bytePos < codeRowBytes; bytePos++) {
+ sum += lut[bytePos][planeBuffer.get(offset + bytePos) & 0xFF];
+ }
+ return sum;
+ }
+
+ /**
+ * Pass-1 sign-only score {@code dot(query, sign) - 0.5*sumQuery} (== {@code dotSignRow}). Callers
+ * that also run pass-2 should keep the {@link #planeDot} sign value and reuse it via
+ * {@link #pass1FromDot(double)} and {@link #pass2(double, PostingBlockView, ByteBuffer, int, int, int)}
+ * rather than recomputing the sign dot.
+ */
+ public float pass1(ByteBuffer signBuffer, int signOffset) {
+ return pass1FromDot(planeDot(signBuffer, signOffset));
+ }
+
+ /** Pass-1 score from an already-computed sign-plane dot (see {@link #planeDot}). */
+ public float pass1FromDot(double signDot) {
+ return (float) (signDot + querySum * -0.5f);
+ }
+
+ /**
+ * Pass-2 full multibit dot term, scored directly from the sign plane and extended bit-planes
+ * with no repacking and no per-survivor allocation. Bit-plane decomposition of the centered
+ * code makes this algebraically identical to {@link RaBitQEncoder#multibitDotTerm}:
+ * <pre>
+ * extendedDot = sum_p 2^(exBits-1-p) * dot(query, exPlane_p)
+ * dotTerm = 2^exBits * signDot + extendedDot + sumQuery * -((2^bits - 1)/2)
+ * </pre>
+ *
+ * @param signDot the raw sign-plane dot from {@link #planeDot} (reuse the pass-1 value)
+ * @param view the posting block view (for extended-plane offsets)
+ * @param exBuffer the extended-planes buffer ({@link PostingBlockView#exPlanesBuffer()})
+ * @param vectorIndex the vector ordinal within the block
+ * @param exBits number of extended planes ({@code bits - 1})
+ * @param bits total RaBitQ bits
+ */
+ public float pass2(double signDot, PostingBlockView view, ByteBuffer exBuffer,
+ int vectorIndex, int exBits, int bits) {
+ if (view == null || exBuffer == null || bits < 1 || bits > 8 || exBits != bits - 1) {
+ throw new IllegalArgumentException("Posting view and a consistent 1-8 bit width are required");
+ }
+ if (view.codeRowBytes() != codeRowBytes || view.numExPlanes() != exBits) {
+ throw new IllegalArgumentException("Scorer and posting block layouts do not match");
+ }
+ view.signPlaneOffset(vectorIndex); // validates the vector index before any early return
+ if (exBits <= 0) {
+ return (float) (signDot + querySum * -0.5f);
+ }
+ double extendedDot = 0.0;
+ for (int p = 0; p < exBits; p++) {
+ extendedDot += (double) (1L << (exBits - 1 - p)) * planeDot(exBuffer, view.exPlaneOffset(vectorIndex, p));
Review Comment:
π€ This weights extended plane `p` by `2^(exBits-1-p)` (plane 0 = MSB), but `RaBitQPlaneKernel.scorePass2` weights plane `b` by `2^b` (plane 0 = LSB). Both docs claim to reconstruct the same centered code as `multibitDotTerm`. Could you confirm the posting-block `exPlanes` writer and the `long[][]` plane writer really emit opposite bit orderings? If a single repack ever feeds both with the same plane index, one path would silently return wrong scores.
<sub><i>β οΈ AI-generated; verify before applying. React π/π to flag quality.</i></sub>
##########
hudi-common/src/main/java/org/apache/hudi/metadata/HoodieMetadataPayload.java:
##########
@@ -253,6 +300,410 @@ protected HoodieMetadataPayload(String key, HoodieSecondaryIndexInfo secondaryIn
this(key, MetadataPartitionType.SECONDARY_INDEX.getRecordType(), null, null, null, null, secondaryIndexMetadata, secondaryIndexMetadata.getIsDeleted());
}
+ protected HoodieMetadataPayload(String key, Object vectorIndexInfo) {
+ this.key = key;
+ this.type = MetadataPartitionType.VECTOR_INDEX.getRecordType();
+ this.vectorIndexMetadata = vectorIndexInfo;
+ this.isDeletedRecord = vectorIndexInfo instanceof HoodieVectorIndexTombstone;
+ }
+
+ /**
+ * Create the singleton reader-visible generation pointer.
+ */
+ public static HoodieRecord<HoodieMetadataPayload> createVectorIndexActiveManifestRecord(
+ Integer activeGeneration, String metadataPartitionPath) {
+ String recordKey = VectorIndexMetadataKey.activeManifest();
+ HoodieVectorIndexActiveManifest manifest = new HoodieVectorIndexActiveManifest(1, activeGeneration);
+ return new HoodieAvroRecord<>(
+ new HoodieKey(recordKey, metadataPartitionPath),
+ new HoodieMetadataPayload(recordKey, manifest));
+ }
+
+ /**
+ * Create the generation-one centroid record for the given index partition.
+ */
+ public static HoodieRecord<HoodieMetadataPayload> createVectorIndexCentroidsRecord(
+ ByteBuffer centroidBytes, String partitionPath) {
+ HoodieVectorIndexCentroids centroids = new HoodieVectorIndexCentroids(
+ ByteBuffer.allocate(0),
+ centroidBytes,
+ ByteBuffer.allocate(0));
+ String recordKey = VectorIndexMetadataKey.centroids(1, 0);
+ HoodieMetadataPayload payload = new HoodieMetadataPayload(recordKey, centroids);
+ HoodieKey key = new HoodieKey(recordKey, partitionPath);
+ return new HoodieAvroRecord<>(key, payload);
+ }
+
+ public static HoodieRecord<HoodieMetadataPayload> createVectorIndexCentroidsRecord(
+ int generation,
+ int chunk,
+ ByteBuffer clusterIds,
+ ByteBuffer centroidBytes,
+ ByteBuffer clusterRadii,
+ String partitionPath) {
+ String recordKey = VectorIndexMetadataKey.centroids(generation, chunk);
+ HoodieVectorIndexCentroids centroids = new HoodieVectorIndexCentroids(
+ clusterIds, centroidBytes, clusterRadii);
+ return new HoodieAvroRecord<>(
+ new HoodieKey(recordKey, partitionPath),
+ new HoodieMetadataPayload(recordKey, centroids));
+ }
+
+ /**
+ * Create the generation-one quantizer metadata record for the given index partition.
+ */
+ public static HoodieRecord<HoodieMetadataPayload> createVectorIndexQuantizerMetadataRecord(
+ String quantizerType,
+ int quantizedCodeBytes,
+ long randomSeed,
+ boolean assumeNormalized,
+ String partitionPath) {
+ return createVectorIndexQuantizerMetadataRecord(
+ quantizerType,
+ quantizedCodeBytes,
+ 1,
+ randomSeed,
+ assumeNormalized,
+ partitionPath);
+ }
+
+ public static HoodieRecord<HoodieMetadataPayload> createVectorIndexQuantizerMetadataRecord(
+ String quantizerType,
+ int quantizedCodeBytes,
+ int rabitqBits,
+ long randomSeed,
+ boolean assumeNormalized,
+ String partitionPath) {
+ return createVectorIndexQuantizerMetadataRecord(1, 0, quantizerType, randomSeed, null, partitionPath);
+ }
+
+ public static HoodieRecord<HoodieMetadataPayload> createVectorIndexQuantizerMetadataRecord(
Review Comment:
π€ nit: `createVectorIndexManifestRecord` has ~30 parameters, which makes call sites very hard to read and maintain. Have you considered introducing a `VectorIndexManifestSpec` value object (or a builder) to carry these fields? Even grouping the factor-config params (`kappa`, `gMin`, `eps1Max`, `epsNRel`) into the existing `RaBitQFactorConfig` would meaningfully reduce the arity here.
<sub><i>β οΈ AI-generated; verify before applying. React π/π to flag quality.</i></sub>
##########
hudi-common/src/main/java/org/apache/hudi/metadata/HoodieMetadataPayload.java:
##########
@@ -253,6 +300,410 @@ protected HoodieMetadataPayload(String key, HoodieSecondaryIndexInfo secondaryIn
this(key, MetadataPartitionType.SECONDARY_INDEX.getRecordType(), null, null, null, null, secondaryIndexMetadata, secondaryIndexMetadata.getIsDeleted());
}
+ protected HoodieMetadataPayload(String key, Object vectorIndexInfo) {
+ this.key = key;
+ this.type = MetadataPartitionType.VECTOR_INDEX.getRecordType();
+ this.vectorIndexMetadata = vectorIndexInfo;
+ this.isDeletedRecord = vectorIndexInfo instanceof HoodieVectorIndexTombstone;
+ }
+
+ /**
+ * Create the singleton reader-visible generation pointer.
+ */
+ public static HoodieRecord<HoodieMetadataPayload> createVectorIndexActiveManifestRecord(
+ Integer activeGeneration, String metadataPartitionPath) {
+ String recordKey = VectorIndexMetadataKey.activeManifest();
+ HoodieVectorIndexActiveManifest manifest = new HoodieVectorIndexActiveManifest(1, activeGeneration);
+ return new HoodieAvroRecord<>(
+ new HoodieKey(recordKey, metadataPartitionPath),
+ new HoodieMetadataPayload(recordKey, manifest));
+ }
+
+ /**
+ * Create the generation-one centroid record for the given index partition.
+ */
+ public static HoodieRecord<HoodieMetadataPayload> createVectorIndexCentroidsRecord(
+ ByteBuffer centroidBytes, String partitionPath) {
+ HoodieVectorIndexCentroids centroids = new HoodieVectorIndexCentroids(
+ ByteBuffer.allocate(0),
+ centroidBytes,
+ ByteBuffer.allocate(0));
+ String recordKey = VectorIndexMetadataKey.centroids(1, 0);
+ HoodieMetadataPayload payload = new HoodieMetadataPayload(recordKey, centroids);
+ HoodieKey key = new HoodieKey(recordKey, partitionPath);
+ return new HoodieAvroRecord<>(key, payload);
+ }
+
+ public static HoodieRecord<HoodieMetadataPayload> createVectorIndexCentroidsRecord(
+ int generation,
+ int chunk,
+ ByteBuffer clusterIds,
+ ByteBuffer centroidBytes,
+ ByteBuffer clusterRadii,
+ String partitionPath) {
+ String recordKey = VectorIndexMetadataKey.centroids(generation, chunk);
+ HoodieVectorIndexCentroids centroids = new HoodieVectorIndexCentroids(
+ clusterIds, centroidBytes, clusterRadii);
+ return new HoodieAvroRecord<>(
+ new HoodieKey(recordKey, partitionPath),
+ new HoodieMetadataPayload(recordKey, centroids));
+ }
+
+ /**
+ * Create the generation-one quantizer metadata record for the given index partition.
+ */
+ public static HoodieRecord<HoodieMetadataPayload> createVectorIndexQuantizerMetadataRecord(
+ String quantizerType,
+ int quantizedCodeBytes,
+ long randomSeed,
+ boolean assumeNormalized,
+ String partitionPath) {
+ return createVectorIndexQuantizerMetadataRecord(
+ quantizerType,
+ quantizedCodeBytes,
+ 1,
+ randomSeed,
+ assumeNormalized,
+ partitionPath);
+ }
+
+ public static HoodieRecord<HoodieMetadataPayload> createVectorIndexQuantizerMetadataRecord(
+ String quantizerType,
+ int quantizedCodeBytes,
+ int rabitqBits,
+ long randomSeed,
+ boolean assumeNormalized,
+ String partitionPath) {
+ return createVectorIndexQuantizerMetadataRecord(1, 0, quantizerType, randomSeed, null, partitionPath);
+ }
+
+ public static HoodieRecord<HoodieMetadataPayload> createVectorIndexQuantizerMetadataRecord(
+ int generation,
+ int chunk,
+ String quantizerType,
+ long randomSeed,
+ ByteBuffer rotationBytes,
+ String partitionPath) {
+ String recordKey = VectorIndexMetadataKey.quantizer(generation, chunk);
+ HoodieVectorIndexQuantizer quantizer = new HoodieVectorIndexQuantizer(quantizerType, randomSeed, rotationBytes);
+ return new HoodieAvroRecord<>(
+ new HoodieKey(recordKey, partitionPath),
+ new HoodieMetadataPayload(recordKey, quantizer));
+ }
+
+ public static HoodieRecord<HoodieMetadataPayload> createVectorIndexManifestRecord(
+ int generation,
+ String generationOrdinalText,
+ String state,
+ int dim,
+ int dimPadded,
+ int codeRowBytes,
+ int bitsTotal,
+ int numExPlanes,
+ int numClusters,
+ int shardCount,
+ int fileGroupCount,
+ String metric,
+ boolean assumeNormalized,
+ boolean residualEncoding,
+ String vectorColumn,
+ int targetBlockBytes,
+ int vectorsPerBlock,
+ int blockFormatVersion,
+ int factorVersion,
+ double kappa,
+ double gMin,
+ double eps1Max,
+ double epsNRel,
+ int centroidChunkCount,
+ String centroidChecksum,
+ int splitLimit,
+ int mergeFloor,
+ String bootstrapInstant,
+ String verifiedFrontier,
+ long createdTs,
+ String metadataPartitionPath) {
+ String recordKey = VectorIndexMetadataKey.manifest(generation);
+ HoodieVectorIndexManifest manifest = new HoodieVectorIndexManifest(
+ 1,
+ generationOrdinalText,
+ state,
+ dim,
+ dimPadded,
+ codeRowBytes,
+ bitsTotal,
+ numExPlanes,
+ numClusters,
+ shardCount,
+ fileGroupCount,
+ metric,
+ assumeNormalized,
+ residualEncoding,
+ vectorColumn == null ? "" : vectorColumn,
+ targetBlockBytes,
+ vectorsPerBlock,
+ blockFormatVersion,
+ factorVersion,
+ kappa,
+ gMin,
+ eps1Max,
+ epsNRel,
+ centroidChunkCount,
+ centroidChecksum,
+ splitLimit,
+ mergeFloor,
+ bootstrapInstant,
+ verifiedFrontier,
+ createdTs);
+ return new HoodieAvroRecord<>(
+ new HoodieKey(recordKey, metadataPartitionPath),
+ new HoodieMetadataPayload(recordKey, manifest));
+ }
+
+ public static HoodieRecord<HoodieMetadataPayload> createVectorIndexClusterManifestRecord(
+ int generation,
+ int clusterId,
+ int shardCount,
+ Collection<String> fileGroupIds,
+ long vectorCount,
+ long lastUpdatedTs,
+ String metadataPartitionPath) {
+ return createVectorIndexClusterManifestRecord(
+ generation, clusterId, 0, shardCount, fileGroupIds, vectorCount, lastUpdatedTs, metadataPartitionPath);
+ }
+
+ public static HoodieRecord<HoodieMetadataPayload> createVectorIndexClusterManifestRecord(
+ int generation,
+ int clusterId,
+ int routingVersion,
+ int shardCount,
+ Collection<String> fileGroupIds,
+ long vectorCount,
+ long lastUpdatedTs,
+ String metadataPartitionPath) {
+ String recordKey = VectorIndexMetadataKey.clusterStats(generation, clusterId);
+ HoodieVectorIndexClusterStats stats = new HoodieVectorIndexClusterStats(
+ routingVersion,
+ shardCount,
Review Comment:
π€ nit: `fileGroupIds == null ? java.util.Collections.emptyList() : fileGroupIds.stream().collect(Collectors.toList())` β the fully-qualified `java.util.Collections` is unusual (there are imports already), and when `fileGroupIds` is non-null `new ArrayList<>(fileGroupIds)` is simpler and avoids the stream allocation.
<sub><i>β οΈ AI-generated; verify before applying. React π/π to flag quality.</i></sub>
##########
hudi-common/src/main/java/org/apache/hudi/metadata/HoodieMetadataPayload.java:
##########
@@ -253,6 +300,410 @@ protected HoodieMetadataPayload(String key, HoodieSecondaryIndexInfo secondaryIn
this(key, MetadataPartitionType.SECONDARY_INDEX.getRecordType(), null, null, null, null, secondaryIndexMetadata, secondaryIndexMetadata.getIsDeleted());
}
+ protected HoodieMetadataPayload(String key, Object vectorIndexInfo) {
+ this.key = key;
+ this.type = MetadataPartitionType.VECTOR_INDEX.getRecordType();
+ this.vectorIndexMetadata = vectorIndexInfo;
+ this.isDeletedRecord = vectorIndexInfo instanceof HoodieVectorIndexTombstone;
+ }
+
+ /**
+ * Create the singleton reader-visible generation pointer.
+ */
+ public static HoodieRecord<HoodieMetadataPayload> createVectorIndexActiveManifestRecord(
+ Integer activeGeneration, String metadataPartitionPath) {
+ String recordKey = VectorIndexMetadataKey.activeManifest();
+ HoodieVectorIndexActiveManifest manifest = new HoodieVectorIndexActiveManifest(1, activeGeneration);
+ return new HoodieAvroRecord<>(
+ new HoodieKey(recordKey, metadataPartitionPath),
+ new HoodieMetadataPayload(recordKey, manifest));
+ }
+
+ /**
+ * Create the generation-one centroid record for the given index partition.
+ */
+ public static HoodieRecord<HoodieMetadataPayload> createVectorIndexCentroidsRecord(
+ ByteBuffer centroidBytes, String partitionPath) {
+ HoodieVectorIndexCentroids centroids = new HoodieVectorIndexCentroids(
+ ByteBuffer.allocate(0),
+ centroidBytes,
+ ByteBuffer.allocate(0));
+ String recordKey = VectorIndexMetadataKey.centroids(1, 0);
+ HoodieMetadataPayload payload = new HoodieMetadataPayload(recordKey, centroids);
+ HoodieKey key = new HoodieKey(recordKey, partitionPath);
+ return new HoodieAvroRecord<>(key, payload);
+ }
+
+ public static HoodieRecord<HoodieMetadataPayload> createVectorIndexCentroidsRecord(
+ int generation,
+ int chunk,
+ ByteBuffer clusterIds,
+ ByteBuffer centroidBytes,
+ ByteBuffer clusterRadii,
+ String partitionPath) {
+ String recordKey = VectorIndexMetadataKey.centroids(generation, chunk);
+ HoodieVectorIndexCentroids centroids = new HoodieVectorIndexCentroids(
+ clusterIds, centroidBytes, clusterRadii);
+ return new HoodieAvroRecord<>(
+ new HoodieKey(recordKey, partitionPath),
+ new HoodieMetadataPayload(recordKey, centroids));
+ }
+
+ /**
+ * Create the generation-one quantizer metadata record for the given index partition.
+ */
+ public static HoodieRecord<HoodieMetadataPayload> createVectorIndexQuantizerMetadataRecord(
+ String quantizerType,
+ int quantizedCodeBytes,
+ long randomSeed,
+ boolean assumeNormalized,
+ String partitionPath) {
+ return createVectorIndexQuantizerMetadataRecord(
+ quantizerType,
+ quantizedCodeBytes,
+ 1,
Review Comment:
π€ nit: the 6-param overload accepts `quantizedCodeBytes` and `rabitqBits` but then silently ignores both and delegates to the 3-param version β could you either use those arguments (pass `rabitqBits` instead of `1`) or remove the overload entirely? A caller who passes a custom `bits` value will be surprised to find their setting discarded.
<sub><i>β οΈ AI-generated; verify before applying. React π/π to flag quality.</i></sub>
##########
hudi-common/src/main/java/org/apache/hudi/common/index/vector/PostingBlockBuilder.java:
##########
@@ -0,0 +1,346 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.hudi.common.index.vector;
+
+import org.apache.hudi.avro.model.HoodieVectorIndexPostingBlock;
+
+import java.nio.ByteBuffer;
+import java.nio.ByteOrder;
+import java.nio.charset.StandardCharsets;
+import java.util.ArrayList;
+import java.util.LinkedHashMap;
+import java.util.List;
+import java.util.Map;
+
+import static org.apache.hudi.common.util.ValidationUtils.checkArgument;
+
+/**
+ * Streaming-friendly builder for one immutable vector posting block.
+ */
+public final class PostingBlockBuilder {
+
+ public static final int BLOCK_FORMAT_VERSION = 1;
+ public static final int SCALAR_FACTOR_COUNT = 6;
+ public static final int SCALAR_FACTOR_COUNT_WITH_VECTOR_NORM = 7;
+ public static final int ROW_LOCATOR_BYTES = 8;
+
+ private final int codeRowBytes;
+ private final int numExPlanes;
+ private final boolean includeVectorNorm;
+ private final List<Row> rows = new ArrayList<>();
+ private final Map<String, Integer> fileGroupDict = new LinkedHashMap<>();
+ private final Map<String, Integer> instantTimeDict = new LinkedHashMap<>();
+ private final List<String> partitionDict = new ArrayList<>();
+
+ public PostingBlockBuilder(int codeRowBytes, int numExPlanes) {
+ this(codeRowBytes, numExPlanes, false);
+ }
+
+ public PostingBlockBuilder(int codeRowBytes, int numExPlanes, boolean includeVectorNorm) {
+ checkArgument(codeRowBytes > 0 && codeRowBytes % Long.BYTES == 0,
+ "codeRowBytes must be positive and long-aligned: " + codeRowBytes);
+ checkArgument(numExPlanes >= 0, "numExPlanes must be non-negative: " + numExPlanes);
+ this.codeRowBytes = codeRowBytes;
+ this.numExPlanes = numExPlanes;
+ this.includeVectorNorm = includeVectorNorm;
+ }
+
+ public PostingBlockBuilder addRow(String recordKey,
+ byte[] signPlane,
+ byte[] exPlanes,
+ float fAdd1,
+ float fRescale1,
+ float err1,
+ float fAddEx,
+ float fRescaleEx,
+ float residualNorm,
+ String fileGroupId,
+ String instantTime,
+ String partitionPath,
+ long rowPosition) {
+ return addRow(
+ recordKey,
+ signPlane,
+ exPlanes,
+ fAdd1,
+ fRescale1,
+ err1,
+ fAddEx,
+ fRescaleEx,
+ residualNorm,
+ null,
+ fileGroupId,
+ instantTime,
+ partitionPath,
+ rowPosition);
+ }
+
+ public PostingBlockBuilder addRow(String recordKey,
Review Comment:
π€ nit: the 14-parameter `addRow` overload is hard to call without a named-argument IDE. Have you considered introducing a small `RowSpec` (or builder) to bundle the scalar factors and location fields? Even just grouping the six scalar floats (`fAdd1`, `fRescale1`, `err1`, `fAddEx`, `fRescaleEx`, `residualNorm`) into an existing type like `QuantizedVector` would cut the arity significantly.
<sub><i>β οΈ AI-generated; verify before applying. React π/π to flag quality.</i></sub>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@hudi.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat(index): add RaBitQ encoder and multibit-aware scorer contract [hudi]
Posted by "voonhous (via GitHub) via commits" <co...@hudi.apache.org>.
voonhous closed pull request #19318: feat(index): add RaBitQ encoder and multibit-aware scorer contract
URL: https://github.com/apache/hudi/pull/19318
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@hudi.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat(index): add RaBitQ encoder and multibit-aware scorer contract [hudi]
Posted by "voonhous (via GitHub) via commits" <co...@hudi.apache.org>.
voonhous commented on PR #19318:
URL: https://github.com/apache/hudi/pull/19318#issuecomment-6701207505
Temporarily closing this PR while we debug a GitHub settings error on master (#20471); it will be reopened shortly, no action needed.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@hudi.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat(index): add RaBitQ encoder and multibit-aware scorer contract [hudi]
Posted by "chrevanthreddy (via GitHub)" <gi...@apache.org>.
chrevanthreddy commented on code in PR #19318:
URL: https://github.com/apache/hudi/pull/19318#discussion_r4148951098
##########
hudi-common/src/main/java/org/apache/hudi/common/index/vector/RaBitQEncoder.java:
##########
@@ -0,0 +1,588 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.hudi.common.index.vector;
+
+import java.io.Serializable;
+import java.util.Map;
+import java.util.Objects;
+import java.util.Random;
+import java.util.concurrent.ConcurrentHashMap;
+
+/**
+ * RaBitQ (Randomized Binary Quantization) encoder.
+ *
+ * <p>Encodes float vectors into 1-bit-per-dimension binary codes using a random
+ * orthogonal rotation matrix R. The rotation is deterministic given (seed, dimension),
+ * so R is stored as a seed β it never needs retraining.
+ *
+ * <p><b>Encoding (write path):</b>
+ * <ol>
+ * <li>Normalize: vΜ = v / ||v||</li>
+ * <li>Rotate: v_rot = R @ vΜ</li>
+ * <li>Binarize: code = pack(sign(v_rot)) β D bits β ceil(D/8) bytes</li>
+ * <li>Scalar: s = ||v|| (stored alongside code; 1.0 if assume_normalized)</li>
+ * </ol>
+ *
+ * <p><b>Query scan (read path):</b>
+ * <ol>
+ * <li>Normalize + rotate the query vector (same R)</li>
+ * <li>Binarize to get q_bin</li>
+ * <li>For each database code b: Hamming(q_bin, b) β estimated cosine</li>
+ * <li>Re-rank top-R candidates with exact distance</li>
+ * </ol>
+ *
+ * <p>Memory: the rotation matrix is DΓD floats = 4Β·DΒ² bytes (~2.3 MB at D=768).
+ * It is built lazily on first use and reused across encode calls.
+ *
+ * <p>Thread-safe after the first call to {@link #encode} or {@link #encodeQuery}
+ * (the lazy init is synchronized).
+ */
+public final class RaBitQEncoder implements Serializable {
+ private static final long serialVersionUID = 1L;
+ private static final Map<RotationKey, float[][]> ROTATION_MATRIX_CACHE = new ConcurrentHashMap<>();
+ /** Neutral-factor thresholds for the current posting-block format (RFC-109 Β§3). */
+ private static final RaBitQFactorConfig FACTOR_CONFIG = RaBitQFactorConfig.defaults();
+ private final int dimension;
+ private final int bits;
+ private final long seed;
+ private final boolean assumeNormalized;
+
+ /** Rotation matrix, row-major. Populated lazily. */
+ private transient volatile float[][] rotMat;
+ public RaBitQEncoder(int dimension, long seed, boolean assumeNormalized) {
+ this(dimension, 1, seed, assumeNormalized);
+ }
+
+ public RaBitQEncoder(int dimension, int bits, long seed, boolean assumeNormalized) {
+ if (dimension <= 0) {
+ throw new IllegalArgumentException("Dimension must be positive, got: " + dimension);
+ }
+ if (bits <= 0 || bits > 8) {
+ throw new IllegalArgumentException("RaBitQ bits must be in [1, 8], got: " + bits);
+ }
+ this.dimension = dimension;
+ this.bits = bits;
+ this.seed = seed;
+ this.assumeNormalized = assumeNormalized;
+ }
+
+ /** Convenience constructor using default seed. */
+ public RaBitQEncoder(int dimension) {
+ this(dimension, 1, 42L, false);
+ }
+
+ // ---- encoding ----------------------------------------------------------
+
+ public QuantizedVector encode(float[] vector) {
+ validateVector(vector, "vector");
+ float norm = norm(vector);
+ float scalar = assumeNormalized ? 1.0f : norm;
+ float[] normalized = (norm == 0f || assumeNormalized)
+ ? vector
+ : normalize(vector, norm);
+ float[] rotated = rotate(normalized);
+ return new QuantizedVector(binarize(rotated), scalar);
+ }
+
+ /**
+ * Metric-neutral residual encoding used by MDT postings.
+ *
+ * <p>The optional {@code center} is the IVF centroid in the <b>original</b> vector space.
+ * When null, the vector is encoded relative to the origin.
+ */
+ public QuantizedVector encodeResidual(float[] vector, float[] center) {
+ validateVector(vector, "vector");
+ if (center != null) {
+ validateVector(center, "center");
+ }
+ float[] rotatedVector = rotate(vector);
+ float[] rotatedCenter = center == null ? new float[dimension] : rotate(center);
+ float[] residual = subtract(rotatedVector, rotatedCenter);
+ byte[] binaryCode = binarize(residual);
+
+ float residualNorm = norm(residual);
+ if (residualNorm == 0.0f) {
+ return new QuantizedVector(
+ binaryCode,
+ new byte[extendedCodeBytes()],
+ 0.0f,
+ 0.0f,
+ 0.0f,
+ 0.0f,
+ 0.0f,
+ 0.0f,
+ norm(vector),
+ bits);
+ }
+
+ if (bits <= 1) {
+ double ipResidual1 = 0.0d;
+ for (int i = 0; i < dimension; i++) {
+ ipResidual1 += residual[i] * (residual[i] > 0f ? 0.5d : -0.5d);
+ }
+ RaBitQNeutralFactors.Factors factors = RaBitQNeutralFactors.compute(
+ residual,
+ rotatedCenter,
+ rotatedVector,
+ ipResidual1,
+ ipResidual1,
+ dimension,
+ FACTOR_CONFIG);
+ return new QuantizedVector(
+ binaryCode,
+ new byte[0],
+ factors.residualNorm,
+ factors.centerRip,
+ factors.fRescale1,
+ factors.centerRip,
+ factors.fRescale1,
+ factors.err1,
+ factors.vectorNorm,
+ bits);
+ }
+
+ int exBits = bits - 1;
+
+ float[] absNormalizedResidual = new float[dimension];
+ for (int i = 0; i < dimension; i++) {
+ absNormalizedResidual[i] = Math.abs(residual[i] / residualNorm);
+ }
+
+ QuantizedLevels quantizedLevels = quantizeEx(absNormalizedResidual, exBits);
+ int[] exCode = quantizedLevels.levels;
+ int mask = (1 << exBits) - 1;
+ for (int i = 0; i < dimension; i++) {
+ if (residual[i] < 0f) {
+ exCode[i] = mask - exCode[i];
+ }
+ }
+
+ float cBias = (float) -((1 << exBits) - 0.5d);
+ double ipResidual1 = 0.0d;
+ double ipResidual = 0.0d;
+ for (int i = 0; i < dimension; i++) {
+ boolean positive = residual[i] > 0f;
+ double signOnlyCode = positive ? 0.5d : -0.5d;
+ float centeredCode = exCode[i] + (positive ? (1 << exBits) : 0) + cBias;
+ ipResidual1 += residual[i] * signOnlyCode;
+ ipResidual += residual[i] * centeredCode;
+ }
+
+ RaBitQNeutralFactors.Factors factors = RaBitQNeutralFactors.compute(
+ residual,
+ rotatedCenter,
+ rotatedVector,
+ ipResidual1,
+ ipResidual,
+ dimension,
+ FACTOR_CONFIG);
+ return new QuantizedVector(
+ binaryCode,
+ packUnsignedLevels(exCode, exBits),
+ factors.residualNorm,
+ factors.centerRip,
+ factors.fRescaleEx,
+ factors.centerRip,
+ factors.fRescale1,
+ factors.err1,
+ factors.vectorNorm,
+ bits);
+ }
+
+ /**
+ * Compatibility shim for old call sites. New postings must use the metric-neutral
+ * residual factor convention produced by {@link #encodeResidual(float[], float[])}.
+ */
+ public QuantizedVector encodeForL2(float[] vector, float[] center) {
+ return encodeResidual(vector, center);
+ }
+
+ public RaBitQQueryState encodeQuery(float[] queryVector) {
+ validateVector(queryVector, "query");
+ float norm = norm(queryVector);
+ float[] normalized = norm == 0f ? queryVector : normalize(queryVector, norm);
+ float[] rotated = rotate(normalized);
+ return new RaBitQQueryState(binarize(rotated), rotated, norm);
+ }
+
+ public RaBitQQueryState encodeQueryForL2(float[] queryVector) {
+ validateVector(queryVector, "query");
+ float[] rotated = rotate(queryVector);
+ return new RaBitQQueryState(binarize(rotated), rotated, norm(queryVector));
+ }
+
+ public float estimateDistance(RaBitQQueryState queryState, QuantizedVector encoded) {
+ return RaBitQDistanceScorer.estimateDistance(
+ queryState.binaryCodeUnsafe(), encoded.code, encoded.scalar, dimension);
+ }
+
+ /** Metric-aware approximate distance using symmetric or asymmetric cosine estimation. */
+ public float estimateDistance(RaBitQQueryState queryState,
+ QuantizedVector encoded,
+ VectorDistanceMetric metric,
+ boolean asymmetric) {
+ float cosine = asymmetric
+ ? RaBitQDistanceScorer.asymmetricCosine(queryState.rotatedQueryUnsafe(), encoded.code, dimension)
+ : RaBitQDistanceScorer.symmetricCosine(queryState.binaryCodeUnsafe(), encoded.code, dimension);
+ return RaBitQDistanceScorer.reconstructDistance(
+ metric, cosine, queryState.getQueryNorm(), encoded.scalar);
+ }
+
+ public int codeBytes() {
+ return (dimension + 7) / 8;
+ }
+
+ public int extendedCodeBytes() {
+ return bits <= 1 ? 0 : (dimension * (bits - 1) + 7) / 8;
+ }
+
+ public int totalCodeBytes() {
+ return codeBytes() + extendedCodeBytes();
+ }
+
+ public int getBits() {
+ return bits;
+ }
+
+ // ---- public utilities --------------------------------------------------
+
+ /** L2 norm of a float vector. */
+ public static float norm(float[] v) {
+ double sum = 0.0;
+ for (float x : v) {
+ sum += (double) x * x;
+ }
+ return (float) Math.sqrt(sum);
+ }
+
+ public static float l2Squared(float[] left, float[] right) {
+ double sum = 0.0;
+ for (int i = 0; i < left.length; i++) {
+ double delta = (double) left[i] - right[i];
+ sum += delta * delta;
+ }
+ return (float) sum;
+ }
+
+ public float[] rotateVector(float[] vector) {
+ validateVector(vector, "vector");
+ return rotate(vector);
+ }
+
+ public static float dotPackedBinary(byte[] binaryCode, float[] query, int dimension) {
+ double sum = 0.0;
+ for (int i = 0; i < dimension; i++) {
+ if ((binaryCode[i >> 3] & (1 << (i & 7))) != 0) {
+ sum += query[i];
+ }
+ }
+ return (float) sum;
+ }
+
+ public static float dotPackedUnsigned(byte[] packedLevels, int bitsPerValue, float[] query, int dimension) {
+ if (packedLevels == null || bitsPerValue <= 0) {
+ return 0.0f;
+ }
+ double sum = 0.0;
+ int bitOffset = 0;
+ for (int i = 0; i < dimension; i++) {
+ int value = 0;
+ for (int bit = 0; bit < bitsPerValue; bit++) {
+ int absoluteBit = bitOffset + bit;
+ int byteIndex = absoluteBit >> 3;
+ int bitIndex = absoluteBit & 7;
+ if ((packedLevels[byteIndex] & (1 << bitIndex)) != 0) {
+ value |= (1 << bit);
+ }
+ }
+ sum += (double) value * query[i];
+ bitOffset += bitsPerValue;
+ }
+ return (float) sum;
+ }
+
+ public static float multibitDotTerm(float[] rotatedQuery,
+ float sumQuery,
+ byte[] binaryCode,
+ byte[] extendedCode,
+ int dimension,
+ int bits) {
+ int exBits = bits - 1;
+ float binaryDot = dotPackedBinary(binaryCode, rotatedQuery, dimension);
+ if (exBits <= 0) {
+ return binaryDot + (sumQuery * -0.5f);
+ }
+ float extendedDot = dotPackedUnsigned(extendedCode, exBits, rotatedQuery, dimension);
+ float cBias = (float) -((1 << bits) - 1) / 2.0f;
+ return ((float) (1 << exBits) * binaryDot) + extendedDot + (sumQuery * cBias);
+ }
+
+ public static float multibitDotTerm(float[] rotatedQuery,
+ byte[] binaryCode,
+ byte[] extendedCode,
+ int dimension,
+ int bits) {
+ return multibitDotTerm(rotatedQuery, sum(rotatedQuery), binaryCode, extendedCode, dimension, bits);
+ }
+
+ // ---- private -----------------------------------------------------------
+
+ private void validateVector(float[] vector, String name) {
+ if (vector == null) {
+ throw new IllegalArgumentException(name + " must not be null");
+ }
+ if (vector.length != dimension) {
+ throw new IllegalArgumentException(
+ "Expected " + name + " dimension " + dimension + ", got " + vector.length);
+ }
+ for (int i = 0; i < vector.length; i++) {
+ if (!Float.isFinite(vector[i])) {
+ throw new IllegalArgumentException(
+ name + " contains a non-finite value at dimension " + i + ": " + vector[i]);
+ }
+ }
+ }
+
+ private float[] normalize(float[] v, float norm) {
+ float[] out = new float[dimension];
+ for (int i = 0; i < dimension; i++) {
+ out[i] = v[i] / norm;
+ }
+ return out;
+ }
+
+ /** Applies the DΓD rotation matrix to the (normalized) input. */
+ private float[] rotate(float[] v) {
+ float[][] rotation = getRotationMatrix();
+ float[] out = new float[dimension];
+ for (int i = 0; i < dimension; i++) {
+ double acc = 0.0;
+ float[] row = rotation[i];
+ for (int j = 0; j < dimension; j++) {
+ acc += (double) row[j] * v[j];
+ }
+ out[i] = (float) acc;
+ }
+ return out;
+ }
+
+ /** Packs sign(v[i]) into ceil(D/8) bytes. Positive = bit 1, non-positive = bit 0. */
+ private byte[] binarize(float[] v) {
+ byte[] code = new byte[(dimension + 7) / 8];
+ for (int i = 0; i < dimension; i++) {
+ if (v[i] > 0f) {
+ code[i >> 3] |= (byte) (1 << (i & 7));
+ }
+ }
+ return code;
+ }
+
+ /** Lazy double-checked rotation matrix construction (Modified Gram-Schmidt). */
+ private float[][] getRotationMatrix() {
+ if (rotMat == null) {
+ synchronized (this) {
+ if (rotMat == null) {
+ rotMat = getOrBuildRotationMatrix(dimension, seed);
+ }
+ }
+ }
+ return rotMat;
+ }
+
+ private static float[][] getOrBuildRotationMatrix(int dimension, long seed) {
+ return ROTATION_MATRIX_CACHE.computeIfAbsent(new RotationKey(dimension, seed),
+ key -> buildRotationMatrix(key.dimension, key.seed));
+ }
+
+ /**
+ * Builds a random orthogonal DΓD matrix using Modified Gram-Schmidt (MGS).
+ * Runtime: O(DΒ³) β acceptable as a one-time cost (~0.5 s at D=768).
+ * Memory: 4 * DΒ² bytes (~2.3 MB at D=768).
+ */
+ static float[][] buildRotationMatrix(int d, long seed) {
Review Comment:
Thanks for this. The column wise comes directly from the RabitQ paper implementation. The matrix is built once per JVM and cached; every per-vector rotation (encode side) and per-query rotation (driver side) is the same O(DΒ²) multiply against the same bytes. So the other parts of the equation should dominate more. But this is worth a look to look at to consider for a quick end to end benchmark.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@hudi.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat(index): add RaBitQ encoder and multibit-aware scorer contract [hudi]
Posted by "sushrut-raina (via GitHub)" <gi...@apache.org>.
sushrut-raina commented on code in PR #19318:
URL: https://github.com/apache/hudi/pull/19318#discussion_r4114516148
##########
hudi-common/src/main/java/org/apache/hudi/common/index/vector/RaBitQEncoder.java:
##########
@@ -0,0 +1,588 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.hudi.common.index.vector;
+
+import java.io.Serializable;
+import java.util.Map;
+import java.util.Objects;
+import java.util.Random;
+import java.util.concurrent.ConcurrentHashMap;
+
+/**
+ * RaBitQ (Randomized Binary Quantization) encoder.
+ *
+ * <p>Encodes float vectors into 1-bit-per-dimension binary codes using a random
+ * orthogonal rotation matrix R. The rotation is deterministic given (seed, dimension),
+ * so R is stored as a seed β it never needs retraining.
+ *
+ * <p><b>Encoding (write path):</b>
+ * <ol>
+ * <li>Normalize: vΜ = v / ||v||</li>
+ * <li>Rotate: v_rot = R @ vΜ</li>
+ * <li>Binarize: code = pack(sign(v_rot)) β D bits β ceil(D/8) bytes</li>
+ * <li>Scalar: s = ||v|| (stored alongside code; 1.0 if assume_normalized)</li>
+ * </ol>
+ *
+ * <p><b>Query scan (read path):</b>
+ * <ol>
+ * <li>Normalize + rotate the query vector (same R)</li>
+ * <li>Binarize to get q_bin</li>
+ * <li>For each database code b: Hamming(q_bin, b) β estimated cosine</li>
+ * <li>Re-rank top-R candidates with exact distance</li>
+ * </ol>
+ *
+ * <p>Memory: the rotation matrix is DΓD floats = 4Β·DΒ² bytes (~2.3 MB at D=768).
+ * It is built lazily on first use and reused across encode calls.
+ *
+ * <p>Thread-safe after the first call to {@link #encode} or {@link #encodeQuery}
+ * (the lazy init is synchronized).
+ */
+public final class RaBitQEncoder implements Serializable {
+ private static final long serialVersionUID = 1L;
+ private static final Map<RotationKey, float[][]> ROTATION_MATRIX_CACHE = new ConcurrentHashMap<>();
+ /** Neutral-factor thresholds for the current posting-block format (RFC-109 Β§3). */
+ private static final RaBitQFactorConfig FACTOR_CONFIG = RaBitQFactorConfig.defaults();
+ private final int dimension;
+ private final int bits;
+ private final long seed;
+ private final boolean assumeNormalized;
+
+ /** Rotation matrix, row-major. Populated lazily. */
+ private transient volatile float[][] rotMat;
+ public RaBitQEncoder(int dimension, long seed, boolean assumeNormalized) {
+ this(dimension, 1, seed, assumeNormalized);
+ }
+
+ public RaBitQEncoder(int dimension, int bits, long seed, boolean assumeNormalized) {
+ if (dimension <= 0) {
+ throw new IllegalArgumentException("Dimension must be positive, got: " + dimension);
+ }
+ if (bits <= 0 || bits > 8) {
+ throw new IllegalArgumentException("RaBitQ bits must be in [1, 8], got: " + bits);
+ }
+ this.dimension = dimension;
+ this.bits = bits;
+ this.seed = seed;
+ this.assumeNormalized = assumeNormalized;
+ }
+
+ /** Convenience constructor using default seed. */
+ public RaBitQEncoder(int dimension) {
+ this(dimension, 1, 42L, false);
+ }
+
+ // ---- encoding ----------------------------------------------------------
+
+ public QuantizedVector encode(float[] vector) {
+ validateVector(vector, "vector");
+ float norm = norm(vector);
+ float scalar = assumeNormalized ? 1.0f : norm;
+ float[] normalized = (norm == 0f || assumeNormalized)
+ ? vector
+ : normalize(vector, norm);
+ float[] rotated = rotate(normalized);
+ return new QuantizedVector(binarize(rotated), scalar);
+ }
+
+ /**
+ * Metric-neutral residual encoding used by MDT postings.
+ *
+ * <p>The optional {@code center} is the IVF centroid in the <b>original</b> vector space.
+ * When null, the vector is encoded relative to the origin.
+ */
+ public QuantizedVector encodeResidual(float[] vector, float[] center) {
+ validateVector(vector, "vector");
+ if (center != null) {
+ validateVector(center, "center");
+ }
+ float[] rotatedVector = rotate(vector);
+ float[] rotatedCenter = center == null ? new float[dimension] : rotate(center);
+ float[] residual = subtract(rotatedVector, rotatedCenter);
+ byte[] binaryCode = binarize(residual);
+
+ float residualNorm = norm(residual);
+ if (residualNorm == 0.0f) {
+ return new QuantizedVector(
+ binaryCode,
+ new byte[extendedCodeBytes()],
+ 0.0f,
+ 0.0f,
+ 0.0f,
+ 0.0f,
+ 0.0f,
+ 0.0f,
+ norm(vector),
+ bits);
+ }
+
+ if (bits <= 1) {
+ double ipResidual1 = 0.0d;
+ for (int i = 0; i < dimension; i++) {
+ ipResidual1 += residual[i] * (residual[i] > 0f ? 0.5d : -0.5d);
+ }
+ RaBitQNeutralFactors.Factors factors = RaBitQNeutralFactors.compute(
+ residual,
+ rotatedCenter,
+ rotatedVector,
+ ipResidual1,
+ ipResidual1,
+ dimension,
+ FACTOR_CONFIG);
+ return new QuantizedVector(
+ binaryCode,
+ new byte[0],
+ factors.residualNorm,
+ factors.centerRip,
+ factors.fRescale1,
+ factors.centerRip,
+ factors.fRescale1,
+ factors.err1,
+ factors.vectorNorm,
+ bits);
+ }
+
+ int exBits = bits - 1;
+
+ float[] absNormalizedResidual = new float[dimension];
+ for (int i = 0; i < dimension; i++) {
+ absNormalizedResidual[i] = Math.abs(residual[i] / residualNorm);
+ }
+
+ QuantizedLevels quantizedLevels = quantizeEx(absNormalizedResidual, exBits);
+ int[] exCode = quantizedLevels.levels;
+ int mask = (1 << exBits) - 1;
+ for (int i = 0; i < dimension; i++) {
+ if (residual[i] < 0f) {
+ exCode[i] = mask - exCode[i];
+ }
+ }
+
+ float cBias = (float) -((1 << exBits) - 0.5d);
+ double ipResidual1 = 0.0d;
+ double ipResidual = 0.0d;
+ for (int i = 0; i < dimension; i++) {
+ boolean positive = residual[i] > 0f;
+ double signOnlyCode = positive ? 0.5d : -0.5d;
+ float centeredCode = exCode[i] + (positive ? (1 << exBits) : 0) + cBias;
+ ipResidual1 += residual[i] * signOnlyCode;
+ ipResidual += residual[i] * centeredCode;
+ }
+
+ RaBitQNeutralFactors.Factors factors = RaBitQNeutralFactors.compute(
+ residual,
+ rotatedCenter,
+ rotatedVector,
+ ipResidual1,
+ ipResidual,
+ dimension,
+ FACTOR_CONFIG);
+ return new QuantizedVector(
+ binaryCode,
+ packUnsignedLevels(exCode, exBits),
+ factors.residualNorm,
+ factors.centerRip,
+ factors.fRescaleEx,
+ factors.centerRip,
+ factors.fRescale1,
+ factors.err1,
+ factors.vectorNorm,
+ bits);
+ }
+
+ /**
+ * Compatibility shim for old call sites. New postings must use the metric-neutral
+ * residual factor convention produced by {@link #encodeResidual(float[], float[])}.
+ */
+ public QuantizedVector encodeForL2(float[] vector, float[] center) {
+ return encodeResidual(vector, center);
+ }
+
+ public RaBitQQueryState encodeQuery(float[] queryVector) {
+ validateVector(queryVector, "query");
+ float norm = norm(queryVector);
+ float[] normalized = norm == 0f ? queryVector : normalize(queryVector, norm);
+ float[] rotated = rotate(normalized);
+ return new RaBitQQueryState(binarize(rotated), rotated, norm);
+ }
+
+ public RaBitQQueryState encodeQueryForL2(float[] queryVector) {
+ validateVector(queryVector, "query");
+ float[] rotated = rotate(queryVector);
+ return new RaBitQQueryState(binarize(rotated), rotated, norm(queryVector));
+ }
+
+ public float estimateDistance(RaBitQQueryState queryState, QuantizedVector encoded) {
+ return RaBitQDistanceScorer.estimateDistance(
+ queryState.binaryCodeUnsafe(), encoded.code, encoded.scalar, dimension);
+ }
+
+ /** Metric-aware approximate distance using symmetric or asymmetric cosine estimation. */
+ public float estimateDistance(RaBitQQueryState queryState,
+ QuantizedVector encoded,
+ VectorDistanceMetric metric,
+ boolean asymmetric) {
+ float cosine = asymmetric
+ ? RaBitQDistanceScorer.asymmetricCosine(queryState.rotatedQueryUnsafe(), encoded.code, dimension)
+ : RaBitQDistanceScorer.symmetricCosine(queryState.binaryCodeUnsafe(), encoded.code, dimension);
+ return RaBitQDistanceScorer.reconstructDistance(
+ metric, cosine, queryState.getQueryNorm(), encoded.scalar);
+ }
+
+ public int codeBytes() {
+ return (dimension + 7) / 8;
+ }
+
+ public int extendedCodeBytes() {
+ return bits <= 1 ? 0 : (dimension * (bits - 1) + 7) / 8;
+ }
+
+ public int totalCodeBytes() {
+ return codeBytes() + extendedCodeBytes();
+ }
+
+ public int getBits() {
+ return bits;
+ }
+
+ // ---- public utilities --------------------------------------------------
+
+ /** L2 norm of a float vector. */
+ public static float norm(float[] v) {
+ double sum = 0.0;
+ for (float x : v) {
+ sum += (double) x * x;
+ }
+ return (float) Math.sqrt(sum);
+ }
+
+ public static float l2Squared(float[] left, float[] right) {
+ double sum = 0.0;
+ for (int i = 0; i < left.length; i++) {
+ double delta = (double) left[i] - right[i];
+ sum += delta * delta;
+ }
+ return (float) sum;
+ }
+
+ public float[] rotateVector(float[] vector) {
+ validateVector(vector, "vector");
+ return rotate(vector);
+ }
+
+ public static float dotPackedBinary(byte[] binaryCode, float[] query, int dimension) {
+ double sum = 0.0;
+ for (int i = 0; i < dimension; i++) {
+ if ((binaryCode[i >> 3] & (1 << (i & 7))) != 0) {
+ sum += query[i];
+ }
+ }
+ return (float) sum;
+ }
+
+ public static float dotPackedUnsigned(byte[] packedLevels, int bitsPerValue, float[] query, int dimension) {
+ if (packedLevels == null || bitsPerValue <= 0) {
+ return 0.0f;
+ }
+ double sum = 0.0;
+ int bitOffset = 0;
+ for (int i = 0; i < dimension; i++) {
+ int value = 0;
+ for (int bit = 0; bit < bitsPerValue; bit++) {
+ int absoluteBit = bitOffset + bit;
+ int byteIndex = absoluteBit >> 3;
+ int bitIndex = absoluteBit & 7;
+ if ((packedLevels[byteIndex] & (1 << bitIndex)) != 0) {
+ value |= (1 << bit);
+ }
+ }
+ sum += (double) value * query[i];
+ bitOffset += bitsPerValue;
+ }
+ return (float) sum;
+ }
+
+ public static float multibitDotTerm(float[] rotatedQuery,
+ float sumQuery,
+ byte[] binaryCode,
+ byte[] extendedCode,
+ int dimension,
+ int bits) {
+ int exBits = bits - 1;
+ float binaryDot = dotPackedBinary(binaryCode, rotatedQuery, dimension);
+ if (exBits <= 0) {
+ return binaryDot + (sumQuery * -0.5f);
+ }
+ float extendedDot = dotPackedUnsigned(extendedCode, exBits, rotatedQuery, dimension);
+ float cBias = (float) -((1 << bits) - 1) / 2.0f;
+ return ((float) (1 << exBits) * binaryDot) + extendedDot + (sumQuery * cBias);
+ }
+
+ public static float multibitDotTerm(float[] rotatedQuery,
+ byte[] binaryCode,
+ byte[] extendedCode,
+ int dimension,
+ int bits) {
+ return multibitDotTerm(rotatedQuery, sum(rotatedQuery), binaryCode, extendedCode, dimension, bits);
+ }
+
+ // ---- private -----------------------------------------------------------
+
+ private void validateVector(float[] vector, String name) {
+ if (vector == null) {
+ throw new IllegalArgumentException(name + " must not be null");
+ }
+ if (vector.length != dimension) {
+ throw new IllegalArgumentException(
+ "Expected " + name + " dimension " + dimension + ", got " + vector.length);
+ }
+ for (int i = 0; i < vector.length; i++) {
+ if (!Float.isFinite(vector[i])) {
+ throw new IllegalArgumentException(
+ name + " contains a non-finite value at dimension " + i + ": " + vector[i]);
+ }
+ }
+ }
+
+ private float[] normalize(float[] v, float norm) {
+ float[] out = new float[dimension];
+ for (int i = 0; i < dimension; i++) {
+ out[i] = v[i] / norm;
+ }
+ return out;
+ }
+
+ /** Applies the DΓD rotation matrix to the (normalized) input. */
+ private float[] rotate(float[] v) {
+ float[][] rotation = getRotationMatrix();
+ float[] out = new float[dimension];
+ for (int i = 0; i < dimension; i++) {
+ double acc = 0.0;
+ float[] row = rotation[i];
+ for (int j = 0; j < dimension; j++) {
+ acc += (double) row[j] * v[j];
+ }
+ out[i] = (float) acc;
+ }
+ return out;
+ }
+
+ /** Packs sign(v[i]) into ceil(D/8) bytes. Positive = bit 1, non-positive = bit 0. */
+ private byte[] binarize(float[] v) {
+ byte[] code = new byte[(dimension + 7) / 8];
+ for (int i = 0; i < dimension; i++) {
+ if (v[i] > 0f) {
+ code[i >> 3] |= (byte) (1 << (i & 7));
+ }
+ }
+ return code;
+ }
+
+ /** Lazy double-checked rotation matrix construction (Modified Gram-Schmidt). */
+ private float[][] getRotationMatrix() {
+ if (rotMat == null) {
+ synchronized (this) {
+ if (rotMat == null) {
+ rotMat = getOrBuildRotationMatrix(dimension, seed);
+ }
+ }
+ }
+ return rotMat;
+ }
+
+ private static float[][] getOrBuildRotationMatrix(int dimension, long seed) {
+ return ROTATION_MATRIX_CACHE.computeIfAbsent(new RotationKey(dimension, seed),
+ key -> buildRotationMatrix(key.dimension, key.seed));
+ }
+
+ /**
+ * Builds a random orthogonal DΓD matrix using Modified Gram-Schmidt (MGS).
+ * Runtime: O(DΒ³) β acceptable as a one-time cost (~0.5 s at D=768).
+ * Memory: 4 * DΒ² bytes (~2.3 MB at D=768).
+ */
+ static float[][] buildRotationMatrix(int d, long seed) {
Review Comment:
@chrevanthreddy , any particular reason orthogonalizatoin is column wise ? the matrix is anyways transposed , so we could orthogonalize the rows themselves for better cache friendliness, below are some some nos I ran with row wise orthogonalisation.
Setup: MacBook Pro, Apple M4 (10 cores, 16 GB, 4 MB L2), OpenJDK 17.0.20. Each value is the best of 3 builds, and ranges cover 3β5 separate runs.
```
D column-wise row-wise speedup max |RΒ·Rα΅ β I| (col / row)
768 377β396 ms 144β156 ms ~2.6x 9.8e-9 / 1.1e-8
1024 1784β1827 ms 341β353 ms ~5.2x 1.1e-8 / 7.9e-9
2048 16273β16913 ms 2830β2933 ms ~5.8x 6.9e-9 / 6.3e-9
```
- Accuracy is the same. Both versions stay within about 1e-8 of orthogonal, which is just the rounding from the final double-to-float conversion, and rotated vectors keep their length to within about 1e-8.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@hudi.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat(index): add RaBitQ encoder and multibit-aware scorer contract [hudi]
Posted by "hudi-bot (via GitHub)" <gi...@apache.org>.
hudi-bot commented on PR #19318:
URL: https://github.com/apache/hudi/pull/19318#issuecomment-5134604486
<!--
Meta data
{
"version" : 1,
"metaDataEntries" : [ {
"hash" : "c4189f94d6aecdcc696fdc6e6c714eb4f6843127",
"status" : "FAILURE",
"url" : "https://dev.azure.com/apachehudi/a1a51da7-8592-47d4-88dc-fd67bed336bb/_build/results?buildId=15521",
"triggerID" : "c4189f94d6aecdcc696fdc6e6c714eb4f6843127",
"triggerType" : "PUSH"
}, {
"hash" : "0682b183e048ce380025c634aef381e932994ae0",
"status" : "PENDING",
"url" : "https://dev.azure.com/apachehudi/a1a51da7-8592-47d4-88dc-fd67bed336bb/_build/results?buildId=15866",
"triggerID" : "0682b183e048ce380025c634aef381e932994ae0",
"triggerType" : "PUSH"
} ]
}-->
## CI report:
* c4189f94d6aecdcc696fdc6e6c714eb4f6843127 Azure: [FAILURE](https://dev.azure.com/apachehudi/a1a51da7-8592-47d4-88dc-fd67bed336bb/_build/results?buildId=15521)
* 0682b183e048ce380025c634aef381e932994ae0 Azure: [PENDING](https://dev.azure.com/apachehudi/a1a51da7-8592-47d4-88dc-fd67bed336bb/_build/results?buildId=15866)
<details>
<summary>Bot commands</summary>
@hudi-bot supports the following commands:
- `@hudi-bot run azure` re-run the last Azure build
</details>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@hudi.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat(index): add RaBitQ encoder and multibit-aware scorer contract [hudi]
Posted by "hudi-bot (via GitHub)" <gi...@apache.org>.
hudi-bot commented on PR #19318:
URL: https://github.com/apache/hudi/pull/19318#issuecomment-5134542363
<!--
Meta data
{
"version" : 1,
"metaDataEntries" : [ {
"hash" : "c4189f94d6aecdcc696fdc6e6c714eb4f6843127",
"status" : "FAILURE",
"url" : "https://dev.azure.com/apachehudi/a1a51da7-8592-47d4-88dc-fd67bed336bb/_build/results?buildId=15521",
"triggerID" : "c4189f94d6aecdcc696fdc6e6c714eb4f6843127",
"triggerType" : "PUSH"
}, {
"hash" : "0682b183e048ce380025c634aef381e932994ae0",
"status" : "UNKNOWN",
"url" : "TBD",
"triggerID" : "0682b183e048ce380025c634aef381e932994ae0",
"triggerType" : "PUSH"
} ]
}-->
## CI report:
* c4189f94d6aecdcc696fdc6e6c714eb4f6843127 Azure: [FAILURE](https://dev.azure.com/apachehudi/a1a51da7-8592-47d4-88dc-fd67bed336bb/_build/results?buildId=15521)
* 0682b183e048ce380025c634aef381e932994ae0 UNKNOWN
<details>
<summary>Bot commands</summary>
@hudi-bot supports the following commands:
- `@hudi-bot run azure` re-run the last Azure build
</details>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@hudi.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat(index): add RaBitQ encoder and multibit-aware scorer contract [hudi]
Posted by "hudi-bot (via GitHub)" <gi...@apache.org>.
hudi-bot commented on PR #19318:
URL: https://github.com/apache/hudi/pull/19318#issuecomment-5184478133
<!--
Meta data
{
"version" : 1,
"metaDataEntries" : [ {
"hash" : "c4189f94d6aecdcc696fdc6e6c714eb4f6843127",
"status" : "DELETED",
"url" : "https://dev.azure.com/apachehudi/a1a51da7-8592-47d4-88dc-fd67bed336bb/_build/results?buildId=15521",
"triggerID" : "c4189f94d6aecdcc696fdc6e6c714eb4f6843127",
"triggerType" : "PUSH"
}, {
"hash" : "0682b183e048ce380025c634aef381e932994ae0",
"status" : "SUCCESS",
"url" : "https://dev.azure.com/apachehudi/a1a51da7-8592-47d4-88dc-fd67bed336bb/_build/results?buildId=15866",
"triggerID" : "0682b183e048ce380025c634aef381e932994ae0",
"triggerType" : "PUSH"
}, {
"hash" : "6e11f97db99b2681b608ab6ed56994e55e19e1b4",
"status" : "UNKNOWN",
"url" : "TBD",
"triggerID" : "6e11f97db99b2681b608ab6ed56994e55e19e1b4",
"triggerType" : "PUSH"
} ]
}-->
## CI report:
* 0682b183e048ce380025c634aef381e932994ae0 Azure: [SUCCESS](https://dev.azure.com/apachehudi/a1a51da7-8592-47d4-88dc-fd67bed336bb/_build/results?buildId=15866)
* 6e11f97db99b2681b608ab6ed56994e55e19e1b4 UNKNOWN
<details>
<summary>Bot commands</summary>
@hudi-bot supports the following commands:
- `@hudi-bot run azure` re-run the last Azure build
</details>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@hudi.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat(index): add RaBitQ encoder and multibit-aware scorer contract [hudi]
Posted by "sushrut-raina (via GitHub)" <gi...@apache.org>.
sushrut-raina commented on code in PR #19318:
URL: https://github.com/apache/hudi/pull/19318#discussion_r4114516148
##########
hudi-common/src/main/java/org/apache/hudi/common/index/vector/RaBitQEncoder.java:
##########
@@ -0,0 +1,588 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.hudi.common.index.vector;
+
+import java.io.Serializable;
+import java.util.Map;
+import java.util.Objects;
+import java.util.Random;
+import java.util.concurrent.ConcurrentHashMap;
+
+/**
+ * RaBitQ (Randomized Binary Quantization) encoder.
+ *
+ * <p>Encodes float vectors into 1-bit-per-dimension binary codes using a random
+ * orthogonal rotation matrix R. The rotation is deterministic given (seed, dimension),
+ * so R is stored as a seed β it never needs retraining.
+ *
+ * <p><b>Encoding (write path):</b>
+ * <ol>
+ * <li>Normalize: vΜ = v / ||v||</li>
+ * <li>Rotate: v_rot = R @ vΜ</li>
+ * <li>Binarize: code = pack(sign(v_rot)) β D bits β ceil(D/8) bytes</li>
+ * <li>Scalar: s = ||v|| (stored alongside code; 1.0 if assume_normalized)</li>
+ * </ol>
+ *
+ * <p><b>Query scan (read path):</b>
+ * <ol>
+ * <li>Normalize + rotate the query vector (same R)</li>
+ * <li>Binarize to get q_bin</li>
+ * <li>For each database code b: Hamming(q_bin, b) β estimated cosine</li>
+ * <li>Re-rank top-R candidates with exact distance</li>
+ * </ol>
+ *
+ * <p>Memory: the rotation matrix is DΓD floats = 4Β·DΒ² bytes (~2.3 MB at D=768).
+ * It is built lazily on first use and reused across encode calls.
+ *
+ * <p>Thread-safe after the first call to {@link #encode} or {@link #encodeQuery}
+ * (the lazy init is synchronized).
+ */
+public final class RaBitQEncoder implements Serializable {
+ private static final long serialVersionUID = 1L;
+ private static final Map<RotationKey, float[][]> ROTATION_MATRIX_CACHE = new ConcurrentHashMap<>();
+ /** Neutral-factor thresholds for the current posting-block format (RFC-109 Β§3). */
+ private static final RaBitQFactorConfig FACTOR_CONFIG = RaBitQFactorConfig.defaults();
+ private final int dimension;
+ private final int bits;
+ private final long seed;
+ private final boolean assumeNormalized;
+
+ /** Rotation matrix, row-major. Populated lazily. */
+ private transient volatile float[][] rotMat;
+ public RaBitQEncoder(int dimension, long seed, boolean assumeNormalized) {
+ this(dimension, 1, seed, assumeNormalized);
+ }
+
+ public RaBitQEncoder(int dimension, int bits, long seed, boolean assumeNormalized) {
+ if (dimension <= 0) {
+ throw new IllegalArgumentException("Dimension must be positive, got: " + dimension);
+ }
+ if (bits <= 0 || bits > 8) {
+ throw new IllegalArgumentException("RaBitQ bits must be in [1, 8], got: " + bits);
+ }
+ this.dimension = dimension;
+ this.bits = bits;
+ this.seed = seed;
+ this.assumeNormalized = assumeNormalized;
+ }
+
+ /** Convenience constructor using default seed. */
+ public RaBitQEncoder(int dimension) {
+ this(dimension, 1, 42L, false);
+ }
+
+ // ---- encoding ----------------------------------------------------------
+
+ public QuantizedVector encode(float[] vector) {
+ validateVector(vector, "vector");
+ float norm = norm(vector);
+ float scalar = assumeNormalized ? 1.0f : norm;
+ float[] normalized = (norm == 0f || assumeNormalized)
+ ? vector
+ : normalize(vector, norm);
+ float[] rotated = rotate(normalized);
+ return new QuantizedVector(binarize(rotated), scalar);
+ }
+
+ /**
+ * Metric-neutral residual encoding used by MDT postings.
+ *
+ * <p>The optional {@code center} is the IVF centroid in the <b>original</b> vector space.
+ * When null, the vector is encoded relative to the origin.
+ */
+ public QuantizedVector encodeResidual(float[] vector, float[] center) {
+ validateVector(vector, "vector");
+ if (center != null) {
+ validateVector(center, "center");
+ }
+ float[] rotatedVector = rotate(vector);
+ float[] rotatedCenter = center == null ? new float[dimension] : rotate(center);
+ float[] residual = subtract(rotatedVector, rotatedCenter);
+ byte[] binaryCode = binarize(residual);
+
+ float residualNorm = norm(residual);
+ if (residualNorm == 0.0f) {
+ return new QuantizedVector(
+ binaryCode,
+ new byte[extendedCodeBytes()],
+ 0.0f,
+ 0.0f,
+ 0.0f,
+ 0.0f,
+ 0.0f,
+ 0.0f,
+ norm(vector),
+ bits);
+ }
+
+ if (bits <= 1) {
+ double ipResidual1 = 0.0d;
+ for (int i = 0; i < dimension; i++) {
+ ipResidual1 += residual[i] * (residual[i] > 0f ? 0.5d : -0.5d);
+ }
+ RaBitQNeutralFactors.Factors factors = RaBitQNeutralFactors.compute(
+ residual,
+ rotatedCenter,
+ rotatedVector,
+ ipResidual1,
+ ipResidual1,
+ dimension,
+ FACTOR_CONFIG);
+ return new QuantizedVector(
+ binaryCode,
+ new byte[0],
+ factors.residualNorm,
+ factors.centerRip,
+ factors.fRescale1,
+ factors.centerRip,
+ factors.fRescale1,
+ factors.err1,
+ factors.vectorNorm,
+ bits);
+ }
+
+ int exBits = bits - 1;
+
+ float[] absNormalizedResidual = new float[dimension];
+ for (int i = 0; i < dimension; i++) {
+ absNormalizedResidual[i] = Math.abs(residual[i] / residualNorm);
+ }
+
+ QuantizedLevels quantizedLevels = quantizeEx(absNormalizedResidual, exBits);
+ int[] exCode = quantizedLevels.levels;
+ int mask = (1 << exBits) - 1;
+ for (int i = 0; i < dimension; i++) {
+ if (residual[i] < 0f) {
+ exCode[i] = mask - exCode[i];
+ }
+ }
+
+ float cBias = (float) -((1 << exBits) - 0.5d);
+ double ipResidual1 = 0.0d;
+ double ipResidual = 0.0d;
+ for (int i = 0; i < dimension; i++) {
+ boolean positive = residual[i] > 0f;
+ double signOnlyCode = positive ? 0.5d : -0.5d;
+ float centeredCode = exCode[i] + (positive ? (1 << exBits) : 0) + cBias;
+ ipResidual1 += residual[i] * signOnlyCode;
+ ipResidual += residual[i] * centeredCode;
+ }
+
+ RaBitQNeutralFactors.Factors factors = RaBitQNeutralFactors.compute(
+ residual,
+ rotatedCenter,
+ rotatedVector,
+ ipResidual1,
+ ipResidual,
+ dimension,
+ FACTOR_CONFIG);
+ return new QuantizedVector(
+ binaryCode,
+ packUnsignedLevels(exCode, exBits),
+ factors.residualNorm,
+ factors.centerRip,
+ factors.fRescaleEx,
+ factors.centerRip,
+ factors.fRescale1,
+ factors.err1,
+ factors.vectorNorm,
+ bits);
+ }
+
+ /**
+ * Compatibility shim for old call sites. New postings must use the metric-neutral
+ * residual factor convention produced by {@link #encodeResidual(float[], float[])}.
+ */
+ public QuantizedVector encodeForL2(float[] vector, float[] center) {
+ return encodeResidual(vector, center);
+ }
+
+ public RaBitQQueryState encodeQuery(float[] queryVector) {
+ validateVector(queryVector, "query");
+ float norm = norm(queryVector);
+ float[] normalized = norm == 0f ? queryVector : normalize(queryVector, norm);
+ float[] rotated = rotate(normalized);
+ return new RaBitQQueryState(binarize(rotated), rotated, norm);
+ }
+
+ public RaBitQQueryState encodeQueryForL2(float[] queryVector) {
+ validateVector(queryVector, "query");
+ float[] rotated = rotate(queryVector);
+ return new RaBitQQueryState(binarize(rotated), rotated, norm(queryVector));
+ }
+
+ public float estimateDistance(RaBitQQueryState queryState, QuantizedVector encoded) {
+ return RaBitQDistanceScorer.estimateDistance(
+ queryState.binaryCodeUnsafe(), encoded.code, encoded.scalar, dimension);
+ }
+
+ /** Metric-aware approximate distance using symmetric or asymmetric cosine estimation. */
+ public float estimateDistance(RaBitQQueryState queryState,
+ QuantizedVector encoded,
+ VectorDistanceMetric metric,
+ boolean asymmetric) {
+ float cosine = asymmetric
+ ? RaBitQDistanceScorer.asymmetricCosine(queryState.rotatedQueryUnsafe(), encoded.code, dimension)
+ : RaBitQDistanceScorer.symmetricCosine(queryState.binaryCodeUnsafe(), encoded.code, dimension);
+ return RaBitQDistanceScorer.reconstructDistance(
+ metric, cosine, queryState.getQueryNorm(), encoded.scalar);
+ }
+
+ public int codeBytes() {
+ return (dimension + 7) / 8;
+ }
+
+ public int extendedCodeBytes() {
+ return bits <= 1 ? 0 : (dimension * (bits - 1) + 7) / 8;
+ }
+
+ public int totalCodeBytes() {
+ return codeBytes() + extendedCodeBytes();
+ }
+
+ public int getBits() {
+ return bits;
+ }
+
+ // ---- public utilities --------------------------------------------------
+
+ /** L2 norm of a float vector. */
+ public static float norm(float[] v) {
+ double sum = 0.0;
+ for (float x : v) {
+ sum += (double) x * x;
+ }
+ return (float) Math.sqrt(sum);
+ }
+
+ public static float l2Squared(float[] left, float[] right) {
+ double sum = 0.0;
+ for (int i = 0; i < left.length; i++) {
+ double delta = (double) left[i] - right[i];
+ sum += delta * delta;
+ }
+ return (float) sum;
+ }
+
+ public float[] rotateVector(float[] vector) {
+ validateVector(vector, "vector");
+ return rotate(vector);
+ }
+
+ public static float dotPackedBinary(byte[] binaryCode, float[] query, int dimension) {
+ double sum = 0.0;
+ for (int i = 0; i < dimension; i++) {
+ if ((binaryCode[i >> 3] & (1 << (i & 7))) != 0) {
+ sum += query[i];
+ }
+ }
+ return (float) sum;
+ }
+
+ public static float dotPackedUnsigned(byte[] packedLevels, int bitsPerValue, float[] query, int dimension) {
+ if (packedLevels == null || bitsPerValue <= 0) {
+ return 0.0f;
+ }
+ double sum = 0.0;
+ int bitOffset = 0;
+ for (int i = 0; i < dimension; i++) {
+ int value = 0;
+ for (int bit = 0; bit < bitsPerValue; bit++) {
+ int absoluteBit = bitOffset + bit;
+ int byteIndex = absoluteBit >> 3;
+ int bitIndex = absoluteBit & 7;
+ if ((packedLevels[byteIndex] & (1 << bitIndex)) != 0) {
+ value |= (1 << bit);
+ }
+ }
+ sum += (double) value * query[i];
+ bitOffset += bitsPerValue;
+ }
+ return (float) sum;
+ }
+
+ public static float multibitDotTerm(float[] rotatedQuery,
+ float sumQuery,
+ byte[] binaryCode,
+ byte[] extendedCode,
+ int dimension,
+ int bits) {
+ int exBits = bits - 1;
+ float binaryDot = dotPackedBinary(binaryCode, rotatedQuery, dimension);
+ if (exBits <= 0) {
+ return binaryDot + (sumQuery * -0.5f);
+ }
+ float extendedDot = dotPackedUnsigned(extendedCode, exBits, rotatedQuery, dimension);
+ float cBias = (float) -((1 << bits) - 1) / 2.0f;
+ return ((float) (1 << exBits) * binaryDot) + extendedDot + (sumQuery * cBias);
+ }
+
+ public static float multibitDotTerm(float[] rotatedQuery,
+ byte[] binaryCode,
+ byte[] extendedCode,
+ int dimension,
+ int bits) {
+ return multibitDotTerm(rotatedQuery, sum(rotatedQuery), binaryCode, extendedCode, dimension, bits);
+ }
+
+ // ---- private -----------------------------------------------------------
+
+ private void validateVector(float[] vector, String name) {
+ if (vector == null) {
+ throw new IllegalArgumentException(name + " must not be null");
+ }
+ if (vector.length != dimension) {
+ throw new IllegalArgumentException(
+ "Expected " + name + " dimension " + dimension + ", got " + vector.length);
+ }
+ for (int i = 0; i < vector.length; i++) {
+ if (!Float.isFinite(vector[i])) {
+ throw new IllegalArgumentException(
+ name + " contains a non-finite value at dimension " + i + ": " + vector[i]);
+ }
+ }
+ }
+
+ private float[] normalize(float[] v, float norm) {
+ float[] out = new float[dimension];
+ for (int i = 0; i < dimension; i++) {
+ out[i] = v[i] / norm;
+ }
+ return out;
+ }
+
+ /** Applies the DΓD rotation matrix to the (normalized) input. */
+ private float[] rotate(float[] v) {
+ float[][] rotation = getRotationMatrix();
+ float[] out = new float[dimension];
+ for (int i = 0; i < dimension; i++) {
+ double acc = 0.0;
+ float[] row = rotation[i];
+ for (int j = 0; j < dimension; j++) {
+ acc += (double) row[j] * v[j];
+ }
+ out[i] = (float) acc;
+ }
+ return out;
+ }
+
+ /** Packs sign(v[i]) into ceil(D/8) bytes. Positive = bit 1, non-positive = bit 0. */
+ private byte[] binarize(float[] v) {
+ byte[] code = new byte[(dimension + 7) / 8];
+ for (int i = 0; i < dimension; i++) {
+ if (v[i] > 0f) {
+ code[i >> 3] |= (byte) (1 << (i & 7));
+ }
+ }
+ return code;
+ }
+
+ /** Lazy double-checked rotation matrix construction (Modified Gram-Schmidt). */
+ private float[][] getRotationMatrix() {
+ if (rotMat == null) {
+ synchronized (this) {
+ if (rotMat == null) {
+ rotMat = getOrBuildRotationMatrix(dimension, seed);
+ }
+ }
+ }
+ return rotMat;
+ }
+
+ private static float[][] getOrBuildRotationMatrix(int dimension, long seed) {
+ return ROTATION_MATRIX_CACHE.computeIfAbsent(new RotationKey(dimension, seed),
+ key -> buildRotationMatrix(key.dimension, key.seed));
+ }
+
+ /**
+ * Builds a random orthogonal DΓD matrix using Modified Gram-Schmidt (MGS).
+ * Runtime: O(DΒ³) β acceptable as a one-time cost (~0.5 s at D=768).
+ * Memory: 4 * DΒ² bytes (~2.3 MB at D=768).
+ */
+ static float[][] buildRotationMatrix(int d, long seed) {
Review Comment:
@chrevanthreddy , any particular reason orthogonalizatoin is column wise ? the matrix is anyways transposed , so we could orthogonalize the rows themselves for better cache friendliness, below are some some nos I ran with row wise orthogonalisation.
Setup: MacBook Pro, Apple M4 (10 cores, 16 GB, 4 MB L2), OpenJDK 17.0.20. Each value is the best of 3 builds, and ranges cover 3β5 separate runs.
```
D column-wise row-wise speedup max |RΒ·Rα΅ β I| (col / row)
768 377β396 ms 144β156 ms ~2.6x 9.8e-9 / 1.1e-8
1024 1784β1827 ms 341β353 ms ~5.2x 1.1e-8 / 7.9e-9
2048 16273β16913 ms 2830β2933 ms ~5.8x 6.9e-9 / 6.3e-9
```
- Accuracy is the same. Both versions stay within about 1e-8 of orthogonal.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@hudi.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat(index): add RaBitQ encoder and multibit-aware scorer contract [hudi]
Posted by "codecov-commenter (via GitHub)" <gi...@apache.org>.
codecov-commenter commented on PR #19318:
URL: https://github.com/apache/hudi/pull/19318#issuecomment-5134625738
## [Codecov](https://app.codecov.io/gh/apache/hudi/pull/19318?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) Report
:x: Patch coverage is `0.53929%` with `1291 lines` in your changes missing coverage. Please review.
:white_check_mark: Project coverage is 71.78%. Comparing base ([`633d142`](https://app.codecov.io/gh/apache/hudi/commit/633d1427f35fd2d4a21c6e02363dc8dd90239237?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)) to head ([`0682b18`](https://app.codecov.io/gh/apache/hudi/commit/0682b183e048ce380025c634aef381e932994ae0?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)).
| [Files with missing lines](https://app.codecov.io/gh/apache/hudi/pull/19318?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | Patch % | Lines |
|---|---|---|
| [...apache/hudi/common/index/vector/RaBitQEncoder.java](https://app.codecov.io/gh/apache/hudi/pull/19318?src=pr&el=tree&filepath=hudi-common%2Fsrc%2Fmain%2Fjava%2Forg%2Fapache%2Fhudi%2Fcommon%2Findex%2Fvector%2FRaBitQEncoder.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-aHVkaS1jb21tb24vc3JjL21haW4vamF2YS9vcmcvYXBhY2hlL2h1ZGkvY29tbW9uL2luZGV4L3ZlY3Rvci9SYUJpdFFFbmNvZGVyLmphdmE=) | 0.00% | [271 Missing :warning: ](https://app.codecov.io/gh/apache/hudi/pull/19318?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
| [.../hudi/common/index/vector/PostingBlockBuilder.java](https://app.codecov.io/gh/apache/hudi/pull/19318?src=pr&el=tree&filepath=hudi-common%2Fsrc%2Fmain%2Fjava%2Forg%2Fapache%2Fhudi%2Fcommon%2Findex%2Fvector%2FPostingBlockBuilder.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-aHVkaS1jb21tb24vc3JjL21haW4vamF2YS9vcmcvYXBhY2hlL2h1ZGkvY29tbW9uL2luZGV4L3ZlY3Rvci9Qb3N0aW5nQmxvY2tCdWlsZGVyLmphdmE=) | 0.00% | [149 Missing :warning: ](https://app.codecov.io/gh/apache/hudi/pull/19318?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
| [...che/hudi/common/index/vector/PostingBlockView.java](https://app.codecov.io/gh/apache/hudi/pull/19318?src=pr&el=tree&filepath=hudi-common%2Fsrc%2Fmain%2Fjava%2Forg%2Fapache%2Fhudi%2Fcommon%2Findex%2Fvector%2FPostingBlockView.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-aHVkaS1jb21tb24vc3JjL21haW4vamF2YS9vcmcvYXBhY2hlL2h1ZGkvY29tbW9uL2luZGV4L3ZlY3Rvci9Qb3N0aW5nQmxvY2tWaWV3LmphdmE=) | 0.00% | [104 Missing :warning: ](https://app.codecov.io/gh/apache/hudi/pull/19318?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
| [...rg/apache/hudi/metadata/HoodieMetadataPayload.java](https://app.codecov.io/gh/apache/hudi/pull/19318?src=pr&el=tree&filepath=hudi-common%2Fsrc%2Fmain%2Fjava%2Forg%2Fapache%2Fhudi%2Fmetadata%2FHoodieMetadataPayload.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-aHVkaS1jb21tb24vc3JjL21haW4vamF2YS9vcmcvYXBhY2hlL2h1ZGkvbWV0YWRhdGEvSG9vZGllTWV0YWRhdGFQYXlsb2FkLmphdmE=) | 0.95% | [103 Missing and 1 partial :warning: ](https://app.codecov.io/gh/apache/hudi/pull/19318?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
| [...che/hudi/common/index/vector/MetricQueryState.java](https://app.codecov.io/gh/apache/hudi/pull/19318?src=pr&el=tree&filepath=hudi-common%2Fsrc%2Fmain%2Fjava%2Forg%2Fapache%2Fhudi%2Fcommon%2Findex%2Fvector%2FMetricQueryState.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-aHVkaS1jb21tb24vc3JjL21haW4vamF2YS9vcmcvYXBhY2hlL2h1ZGkvY29tbW9uL2luZGV4L3ZlY3Rvci9NZXRyaWNRdWVyeVN0YXRlLmphdmE=) | 0.00% | [93 Missing :warning: ](https://app.codecov.io/gh/apache/hudi/pull/19318?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
| [...e/hudi/common/index/vector/VectorIndexOptions.java](https://app.codecov.io/gh/apache/hudi/pull/19318?src=pr&el=tree&filepath=hudi-common%2Fsrc%2Fmain%2Fjava%2Forg%2Fapache%2Fhudi%2Fcommon%2Findex%2Fvector%2FVectorIndexOptions.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-aHVkaS1jb21tb24vc3JjL21haW4vamF2YS9vcmcvYXBhY2hlL2h1ZGkvY29tbW9uL2luZGV4L3ZlY3Rvci9WZWN0b3JJbmRleE9wdGlvbnMuamF2YQ==) | 0.00% | [83 Missing :warning: ](https://app.codecov.io/gh/apache/hudi/pull/19318?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
| [...g/apache/hudi/metadata/VectorIndexMetadataKey.java](https://app.codecov.io/gh/apache/hudi/pull/19318?src=pr&el=tree&filepath=hudi-common%2Fsrc%2Fmain%2Fjava%2Forg%2Fapache%2Fhudi%2Fmetadata%2FVectorIndexMetadataKey.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-aHVkaS1jb21tb24vc3JjL21haW4vamF2YS9vcmcvYXBhY2hlL2h1ZGkvbWV0YWRhdGEvVmVjdG9ySW5kZXhNZXRhZGF0YUtleS5qYXZh) | 0.00% | [78 Missing :warning: ](https://app.codecov.io/gh/apache/hudi/pull/19318?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
| [...he/hudi/common/index/vector/VectorQueryPlanes.java](https://app.codecov.io/gh/apache/hudi/pull/19318?src=pr&el=tree&filepath=hudi-common%2Fsrc%2Fmain%2Fjava%2Forg%2Fapache%2Fhudi%2Fcommon%2Findex%2Fvector%2FVectorQueryPlanes.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-aHVkaS1jb21tb24vc3JjL21haW4vamF2YS9vcmcvYXBhY2hlL2h1ZGkvY29tbW9uL2luZGV4L3ZlY3Rvci9WZWN0b3JRdWVyeVBsYW5lcy5qYXZh) | 0.00% | [68 Missing :warning: ](https://app.codecov.io/gh/apache/hudi/pull/19318?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
| [...ache/hudi/common/index/vector/QuantizedVector.java](https://app.codecov.io/gh/apache/hudi/pull/19318?src=pr&el=tree&filepath=hudi-common%2Fsrc%2Fmain%2Fjava%2Forg%2Fapache%2Fhudi%2Fcommon%2Findex%2Fvector%2FQuantizedVector.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-aHVkaS1jb21tb24vc3JjL21haW4vamF2YS9vcmcvYXBhY2hlL2h1ZGkvY29tbW9uL2luZGV4L3ZlY3Rvci9RdWFudGl6ZWRWZWN0b3IuamF2YQ==) | 0.00% | [49 Missing :warning: ](https://app.codecov.io/gh/apache/hudi/pull/19318?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
| [...hudi/common/index/vector/RaBitQDistanceScorer.java](https://app.codecov.io/gh/apache/hudi/pull/19318?src=pr&el=tree&filepath=hudi-common%2Fsrc%2Fmain%2Fjava%2Forg%2Fapache%2Fhudi%2Fcommon%2Findex%2Fvector%2FRaBitQDistanceScorer.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-aHVkaS1jb21tb24vc3JjL21haW4vamF2YS9vcmcvYXBhY2hlL2h1ZGkvY29tbW9uL2luZGV4L3ZlY3Rvci9SYUJpdFFEaXN0YW5jZVNjb3Jlci5qYXZh) | 0.00% | [49 Missing :warning: ](https://app.codecov.io/gh/apache/hudi/pull/19318?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
| ... and [15 more](https://app.codecov.io/gh/apache/hudi/pull/19318?src=pr&el=tree-more&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | |
<details><summary>Additional details and impacted files</summary>
```diff
@@ Coverage Diff @@
## master #19318 +/- ##
============================================
- Coverage 72.43% 71.78% -0.66%
- Complexity 30918 30920 +2
============================================
Files 2559 2580 +21
Lines 141735 143033 +1298
Branches 17278 17491 +213
============================================
+ Hits 102671 102680 +9
- Misses 31113 32402 +1289
Partials 7951 7951
```
| [Components](https://app.codecov.io/gh/apache/hudi/pull/19318/components?src=pr&el=components&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | Coverage Ξ | |
|---|---|---|
| [hudi-common](https://app.codecov.io/gh/apache/hudi/pull/19318/components?src=pr&el=component&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `77.77% <0.53%> (-2.98%)` | :arrow_down: |
| [hudi-client](https://app.codecov.io/gh/apache/hudi/pull/19318/components?src=pr&el=component&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `76.92% <ΓΈ> (ΓΈ)` | |
| [hudi-flink](https://app.codecov.io/gh/apache/hudi/pull/19318/components?src=pr&el=component&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `84.03% <ΓΈ> (ΓΈ)` | |
| [hudi-spark-datasource](https://app.codecov.io/gh/apache/hudi/pull/19318/components?src=pr&el=component&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `59.71% <ΓΈ> (ΓΈ)` | |
| [hudi-utilities](https://app.codecov.io/gh/apache/hudi/pull/19318/components?src=pr&el=component&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `71.19% <ΓΈ> (ΓΈ)` | |
| [hudi-cli](https://app.codecov.io/gh/apache/hudi/pull/19318/components?src=pr&el=component&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `15.32% <ΓΈ> (ΓΈ)` | |
| [hudi-hadoop](https://app.codecov.io/gh/apache/hudi/pull/19318/components?src=pr&el=component&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `60.13% <ΓΈ> (ΓΈ)` | |
| [hudi-sync](https://app.codecov.io/gh/apache/hudi/pull/19318/components?src=pr&el=component&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `70.72% <ΓΈ> (ΓΈ)` | |
| [hudi-io](https://app.codecov.io/gh/apache/hudi/pull/19318/components?src=pr&el=component&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `79.33% <ΓΈ> (ΓΈ)` | |
| [hudi-timeline-service](https://app.codecov.io/gh/apache/hudi/pull/19318/components?src=pr&el=component&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `77.57% <ΓΈ> (ΓΈ)` | |
| [hudi-cloud](https://app.codecov.io/gh/apache/hudi/pull/19318/components?src=pr&el=component&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `64.00% <ΓΈ> (ΓΈ)` | |
| [hudi-kafka-connect](https://app.codecov.io/gh/apache/hudi/pull/19318/components?src=pr&el=component&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `53.96% <ΓΈ> (ΓΈ)` | |
| [Flag](https://app.codecov.io/gh/apache/hudi/pull/19318/flags?src=pr&el=flags&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | Coverage Ξ | |
|---|---|---|
| [hadoop-mr-java-client](https://app.codecov.io/gh/apache/hudi/pull/19318/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `42.56% <0.53%> (-0.76%)` | :arrow_down: |
Flags with carried forward coverage won't be shown. [Click here](https://docs.codecov.io/docs/carryforward-flags?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#carryforward-flags-in-the-pull-request-comment) to find out more.
| [Files with missing lines](https://app.codecov.io/gh/apache/hudi/pull/19318?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | Coverage Ξ | |
|---|---|---|
| [...a/org/apache/hudi/metadata/HoodieIndexVersion.java](https://app.codecov.io/gh/apache/hudi/pull/19318?src=pr&el=tree&filepath=hudi-common%2Fsrc%2Fmain%2Fjava%2Forg%2Fapache%2Fhudi%2Fmetadata%2FHoodieIndexVersion.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-aHVkaS1jb21tb24vc3JjL21haW4vamF2YS9vcmcvYXBhY2hlL2h1ZGkvbWV0YWRhdGEvSG9vZGllSW5kZXhWZXJzaW9uLmphdmE=) | `85.71% <0.00%> (-2.53%)` | :arrow_down: |
| [.../org/apache/hudi/metadata/VectorClusterRawKey.java](https://app.codecov.io/gh/apache/hudi/pull/19318?src=pr&el=tree&filepath=hudi-common%2Fsrc%2Fmain%2Fjava%2Forg%2Fapache%2Fhudi%2Fmetadata%2FVectorClusterRawKey.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-aHVkaS1jb21tb24vc3JjL21haW4vamF2YS9vcmcvYXBhY2hlL2h1ZGkvbWV0YWRhdGEvVmVjdG9yQ2x1c3RlclJhd0tleS5qYXZh) | `0.00% <0.00%> (ΓΈ)` | |
| [.../hudi/metadata/VectorGenerationManifestRawKey.java](https://app.codecov.io/gh/apache/hudi/pull/19318?src=pr&el=tree&filepath=hudi-common%2Fsrc%2Fmain%2Fjava%2Forg%2Fapache%2Fhudi%2Fmetadata%2FVectorGenerationManifestRawKey.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-aHVkaS1jb21tb24vc3JjL21haW4vamF2YS9vcmcvYXBhY2hlL2h1ZGkvbWV0YWRhdGEvVmVjdG9yR2VuZXJhdGlvbk1hbmlmZXN0UmF3S2V5LmphdmE=) | `0.00% <0.00%> (ΓΈ)` | |
| [...ache/hudi/common/index/vector/VectorQuantizer.java](https://app.codecov.io/gh/apache/hudi/pull/19318?src=pr&el=tree&filepath=hudi-common%2Fsrc%2Fmain%2Fjava%2Forg%2Fapache%2Fhudi%2Fcommon%2Findex%2Fvector%2FVectorQuantizer.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-aHVkaS1jb21tb24vc3JjL21haW4vamF2YS9vcmcvYXBhY2hlL2h1ZGkvY29tbW9uL2luZGV4L3ZlY3Rvci9WZWN0b3JRdWFudGl6ZXIuamF2YQ==) | `0.00% <0.00%> (ΓΈ)` | |
| [...pache/hudi/metadata/VectorPostingPrefixRawKey.java](https://app.codecov.io/gh/apache/hudi/pull/19318?src=pr&el=tree&filepath=hudi-common%2Fsrc%2Fmain%2Fjava%2Forg%2Fapache%2Fhudi%2Fmetadata%2FVectorPostingPrefixRawKey.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-aHVkaS1jb21tb24vc3JjL21haW4vamF2YS9vcmcvYXBhY2hlL2h1ZGkvbWV0YWRhdGEvVmVjdG9yUG9zdGluZ1ByZWZpeFJhd0tleS5qYXZh) | `0.00% <0.00%> (ΓΈ)` | |
| [...ache/hudi/common/index/vector/VectorQueryMode.java](https://app.codecov.io/gh/apache/hudi/pull/19318?src=pr&el=tree&filepath=hudi-common%2Fsrc%2Fmain%2Fjava%2Forg%2Fapache%2Fhudi%2Fcommon%2Findex%2Fvector%2FVectorQueryMode.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-aHVkaS1jb21tb24vc3JjL21haW4vamF2YS9vcmcvYXBhY2hlL2h1ZGkvY29tbW9uL2luZGV4L3ZlY3Rvci9WZWN0b3JRdWVyeU1vZGUuamF2YQ==) | `0.00% <0.00%> (ΓΈ)` | |
| [...he/hudi/common/index/vector/VectorStalePolicy.java](https://app.codecov.io/gh/apache/hudi/pull/19318?src=pr&el=tree&filepath=hudi-common%2Fsrc%2Fmain%2Fjava%2Forg%2Fapache%2Fhudi%2Fcommon%2Findex%2Fvector%2FVectorStalePolicy.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-aHVkaS1jb21tb24vc3JjL21haW4vamF2YS9vcmcvYXBhY2hlL2h1ZGkvY29tbW9uL2luZGV4L3ZlY3Rvci9WZWN0b3JTdGFsZVBvbGljeS5qYXZh) | `0.00% <0.00%> (ΓΈ)` | |
| [...rg/apache/hudi/metadata/MetadataPartitionType.java](https://app.codecov.io/gh/apache/hudi/pull/19318?src=pr&el=tree&filepath=hudi-common%2Fsrc%2Fmain%2Fjava%2Forg%2Fapache%2Fhudi%2Fmetadata%2FMetadataPartitionType.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-aHVkaS1jb21tb24vc3JjL21haW4vamF2YS9vcmcvYXBhY2hlL2h1ZGkvbWV0YWRhdGEvTWV0YWRhdGFQYXJ0aXRpb25UeXBlLmphdmE=) | `89.69% <40.00%> (-4.17%)` | :arrow_down: |
| [...e/hudi/common/index/vector/RaBitQFactorConfig.java](https://app.codecov.io/gh/apache/hudi/pull/19318?src=pr&el=tree&filepath=hudi-common%2Fsrc%2Fmain%2Fjava%2Forg%2Fapache%2Fhudi%2Fcommon%2Findex%2Fvector%2FRaBitQFactorConfig.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-aHVkaS1jb21tb24vc3JjL21haW4vamF2YS9vcmcvYXBhY2hlL2h1ZGkvY29tbW9uL2luZGV4L3ZlY3Rvci9SYUJpdFFGYWN0b3JDb25maWcuamF2YQ==) | `0.00% <0.00%> (ΓΈ)` | |
| [...che/hudi/common/index/vector/RaBitQQueryState.java](https://app.codecov.io/gh/apache/hudi/pull/19318?src=pr&el=tree&filepath=hudi-common%2Fsrc%2Fmain%2Fjava%2Forg%2Fapache%2Fhudi%2Fcommon%2Findex%2Fvector%2FRaBitQQueryState.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-aHVkaS1jb21tb24vc3JjL21haW4vamF2YS9vcmcvYXBhY2hlL2h1ZGkvY29tbW9uL2luZGV4L3ZlY3Rvci9SYUJpdFFRdWVyeVN0YXRlLmphdmE=) | `0.00% <0.00%> (ΓΈ)` | |
| ... and [15 more](https://app.codecov.io/gh/apache/hudi/pull/19318?src=pr&el=tree-more&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | |
... and [1 file with indirect coverage changes](https://app.codecov.io/gh/apache/hudi/pull/19318/indirect-changes?src=pr&el=tree-more&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)
</details>
<details><summary> :rocket: New features to boost your workflow: </summary>
- :snowflake: [Test Analytics](https://docs.codecov.com/docs/test-analytics): Detect flaky tests, report on failures, and find test suite problems.
- :package: [JS Bundle Analysis](https://docs.codecov.com/docs/javascript-bundle-analysis): Save yourself from yourself by tracking and limiting bundle sizes in JS merges.
</details>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@hudi.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat(index): add RaBitQ encoder and multibit-aware scorer contract [hudi]
Posted by "hudi-bot (via GitHub)" <gi...@apache.org>.
hudi-bot commented on PR #19318:
URL: https://github.com/apache/hudi/pull/19318#issuecomment-5185326934
<!--
Meta data
{
"version" : 1,
"metaDataEntries" : [ {
"hash" : "c4189f94d6aecdcc696fdc6e6c714eb4f6843127",
"status" : "DELETED",
"url" : "https://dev.azure.com/apachehudi/a1a51da7-8592-47d4-88dc-fd67bed336bb/_build/results?buildId=15521",
"triggerID" : "c4189f94d6aecdcc696fdc6e6c714eb4f6843127",
"triggerType" : "PUSH"
}, {
"hash" : "0682b183e048ce380025c634aef381e932994ae0",
"status" : "DELETED",
"url" : "https://dev.azure.com/apachehudi/a1a51da7-8592-47d4-88dc-fd67bed336bb/_build/results?buildId=15866",
"triggerID" : "0682b183e048ce380025c634aef381e932994ae0",
"triggerType" : "PUSH"
}, {
"hash" : "6e11f97db99b2681b608ab6ed56994e55e19e1b4",
"status" : "SUCCESS",
"url" : "https://dev.azure.com/apachehudi/a1a51da7-8592-47d4-88dc-fd67bed336bb/_build/results?buildId=16064",
"triggerID" : "6e11f97db99b2681b608ab6ed56994e55e19e1b4",
"triggerType" : "PUSH"
} ]
}-->
## CI report:
* 6e11f97db99b2681b608ab6ed56994e55e19e1b4 Azure: [SUCCESS](https://dev.azure.com/apachehudi/a1a51da7-8592-47d4-88dc-fd67bed336bb/_build/results?buildId=16064)
<details>
<summary>Bot commands</summary>
@hudi-bot supports the following commands:
- `@hudi-bot run azure` re-run the last Azure build
</details>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@hudi.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat(index): add RaBitQ encoder and multibit-aware scorer contract [hudi]
Posted by "chrevanthreddy (via GitHub)" <gi...@apache.org>.
chrevanthreddy commented on code in PR #19318:
URL: https://github.com/apache/hudi/pull/19318#discussion_r4148951098
##########
hudi-common/src/main/java/org/apache/hudi/common/index/vector/RaBitQEncoder.java:
##########
@@ -0,0 +1,588 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.hudi.common.index.vector;
+
+import java.io.Serializable;
+import java.util.Map;
+import java.util.Objects;
+import java.util.Random;
+import java.util.concurrent.ConcurrentHashMap;
+
+/**
+ * RaBitQ (Randomized Binary Quantization) encoder.
+ *
+ * <p>Encodes float vectors into 1-bit-per-dimension binary codes using a random
+ * orthogonal rotation matrix R. The rotation is deterministic given (seed, dimension),
+ * so R is stored as a seed β it never needs retraining.
+ *
+ * <p><b>Encoding (write path):</b>
+ * <ol>
+ * <li>Normalize: vΜ = v / ||v||</li>
+ * <li>Rotate: v_rot = R @ vΜ</li>
+ * <li>Binarize: code = pack(sign(v_rot)) β D bits β ceil(D/8) bytes</li>
+ * <li>Scalar: s = ||v|| (stored alongside code; 1.0 if assume_normalized)</li>
+ * </ol>
+ *
+ * <p><b>Query scan (read path):</b>
+ * <ol>
+ * <li>Normalize + rotate the query vector (same R)</li>
+ * <li>Binarize to get q_bin</li>
+ * <li>For each database code b: Hamming(q_bin, b) β estimated cosine</li>
+ * <li>Re-rank top-R candidates with exact distance</li>
+ * </ol>
+ *
+ * <p>Memory: the rotation matrix is DΓD floats = 4Β·DΒ² bytes (~2.3 MB at D=768).
+ * It is built lazily on first use and reused across encode calls.
+ *
+ * <p>Thread-safe after the first call to {@link #encode} or {@link #encodeQuery}
+ * (the lazy init is synchronized).
+ */
+public final class RaBitQEncoder implements Serializable {
+ private static final long serialVersionUID = 1L;
+ private static final Map<RotationKey, float[][]> ROTATION_MATRIX_CACHE = new ConcurrentHashMap<>();
+ /** Neutral-factor thresholds for the current posting-block format (RFC-109 Β§3). */
+ private static final RaBitQFactorConfig FACTOR_CONFIG = RaBitQFactorConfig.defaults();
+ private final int dimension;
+ private final int bits;
+ private final long seed;
+ private final boolean assumeNormalized;
+
+ /** Rotation matrix, row-major. Populated lazily. */
+ private transient volatile float[][] rotMat;
+ public RaBitQEncoder(int dimension, long seed, boolean assumeNormalized) {
+ this(dimension, 1, seed, assumeNormalized);
+ }
+
+ public RaBitQEncoder(int dimension, int bits, long seed, boolean assumeNormalized) {
+ if (dimension <= 0) {
+ throw new IllegalArgumentException("Dimension must be positive, got: " + dimension);
+ }
+ if (bits <= 0 || bits > 8) {
+ throw new IllegalArgumentException("RaBitQ bits must be in [1, 8], got: " + bits);
+ }
+ this.dimension = dimension;
+ this.bits = bits;
+ this.seed = seed;
+ this.assumeNormalized = assumeNormalized;
+ }
+
+ /** Convenience constructor using default seed. */
+ public RaBitQEncoder(int dimension) {
+ this(dimension, 1, 42L, false);
+ }
+
+ // ---- encoding ----------------------------------------------------------
+
+ public QuantizedVector encode(float[] vector) {
+ validateVector(vector, "vector");
+ float norm = norm(vector);
+ float scalar = assumeNormalized ? 1.0f : norm;
+ float[] normalized = (norm == 0f || assumeNormalized)
+ ? vector
+ : normalize(vector, norm);
+ float[] rotated = rotate(normalized);
+ return new QuantizedVector(binarize(rotated), scalar);
+ }
+
+ /**
+ * Metric-neutral residual encoding used by MDT postings.
+ *
+ * <p>The optional {@code center} is the IVF centroid in the <b>original</b> vector space.
+ * When null, the vector is encoded relative to the origin.
+ */
+ public QuantizedVector encodeResidual(float[] vector, float[] center) {
+ validateVector(vector, "vector");
+ if (center != null) {
+ validateVector(center, "center");
+ }
+ float[] rotatedVector = rotate(vector);
+ float[] rotatedCenter = center == null ? new float[dimension] : rotate(center);
+ float[] residual = subtract(rotatedVector, rotatedCenter);
+ byte[] binaryCode = binarize(residual);
+
+ float residualNorm = norm(residual);
+ if (residualNorm == 0.0f) {
+ return new QuantizedVector(
+ binaryCode,
+ new byte[extendedCodeBytes()],
+ 0.0f,
+ 0.0f,
+ 0.0f,
+ 0.0f,
+ 0.0f,
+ 0.0f,
+ norm(vector),
+ bits);
+ }
+
+ if (bits <= 1) {
+ double ipResidual1 = 0.0d;
+ for (int i = 0; i < dimension; i++) {
+ ipResidual1 += residual[i] * (residual[i] > 0f ? 0.5d : -0.5d);
+ }
+ RaBitQNeutralFactors.Factors factors = RaBitQNeutralFactors.compute(
+ residual,
+ rotatedCenter,
+ rotatedVector,
+ ipResidual1,
+ ipResidual1,
+ dimension,
+ FACTOR_CONFIG);
+ return new QuantizedVector(
+ binaryCode,
+ new byte[0],
+ factors.residualNorm,
+ factors.centerRip,
+ factors.fRescale1,
+ factors.centerRip,
+ factors.fRescale1,
+ factors.err1,
+ factors.vectorNorm,
+ bits);
+ }
+
+ int exBits = bits - 1;
+
+ float[] absNormalizedResidual = new float[dimension];
+ for (int i = 0; i < dimension; i++) {
+ absNormalizedResidual[i] = Math.abs(residual[i] / residualNorm);
+ }
+
+ QuantizedLevels quantizedLevels = quantizeEx(absNormalizedResidual, exBits);
+ int[] exCode = quantizedLevels.levels;
+ int mask = (1 << exBits) - 1;
+ for (int i = 0; i < dimension; i++) {
+ if (residual[i] < 0f) {
+ exCode[i] = mask - exCode[i];
+ }
+ }
+
+ float cBias = (float) -((1 << exBits) - 0.5d);
+ double ipResidual1 = 0.0d;
+ double ipResidual = 0.0d;
+ for (int i = 0; i < dimension; i++) {
+ boolean positive = residual[i] > 0f;
+ double signOnlyCode = positive ? 0.5d : -0.5d;
+ float centeredCode = exCode[i] + (positive ? (1 << exBits) : 0) + cBias;
+ ipResidual1 += residual[i] * signOnlyCode;
+ ipResidual += residual[i] * centeredCode;
+ }
+
+ RaBitQNeutralFactors.Factors factors = RaBitQNeutralFactors.compute(
+ residual,
+ rotatedCenter,
+ rotatedVector,
+ ipResidual1,
+ ipResidual,
+ dimension,
+ FACTOR_CONFIG);
+ return new QuantizedVector(
+ binaryCode,
+ packUnsignedLevels(exCode, exBits),
+ factors.residualNorm,
+ factors.centerRip,
+ factors.fRescaleEx,
+ factors.centerRip,
+ factors.fRescale1,
+ factors.err1,
+ factors.vectorNorm,
+ bits);
+ }
+
+ /**
+ * Compatibility shim for old call sites. New postings must use the metric-neutral
+ * residual factor convention produced by {@link #encodeResidual(float[], float[])}.
+ */
+ public QuantizedVector encodeForL2(float[] vector, float[] center) {
+ return encodeResidual(vector, center);
+ }
+
+ public RaBitQQueryState encodeQuery(float[] queryVector) {
+ validateVector(queryVector, "query");
+ float norm = norm(queryVector);
+ float[] normalized = norm == 0f ? queryVector : normalize(queryVector, norm);
+ float[] rotated = rotate(normalized);
+ return new RaBitQQueryState(binarize(rotated), rotated, norm);
+ }
+
+ public RaBitQQueryState encodeQueryForL2(float[] queryVector) {
+ validateVector(queryVector, "query");
+ float[] rotated = rotate(queryVector);
+ return new RaBitQQueryState(binarize(rotated), rotated, norm(queryVector));
+ }
+
+ public float estimateDistance(RaBitQQueryState queryState, QuantizedVector encoded) {
+ return RaBitQDistanceScorer.estimateDistance(
+ queryState.binaryCodeUnsafe(), encoded.code, encoded.scalar, dimension);
+ }
+
+ /** Metric-aware approximate distance using symmetric or asymmetric cosine estimation. */
+ public float estimateDistance(RaBitQQueryState queryState,
+ QuantizedVector encoded,
+ VectorDistanceMetric metric,
+ boolean asymmetric) {
+ float cosine = asymmetric
+ ? RaBitQDistanceScorer.asymmetricCosine(queryState.rotatedQueryUnsafe(), encoded.code, dimension)
+ : RaBitQDistanceScorer.symmetricCosine(queryState.binaryCodeUnsafe(), encoded.code, dimension);
+ return RaBitQDistanceScorer.reconstructDistance(
+ metric, cosine, queryState.getQueryNorm(), encoded.scalar);
+ }
+
+ public int codeBytes() {
+ return (dimension + 7) / 8;
+ }
+
+ public int extendedCodeBytes() {
+ return bits <= 1 ? 0 : (dimension * (bits - 1) + 7) / 8;
+ }
+
+ public int totalCodeBytes() {
+ return codeBytes() + extendedCodeBytes();
+ }
+
+ public int getBits() {
+ return bits;
+ }
+
+ // ---- public utilities --------------------------------------------------
+
+ /** L2 norm of a float vector. */
+ public static float norm(float[] v) {
+ double sum = 0.0;
+ for (float x : v) {
+ sum += (double) x * x;
+ }
+ return (float) Math.sqrt(sum);
+ }
+
+ public static float l2Squared(float[] left, float[] right) {
+ double sum = 0.0;
+ for (int i = 0; i < left.length; i++) {
+ double delta = (double) left[i] - right[i];
+ sum += delta * delta;
+ }
+ return (float) sum;
+ }
+
+ public float[] rotateVector(float[] vector) {
+ validateVector(vector, "vector");
+ return rotate(vector);
+ }
+
+ public static float dotPackedBinary(byte[] binaryCode, float[] query, int dimension) {
+ double sum = 0.0;
+ for (int i = 0; i < dimension; i++) {
+ if ((binaryCode[i >> 3] & (1 << (i & 7))) != 0) {
+ sum += query[i];
+ }
+ }
+ return (float) sum;
+ }
+
+ public static float dotPackedUnsigned(byte[] packedLevels, int bitsPerValue, float[] query, int dimension) {
+ if (packedLevels == null || bitsPerValue <= 0) {
+ return 0.0f;
+ }
+ double sum = 0.0;
+ int bitOffset = 0;
+ for (int i = 0; i < dimension; i++) {
+ int value = 0;
+ for (int bit = 0; bit < bitsPerValue; bit++) {
+ int absoluteBit = bitOffset + bit;
+ int byteIndex = absoluteBit >> 3;
+ int bitIndex = absoluteBit & 7;
+ if ((packedLevels[byteIndex] & (1 << bitIndex)) != 0) {
+ value |= (1 << bit);
+ }
+ }
+ sum += (double) value * query[i];
+ bitOffset += bitsPerValue;
+ }
+ return (float) sum;
+ }
+
+ public static float multibitDotTerm(float[] rotatedQuery,
+ float sumQuery,
+ byte[] binaryCode,
+ byte[] extendedCode,
+ int dimension,
+ int bits) {
+ int exBits = bits - 1;
+ float binaryDot = dotPackedBinary(binaryCode, rotatedQuery, dimension);
+ if (exBits <= 0) {
+ return binaryDot + (sumQuery * -0.5f);
+ }
+ float extendedDot = dotPackedUnsigned(extendedCode, exBits, rotatedQuery, dimension);
+ float cBias = (float) -((1 << bits) - 1) / 2.0f;
+ return ((float) (1 << exBits) * binaryDot) + extendedDot + (sumQuery * cBias);
+ }
+
+ public static float multibitDotTerm(float[] rotatedQuery,
+ byte[] binaryCode,
+ byte[] extendedCode,
+ int dimension,
+ int bits) {
+ return multibitDotTerm(rotatedQuery, sum(rotatedQuery), binaryCode, extendedCode, dimension, bits);
+ }
+
+ // ---- private -----------------------------------------------------------
+
+ private void validateVector(float[] vector, String name) {
+ if (vector == null) {
+ throw new IllegalArgumentException(name + " must not be null");
+ }
+ if (vector.length != dimension) {
+ throw new IllegalArgumentException(
+ "Expected " + name + " dimension " + dimension + ", got " + vector.length);
+ }
+ for (int i = 0; i < vector.length; i++) {
+ if (!Float.isFinite(vector[i])) {
+ throw new IllegalArgumentException(
+ name + " contains a non-finite value at dimension " + i + ": " + vector[i]);
+ }
+ }
+ }
+
+ private float[] normalize(float[] v, float norm) {
+ float[] out = new float[dimension];
+ for (int i = 0; i < dimension; i++) {
+ out[i] = v[i] / norm;
+ }
+ return out;
+ }
+
+ /** Applies the DΓD rotation matrix to the (normalized) input. */
+ private float[] rotate(float[] v) {
+ float[][] rotation = getRotationMatrix();
+ float[] out = new float[dimension];
+ for (int i = 0; i < dimension; i++) {
+ double acc = 0.0;
+ float[] row = rotation[i];
+ for (int j = 0; j < dimension; j++) {
+ acc += (double) row[j] * v[j];
+ }
+ out[i] = (float) acc;
+ }
+ return out;
+ }
+
+ /** Packs sign(v[i]) into ceil(D/8) bytes. Positive = bit 1, non-positive = bit 0. */
+ private byte[] binarize(float[] v) {
+ byte[] code = new byte[(dimension + 7) / 8];
+ for (int i = 0; i < dimension; i++) {
+ if (v[i] > 0f) {
+ code[i >> 3] |= (byte) (1 << (i & 7));
+ }
+ }
+ return code;
+ }
+
+ /** Lazy double-checked rotation matrix construction (Modified Gram-Schmidt). */
+ private float[][] getRotationMatrix() {
+ if (rotMat == null) {
+ synchronized (this) {
+ if (rotMat == null) {
+ rotMat = getOrBuildRotationMatrix(dimension, seed);
+ }
+ }
+ }
+ return rotMat;
+ }
+
+ private static float[][] getOrBuildRotationMatrix(int dimension, long seed) {
+ return ROTATION_MATRIX_CACHE.computeIfAbsent(new RotationKey(dimension, seed),
+ key -> buildRotationMatrix(key.dimension, key.seed));
+ }
+
+ /**
+ * Builds a random orthogonal DΓD matrix using Modified Gram-Schmidt (MGS).
+ * Runtime: O(DΒ³) β acceptable as a one-time cost (~0.5 s at D=768).
+ * Memory: 4 * DΒ² bytes (~2.3 MB at D=768).
+ */
+ static float[][] buildRotationMatrix(int d, long seed) {
Review Comment:
Thanks for this. The column wise comes directly from the RabitQ paper implementation. The matrix is built once per JVM and cached; every per-vector rotation (encode side) and per-query rotation (driver side) is the same O(DΒ²) multiply against the same bytes. So the other parts of the equation should dominate more. But this is worth a look to consider for a quick end to end benchmark.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@hudi.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat(index): add RaBitQ encoder and multibit-aware scorer contract [hudi]
Posted by "hudi-bot (via GitHub)" <gi...@apache.org>.
hudi-bot commented on PR #19318:
URL: https://github.com/apache/hudi/pull/19318#issuecomment-5135741510
<!--
Meta data
{
"version" : 1,
"metaDataEntries" : [ {
"hash" : "c4189f94d6aecdcc696fdc6e6c714eb4f6843127",
"status" : "DELETED",
"url" : "https://dev.azure.com/apachehudi/a1a51da7-8592-47d4-88dc-fd67bed336bb/_build/results?buildId=15521",
"triggerID" : "c4189f94d6aecdcc696fdc6e6c714eb4f6843127",
"triggerType" : "PUSH"
}, {
"hash" : "0682b183e048ce380025c634aef381e932994ae0",
"status" : "SUCCESS",
"url" : "https://dev.azure.com/apachehudi/a1a51da7-8592-47d4-88dc-fd67bed336bb/_build/results?buildId=15866",
"triggerID" : "0682b183e048ce380025c634aef381e932994ae0",
"triggerType" : "PUSH"
} ]
}-->
## CI report:
* 0682b183e048ce380025c634aef381e932994ae0 Azure: [SUCCESS](https://dev.azure.com/apachehudi/a1a51da7-8592-47d4-88dc-fd67bed336bb/_build/results?buildId=15866)
<details>
<summary>Bot commands</summary>
@hudi-bot supports the following commands:
- `@hudi-bot run azure` re-run the last Azure build
</details>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@hudi.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat(index): add RaBitQ encoder and multibit-aware scorer contract [hudi]
Posted by "hudi-bot (via GitHub)" <gi...@apache.org>.
hudi-bot commented on PR #19318:
URL: https://github.com/apache/hudi/pull/19318#issuecomment-5026974852
<!--
Meta data
{
"version" : 1,
"metaDataEntries" : [ {
"hash" : "c4189f94d6aecdcc696fdc6e6c714eb4f6843127",
"status" : "FAILURE",
"url" : "https://dev.azure.com/apachehudi/a1a51da7-8592-47d4-88dc-fd67bed336bb/_build/results?buildId=15521",
"triggerID" : "c4189f94d6aecdcc696fdc6e6c714eb4f6843127",
"triggerType" : "PUSH"
} ]
}-->
## CI report:
* c4189f94d6aecdcc696fdc6e6c714eb4f6843127 Azure: [FAILURE](https://dev.azure.com/apachehudi/a1a51da7-8592-47d4-88dc-fd67bed336bb/_build/results?buildId=15521)
<details>
<summary>Bot commands</summary>
@hudi-bot supports the following commands:
- `@hudi-bot run azure` re-run the last Azure build
</details>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@hudi.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat(index): add RaBitQ encoder and multibit-aware scorer contract [hudi]
Posted by "sushrut-raina (via GitHub)" <gi...@apache.org>.
sushrut-raina commented on code in PR #19318:
URL: https://github.com/apache/hudi/pull/19318#discussion_r4114516148
##########
hudi-common/src/main/java/org/apache/hudi/common/index/vector/RaBitQEncoder.java:
##########
@@ -0,0 +1,588 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.hudi.common.index.vector;
+
+import java.io.Serializable;
+import java.util.Map;
+import java.util.Objects;
+import java.util.Random;
+import java.util.concurrent.ConcurrentHashMap;
+
+/**
+ * RaBitQ (Randomized Binary Quantization) encoder.
+ *
+ * <p>Encodes float vectors into 1-bit-per-dimension binary codes using a random
+ * orthogonal rotation matrix R. The rotation is deterministic given (seed, dimension),
+ * so R is stored as a seed β it never needs retraining.
+ *
+ * <p><b>Encoding (write path):</b>
+ * <ol>
+ * <li>Normalize: vΜ = v / ||v||</li>
+ * <li>Rotate: v_rot = R @ vΜ</li>
+ * <li>Binarize: code = pack(sign(v_rot)) β D bits β ceil(D/8) bytes</li>
+ * <li>Scalar: s = ||v|| (stored alongside code; 1.0 if assume_normalized)</li>
+ * </ol>
+ *
+ * <p><b>Query scan (read path):</b>
+ * <ol>
+ * <li>Normalize + rotate the query vector (same R)</li>
+ * <li>Binarize to get q_bin</li>
+ * <li>For each database code b: Hamming(q_bin, b) β estimated cosine</li>
+ * <li>Re-rank top-R candidates with exact distance</li>
+ * </ol>
+ *
+ * <p>Memory: the rotation matrix is DΓD floats = 4Β·DΒ² bytes (~2.3 MB at D=768).
+ * It is built lazily on first use and reused across encode calls.
+ *
+ * <p>Thread-safe after the first call to {@link #encode} or {@link #encodeQuery}
+ * (the lazy init is synchronized).
+ */
+public final class RaBitQEncoder implements Serializable {
+ private static final long serialVersionUID = 1L;
+ private static final Map<RotationKey, float[][]> ROTATION_MATRIX_CACHE = new ConcurrentHashMap<>();
+ /** Neutral-factor thresholds for the current posting-block format (RFC-109 Β§3). */
+ private static final RaBitQFactorConfig FACTOR_CONFIG = RaBitQFactorConfig.defaults();
+ private final int dimension;
+ private final int bits;
+ private final long seed;
+ private final boolean assumeNormalized;
+
+ /** Rotation matrix, row-major. Populated lazily. */
+ private transient volatile float[][] rotMat;
+ public RaBitQEncoder(int dimension, long seed, boolean assumeNormalized) {
+ this(dimension, 1, seed, assumeNormalized);
+ }
+
+ public RaBitQEncoder(int dimension, int bits, long seed, boolean assumeNormalized) {
+ if (dimension <= 0) {
+ throw new IllegalArgumentException("Dimension must be positive, got: " + dimension);
+ }
+ if (bits <= 0 || bits > 8) {
+ throw new IllegalArgumentException("RaBitQ bits must be in [1, 8], got: " + bits);
+ }
+ this.dimension = dimension;
+ this.bits = bits;
+ this.seed = seed;
+ this.assumeNormalized = assumeNormalized;
+ }
+
+ /** Convenience constructor using default seed. */
+ public RaBitQEncoder(int dimension) {
+ this(dimension, 1, 42L, false);
+ }
+
+ // ---- encoding ----------------------------------------------------------
+
+ public QuantizedVector encode(float[] vector) {
+ validateVector(vector, "vector");
+ float norm = norm(vector);
+ float scalar = assumeNormalized ? 1.0f : norm;
+ float[] normalized = (norm == 0f || assumeNormalized)
+ ? vector
+ : normalize(vector, norm);
+ float[] rotated = rotate(normalized);
+ return new QuantizedVector(binarize(rotated), scalar);
+ }
+
+ /**
+ * Metric-neutral residual encoding used by MDT postings.
+ *
+ * <p>The optional {@code center} is the IVF centroid in the <b>original</b> vector space.
+ * When null, the vector is encoded relative to the origin.
+ */
+ public QuantizedVector encodeResidual(float[] vector, float[] center) {
+ validateVector(vector, "vector");
+ if (center != null) {
+ validateVector(center, "center");
+ }
+ float[] rotatedVector = rotate(vector);
+ float[] rotatedCenter = center == null ? new float[dimension] : rotate(center);
+ float[] residual = subtract(rotatedVector, rotatedCenter);
+ byte[] binaryCode = binarize(residual);
+
+ float residualNorm = norm(residual);
+ if (residualNorm == 0.0f) {
+ return new QuantizedVector(
+ binaryCode,
+ new byte[extendedCodeBytes()],
+ 0.0f,
+ 0.0f,
+ 0.0f,
+ 0.0f,
+ 0.0f,
+ 0.0f,
+ norm(vector),
+ bits);
+ }
+
+ if (bits <= 1) {
+ double ipResidual1 = 0.0d;
+ for (int i = 0; i < dimension; i++) {
+ ipResidual1 += residual[i] * (residual[i] > 0f ? 0.5d : -0.5d);
+ }
+ RaBitQNeutralFactors.Factors factors = RaBitQNeutralFactors.compute(
+ residual,
+ rotatedCenter,
+ rotatedVector,
+ ipResidual1,
+ ipResidual1,
+ dimension,
+ FACTOR_CONFIG);
+ return new QuantizedVector(
+ binaryCode,
+ new byte[0],
+ factors.residualNorm,
+ factors.centerRip,
+ factors.fRescale1,
+ factors.centerRip,
+ factors.fRescale1,
+ factors.err1,
+ factors.vectorNorm,
+ bits);
+ }
+
+ int exBits = bits - 1;
+
+ float[] absNormalizedResidual = new float[dimension];
+ for (int i = 0; i < dimension; i++) {
+ absNormalizedResidual[i] = Math.abs(residual[i] / residualNorm);
+ }
+
+ QuantizedLevels quantizedLevels = quantizeEx(absNormalizedResidual, exBits);
+ int[] exCode = quantizedLevels.levels;
+ int mask = (1 << exBits) - 1;
+ for (int i = 0; i < dimension; i++) {
+ if (residual[i] < 0f) {
+ exCode[i] = mask - exCode[i];
+ }
+ }
+
+ float cBias = (float) -((1 << exBits) - 0.5d);
+ double ipResidual1 = 0.0d;
+ double ipResidual = 0.0d;
+ for (int i = 0; i < dimension; i++) {
+ boolean positive = residual[i] > 0f;
+ double signOnlyCode = positive ? 0.5d : -0.5d;
+ float centeredCode = exCode[i] + (positive ? (1 << exBits) : 0) + cBias;
+ ipResidual1 += residual[i] * signOnlyCode;
+ ipResidual += residual[i] * centeredCode;
+ }
+
+ RaBitQNeutralFactors.Factors factors = RaBitQNeutralFactors.compute(
+ residual,
+ rotatedCenter,
+ rotatedVector,
+ ipResidual1,
+ ipResidual,
+ dimension,
+ FACTOR_CONFIG);
+ return new QuantizedVector(
+ binaryCode,
+ packUnsignedLevels(exCode, exBits),
+ factors.residualNorm,
+ factors.centerRip,
+ factors.fRescaleEx,
+ factors.centerRip,
+ factors.fRescale1,
+ factors.err1,
+ factors.vectorNorm,
+ bits);
+ }
+
+ /**
+ * Compatibility shim for old call sites. New postings must use the metric-neutral
+ * residual factor convention produced by {@link #encodeResidual(float[], float[])}.
+ */
+ public QuantizedVector encodeForL2(float[] vector, float[] center) {
+ return encodeResidual(vector, center);
+ }
+
+ public RaBitQQueryState encodeQuery(float[] queryVector) {
+ validateVector(queryVector, "query");
+ float norm = norm(queryVector);
+ float[] normalized = norm == 0f ? queryVector : normalize(queryVector, norm);
+ float[] rotated = rotate(normalized);
+ return new RaBitQQueryState(binarize(rotated), rotated, norm);
+ }
+
+ public RaBitQQueryState encodeQueryForL2(float[] queryVector) {
+ validateVector(queryVector, "query");
+ float[] rotated = rotate(queryVector);
+ return new RaBitQQueryState(binarize(rotated), rotated, norm(queryVector));
+ }
+
+ public float estimateDistance(RaBitQQueryState queryState, QuantizedVector encoded) {
+ return RaBitQDistanceScorer.estimateDistance(
+ queryState.binaryCodeUnsafe(), encoded.code, encoded.scalar, dimension);
+ }
+
+ /** Metric-aware approximate distance using symmetric or asymmetric cosine estimation. */
+ public float estimateDistance(RaBitQQueryState queryState,
+ QuantizedVector encoded,
+ VectorDistanceMetric metric,
+ boolean asymmetric) {
+ float cosine = asymmetric
+ ? RaBitQDistanceScorer.asymmetricCosine(queryState.rotatedQueryUnsafe(), encoded.code, dimension)
+ : RaBitQDistanceScorer.symmetricCosine(queryState.binaryCodeUnsafe(), encoded.code, dimension);
+ return RaBitQDistanceScorer.reconstructDistance(
+ metric, cosine, queryState.getQueryNorm(), encoded.scalar);
+ }
+
+ public int codeBytes() {
+ return (dimension + 7) / 8;
+ }
+
+ public int extendedCodeBytes() {
+ return bits <= 1 ? 0 : (dimension * (bits - 1) + 7) / 8;
+ }
+
+ public int totalCodeBytes() {
+ return codeBytes() + extendedCodeBytes();
+ }
+
+ public int getBits() {
+ return bits;
+ }
+
+ // ---- public utilities --------------------------------------------------
+
+ /** L2 norm of a float vector. */
+ public static float norm(float[] v) {
+ double sum = 0.0;
+ for (float x : v) {
+ sum += (double) x * x;
+ }
+ return (float) Math.sqrt(sum);
+ }
+
+ public static float l2Squared(float[] left, float[] right) {
+ double sum = 0.0;
+ for (int i = 0; i < left.length; i++) {
+ double delta = (double) left[i] - right[i];
+ sum += delta * delta;
+ }
+ return (float) sum;
+ }
+
+ public float[] rotateVector(float[] vector) {
+ validateVector(vector, "vector");
+ return rotate(vector);
+ }
+
+ public static float dotPackedBinary(byte[] binaryCode, float[] query, int dimension) {
+ double sum = 0.0;
+ for (int i = 0; i < dimension; i++) {
+ if ((binaryCode[i >> 3] & (1 << (i & 7))) != 0) {
+ sum += query[i];
+ }
+ }
+ return (float) sum;
+ }
+
+ public static float dotPackedUnsigned(byte[] packedLevels, int bitsPerValue, float[] query, int dimension) {
+ if (packedLevels == null || bitsPerValue <= 0) {
+ return 0.0f;
+ }
+ double sum = 0.0;
+ int bitOffset = 0;
+ for (int i = 0; i < dimension; i++) {
+ int value = 0;
+ for (int bit = 0; bit < bitsPerValue; bit++) {
+ int absoluteBit = bitOffset + bit;
+ int byteIndex = absoluteBit >> 3;
+ int bitIndex = absoluteBit & 7;
+ if ((packedLevels[byteIndex] & (1 << bitIndex)) != 0) {
+ value |= (1 << bit);
+ }
+ }
+ sum += (double) value * query[i];
+ bitOffset += bitsPerValue;
+ }
+ return (float) sum;
+ }
+
+ public static float multibitDotTerm(float[] rotatedQuery,
+ float sumQuery,
+ byte[] binaryCode,
+ byte[] extendedCode,
+ int dimension,
+ int bits) {
+ int exBits = bits - 1;
+ float binaryDot = dotPackedBinary(binaryCode, rotatedQuery, dimension);
+ if (exBits <= 0) {
+ return binaryDot + (sumQuery * -0.5f);
+ }
+ float extendedDot = dotPackedUnsigned(extendedCode, exBits, rotatedQuery, dimension);
+ float cBias = (float) -((1 << bits) - 1) / 2.0f;
+ return ((float) (1 << exBits) * binaryDot) + extendedDot + (sumQuery * cBias);
+ }
+
+ public static float multibitDotTerm(float[] rotatedQuery,
+ byte[] binaryCode,
+ byte[] extendedCode,
+ int dimension,
+ int bits) {
+ return multibitDotTerm(rotatedQuery, sum(rotatedQuery), binaryCode, extendedCode, dimension, bits);
+ }
+
+ // ---- private -----------------------------------------------------------
+
+ private void validateVector(float[] vector, String name) {
+ if (vector == null) {
+ throw new IllegalArgumentException(name + " must not be null");
+ }
+ if (vector.length != dimension) {
+ throw new IllegalArgumentException(
+ "Expected " + name + " dimension " + dimension + ", got " + vector.length);
+ }
+ for (int i = 0; i < vector.length; i++) {
+ if (!Float.isFinite(vector[i])) {
+ throw new IllegalArgumentException(
+ name + " contains a non-finite value at dimension " + i + ": " + vector[i]);
+ }
+ }
+ }
+
+ private float[] normalize(float[] v, float norm) {
+ float[] out = new float[dimension];
+ for (int i = 0; i < dimension; i++) {
+ out[i] = v[i] / norm;
+ }
+ return out;
+ }
+
+ /** Applies the DΓD rotation matrix to the (normalized) input. */
+ private float[] rotate(float[] v) {
+ float[][] rotation = getRotationMatrix();
+ float[] out = new float[dimension];
+ for (int i = 0; i < dimension; i++) {
+ double acc = 0.0;
+ float[] row = rotation[i];
+ for (int j = 0; j < dimension; j++) {
+ acc += (double) row[j] * v[j];
+ }
+ out[i] = (float) acc;
+ }
+ return out;
+ }
+
+ /** Packs sign(v[i]) into ceil(D/8) bytes. Positive = bit 1, non-positive = bit 0. */
+ private byte[] binarize(float[] v) {
+ byte[] code = new byte[(dimension + 7) / 8];
+ for (int i = 0; i < dimension; i++) {
+ if (v[i] > 0f) {
+ code[i >> 3] |= (byte) (1 << (i & 7));
+ }
+ }
+ return code;
+ }
+
+ /** Lazy double-checked rotation matrix construction (Modified Gram-Schmidt). */
+ private float[][] getRotationMatrix() {
+ if (rotMat == null) {
+ synchronized (this) {
+ if (rotMat == null) {
+ rotMat = getOrBuildRotationMatrix(dimension, seed);
+ }
+ }
+ }
+ return rotMat;
+ }
+
+ private static float[][] getOrBuildRotationMatrix(int dimension, long seed) {
+ return ROTATION_MATRIX_CACHE.computeIfAbsent(new RotationKey(dimension, seed),
+ key -> buildRotationMatrix(key.dimension, key.seed));
+ }
+
+ /**
+ * Builds a random orthogonal DΓD matrix using Modified Gram-Schmidt (MGS).
+ * Runtime: O(DΒ³) β acceptable as a one-time cost (~0.5 s at D=768).
+ * Memory: 4 * DΒ² bytes (~2.3 MB at D=768).
+ */
+ static float[][] buildRotationMatrix(int d, long seed) {
Review Comment:
@chrevanthreddy , any particular reason orthogonalizatoin is column wise ? the matrix is anyways transposed , so we could orthogonalize the rows themselves for better cache friendliness, below are some some nos I ran with row wise orthogonalisation.
Setup: MacBook Pro, Apple M4 (10 cores, 16 GB, 4 MB L2), OpenJDK 17.0.20. Each value is the best of 3 builds, and ranges cover 3β5 separate runs.
```
D column-wise row-wise speedup max |RΒ·Rα΅ β I| (col / row)
768 377β396 ms 144β156 ms ~2.6x 9.8e-9 / 1.1e-8
1024 1784β1827 ms 341β353 ms ~5.2x 1.1e-8 / 7.9e-9
2048 16273β16913 ms 2830β2933 ms ~5.8x 6.9e-9 / 6.3e-9
```
- Accuracy is the same. Both versions stay within about 1e-9 of orthogonal.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@hudi.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat(index): add RaBitQ encoder and multibit-aware scorer contract [hudi]
Posted by "sushrut-raina (via GitHub)" <gi...@apache.org>.
sushrut-raina commented on code in PR #19318:
URL: https://github.com/apache/hudi/pull/19318#discussion_r4114516148
##########
hudi-common/src/main/java/org/apache/hudi/common/index/vector/RaBitQEncoder.java:
##########
@@ -0,0 +1,588 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.hudi.common.index.vector;
+
+import java.io.Serializable;
+import java.util.Map;
+import java.util.Objects;
+import java.util.Random;
+import java.util.concurrent.ConcurrentHashMap;
+
+/**
+ * RaBitQ (Randomized Binary Quantization) encoder.
+ *
+ * <p>Encodes float vectors into 1-bit-per-dimension binary codes using a random
+ * orthogonal rotation matrix R. The rotation is deterministic given (seed, dimension),
+ * so R is stored as a seed β it never needs retraining.
+ *
+ * <p><b>Encoding (write path):</b>
+ * <ol>
+ * <li>Normalize: vΜ = v / ||v||</li>
+ * <li>Rotate: v_rot = R @ vΜ</li>
+ * <li>Binarize: code = pack(sign(v_rot)) β D bits β ceil(D/8) bytes</li>
+ * <li>Scalar: s = ||v|| (stored alongside code; 1.0 if assume_normalized)</li>
+ * </ol>
+ *
+ * <p><b>Query scan (read path):</b>
+ * <ol>
+ * <li>Normalize + rotate the query vector (same R)</li>
+ * <li>Binarize to get q_bin</li>
+ * <li>For each database code b: Hamming(q_bin, b) β estimated cosine</li>
+ * <li>Re-rank top-R candidates with exact distance</li>
+ * </ol>
+ *
+ * <p>Memory: the rotation matrix is DΓD floats = 4Β·DΒ² bytes (~2.3 MB at D=768).
+ * It is built lazily on first use and reused across encode calls.
+ *
+ * <p>Thread-safe after the first call to {@link #encode} or {@link #encodeQuery}
+ * (the lazy init is synchronized).
+ */
+public final class RaBitQEncoder implements Serializable {
+ private static final long serialVersionUID = 1L;
+ private static final Map<RotationKey, float[][]> ROTATION_MATRIX_CACHE = new ConcurrentHashMap<>();
+ /** Neutral-factor thresholds for the current posting-block format (RFC-109 Β§3). */
+ private static final RaBitQFactorConfig FACTOR_CONFIG = RaBitQFactorConfig.defaults();
+ private final int dimension;
+ private final int bits;
+ private final long seed;
+ private final boolean assumeNormalized;
+
+ /** Rotation matrix, row-major. Populated lazily. */
+ private transient volatile float[][] rotMat;
+ public RaBitQEncoder(int dimension, long seed, boolean assumeNormalized) {
+ this(dimension, 1, seed, assumeNormalized);
+ }
+
+ public RaBitQEncoder(int dimension, int bits, long seed, boolean assumeNormalized) {
+ if (dimension <= 0) {
+ throw new IllegalArgumentException("Dimension must be positive, got: " + dimension);
+ }
+ if (bits <= 0 || bits > 8) {
+ throw new IllegalArgumentException("RaBitQ bits must be in [1, 8], got: " + bits);
+ }
+ this.dimension = dimension;
+ this.bits = bits;
+ this.seed = seed;
+ this.assumeNormalized = assumeNormalized;
+ }
+
+ /** Convenience constructor using default seed. */
+ public RaBitQEncoder(int dimension) {
+ this(dimension, 1, 42L, false);
+ }
+
+ // ---- encoding ----------------------------------------------------------
+
+ public QuantizedVector encode(float[] vector) {
+ validateVector(vector, "vector");
+ float norm = norm(vector);
+ float scalar = assumeNormalized ? 1.0f : norm;
+ float[] normalized = (norm == 0f || assumeNormalized)
+ ? vector
+ : normalize(vector, norm);
+ float[] rotated = rotate(normalized);
+ return new QuantizedVector(binarize(rotated), scalar);
+ }
+
+ /**
+ * Metric-neutral residual encoding used by MDT postings.
+ *
+ * <p>The optional {@code center} is the IVF centroid in the <b>original</b> vector space.
+ * When null, the vector is encoded relative to the origin.
+ */
+ public QuantizedVector encodeResidual(float[] vector, float[] center) {
+ validateVector(vector, "vector");
+ if (center != null) {
+ validateVector(center, "center");
+ }
+ float[] rotatedVector = rotate(vector);
+ float[] rotatedCenter = center == null ? new float[dimension] : rotate(center);
+ float[] residual = subtract(rotatedVector, rotatedCenter);
+ byte[] binaryCode = binarize(residual);
+
+ float residualNorm = norm(residual);
+ if (residualNorm == 0.0f) {
+ return new QuantizedVector(
+ binaryCode,
+ new byte[extendedCodeBytes()],
+ 0.0f,
+ 0.0f,
+ 0.0f,
+ 0.0f,
+ 0.0f,
+ 0.0f,
+ norm(vector),
+ bits);
+ }
+
+ if (bits <= 1) {
+ double ipResidual1 = 0.0d;
+ for (int i = 0; i < dimension; i++) {
+ ipResidual1 += residual[i] * (residual[i] > 0f ? 0.5d : -0.5d);
+ }
+ RaBitQNeutralFactors.Factors factors = RaBitQNeutralFactors.compute(
+ residual,
+ rotatedCenter,
+ rotatedVector,
+ ipResidual1,
+ ipResidual1,
+ dimension,
+ FACTOR_CONFIG);
+ return new QuantizedVector(
+ binaryCode,
+ new byte[0],
+ factors.residualNorm,
+ factors.centerRip,
+ factors.fRescale1,
+ factors.centerRip,
+ factors.fRescale1,
+ factors.err1,
+ factors.vectorNorm,
+ bits);
+ }
+
+ int exBits = bits - 1;
+
+ float[] absNormalizedResidual = new float[dimension];
+ for (int i = 0; i < dimension; i++) {
+ absNormalizedResidual[i] = Math.abs(residual[i] / residualNorm);
+ }
+
+ QuantizedLevels quantizedLevels = quantizeEx(absNormalizedResidual, exBits);
+ int[] exCode = quantizedLevels.levels;
+ int mask = (1 << exBits) - 1;
+ for (int i = 0; i < dimension; i++) {
+ if (residual[i] < 0f) {
+ exCode[i] = mask - exCode[i];
+ }
+ }
+
+ float cBias = (float) -((1 << exBits) - 0.5d);
+ double ipResidual1 = 0.0d;
+ double ipResidual = 0.0d;
+ for (int i = 0; i < dimension; i++) {
+ boolean positive = residual[i] > 0f;
+ double signOnlyCode = positive ? 0.5d : -0.5d;
+ float centeredCode = exCode[i] + (positive ? (1 << exBits) : 0) + cBias;
+ ipResidual1 += residual[i] * signOnlyCode;
+ ipResidual += residual[i] * centeredCode;
+ }
+
+ RaBitQNeutralFactors.Factors factors = RaBitQNeutralFactors.compute(
+ residual,
+ rotatedCenter,
+ rotatedVector,
+ ipResidual1,
+ ipResidual,
+ dimension,
+ FACTOR_CONFIG);
+ return new QuantizedVector(
+ binaryCode,
+ packUnsignedLevels(exCode, exBits),
+ factors.residualNorm,
+ factors.centerRip,
+ factors.fRescaleEx,
+ factors.centerRip,
+ factors.fRescale1,
+ factors.err1,
+ factors.vectorNorm,
+ bits);
+ }
+
+ /**
+ * Compatibility shim for old call sites. New postings must use the metric-neutral
+ * residual factor convention produced by {@link #encodeResidual(float[], float[])}.
+ */
+ public QuantizedVector encodeForL2(float[] vector, float[] center) {
+ return encodeResidual(vector, center);
+ }
+
+ public RaBitQQueryState encodeQuery(float[] queryVector) {
+ validateVector(queryVector, "query");
+ float norm = norm(queryVector);
+ float[] normalized = norm == 0f ? queryVector : normalize(queryVector, norm);
+ float[] rotated = rotate(normalized);
+ return new RaBitQQueryState(binarize(rotated), rotated, norm);
+ }
+
+ public RaBitQQueryState encodeQueryForL2(float[] queryVector) {
+ validateVector(queryVector, "query");
+ float[] rotated = rotate(queryVector);
+ return new RaBitQQueryState(binarize(rotated), rotated, norm(queryVector));
+ }
+
+ public float estimateDistance(RaBitQQueryState queryState, QuantizedVector encoded) {
+ return RaBitQDistanceScorer.estimateDistance(
+ queryState.binaryCodeUnsafe(), encoded.code, encoded.scalar, dimension);
+ }
+
+ /** Metric-aware approximate distance using symmetric or asymmetric cosine estimation. */
+ public float estimateDistance(RaBitQQueryState queryState,
+ QuantizedVector encoded,
+ VectorDistanceMetric metric,
+ boolean asymmetric) {
+ float cosine = asymmetric
+ ? RaBitQDistanceScorer.asymmetricCosine(queryState.rotatedQueryUnsafe(), encoded.code, dimension)
+ : RaBitQDistanceScorer.symmetricCosine(queryState.binaryCodeUnsafe(), encoded.code, dimension);
+ return RaBitQDistanceScorer.reconstructDistance(
+ metric, cosine, queryState.getQueryNorm(), encoded.scalar);
+ }
+
+ public int codeBytes() {
+ return (dimension + 7) / 8;
+ }
+
+ public int extendedCodeBytes() {
+ return bits <= 1 ? 0 : (dimension * (bits - 1) + 7) / 8;
+ }
+
+ public int totalCodeBytes() {
+ return codeBytes() + extendedCodeBytes();
+ }
+
+ public int getBits() {
+ return bits;
+ }
+
+ // ---- public utilities --------------------------------------------------
+
+ /** L2 norm of a float vector. */
+ public static float norm(float[] v) {
+ double sum = 0.0;
+ for (float x : v) {
+ sum += (double) x * x;
+ }
+ return (float) Math.sqrt(sum);
+ }
+
+ public static float l2Squared(float[] left, float[] right) {
+ double sum = 0.0;
+ for (int i = 0; i < left.length; i++) {
+ double delta = (double) left[i] - right[i];
+ sum += delta * delta;
+ }
+ return (float) sum;
+ }
+
+ public float[] rotateVector(float[] vector) {
+ validateVector(vector, "vector");
+ return rotate(vector);
+ }
+
+ public static float dotPackedBinary(byte[] binaryCode, float[] query, int dimension) {
+ double sum = 0.0;
+ for (int i = 0; i < dimension; i++) {
+ if ((binaryCode[i >> 3] & (1 << (i & 7))) != 0) {
+ sum += query[i];
+ }
+ }
+ return (float) sum;
+ }
+
+ public static float dotPackedUnsigned(byte[] packedLevels, int bitsPerValue, float[] query, int dimension) {
+ if (packedLevels == null || bitsPerValue <= 0) {
+ return 0.0f;
+ }
+ double sum = 0.0;
+ int bitOffset = 0;
+ for (int i = 0; i < dimension; i++) {
+ int value = 0;
+ for (int bit = 0; bit < bitsPerValue; bit++) {
+ int absoluteBit = bitOffset + bit;
+ int byteIndex = absoluteBit >> 3;
+ int bitIndex = absoluteBit & 7;
+ if ((packedLevels[byteIndex] & (1 << bitIndex)) != 0) {
+ value |= (1 << bit);
+ }
+ }
+ sum += (double) value * query[i];
+ bitOffset += bitsPerValue;
+ }
+ return (float) sum;
+ }
+
+ public static float multibitDotTerm(float[] rotatedQuery,
+ float sumQuery,
+ byte[] binaryCode,
+ byte[] extendedCode,
+ int dimension,
+ int bits) {
+ int exBits = bits - 1;
+ float binaryDot = dotPackedBinary(binaryCode, rotatedQuery, dimension);
+ if (exBits <= 0) {
+ return binaryDot + (sumQuery * -0.5f);
+ }
+ float extendedDot = dotPackedUnsigned(extendedCode, exBits, rotatedQuery, dimension);
+ float cBias = (float) -((1 << bits) - 1) / 2.0f;
+ return ((float) (1 << exBits) * binaryDot) + extendedDot + (sumQuery * cBias);
+ }
+
+ public static float multibitDotTerm(float[] rotatedQuery,
+ byte[] binaryCode,
+ byte[] extendedCode,
+ int dimension,
+ int bits) {
+ return multibitDotTerm(rotatedQuery, sum(rotatedQuery), binaryCode, extendedCode, dimension, bits);
+ }
+
+ // ---- private -----------------------------------------------------------
+
+ private void validateVector(float[] vector, String name) {
+ if (vector == null) {
+ throw new IllegalArgumentException(name + " must not be null");
+ }
+ if (vector.length != dimension) {
+ throw new IllegalArgumentException(
+ "Expected " + name + " dimension " + dimension + ", got " + vector.length);
+ }
+ for (int i = 0; i < vector.length; i++) {
+ if (!Float.isFinite(vector[i])) {
+ throw new IllegalArgumentException(
+ name + " contains a non-finite value at dimension " + i + ": " + vector[i]);
+ }
+ }
+ }
+
+ private float[] normalize(float[] v, float norm) {
+ float[] out = new float[dimension];
+ for (int i = 0; i < dimension; i++) {
+ out[i] = v[i] / norm;
+ }
+ return out;
+ }
+
+ /** Applies the DΓD rotation matrix to the (normalized) input. */
+ private float[] rotate(float[] v) {
+ float[][] rotation = getRotationMatrix();
+ float[] out = new float[dimension];
+ for (int i = 0; i < dimension; i++) {
+ double acc = 0.0;
+ float[] row = rotation[i];
+ for (int j = 0; j < dimension; j++) {
+ acc += (double) row[j] * v[j];
+ }
+ out[i] = (float) acc;
+ }
+ return out;
+ }
+
+ /** Packs sign(v[i]) into ceil(D/8) bytes. Positive = bit 1, non-positive = bit 0. */
+ private byte[] binarize(float[] v) {
+ byte[] code = new byte[(dimension + 7) / 8];
+ for (int i = 0; i < dimension; i++) {
+ if (v[i] > 0f) {
+ code[i >> 3] |= (byte) (1 << (i & 7));
+ }
+ }
+ return code;
+ }
+
+ /** Lazy double-checked rotation matrix construction (Modified Gram-Schmidt). */
+ private float[][] getRotationMatrix() {
+ if (rotMat == null) {
+ synchronized (this) {
+ if (rotMat == null) {
+ rotMat = getOrBuildRotationMatrix(dimension, seed);
+ }
+ }
+ }
+ return rotMat;
+ }
+
+ private static float[][] getOrBuildRotationMatrix(int dimension, long seed) {
+ return ROTATION_MATRIX_CACHE.computeIfAbsent(new RotationKey(dimension, seed),
+ key -> buildRotationMatrix(key.dimension, key.seed));
+ }
+
+ /**
+ * Builds a random orthogonal DΓD matrix using Modified Gram-Schmidt (MGS).
+ * Runtime: O(DΒ³) β acceptable as a one-time cost (~0.5 s at D=768).
+ * Memory: 4 * DΒ² bytes (~2.3 MB at D=768).
+ */
+ static float[][] buildRotationMatrix(int d, long seed) {
Review Comment:
@chrevanthreddy , any particular reason orthogonalizatoin is column wise ? the matrix is anyways transposed , so we could orthogonalize the rows themselves for better cache friendliness, ran some nos...
Setup: MacBook Pro, Apple M4 (10 cores, 16 GB, 4 MB L2), OpenJDK 17.0.20. Each value is the best of 3 builds, and ranges cover 3β5 separate runs.
```
D column-wise row-wise speedup max |RΒ·Rα΅ β I| (col / row)
768 377β396 ms 144β156 ms ~2.6x 9.8e-9 / 1.1e-8
1024 1784β1827 ms 341β353 ms ~5.2x 1.1e-8 / 7.9e-9
2048 16273β16913 ms 2830β2933 ms ~5.8x 6.9e-9 / 6.3e-9
```
- Accuracy is the same. Both versions stay within about 1e-8 of orthogonal, which is just the rounding from the final double-to-float conversion, and rotated vectors keep their length to within about 1e-8.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@hudi.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat(index): add RaBitQ encoder and multibit-aware scorer contract [hudi]
Posted by "hudi-bot (via GitHub)" <gi...@apache.org>.
hudi-bot commented on PR #19318:
URL: https://github.com/apache/hudi/pull/19318#issuecomment-5005266248
<!--
Meta data
{
"version" : 1,
"metaDataEntries" : [ {
"hash" : "c4189f94d6aecdcc696fdc6e6c714eb4f6843127",
"status" : "UNKNOWN",
"url" : "TBD",
"triggerID" : "c4189f94d6aecdcc696fdc6e6c714eb4f6843127",
"triggerType" : "PUSH"
} ]
}-->
## CI report:
* c4189f94d6aecdcc696fdc6e6c714eb4f6843127 UNKNOWN
<details>
<summary>Bot commands</summary>
@hudi-bot supports the following commands:
- `@hudi-bot run azure` re-run the last Azure build
</details>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@hudi.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat(index): add RaBitQ encoder and multibit-aware scorer contract [hudi]
Posted by "hudi-bot (via GitHub)" <gi...@apache.org>.
hudi-bot commented on PR #19318:
URL: https://github.com/apache/hudi/pull/19318#issuecomment-5184534262
<!--
Meta data
{
"version" : 1,
"metaDataEntries" : [ {
"hash" : "c4189f94d6aecdcc696fdc6e6c714eb4f6843127",
"status" : "DELETED",
"url" : "https://dev.azure.com/apachehudi/a1a51da7-8592-47d4-88dc-fd67bed336bb/_build/results?buildId=15521",
"triggerID" : "c4189f94d6aecdcc696fdc6e6c714eb4f6843127",
"triggerType" : "PUSH"
}, {
"hash" : "0682b183e048ce380025c634aef381e932994ae0",
"status" : "SUCCESS",
"url" : "https://dev.azure.com/apachehudi/a1a51da7-8592-47d4-88dc-fd67bed336bb/_build/results?buildId=15866",
"triggerID" : "0682b183e048ce380025c634aef381e932994ae0",
"triggerType" : "PUSH"
}, {
"hash" : "6e11f97db99b2681b608ab6ed56994e55e19e1b4",
"status" : "PENDING",
"url" : "https://dev.azure.com/apachehudi/a1a51da7-8592-47d4-88dc-fd67bed336bb/_build/results?buildId=16064",
"triggerID" : "6e11f97db99b2681b608ab6ed56994e55e19e1b4",
"triggerType" : "PUSH"
} ]
}-->
## CI report:
* 0682b183e048ce380025c634aef381e932994ae0 Azure: [SUCCESS](https://dev.azure.com/apachehudi/a1a51da7-8592-47d4-88dc-fd67bed336bb/_build/results?buildId=15866)
* 6e11f97db99b2681b608ab6ed56994e55e19e1b4 Azure: [PENDING](https://dev.azure.com/apachehudi/a1a51da7-8592-47d4-88dc-fd67bed336bb/_build/results?buildId=16064)
<details>
<summary>Bot commands</summary>
@hudi-bot supports the following commands:
- `@hudi-bot run azure` re-run the last Azure build
</details>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@hudi.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] feat(index): add RaBitQ encoder and multibit-aware scorer contract [hudi]
Posted by "chrevanthreddy (via GitHub)" <gi...@apache.org>.
chrevanthreddy commented on PR #19318:
URL: https://github.com/apache/hudi/pull/19318#issuecomment-5184412208
Rebased this stack onto current `master` and aligned it with the finalized RFC-109 schema contract from #19317.
Key correction:
- the first shipped RaBitQ factor semantics are persisted as `factorVersion = 1`;
- `RaBitQFactorConfig.defaults()` returns version 1;
- unsupported factor versions are rejected explicitly;
- neutral-factor results retain the generation factor version for contract validation.
Java 17 validation after the refresh:
- focused encoder/factor tests: 46/46 passed;
- full `hudi-common`: 2,280/2,280 passed;
- Checkstyle: zero violations;
- `git diff --check`: passed.
The earlier internal v2/v3 terminology was intentionally removed: this is a new persisted format, not a migration from the experimental pre-shipping implementation.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@hudi.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org