sfc-gh-aloeser commented on code in PR #16972: URL: https://github.com/apache/iceberg/pull/16972#discussion_r3721606114
########## format/spec.md: ########## @@ -345,9 +346,55 @@ For example, a struct column `point` with fields `x` (default 0) and `y` (defaul Default values are attributes of fields in schemas and serialized with fields in the JSON format. See [Appendix C](#appendix-c-json-serialization). +#### Collations + +A `string` field may carry a **collation**, an attribute that changes how the field's values are compared and ordered without changing how they are stored. Collations enable case-insensitive, accent-insensitive, and locale-aware comparison and sorting. A collation only affects comparison: the stored value is returned unchanged (a value written as `'appLE'` is read back as `'appLE'`). + +This change defines exactly two things: the `collation` annotation on string fields, and collation-aware file pruning through collation metric fields stored in `content_stats`. It does not give collation semantics to any other part of the table format, because collation order and equality are not stable across collation implementation versions or engines, while the rest of the format must be deterministic. Specifically: + +* Byte-order `lower_bounds`/`upper_bounds`, partition transforms (including `truncate`), and `bucket`/hash all operate on the binary UTF-8 value and are collation-unaware. Collation-equal but byte-distinct values may therefore land in different partitions or buckets, and a reader must not use partition or bucket pruning to eliminate candidates for a predicate evaluated under a collation. +* Equality-delete matching and identifier-field equality are binary value equality by field id; a `collation` annotation does not make either collation-aware. An engine that needs a collation-dependent delete must resolve it to position deletes or an explicit set of values. +* This change does not define collation-aware sort orders. + +SQL-level comparison, equality, ordering, grouping, and distinctness are the engine's responsibility. Engines read the `collation` annotation and apply their own semantics; they must not infer broader behavior from the table-format metadata alone. + +A collation may be attached to any field of `string` type, top-level or nested: as a `collation` attribute on a struct field, or as an `element-collation`, `key-collation`, or `value-collation` attribute on an enclosing `list` or `map` (see [Appendix C](#appendix-c-json-serialization)). It may be attached only to `string` types. A string field with no collation defaults to UTF-8 byte-order comparison, the behavior of all prior versions. Nesting does not change how collation bounds work: because every nested string position has its own field id, a collation on a nested string is annotated and given collation metrics exactly as a top-level string field (see [Collation Bounds](#collation-bounds)). + +A collation is identified by a provider-qualified name of the form `<provider>.<name>`, for example `icu.en_US-ci`. The provider names the library that defines the collation (`icu` for collations defined by the [Unicode Collation Algorithm](https://unicode.org/reports/tr10/) over [CLDR](https://cldr.unicode.org/) locale data; other providers may define engine-specific collations such as case-folding variants). The name selects a locale and optional modifiers for case sensitivity (`ci`/`cs`), accent sensitivity (`ai`/`as`), trimming, and case folding. + +The bare name `utf8` is reserved for UTF-8 byte-order comparison and is the one collation name exempt from the `<provider>.<name>` form. It is exactly equivalent to omitting the `collation` attribute: readers and writers must treat a field annotated `utf8` and a field with no collation identically, and adding or removing an explicit `utf8` on an already-uncollated field is a no-op that does not change comparison semantics. A field with collation `utf8` (or no collation) uses the byte-order `lower_bounds`/`upper_bounds` directly and must not declare `collation-metrics`. + +The schema stores the collation **name without a version**, so any engine that supports the collation can read the table. UCA, DUCET, CLDR, and ICU collation orders are [not stable across versions](https://unicode.org/reports/tr10/#Non-Goals), so collation-aware metrics carry the implementation version they were produced under (see below) and a reader uses them only when it can produce the same order. + +The version is the identifier the provider uses to version its collation order, and must be a value that changes only when the collation order can change, so that a byte-exact match between two engines means they produce the same order. For the `icu` provider this is the [ICU collator version](https://unicode-org.github.io/icu/userguide/collation/architecture.html#versioning) reported for the collation (which folds in the UCA, DUCET, and CLDR versions and the tailoring), formatted as ICU reports it. Two engines built against the same collation data therefore report the same version and can share bounds; a provider release that does not change any order reports the same version, so existing bounds stay usable and no new metric field is needed. The version is provider-defined and is compared as an opaque string: a reader treats bounds as usable only on an exact `(collation, version)` match and otherwise scans, so a mismatch degrades pruning but never correctness. + +##### Collation Bounds + +Because a collation can reorder values (for example `'a' < 'B'` under a case-insensitive collation, but `'a' > 'B'` in byte order), byte-order bounds — the v3 `lower_bounds`/`upper_bounds` maps and the byte-order bounds in `content_stats` — cannot be used to evaluate predicates on a collated column. Collation-aware bounds are stored instead as ordinary [content stats](#content-stats), under dedicated **collation metric fields** declared in the schema. + +A collated field declares its collation metric fields as a `collation-metrics` list on the field (see [Appendix C](#appendix-c-json-serialization)). Each entry has: + +| Key | Type | Description | +|-----|------|-------------| +| `id` | `int` | Field id whose `content_stats` struct holds the collation-aware bounds. It is allocated from the table's column id space using `last-column-id`; it is not a data column and carries only stats | +| `collation` | `string` | Collation the bounds are produced for, e.g. `icu.en_US-ci` | +| `version` | `string` | Provider's collation version the bounds were selected under (for `icu`, the ICU collator version); compared as an opaque string on read. See [Collations](#collations) | + +The bounds themselves are an ordinary [field stats struct](#field-statistics) in `content_stats` under the metric field's id: its `lower_bound` and `upper_bound` are `string` values holding the file's minimum and maximum **under the collation order** — the original values, not collation sort keys (sort keys are not stable across implementation versions) — and `tight_bounds` indicates whether they are exact. Collation bounds must be tight: because there is no defined successor under an arbitrary collation order, a writer that cannot store the exact minimum and maximum must omit the bound rather than approximate it. A field may declare several collation metric entries — typically one per `(collation, version)` — so a single file can serve readers pinned to different versions during an upgrade. Review Comment: > Collation bounds must be tight: because there is no defined successor under an arbitrary collation order, a writer that cannot store the exact minimum and maximum must omit the bound rather than approximate it. How would we define tight? Does it mean we do not allow truncation? I'm worried that omitting bounds could negatively impact performance ########## format/spec.md: ########## @@ -345,9 +346,55 @@ For example, a struct column `point` with fields `x` (default 0) and `y` (defaul Default values are attributes of fields in schemas and serialized with fields in the JSON format. See [Appendix C](#appendix-c-json-serialization). +#### Collations + +A `string` field may carry a **collation**, an attribute that changes how the field's values are compared and ordered without changing how they are stored. Collations enable case-insensitive, accent-insensitive, and locale-aware comparison and sorting. A collation only affects comparison: the stored value is returned unchanged (a value written as `'appLE'` is read back as `'appLE'`). + +This change defines exactly two things: the `collation` annotation on string fields, and collation-aware file pruning through collation metric fields stored in `content_stats`. It does not give collation semantics to any other part of the table format, because collation order and equality are not stable across collation implementation versions or engines, while the rest of the format must be deterministic. Specifically: + +* Byte-order `lower_bounds`/`upper_bounds`, partition transforms (including `truncate`), and `bucket`/hash all operate on the binary UTF-8 value and are collation-unaware. Collation-equal but byte-distinct values may therefore land in different partitions or buckets, and a reader must not use partition or bucket pruning to eliminate candidates for a predicate evaluated under a collation. +* Equality-delete matching and identifier-field equality are binary value equality by field id; a `collation` annotation does not make either collation-aware. An engine that needs a collation-dependent delete must resolve it to position deletes or an explicit set of values. +* This change does not define collation-aware sort orders. + +SQL-level comparison, equality, ordering, grouping, and distinctness are the engine's responsibility. Engines read the `collation` annotation and apply their own semantics; they must not infer broader behavior from the table-format metadata alone. + +A collation may be attached to any field of `string` type, top-level or nested: as a `collation` attribute on a struct field, or as an `element-collation`, `key-collation`, or `value-collation` attribute on an enclosing `list` or `map` (see [Appendix C](#appendix-c-json-serialization)). It may be attached only to `string` types. A string field with no collation defaults to UTF-8 byte-order comparison, the behavior of all prior versions. Nesting does not change how collation bounds work: because every nested string position has its own field id, a collation on a nested string is annotated and given collation metrics exactly as a top-level string field (see [Collation Bounds](#collation-bounds)). + +A collation is identified by a provider-qualified name of the form `<provider>.<name>`, for example `icu.en_US-ci`. The provider names the library that defines the collation (`icu` for collations defined by the [Unicode Collation Algorithm](https://unicode.org/reports/tr10/) over [CLDR](https://cldr.unicode.org/) locale data; other providers may define engine-specific collations such as case-folding variants). The name selects a locale and optional modifiers for case sensitivity (`ci`/`cs`), accent sensitivity (`ai`/`as`), trimming, and case folding. + +The bare name `utf8` is reserved for UTF-8 byte-order comparison and is the one collation name exempt from the `<provider>.<name>` form. It is exactly equivalent to omitting the `collation` attribute: readers and writers must treat a field annotated `utf8` and a field with no collation identically, and adding or removing an explicit `utf8` on an already-uncollated field is a no-op that does not change comparison semantics. A field with collation `utf8` (or no collation) uses the byte-order `lower_bounds`/`upper_bounds` directly and must not declare `collation-metrics`. + +The schema stores the collation **name without a version**, so any engine that supports the collation can read the table. UCA, DUCET, CLDR, and ICU collation orders are [not stable across versions](https://unicode.org/reports/tr10/#Non-Goals), so collation-aware metrics carry the implementation version they were produced under (see below) and a reader uses them only when it can produce the same order. + +The version is the identifier the provider uses to version its collation order, and must be a value that changes only when the collation order can change, so that a byte-exact match between two engines means they produce the same order. For the `icu` provider this is the [ICU collator version](https://unicode-org.github.io/icu/userguide/collation/architecture.html#versioning) reported for the collation (which folds in the UCA, DUCET, and CLDR versions and the tailoring), formatted as ICU reports it. Two engines built against the same collation data therefore report the same version and can share bounds; a provider release that does not change any order reports the same version, so existing bounds stay usable and no new metric field is needed. The version is provider-defined and is compared as an opaque string: a reader treats bounds as usable only on an exact `(collation, version)` match and otherwise scans, so a mismatch degrades pruning but never correctness. + +##### Collation Bounds + +Because a collation can reorder values (for example `'a' < 'B'` under a case-insensitive collation, but `'a' > 'B'` in byte order), byte-order bounds — the v3 `lower_bounds`/`upper_bounds` maps and the byte-order bounds in `content_stats` — cannot be used to evaluate predicates on a collated column. Collation-aware bounds are stored instead as ordinary [content stats](#content-stats), under dedicated **collation metric fields** declared in the schema. + +A collated field declares its collation metric fields as a `collation-metrics` list on the field (see [Appendix C](#appendix-c-json-serialization)). Each entry has: + +| Key | Type | Description | +|-----|------|-------------| +| `id` | `int` | Field id whose `content_stats` struct holds the collation-aware bounds. It is allocated from the table's column id space using `last-column-id`; it is not a data column and carries only stats | +| `collation` | `string` | Collation the bounds are produced for, e.g. `icu.en_US-ci` | +| `version` | `string` | Provider's collation version the bounds were selected under (for `icu`, the ICU collator version); compared as an opaque string on read. See [Collations](#collations) | + +The bounds themselves are an ordinary [field stats struct](#field-statistics) in `content_stats` under the metric field's id: its `lower_bound` and `upper_bound` are `string` values holding the file's minimum and maximum **under the collation order** — the original values, not collation sort keys (sort keys are not stable across implementation versions) — and `tight_bounds` indicates whether they are exact. Collation bounds must be tight: because there is no defined successor under an arbitrary collation order, a writer that cannot store the exact minimum and maximum must omit the bound rather than approximate it. A field may declare several collation metric entries — typically one per `(collation, version)` — so a single file can serve readers pinned to different versions during an upgrade. Review Comment: > — the original values, not collation sort keys (sort keys are not stable across implementation versions) that is a good point 👍 unfortunately, original strings are not stable across versions, ICU does not guarantee stable ordering, either. If I understand correctly, this means that original strings provide no pruning benefits compared to sort keys, in the general case. The situation would be different if we had some additional metrics on the data, though. Most of the ordering changes are limited to a small range of codepoints. If we had metadata proving that a file contains none of those (e.g., because it only contains ASCII), we could probably even prune across versions, which I'd consider a point in favor of sort keys -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
