z_order.hpp File Reference

Z-order curve (Morton code) encoding/decoding for multi-dimensional indexing. More...

#include "signet/types.hpp"
#include <algorithm>
#include <cstdint>
#include <cstring>
#include <numeric>
#include <stdexcept>
#include <string>
#include <string_view>
#include <vector>

Go to the source code of this file.

Classes
struct	signet::forge::z_order::ZOrderColumn
	Descriptor for a single column of raw typed data used by ZOrderSorter. More...
struct	signet::forge::z_order::ZOrderSorter
	Computes a permutation vector that reorders rows by Z-order (Morton) key. More...

Namespaces
namespace	signet
namespace	signet::forge
namespace	signet::forge::z_order
	Z-order curve (Morton code) utilities for spatial sort keys.

Functions
uint32_t	signet::forge::z_order::normalize_int32 (int32_t v)
	Normalize a signed 32-bit integer to an unsigned 32-bit integer that preserves the original sort order (flip the sign bit).
uint64_t	signet::forge::z_order::normalize_int64 (int64_t v)
	Normalize a signed 64-bit integer to uint64_t (flip sign bit).
uint32_t	signet::forge::z_order::normalize_float (float v)
	Normalize a 32-bit float to uint32_t preserving total order.
uint64_t	signet::forge::z_order::normalize_double (double v)
	Normalize a 64-bit double to uint64_t preserving total order.
uint32_t	signet::forge::z_order::normalize_string (std::string_view v)
	Normalize a string to uint32_t by taking the first 4 bytes in big-endian order.
uint32_t	signet::forge::z_order::truncate_to_32 (uint64_t v)
	Truncate a uint64_t to uint32_t by extracting the upper 32 bits.
uint64_t	signet::forge::z_order::morton_2d (uint32_t x, uint32_t y)
	Interleave bits of two uint32_t values into a single uint64_t Morton code (2D).
void	signet::forge::z_order::deinterleave_2d (uint64_t code, uint32_t &x, uint32_t &y)
	Deinterleave a 2D Morton code back into its two uint32_t components.
std::vector< uint8_t >	signet::forge::z_order::morton_nd (const std::vector< uint32_t > &normalized, size_t bits_per_col=32)
	Generalized N-column Morton code via round-robin bit interleaving (MSB-first).

Detailed Description

Z-order curve (Morton code) encoding/decoding for multi-dimensional indexing.

Provides three layers of functionality:

1. Value normalization – type-specific mappings that preserve sort order when the result is interpreted as an unsigned integer.
2. Morton code bit-interleaving – 2D fast path (uint64_t key) and N-dimensional generalized path (byte-array key) for 2-8 columns.
3. ZOrderSorter – computes a permutation vector that reorders rows by their Z-order (Morton) key, improving spatial locality for multi-column range queries and enabling better data skipping through column/page min-max statistics.

std::vector<ZOrderColumn> cols = {
    { PhysicalType::INT32, int_data.data(), int_data.size() },
    { PhysicalType::FLOAT, float_data.data(), float_data.size() }
};
auto perm = ZOrderSorter::sort(num_rows, cols);
// Apply perm to reorder rows before writing to Parquet.

See also

SplitBlockBloomFilter for another data-skipping technique.

Definition in file z_order.hpp.