org.apache.paimon.utils

Class ZOrderByteUtils

java.lang.Object

org.apache.paimon.utils.ZOrderByteUtils

public class ZOrderByteUtils
extends Object

Within Z-Ordering the byte representations of objects being compared must be ordered, this requires several types to be transformed when converted to bytes. The goal is to map object's whose byte representation are not lexicographically ordered into representations that are lexicographically ordered. Bytes produced should be compared lexicographically as unsigned bytes, big-endian.

All types except for String are stored within an 8 Byte Buffer

Most of these techniques are derived from https://aws.amazon.com/blogs/database/z-order-indexing-for-multifaceted-queries-in-amazon-dynamodb-part-2/

Field Summary

Fields

Modifier and Type	Field and Description
static byte[]	NULL_BYTES
static int	PRIMITIVE_BUFFER_SIZE

Method Summary

Modifier and Type	Method and Description
static ByteBuffer	byteTruncateOrFill(byte[] val, int length, ByteBuffer reuse) Return a bytebuffer with the given bytes truncated to length, or filled with 0's to length depending on whether the given bytes are larger or smaller than the given length.
static ByteBuffer	doubleToOrderedBytes(double val, ByteBuffer reuse) Doubles are treated the same as floats in floatToOrderedBytes(float, ByteBuffer).
static ByteBuffer	floatToOrderedBytes(float val, ByteBuffer reuse) IEEE 754 : “If two floating-point numbers in the same format are ordered (say, x < y), they are ordered the same way when their bits are reinterpreted as sign-magnitude integers.”
static byte[]	interleaveBits(byte[][] columnsBinary, int interleavedSize)
static byte[]	interleaveBits(byte[][] columnsBinary, int interleavedSize, ByteBuffer reuse) Interleave bits using a naive loop.
static ByteBuffer	intToOrderedBytes(int val, ByteBuffer reuse) Signed ints do not have their bytes in magnitude order because of the sign bit.
static ByteBuffer	longToOrderedBytes(long val, ByteBuffer reuse) Signed longs are treated the same as the signed ints in intToOrderedBytes(int, ByteBuffer).
static ByteBuffer	reuse(ByteBuffer reuse, int length)
static ByteBuffer	shortToOrderedBytes(short val, ByteBuffer reuse) Signed shorts are treated the same as the signed ints in intToOrderedBytes(int, ByteBuffer).
static ByteBuffer	stringToOrderedBytes(String val, int length, ByteBuffer reuse) Strings are lexicographically sortable BUT if different byte array lengths will ruin the Z-Ordering.
static ByteBuffer	tinyintToOrderedBytes(byte val, ByteBuffer reuse) Signed tiny ints are treated the same as the signed ints in intToOrderedBytes(int, ByteBuffer).

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

PRIMITIVE_BUFFER_SIZE

public static final int PRIMITIVE_BUFFER_SIZE

See Also:

Constant Field Values

NULL_BYTES

public static final byte[] NULL_BYTES

Method Detail

intToOrderedBytes

public static ByteBuffer intToOrderedBytes(int val,
                                           ByteBuffer reuse)

Signed ints do not have their bytes in magnitude order because of the sign bit. To fix this, flip the sign bit so that all negatives are ordered before positives. This essentially shifts the 0 value so that we don't break our ordering when we cross the new 0 value.

longToOrderedBytes

public static ByteBuffer longToOrderedBytes(long val,
                                            ByteBuffer reuse)

Signed longs are treated the same as the signed ints in intToOrderedBytes(int, ByteBuffer).

shortToOrderedBytes

public static ByteBuffer shortToOrderedBytes(short val,
                                             ByteBuffer reuse)

Signed shorts are treated the same as the signed ints in intToOrderedBytes(int, ByteBuffer).

tinyintToOrderedBytes

public static ByteBuffer tinyintToOrderedBytes(byte val,
                                               ByteBuffer reuse)

Signed tiny ints are treated the same as the signed ints in intToOrderedBytes(int, ByteBuffer).

floatToOrderedBytes

public static ByteBuffer floatToOrderedBytes(float val,
                                             ByteBuffer reuse)

IEEE 754 : “If two floating-point numbers in the same format are ordered (say, x < y), they are ordered the same way when their bits are reinterpreted as sign-magnitude integers.”

Which means floats can be treated as sign magnitude integers which can then be converted into lexicographically comparable bytes.

doubleToOrderedBytes

public static ByteBuffer doubleToOrderedBytes(double val,
                                              ByteBuffer reuse)

Doubles are treated the same as floats in floatToOrderedBytes(float, ByteBuffer).

stringToOrderedBytes

public static ByteBuffer stringToOrderedBytes(String val,
                                              int length,
                                              ByteBuffer reuse)

Strings are lexicographically sortable BUT if different byte array lengths will ruin the Z-Ordering. (ZOrder requires that a given column contribute the same number of bytes every time). This implementation just uses a set size to for all output byte representations. Truncating longer strings and right padding 0 for shorter strings.

byteTruncateOrFill

public static ByteBuffer byteTruncateOrFill(byte[] val,
                                            int length,
                                            ByteBuffer reuse)

Return a bytebuffer with the given bytes truncated to length, or filled with 0's to length depending on whether the given bytes are larger or smaller than the given length.

interleaveBits

public static byte[] interleaveBits(byte[][] columnsBinary,
                                    int interleavedSize)

interleaveBits

public static byte[] interleaveBits(byte[][] columnsBinary,
                                    int interleavedSize,
                                    ByteBuffer reuse)

Interleave bits using a naive loop. Variable length inputs are allowed but to get a consistent ordering it is required that every column contribute the same number of bytes in each invocation. Bits are interleaved from all columns that have a bit available at that position. Once a Column has no more bits to produce it is skipped in the interleaving.

Parameters:

columnsBinary - an array of ordered byte representations of the columns being ZOrdered

interleavedSize - the number of bytes to use in the output

Returns:

the columnbytes interleaved

reuse

public static ByteBuffer reuse(ByteBuffer reuse,
                               int length)