Skip to content

About

Pure-Python implementation of starfix Arrow logical hasher

Resources

Stars

0 stars

Watchers

0 watching

Forks

Latest commit

 

History

48 Commits

Folders and files

Repository files navigation

starfix-python

Pure-Python implementation of the starfix Arrow logical hasher.

Produces stable SHA-256 hashes of Arrow schemas, tables, record batches and arrays that are:

  • Byte-identical to the Rust implementation: every vector of the shared golden file (tests/golden/format2_v0.5.json, generated by Rust) is matched. The one documented exception concerns stored extension-type metadata that pyarrow cannot observe (see Extension types).
  • Column-order and struct-field-order independent by default. Both orders can be made part of the hash (see Options). Nothing else is reordered: row order and list element order are always hashed.
  • Batch-split independent: splitting rows into batches, slicing, or adding empty batches does not change the hash; adding or removing rows does.
  • Lossless: a null struct differs from a struct whose fields are all null, null rows are counted, every list records its lengths, and the row count is hashed.

Hash format 2 (starfix 0.5). Every hash starts with the 3-byte format number 00 00 02. All hashes differ from those of starfix 0.4 and earlier (format 1, 00 00 01); see Hash format.

Installation

pip install starfix

Requires Python >= 3.10 and pyarrow >= 19.

Usage

import pyarrow as pa
from starfix import ArrowDigester

schema = pa.schema([
    pa.field("id", pa.int32(), nullable=False),
    pa.field("value", pa.float64(), nullable=True),
])

# Hash a full table
table = pa.table({"id": [1, 2, 3], "value": [1.1, 2.2, 3.3]}, schema=schema)
digest = ArrowDigester.hash_table(table)          # 35 bytes: 00 00 02 + SHA-256

# Streaming: feed record batches incrementally (same hash as hash_table)
digester = ArrowDigester(schema)
for batch in table.to_batches():
    digester.update(batch)
digest = digester.finalize()

# A schema, a single record batch, or a single array
ArrowDigester.hash_schema(schema)
ArrowDigester.hash_record_batch(table.to_batches()[0])
ArrowDigester.hash_array(pa.array([1, 2, 3], pa.int32()))

Options

Keyword-only, all False by default, the same names as the Rust HasherConfig fields, accepted by ArrowDigester(...), hash_schema, hash_record_batch, hash_table and hash_array (hash_array has no include_metadata).

Option Effect
ordered_columns The order of the top-level columns is part of the hash.
ordered_struct_fields The order of struct fields, at every depth (struct children, list and fixed-size list elements, map keys and values, dictionary values), is part of the hash.
include_metadata Schema- and field-level Arrow metadata is part of the hash. A schema without metadata hashes the same either way.
# A DataFrame-like value whose column order and struct field order are part of its identity
digest = ArrowDigester.hash_table(table, ordered_columns=True, ordered_struct_fields=True)
  • Leave the order options off to identify data independent of how columns or struct fields happen to be ordered. Turn them on when order is part of the value's identity, as for a DataFrame, or a pa.StructArray whose type struct<a, b> differs from struct<b, a>.
  • Hashes taken with different order options never coincide, even when order cannot matter.
  • With include_metadata, metadata is keyed by each field's node path (column c, struct child c/x, list or fixed-size list element c/, map key and value m//key and m//value). Extension types are hashed as their storage type; with include_metadata their ARROW:extension:name and ARROW:extension:metadata are hashed too (see Extension types).
  • hash_array has no include_metadata on purpose: an array carries no schema or field metadata. It accepts a ChunkedArray (hashed like the combined array).
  • A digester is not thread-safe; a batch rejected by update leaves it unchanged.

Fixed-size lists

FixedSizeList<T, n> data is hashed (any size n, also 0; at any depth; dictionary-encoded; as the storage of extension types such as arrow.fixed_shape_tensor). It is its own type: it never hashes like List<T> / LargeList<T> with the same values, like a fixed-size list of another size, or like FixedSizeBinary(n). The items under a null slot (or under a slot masked by a null struct) never affect the hash, and neither do child positions past the last slot; a null of a non-nullable item there is accepted, a visible one is rejected.

Extension types

With include_metadata, an extension type's field metadata is hashed as stored, including ARROW:extension:name and ARROW:extension:metadata (an absent ARROW:extension:metadata counts as ""). pyarrow hides these two keys for extension types it has registered and rebuilds the type from them, so starfix-python hashes what pyarrow can observe:

  • Unregistered extension types: the stored keys are hashed verbatim. Identical to Rust.
  • Python-defined pa.ExtensionType subclasses (registered with pa.register_extension_type): the keys are re-added from extension_name and __arrow_ext_serialize__(). Identical to Rust only if the serializer reproduces the stored bytes exactly. Otherwise the hash differs from Rust's, and it also depends on whether the type is registered in the hashing process.
  • pyarrow's built-in canonical extension types (arrow.uuid, arrow.json, arrow.bool8, arrow.opaque, arrow.fixed_shape_tensor, arrow.variable_shape_tensor, depending on the pyarrow version): they have no __arrow_ext_serialize__ in Python, so both keys are read from the field exported through the Arrow C data interface (field.__arrow_c_schema__()), which carries the serialization pyarrow reconstructs from its own definition; pyarrow also rebuilds their storage type. Their hash is therefore defined only when the stored ARROW:extension:metadata is byte-identical to that serialization and the stored storage type is the one pyarrow rebuilds (the form every Arrow implementation writes). Known stored forms that differ from Rust: arrow.json stored with {} (pyarrow reconstructs ""); arrow.opaque or tensor metadata JSON with another key order or with whitespace; a fixed-shape tensor stored over a non-nullable item field.

Rejected inputs

ValueError is raised, in every mode, for:

  • a schema in which two nodes share a path: duplicate column names, duplicate field names within a struct, or a name containing / that aliases another node (a column "a/b" next to a struct column a with a child b). A / that aliases nothing ("km/h") is fine;
  • ListView, LargeListView, Union and RunEndEncoded types;
  • hashing data of a schema that contains Null, Map, Interval, Utf8View or BinaryView (their schemas hash; their data does not), also inside a fixed-size list, whatever the number of rows;
  • a non-nullable field holding a null that no enclosing struct null explains;
  • with include_metadata: a duplicate metadata key on a field or the schema, or explicit ARROW:extension:* keys that conflict with the field's registered extension type;
  • streaming: a batch whose schema differs from the digester's. Physically different but equivalent types (Utf8/LargeUtf8, Binary/LargeBinary, List/LargeList, dictionary and plain values) are accepted; reordered columns or struct fields are accepted unless the matching order option is on.

TypeError is raised for a wrong container type, for example a Table passed to hash_record_batch or a RecordBatch passed to hash_table.

Platforms

Hash format 2 is defined over little-endian buffers (all lengths, counts and values are little-endian). starfix-python hashes Arrow buffers as stored, which is correct on little-endian hosts (x86-64, ARM64 and nearly all others). On a big-endian host every format-2 entry point raises NotImplementedError instead of producing wrong hashes. The Rust crate has the same restriction.

Performance

Hashing takes time linear in the data size and works on Arrow buffers. Leaf values are fed to the digest in bounded chunks without copying the payload, but auxiliary memory is not bounded: it grows with the number of visited elements and list items (validity bitmaps, list lengths, list parent indices), and the values of a dictionary of struct, list or fixed-size list values are materialized (decoded with take) before they are traversed. A fixed-size list column without null slots is hashed from one zero-copy slice of its child; with null slots, its items are selected in chunks of about one million items. Fixed-width, Boolean and list columns hash at tens of millions of rows per second. String and binary columns hash at about 3 to 5 million rows per second, because each value is visited in Python. Each update call also costs a few microseconds per column, to check the batch's schema. starfix-python is a pure-Python implementation; the Rust crate is faster on string-heavy data.

Hash format

The byte layout is specified in starfix's docs/byte-layout-spec.md. The first three bytes of every hash are the format number:

Format Prefix starfix Notes
1 00 00 01 ≤ 0.4 Lost information for some inputs (Booleans, nullable structs, lists of nullable lists or structs, row counts, and in Python a list of numeric dictionary values).
2 00 00 02 0.5 Lossless layout, the two order options, rejections in every mode.

Format-1 hashes of starfix-python 0.4 are still available through the frozen legacy 0.4 mode.

Legacy 0.4 mode

from starfix.legacy.v0_4 import ArrowDigester as LegacyArrowDigester  # hash format 1

old_key = LegacyArrowDigester.hash_table(table)   # 00 00 01 ..., as starfix-python 0.4.x

starfix.legacy.v0_4 reproduces starfix-python 0.4.0 byte for byte: same API (ArrowDigester(schema, *, include_metadata=False), update, finalize, hash_schema, hash_record_batch, hash_table, hash_array), same hashes, same exceptions. It exists only to read or match data hashed by starfix-python 0.4.x (for example to find stored data under its old key). Never hash new data with it: use starfix.ArrowDigester.

It is frozen: never fixed and never extended (no order options). Its code is the 0.4.0 module verbatim except one performance-only line (list columns hash in linear time; no hash changes), kept apart from the format-2 code. Its output is pinned by the restored 0.4.0 tests and golden file, and by a differential test against the released starfix==0.4.0 package.

Known defects, kept on purpose (all fixed in format 2):

  • Booleans are bit-packed per batch without a count: [true] and [true, false, false] in a non-nullable column hash the same, and splitting rows into batches can change the hash.
  • A null struct hashes like a struct whose fields are all null, and null struct rows vanish under non-nullable fields.
  • A list whose element is a nullable list loses its own lengths; a list of nullable structs does not distinguish a null element.
  • The row count of zero-column tables and empty structs is not hashed.
  • A list of dictionary-encoded fixed-width values (for example list<dictionary<int32, int64>>) hashes the dictionary indices instead of the values.

starfix-python 0.4 also differed from the Rust crate 0.4 on these inputs. The legacy mode keeps the Python behaviour, because that is what data hashed with starfix-python 0.4 used:

Input starfix-python 0.4 (legacy mode) Rust starfix 0.4
schema with a Map column Map JSON without the value type and keys_sorted entries field (key and value) and keys_sorted
include_metadata with metadata on map fields value field metadata at m/; key ignored entries field metadata at m/
hash_array of a struct with non-ASCII field names names escaped as \uXXXX raw UTF-8
schema with Null, Interval, Utf8View or BinaryView columns raises NotImplementedError hashes
list of dictionary-encoded fixed-width values hashes the dictionary indices hashes the values
streamed batch whose schema differs from the digester's accepted rejected

License

MIT OR Apache-2.0

About

Pure-Python implementation of starfix Arrow logical hasher

Resources

Stars

0 stars

Watchers

0 watching

Forks

Releases

Packages

Used by

Contributors

Languages