pvary commented on code in PR #16961: URL: https://github.com/apache/iceberg/pull/16961#discussion_r4079916630
########## format/index-spec.md: ########## @@ -0,0 +1,730 @@ +--- +title: "Index Spec" +--- +<!-- + - Licensed to the Apache Software Foundation (ASF) under one or more + - contributor license agreements. See the NOTICE file distributed with + - this work for additional information regarding copyright ownership. + - The ASF licenses this file to You under the Apache License, Version 2.0 + - (the "License"); you may not use this file except in compliance with + - the License. You may obtain a copy of the License at + - + - http://www.apache.org/licenses/LICENSE-2.0 + - + - Unless required by applicable law or agreed to in writing, software + - distributed under the License is distributed on an "AS IS" BASIS, + - WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + - See the License for the specific language governing permissions and + - limitations under the License. + --> +# Iceberg Index Specification + +## Background and Motivation + +An index is most valuable when it is a property of the table rather than of the engine that built it. This +specification defines a common format for index metadata and a common storage architecture for index data, so that any +engine can build an index, maintain it, and use it to plan queries against the table. + +## Goals + +* **Portability** -- An index written by one engine will be readable by any other engine. +* **Separation** -- Index metadata will be committed separately from table metadata. Building and maintaining an index + will not rewrite the table. +* **Optionality** -- Indexes will be optional. Engines may ignore an index they do not support. +* **Consistency** -- Each index snapshot will index exactly the live rows of one source table snapshot. + +## Overview + +An index is recorded in an index metadata file that contains the index definition and a set of index snapshots. Each +index snapshot corresponds to a snapshot of the source table and references the index data for that state. + +Index metadata files and index data files are immutable. Every update writes a new metadata file. An update that adds an +index snapshot also writes a new tracking file and may reuse existing region files. Every update is committed by an +atomic swap of the index metadata file, as defined in [Commits and Concurrency](#commits-and-concurrency). + +The index data of a snapshot is organized as a [tracking file](#tracking-file) that lists a set of +[region files](#region-files): + +```text +Index Metadata + | + +-- Index Snapshot(s) + | + +-- Tracking File + | + +-- Region Files +``` + +## Specification + +### Terms + +* **Index** -- A structure that accelerates retrieval of rows from a source table. +* **Index snapshot** -- The state of an index for a single snapshot of the source table. +* **Index entry** -- The values produced by the index fields for one indexed row of the source table. +* **Clustering key** -- The tuple of values that determines the position of an index entry within an index snapshot. +* **Tracking file** -- A file that lists the region files of an index snapshot; one per index snapshot. +* **Region file** -- A file that stores the index entries for a range of clustering keys; a subset of an index snapshot. + +### Paths in Metadata + +Path strings stored in index metadata are classified and resolved as defined by +[paths in metadata](spec.md#paths-in-metadata) in the table specification. Relative paths are resolved against the +index `location`, which must be an absolute path. + +### Index Definition + +An index is defined by a source table, an index type, identity fields, materialized fields, non-materialized fields, and +a cluster spec. The definition is fixed when the index is created and must not change for the lifetime of the index, so +region files remain readable through every index snapshot that references them. A different definition requires a new +index. + +Index properties are not part of the definition. They configure how an index is written and maintained and may be +changed by a commit. + +A table may have multiple indexes of the same index type. + +#### Index Type + +The index type defines the logical category of an index and the class of queries it accelerates. + +| Type | Description | +|----------|-----------------------------------------------------------------------------------------------------------------------| +| `SCALAR` | Accelerates point lookups on clustered fields, and range filters when the clustering expressions are order preserving | + +This specification defines a single index type, `SCALAR`. Future specifications may define additional types, see +[Future Extensions](#future-extensions). + +Writers must write `type` in upper case. Readers must match it case-insensitively. A reader that does not implement an +index type must ignore the index and read the source table directly; it must not fail. + +#### Index Fields + +An index field defines one value of an index entry, produced for an indexed row of the source table. An index declares +three lists of index fields: [identity fields](#identity-fields) and [materialized fields](#materialized-fields), whose +values are stored in [region files](#region-files), and [non-materialized fields](#non-materialized-fields), which are +represented only by statistics in [tracking file entries](#tracking-file-entry). Every index field has a field ID that +must be unique across the three lists. + +#### Identity Fields + +`identity-fields` is a non-empty list of unique source table field IDs. Each entry must reference a data field. +[Metadata columns](spec.md#reserved-field-ids) are not allowed. Each listed field is stored in the +[region files](#region-files) under its own field ID and takes its type from the schema of the source table snapshot +that an index snapshot references. + +Every source table field referenced by an expression field in the [cluster spec](#cluster-spec) must be an identity +field. + +#### Expression Fields + +Both [materialized fields](#materialized-fields) and [non-materialized fields](#non-materialized-fields) are expression +fields; they differ only in where their values are kept. + +The value of an expression field is produced by evaluating an +[Iceberg value expression](expressions-spec.md#value-expressions) for an indexed row of the source table. +An expression field has the following fields: + +| Requirement | Field name | Type | Description | +|-------------|---------------|-------------------|--------------------------------------------------------------| +| _required_ | `field-id` | `int` | ID that uniquely identifies the index field | +| _required_ | `type` | `expr-value` | Expression field representation | +| _required_ | `data-type` | Iceberg type | Type produced by the expression | +| _required_ | `expr` | JSON expression | Value expression that produces the field, serialized as JSON | + +Each expression field must satisfy the following requirements: + +- `expr` must contain only ID references to source table fields or + [metadata columns](spec.md#reserved-field-ids). Named references must not be used. The `_deleted`, `_change_type`, + `_change_ordinal`, and `_commit_snapshot_id` metadata columns must not be referenced, and neither must the + `file_path`, `pos`, and `row` columns of delete files. +- `expr` must be deterministic and must produce the declared `data-type`. +- `field-id` must not be a [reserved field ID](spec.md#reserved-field-ids). + +Expressions are serialized using the [JSON serialization](expressions-spec.md#appendix-b-json-serialization) defined by +the expressions specification. Types are serialized using the [type serialization](spec.md#schemas) defined by the table +specification. + +##### Materialized Fields + +`materialized-fields` is a list of expression fields whose values are stored in the [region files](#region-files). +Evaluating the identity fields and the materialized fields for one indexed row produces one region file row. + +##### Non-Materialized Fields + +`non-materialized-fields` is a list of expression fields whose row values are not stored in region files. Only their +field statistics are stored, in [tracking file entries](#tracking-file-entry). + +#### Cluster Spec + +`cluster-spec` is a list of field IDs from `identity-fields`, `materialized-fields`, and `non-materialized-fields`. The +values of the referenced fields, in list order, form the clustering key of an indexed row and determine the row's +position in the index, as defined in [Clustering and Ordering](#clustering-and-ordering). The list must not be empty. +Every referenced field must have a primitive type. + +### Index Metadata + +The index metadata file stores the index definition and snapshot history. It is encoded as JSON. + +#### Index Metadata File + +The index metadata file has the following fields: + +| Requirement | Field name | Type | Description | +|-------------|---------------------------|----------------------------|----------------------------------------------------------------------------------------------------| +| _required_ | `format-version` | `int` | Index format version; must be `1` | +| _required_ | `index-uuid` | `string` | Stable UUID assigned at creation | +| _required_ | `table-uuid` | `string` | UUID of the indexed table | +| _required_ | `location` | `string` | Index root location | +| _required_ | `last-updated-ms` | `long` | Timestamp when the index was last updated (ms from epoch) [1] | +| _required_ | `type` | `string` | Logical index type | +| _required_ | `identity-fields` | `list<int>` | Source table fields stored in region files, see [Identity Fields](#identity-fields) | +| _optional_ | `materialized-fields` | `list<expression-field>` | Expression fields stored in region files, see [Materialized Fields](#materialized-fields) | +| _optional_ | `non-materialized-fields` | `list<expression-field>` | Fields stored only in tracking statistics, see [Non-Materialized Fields](#non-materialized-fields) | +| _required_ | `cluster-spec` | `list<int>` | Field IDs that define clustering, see [Cluster Spec](#cluster-spec) | +| _optional_ | `properties` | `map<string, string>` | Index properties applicable for every snapshot | +| _optional_ | `snapshots` | `list<index-snapshot>` | Index snapshots [2] | +| _optional_ | `metadata-log` | `list<metadata-log-entry>` | Previous index metadata files, see [Metadata Log](#metadata-log) | +| _optional_ | `encryption-keys` | `list<encryption-key>` | Encryption keys used by the index, see [Encryption Keys](#encryption-keys) | + +A missing optional list must be read as an empty list. + +Notes: + +1. Each index metadata file should update `last-updated-ms` just before writing. +2. An index that has not been built yet has no snapshots. +3. Index names are not stored in index metadata. It is the catalog's responsibility to map index names to metadata file + locations. +4. How the indexes of a table are discovered is out of scope for this specification and is defined by the catalog + specification. + +#### Index Snapshot + +An index snapshot is an immutable version of the index data generated from a specific source table snapshot. It +references a complete set of index files through the location of a single [tracking file](#tracking-file). + +An index snapshot must index exactly the live rows of the referenced table snapshot. + +| Requirement | Field name | Type | Description | +|-------------|----------------------------|-----------------------|------------------------------------------------------------------------------| +| _required_ | `snapshot-id` | `long` | Index snapshot identifier | +| _required_ | `source-table-snapshot-id` | `long` | Source table snapshot | +| _required_ | `timestamp-ms` | `long` | Timestamp when the index snapshot was created (ms from epoch) | +| _required_ | `tracking-file` | `string` | Location of the tracking file | +| _optional_ | `properties` | `map<string, string>` | Snapshot properties specific to this snapshot | +| _optional_ | `key-id` | `string` | ID of the encryption key that holds the tracking file key metadata | + +Each `snapshot-id` must be unique within the `snapshots` list. Engines locate index data by matching +`source-table-snapshot-id`. More than one index snapshot may reference the same source table snapshot, and an engine may +use any of the matching index snapshots. + +#### Metadata Log + +`metadata-log` records the index metadata files that preceded the current one. A commit should append an entry for the +metadata file it replaces. The number of entries to retain is controlled by the index property +`write.metadata.previous-versions-max`, and a commit drops the oldest entries beyond that limit. When +`write.metadata.delete-after-commit.enabled` is true, a commit also deletes the dropped metadata files. + +| Requirement | Field name | Type | Description | +|-------------|-----------------|----------|-----------------------------------------------------------------| +| _required_ | `metadata-file` | `string` | Location of the index metadata file | +| _required_ | `timestamp-ms` | `long` | `last-updated-ms` of the index metadata file at `metadata-file` | + +#### Encryption Keys + +An index must not store indexed values with weaker protection than its source table. If the source table snapshot that +an index snapshot indexes is encrypted, indicated by the snapshot's `key-id` as defined by the table specification, the +tracking file and the region files of that index snapshot must be encrypted. + +Index metadata is not encrypted, so keys are never stored in plain form. Keys used for index encryption are tracked in +index metadata as a list named `encryption-keys`, using the [encryption keys](spec.md#encryption-keys) structure defined +by the table specification. The format of encrypted key metadata is determined by the index's encryption scheme and can +be a wrapped format specific to the KMS provider. + +The `key-id` of an index snapshot must reference a `key-id` in the index metadata `encryption-keys` list. The +`encrypted-key-metadata` of the referenced entry is the key metadata of the snapshot's tracking file, which in turn +holds the key metadata of the region files. + +### Commits and Concurrency + +Index metadata is immutable. Every update, whether adding a snapshot, dropping a snapshot, or changing index properties, +must produce a new index metadata file with a unique name. + +A commit replaces the current index metadata file with the new one. The swap must be atomic and must succeed only if the +current metadata file is still the file the writer started from, identified by name. If a newer metadata file has been +committed since the writer read the metadata, the commit must be rejected. + +A writer whose commit is rejected must not overwrite the newer metadata. It may re-read the latest committed metadata +and retry the update on top of it, or discard the attempted update. + +Index maintenance may be performed synchronously with the table commit that produces a new source-table snapshot, or +asynchronously by a separate maintenance process. A catalog may enforce transactional commits that atomically update +both the table and the index, guaranteeing that every committed table snapshot has a corresponding index snapshot. When +an index is updated asynchronously, the index may lag behind the table and engines must reconcile the index snapshot +against the source-table snapshot they intend to read. + +### Index Data + +#### Clustering and Ordering + +The cluster spec defines an ordering over all index entries of an index snapshot. Index entries must be partitioned into +ranges of clustering key values that do not overlap, and each range must be stored in a separate region file. A region +boundary must fall at a change in clustering key, so all index entries that share a clustering key are stored in the +same region file. + +Index entries are ordered by the [clustering key](#cluster-spec) produced for each indexed row. The key is compared by +the fields in `cluster-spec` order: index entries are compared by the value of the first field, and the next field is +used only when the preceding values compare as equal. Each field is ordered ascending. + +Primitive values are compared using the rules defined in the +[expressions specification](expressions-spec.md#comparisons), extended so that null and NaN values have a defined +position in the ordering: + +- `null` values are ordered before all other values (nulls-first) +- `float` and `double` values are ordered `-NaN` < `-Infinity` < `-value` < `-0.0` < `0.0` < `value` < `Infinity` < + `NaN`, as defined by [sorting](spec.md#sorting) in the table specification + +#### Tracking File + +The tracking file contains metadata of all region files belonging to the index snapshot. It may be stored using any +supported metadata file format. + +##### Tracking File Entry + +Each tracking file contains a collection of tracking file entries. A tracking file entry describes a single region file +tracked by an index snapshot. The fields are the subset of the V4 [data file fields](spec.md#data-file-fields) that are +relevant to planning queries against the index. + +Tracking file entries must be stored in the [clustering order](#clustering-and-ordering) of the region files they +describe, which is the ascending order of the `group_max_value` statistics recorded for the cluster fields in the +[content statistics](#content-statistics). + +| Requirement | Field id, name | Type | Description | +|-------------|-------------------------------|-----------|------------------------------------------------------------------------------------------------------| +| _required_ | **`100 file_path`** | `string` | Full URI of the referenced region file | +| _required_ | **`101 file_format`** | `string` | File format name, such as `parquet`, `avro`, or `orc` | +| _required_ | **`103 record_count`** | `long` | Number of records contained in the referenced region file | +| _required_ | **`104 file_size_in_bytes`** | `long` | Total file size in bytes | +| _required_ | **`146 content_stats`** | `struct` | Field statistics and clustering bounds for the referenced region file, used for planning and pruning | +| _optional_ | **`131 key_metadata`** | `binary` | Implementation-specific key metadata, used for region file encryption | + +##### Content Statistics + +The `content_stats` structure stores field statistics following the [content stats](spec.md#content-stats) rules of the +table specification. Each stored struct derives its ID and metric types from the index field's ID and type and contains +the metrics supported for that type. + +The following metrics are required: + +| Index field | Required metrics | +|--------------------------|-------------------------------------------------| +| Field in `cluster-spec` | `lower_bound`, `upper_bound`, `group_max_value` | +| Non-materialized field | `lower_bound`, `upper_bound` | +| Other materialized field | None | + +All other metrics are optional. Statistics for a non-materialized field describe the rows that the region file indexes, +not values stored in it. + +###### Group Max Value + +The field statistics struct for each field in `cluster-spec` must contain a `group_max_value` metric at offset `8` from +the field's stats `base-id`. It has the index field's data type and is optional so that it can represent a null +clustering value. Unlike other metrics, a null `group_max_value` is a null clustering value, not an unknown statistic. + +The `group_max_value` metrics, read in `cluster-spec` order, must be the exact clustering key of the last index entry in +the region file according to the [clustering order](#clustering-and-ordering). They must not be truncated or rounded. +Readers use these keys as inclusive region file upper bounds. The clustering keys of a region file are strictly greater +than the `group_max_value` key of the preceding tracking file entry, so tracking file entries must be read in order. + +#### Region Files + +Region files must be valid Iceberg data files stored in Parquet, Avro, or ORC, following the +[format-specific requirements](spec.md#appendix-a-format-specific-requirements) of the table specification. Those +requirements define how each type is encoded and where a column's field ID is recorded in the file. + +Each region file row is one index entry and holds the [identity field](#identity-fields) and +[materialized field](#materialized-fields) values of one indexed row. Index entries within a region file must be stored +in the [clustering order](#clustering-and-ordering). Index entries that share a clustering key may be stored in any +order. + +##### Region Schema + +The region schema is constructed from `identity-fields` followed by `materialized-fields`. The result is a struct +containing one field for each index field in those lists, with fields appearing in that order. An identity field takes +its ID and type from the source table field it names; a materialized field takes its ID from `field-id` and its type +from `data-type`. + +Names of region schema fields are generated by the writer and are not defined by this specification. Users of the index +must not rely on them; readers must match region file columns by field ID. + +## Appendix A: Rationale + +Iceberg standardizes the index lifecycle, snapshot relationship, and the minimum metadata needed for safe cross-engine +use. Beyond that minimum, engines remain free to ignore unsupported indexes, use exact snapshot matches only, or +implement more advanced stale-index and incremental-query logic. The index type is a first filter: it identifies the +class of index, so an engine can skip a type it does not implement without inspecting the definition. + +### Expression-based Definitions + +Beyond the source columns it indexes directly, an index is defined by expressions, which keeps the definition open +ended. Expressions must be deterministic for the same reason clustering must be stable: an expression that depends on +`random` or on the evaluation time would place entries at positions that cannot be reproduced. + +Each expression field contains the expression that produces its value. A field that indexes a source table field as is +carries no expression: it is declared by its ID in `identity-fields`. Materialized field values are stored in region +files, while non-materialized field values are represented only by tracking statistics. The cluster spec lists field +IDs in comparison order without repeating their expressions. Engines match query expressions to index fields to +determine whether the index applies and which stored field contains a result. Because expressions reference only fields +and metadata columns of the source table, each index field can be evaluated directly from a source row. + +That is also why only some metadata columns can be referenced. An index snapshot indexes the live rows of a single +table snapshot, so a row has one position and one file, and the value of a column such as `_deleted` is fixed for every +indexed row. The changelog columns describe a row's change between two snapshots rather than a value within one, and +the delete file columns describe a delete file record rather than a source row, so neither can be evaluated from the +row an index entry is built from. + +### Clustering Order and Pruning + +Each field in the cluster spec determines part of the position of an entry, so its result type is limited to values +that Iceberg can order. Primitives are ordered by the rules the expressions specification already defines. +Multi-component clustering keys are compared field by field, which is an extension of the sort orders in the Iceberg +table specification. Structs, lists, and maps are excluded because Iceberg does not define ordering for lists and maps, +and a struct is represented as separate index fields instead. + +Clustering keys do not have to be unique. Region boundaries fall only where the clustering key changes, so all entries +that share a key are in one region file and a lookup resolves to a single region file. Because a region file holds every +entry with a given clustering key, the order of those entries within the file has no effect on planning or on region +file bounds, and the specification leaves it to the writer. + +The clustering order makes the index usable at two levels: region files can be pruned without being opened, and the +entries of a region file that is opened can be located without reading all of it. + +Region files hold non-overlapping clustering ranges, so the `group_max_value` statistics in the tracking file are enough Review Comment: For me, @liurenjie1024's comment seems more about skew - which I answered there (key index should have a single row for every key - or very few in cases of problems, so have skew on the key) About the write complexity question - we discussed this in detail on the index sync and the decision was that an index should be optimized for reads. If we start optimizing for writes, we very soon lose any gains coming from having the index at all. If you think strongly about this then I suggest to join the sink, so we can reopen the question. -- 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]
