This is an automated email from the ASF dual-hosted git repository. XiaoHongbo-Hope pushed a commit to branch release-2.1 in repository https://gitbox.apache.org/repos/asf/paimon.git
commit 7808aa7c3c11087947361dd3d37a332b54dced36 Author: YangJie <[email protected]> AuthorDate: Sat Sep 12 09:31:57 2026 -0400 [common] Order decimal z-values through the signed long transform (#9626) --- .../org/apache/paimon/sort/zorder/ZIndexer.java | 70 +++++++++--- .../paimon/sort/zorder/TestZOrderByteUtil.java | 124 +++++++++++++++++++++ 2 files changed, 177 insertions(+), 17 deletions(-) diff --git a/paimon-common/src/main/java/org/apache/paimon/sort/zorder/ZIndexer.java b/paimon-common/src/main/java/org/apache/paimon/sort/zorder/ZIndexer.java index 1f21811ed3..ec20e4fe31 100644 --- a/paimon-common/src/main/java/org/apache/paimon/sort/zorder/ZIndexer.java +++ b/paimon-common/src/main/java/org/apache/paimon/sort/zorder/ZIndexer.java @@ -51,6 +51,7 @@ import org.apache.paimon.types.VariantType; import org.apache.paimon.types.VectorType; import java.io.Serializable; +import java.math.BigInteger; import java.nio.ByteBuffer; import java.util.Arrays; import java.util.LinkedHashSet; @@ -76,7 +77,7 @@ public class ZIndexer implements Serializable { public ZIndexer(RowType rowType, List<String> orderColumns, int varTypeSize) { List<String> fields = rowType.getFieldNames(); fieldsIndex = new int[orderColumns.size()]; - int varTypeCount = 0; + int total = 0; for (int i = 0; i < fieldsIndex.length; i++) { int index = fields.indexOf(orderColumns.get(i)); if (index == -1) { @@ -87,15 +88,10 @@ public class ZIndexer implements Serializable { + fields); } fieldsIndex[i] = index; - - if (isVarType(rowType.getFieldTypes().get(index))) { - varTypeCount++; - } + total += zBytes(rowType.getFieldTypes().get(index), varTypeSize); } this.functionSet = constructFunctionMap(rowType.getFields(), varTypeSize); - this.totalBytes = - PRIMITIVE_BUFFER_SIZE * (this.fieldsIndex.length - varTypeCount) - + varTypeSize * varTypeCount; + this.totalBytes = total; } private static boolean isVarType(DataType dataType) { @@ -105,6 +101,26 @@ public class ZIndexer implements Serializable { || dataType instanceof VarBinaryType; } + /** + * Bytes the z-value reserves for a column. A DECIMAL gets a width that holds any unscaled value + * of its precision, so it keeps full ordering resolution; 8 bytes cannot, and projecting into + * them collapses ordinary wide-decimal values to one key. + */ + private static int zBytes(DataType type, int varTypeSize) { + if (isVarType(type)) { + return varTypeSize; + } + if (type instanceof DecimalType) { + return decimalBytes(((DecimalType) type).getPrecision()); + } + return PRIMITIVE_BUFFER_SIZE; + } + + /** Two's-complement byte width that holds any unscaled value with {@code precision} digits. */ + private static int decimalBytes(int precision) { + return BigInteger.TEN.pow(precision).bitLength() / 8 + 1; + } + public void open() { this.reuse = ByteBuffer.allocate(totalBytes); functionSet.forEach(RowProcessor::open); @@ -138,8 +154,7 @@ public class ZIndexer implements Serializable { public static RowProcessor zmapColumnToCalculator(DataField field, int index, int varTypeSize) { DataType type = field.type(); return new RowProcessor( - type.accept(new TypeVisitor(index, varTypeSize)), - isVarType(type) ? varTypeSize : PRIMITIVE_BUFFER_SIZE); + type.accept(new TypeVisitor(index, varTypeSize)), zBytes(type, varTypeSize)); } /** Type Visitor to generate function map from row column to z-index. */ @@ -239,18 +254,39 @@ public class ZIndexer implements Serializable { public ZProcessFunction visit(DecimalType decimalType) { final InternalRow.FieldGetter fieldGetter = InternalRow.createFieldGetter(decimalType, fieldIndex); + // Encode the unscaled value as a fixed-width, sign-flipped big-endian two's complement. + // The width holds any value of this precision, so the encoding is order-preserving + // under the unsigned comparison a z-value gets and keeps full resolution: small + // separated values, their negatives, and values past the long range all get distinct + // keys. An 8-byte projection cannot, since one wide-decimal column exceeds 64 bits and + // every value below the shift collapses to a single key. + final int width = decimalBytes(decimalType.getPrecision()); + final byte[] nullBytes = new byte[width]; return (row, reuse) -> { Object o = fieldGetter.getFieldOrNull(row); - return o == null - ? NULL_BYTES - : ZOrderByteUtils.byteTruncateOrFill( - ((Decimal) o).toUnscaledBytes(), - PRIMITIVE_BUFFER_SIZE, - reuse) - .array(); + if (o == null) { + return nullBytes; + } + Decimal decimal = (Decimal) o; + BigInteger unscaled = + decimal.isCompact() + ? BigInteger.valueOf(decimal.toUnscaledLong()) + : decimal.toBigDecimal().unscaledValue(); + return orderedDecimalBytes(unscaled, width, reuse); }; } + private static byte[] orderedDecimalBytes( + BigInteger unscaled, int width, ByteBuffer reuse) { + byte[] buffer = ZOrderByteUtils.reuse(reuse, width).array(); + Arrays.fill(buffer, 0, width, unscaled.signum() < 0 ? (byte) 0xFF : (byte) 0x00); + byte[] magnitude = unscaled.toByteArray(); + System.arraycopy(magnitude, 0, buffer, width - magnitude.length, magnitude.length); + // Flip the sign bit so signed order becomes unsigned lexicographic order. + buffer[0] ^= (byte) 0x80; + return buffer; + } + @Override public ZProcessFunction visit(TinyIntType tinyIntType) { return (row, reuse) -> diff --git a/paimon-common/src/test/java/org/apache/paimon/sort/zorder/TestZOrderByteUtil.java b/paimon-common/src/test/java/org/apache/paimon/sort/zorder/TestZOrderByteUtil.java index 48e4a87467..8a8a6a4bea 100644 --- a/paimon-common/src/test/java/org/apache/paimon/sort/zorder/TestZOrderByteUtil.java +++ b/paimon-common/src/test/java/org/apache/paimon/sort/zorder/TestZOrderByteUtil.java @@ -18,17 +18,22 @@ package org.apache.paimon.sort.zorder; +import org.apache.paimon.data.Decimal; import org.apache.paimon.data.GenericRow; +import org.apache.paimon.types.DataField; import org.apache.paimon.types.DataType; import org.apache.paimon.types.DataTypes; +import org.apache.paimon.types.DecimalType; import org.apache.paimon.types.RowType; import org.junit.Test; import org.testcontainers.shaded.com.google.common.primitives.UnsignedBytes; +import java.math.BigDecimal; import java.nio.ByteBuffer; import java.util.Arrays; import java.util.Comparator; +import java.util.List; import java.util.Random; import static org.apache.paimon.utils.RandomUtil.randomBytes; @@ -94,6 +99,125 @@ public class TestZOrderByteUtil { return result.toString(); } + /** Decimal z-values must order by value and stay distinct from the null sentinel. */ + @Test + public void testZIndexerDecimalOrdering() { + RowType rowType = + new RowType( + Arrays.asList( + new DataField(0, "a", new DecimalType(20, 2)), + new DataField(1, "b", new DecimalType(20, 2)))); + ZIndexer indexer = new ZIndexer(rowType, Arrays.asList("a", "b")); + indexer.open(); + + // Two rows whose decimal z-values must order by value: (-1, 0) then (0, 1). + // Old code fed minimal two's-complement arrays into unsigned comparison, + // making -1 > 1 and 0 collide with the null sentinel. + GenericRow row1 = new GenericRow(2); + row1.setField(0, Decimal.fromBigDecimal(new BigDecimal("-1.00"), 20, 2)); + row1.setField(1, Decimal.fromBigDecimal(new BigDecimal("0.00"), 20, 2)); + GenericRow row2 = new GenericRow(2); + row2.setField(0, Decimal.fromBigDecimal(new BigDecimal("0.00"), 20, 2)); + row2.setField(1, Decimal.fromBigDecimal(new BigDecimal("1.00"), 20, 2)); + + byte[] z1 = Arrays.copyOf(indexer.index(row1), indexer.size()); + byte[] z2 = Arrays.copyOf(indexer.index(row2), indexer.size()); + // Interleaved bits: column a dominates the high bits of the z-value. + assertThat(compareUnsigned(z1, z2)).isLessThan(0); + + GenericRow rowNull = new GenericRow(2); + rowNull.setField(0, null); + rowNull.setField(1, null); + byte[] zNull = Arrays.copyOf(indexer.index(rowNull), indexer.size()); + // The null sentinel (all-zero bytes) sorts below every real value. + assertThat(compareUnsigned(zNull, z1)).isLessThan(0); + assertThat(compareUnsigned(zNull, z2)).isLessThan(0); + + // A large magnitude still orders correctly against the small positives: the fixed-width + // encoding holds the whole unscaled value rather than projecting it into 8 bytes. + GenericRow big = new GenericRow(2); + big.setField(0, Decimal.fromBigDecimal(new BigDecimal("92233720368547758.08"), 20, 2)); + big.setField(1, Decimal.fromBigDecimal(new BigDecimal("0.00"), 20, 2)); + byte[] zBig = Arrays.copyOf(indexer.index(big), indexer.size()); + assertThat(compareUnsigned(zBig, z2)).isGreaterThan(0); + + // Its negative counterpart orders below the small negatives, but still above the null + // sentinel. + Decimal minUnscaled = + Decimal.fromBigDecimal(new BigDecimal("-92233720368547758.08"), 20, 2); + GenericRow negativeBig = new GenericRow(2); + negativeBig.setField(0, minUnscaled); + negativeBig.setField(1, minUnscaled); + byte[] zNegativeBig = Arrays.copyOf(indexer.index(negativeBig), indexer.size()); + assertThat(compareUnsigned(zNull, zNegativeBig)).isLessThan(0); + assertThat(compareUnsigned(zNegativeBig, z1)).isLessThan(0); + } + + /** + * High-precision decimals must keep full clustering resolution: ordinary small values, their + * negatives, and values past the long range all get distinct, correctly ordered z-keys. + */ + @Test + public void testZIndexerHighPrecisionDecimalClustering() { + RowType rowType = + new RowType( + Arrays.asList( + new DataField(0, "a", new DecimalType(38, 18)), + new DataField(1, "b", new DecimalType(38, 18)))); + ZIndexer indexer = new ZIndexer(rowType, Arrays.asList("a", "b")); + indexer.open(); + + // Strictly ascending values, including small ones well below an 8-byte projection's + // overflow point (which collapsed 0..18 to a single key), sub-unit fractions, negatives, + // and a value past Long.MAX_VALUE. Each must get a strictly greater z-key than the last. + List<String> ascending = + Arrays.asList( + "-90", + "-10", + "-2", + "-1", + "0", + "0.001", + "0.002", + "1", + "2", + "3", + "10", + "20", + "90", + "12345678901234567890.123456789012345678"); + byte[] previous = null; + for (String value : ascending) { + byte[] key = highPrecisionKey(indexer, value); + if (previous != null) { + assertThat(compareUnsigned(previous, key)).isLessThan(0); + } + previous = key; + } + + // Null sorts below every real value. + byte[] zNull = Arrays.copyOf(indexer.index(new GenericRow(2)), indexer.size()); + assertThat(compareUnsigned(zNull, highPrecisionKey(indexer, "-90"))).isLessThan(0); + } + + private static byte[] highPrecisionKey(ZIndexer indexer, String value) { + GenericRow row = new GenericRow(2); + row.setField(0, Decimal.fromBigDecimal(new BigDecimal(value), 38, 18)); + row.setField(1, Decimal.fromBigDecimal(new BigDecimal("0"), 38, 18)); + return Arrays.copyOf(indexer.index(row), indexer.size()); + } + + private static int compareUnsigned(byte[] left, byte[] right) { + for (int i = 0; i < left.length && i < right.length; i++) { + int a = left[i] & 0xFF; + int b = right[i] & 0xFF; + if (a != b) { + return Integer.compare(a, b); + } + } + return Integer.compare(left.length, right.length); + } + /** * Ordered-bytes transforms must preserve value order across negatives for floats and doubles. */
