Metadata-Version: 2.5
Name: starfix
Version: 0.5.0
Summary: Pure-Python implementation of starfix Arrow logical hasher
Author: nauticalab
License-Expression: MIT OR Apache-2.0
Keywords: arrow,hashing
Classifier: Programming Language :: Python :: 3
Requires-Python: >=3.10
Requires-Dist: pyarrow>=19.0.0
Description-Content-Type: text/markdown

# starfix-python

Pure-Python implementation of the [starfix](https://github.com/nauticalab/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](#extension-types)).
- **Column-order and struct-field-order independent** by default. Both orders can be made part
  of the hash (see [Options](#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](#hash-format).

## Installation

```bash
pip install starfix
```

Requires Python >= 3.10 and pyarrow >= 19.

## Usage

```python
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. |

```python
# 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](#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-04-mode).

## Legacy 0.4 mode

```python
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
