lipengming opened a new issue, #11162: URL: https://github.com/apache/paimon/issues/11162
### Search before asking - [x] I searched in the [issues](https://github.com/apache/paimon/issues) and found nothing similar. Searched `graph index`, `graph`, `graphar`, `property graph`, `adjacency`, `two-hop`, `node map`, `cypher`, `gremlin` (issues and PRs). No existing proposal for a graph index on Paimon tables; the only hits were unrelated (vector index, R-tree file index, a REST "dependency graph"). Cross-project search in `apache/incubator-graphar` also found no Paimon integration discussion. ### Motivation Graph-shaped data is common in lakehouse tables: risk-control association networks, fraud-ring detection, entity profiles, recommendations. The three dominant access patterns are: 1. **Attribute entry**: given `phone = '...'`, locate the node ids; 2. **One-hop adjacency**: given a node, return its outgoing/incoming neighbours plus aggregated edge payload (count, amount, last event time); 3. **Two/K-hop expansion**: semi-join / BFS from a node. Today these are served by full scans plus engine-side joins. At 10B-edge scale the latency and cost are unacceptable (minutes to hours, full shuffle per query), while the raw data already lives in Paimon. Paimon already contains every mechanism needed to express this as an **index over existing tables** rather than a new storage format: - primary-key table + `global-index.btree/bitmap` secondary indexes for "value → primary key"; - aggregation merge-engine primary-key table for "adjacency + pre-aggregated payload", with primary-key prefix scans; - deletion vectors and snapshot isolation for correctness of updates; - system tables and `CALL` procedures for observability and lifecycle. ### Proposed solution Add a **declarative graph index**: graph semantics are declared as table options, a versioned expansion translates them into existing Paimon mechanisms, and a small SDK exposes traversal primitives. No new file format, no new index family, no new merge semantics, no change to the base-table commit protocol. #### 1. Declaration (additive table options) Vertex (single-column PK table, PK = node id): ```sql 'graph.vertex.enabled' = 'true', 'graph.vertex.id-field' = 'id', 'graph.vertex.node-map.fields' = 'name,phone,city:bitmap', -- btree (default) / bitmap family 'graph.vertex.node-map.update-action' = 'maintain' -- or 'freeze' ``` Edge (append event table, no PK): ```sql 'graph.edge.enabled' = 'true', 'graph.edge.src-field' = 'src_id', 'graph.edge.dst-field' = 'dst_id', 'graph.edge.src-vertex' = 'person', 'graph.edge.dst-vertex' = 'merchant', 'graph.edge.reverse' = 'true', 'graph.edge.aggregates' = 'amount:sum;tx_time:last_non_null_value;*:count' ``` Runtime options: `graph.index.backend` (`auto`/`pk-index`/`table`), `graph.index.search-mode` (`fast`/`full`/`detail`), watermark interval, build parallelism, lag alert threshold. #### 2. Expansion (versioned rules, backend-pluggable) - **Node side, pk-index backend (default)**: expand node-map fields into `global-index.btree.index-columns` / `global-index.bitmap.index-columns` on the vertex table itself. Index files commit atomically with data (snapshot-consistent), maintained by compaction and deletion vectors. Requires fixed bucket + deletion vectors. - **Node side, table backend (compat)**: standalone `{vertex}__node_map` deduplicate PK table with `(prop_name, prop_value, node_id)` and an order-preserving `prop_value` encoding, for dynamic-bucket tables or older versions. `auto` degrades automatically and annotates the actual backend. - **Edge side (one rule)**: `{edge}__edge` and `{edge}__edge_rev`, unpartitioned aggregation-merge-engine PK tables keyed `(src, dst)` / `(dst, src)` with `bucket-key` on the leading endpoint, so one-hop adjacency is a single-bucket PK prefix scan. `*:count` expands to `cnt BIGINT` + `fields.cnt.aggregate-function = sum` (there is no `count` aggregate function in the merge engine); other functions map 1:1 to official aggregate functions. #### 3. Lifecycle and management - Batch backfill fixed at base snapshot `S` (`OPTIONS('scan.snapshot-id'='S')`); - streaming micro-batch consumes `(watermark, latest]` and writes per-pair partial aggregates (the merge engine composes them with stored totals); - coverage watermark refreshed per checkpoint in a `graph_index_status` table and mirrored onto the base table for `$graph_indexes`; - `CALL sys.create_graph_index(...)` / `CALL sys.drop_graph_index(...)` with `LOGICAL` (default, keep data, stop maintenance/routing), `PURGE` (remove expanded declarations / index tables) and `dry_run`; - `$graph_indexes` system table exposes `index_type/backend/index_table/fields/direction/status/coverage_watermark/lag_seconds/build_options`; - read modes: `fast` (index snapshot only), `full` (catch up the watermark gap at query time and merge), `detail` (full base-vs-index reconciliation). #### 4. Traversal SDK (new `paimon-graph` module, public API only) `nodeMap(field).eq()/between().scanToBitmap()`, `adj(direction).from().project().degreeCap()`, `vertex().lookup()`, `twoHop(...)` (semi-join + top-N intermediate vertices), `kHop(...)` (BFS with a visited bitmap), plus `DegreeCap`/`ResultCap` guards and typed payload access. #### 5. Public interfaces and compatibility Purely additive: new `graph.*` config options, new `@Public` SDK classes, one system table, two procedures. No new index family, file format or merge function; base-table commit protocol, index manifest and merge-engine semantics are untouched. Disabling `graph.index.enabled` degrades to plain Paimon tables. ### Comparison with Apache GraphAr [Apache GraphAr](https://github.com/apache/incubator-graphar) (incubating) is an **open standard data file format for graph storage and retrieval**, plus libraries to read/write/transform it. It defines metadata (`.graph.yml`) that describes vertex/edge schemas, chunk sizes and column groups, and stores a property graph as chunked physical tables: vertex tables, `adjList` tables, edge-property tables and offset tables, with four edge layouts (ordered/unordered by source/dest, i.e. CSR/CSC/COO-like). Its goal is system-independent import/export and efficient bulk loading of graph data into graph processing/query engines; it ships C++/Java/Go/Rust/Python libraries and Spark tooling. The two projects solve different problems and are complementary rather than competing: | Dimension | Paimon graph index (this proposal) | Apache GraphAr | | --- | --- | --- | | Primary goal | Transactional, incrementally maintained **index layer** over live lakehouse tables | Standardized **graph file format** for storage, import/export and bulk analytics | | Data ownership | Stays in the Paimon tables (plus derived index tables in the same catalog) | A separate physical graph representation written by an external job | | Storage format | Existing Paimon tables: PK secondary index (btree/bitmap) and aggregation-merge-engine PK tables | New format: metadata + chunked vertex/adjList/edge-property/offset files (Parquet/ORC) | | Node identity | Paimon primary key (no remapping, stable across updates) | Internal vertex id `0..n-1` assigned per vertex type | | Update semantics | Incremental: new snapshots consumed by a micro-batch; attribute updates handled by DV + compaction; edge aggregates are merged (`sum`, `last_non_null_value`, ...) | Bulk rewrite / re-export; not bound to transactional table commits | | Consistency / freshness | Snapshot-scoped for the pk-index backend; watermark + `fast`/`full` modes for edge and table backends | Consistency determined by the export job; file-level snapshot of the graph | | Query surface | `nodeMap`, one-hop adjacency, two-hop, k-hop (`<=3` practical) via a small SDK; SQL access to index tables | Read APIs in multiple languages to load the graph into a compute engine (BFS/PageRank/GNN etc.) | | Management | Table options + `CALL` procedures + `$graph_indexes` + LOGICAL/PURGE/dry_run | CLI/libraries to generate/validate GraphAr datasets | | Best fit | Point-to-neighbour queries on fresh relational data inside the lakehouse (second-level latency, minute-level freshness) | Offline/batch graph analytics, dataset interchange between systems, graph engine ingestion | | Relationship | Could **export** a Paimon graph binding to GraphAr for deep analytics | Could **import** a GraphAr dataset into Paimon tables as an initial load | **Why not just use GraphAr as the index?** 1. GraphAr is an interchange/storage format, not an index over live tables: serving a point lookup or a one-hop query would still require exporting and keeping a second copy in sync, with a separate lifecycle and consistency model. 2. It has no incremental maintenance bound to Paimon snapshots; every update becomes an export/rewrite problem. 3. It does not express aggregation-reduce semantics (`sum(amount)`, `last_non_null_value(tx_time)` per pair); representing pre-aggregated edges would duplicate data that Paimon's aggregation merge engine already provides. 4. Our target is *freshness + transactional consistency inside the lakehouse*, which is exactly what Paimon snapshots, deletion vectors and merge engines give us for free. **Where GraphAr is the better answer**: multi-hop/global graph algorithms, GNN training pipelines, cross-system dataset exchange, or when a CSR/CSC-like adjacency layout is needed for deep traversal. A Paimon → GraphAr bridge (export the declared vertex/edge tables, or an index-backed adjacency pair table, into GraphAr) looks like a natural follow-up collaboration and avoids duplicating format work in Paimon. We would be happy to align with the GraphAr community on that. ### Alternatives considered 1. **Use GraphAr directly** — rejected as an online index (second copy, no incremental maintenance, no aggregation semantics); complementary as an export target. 2. **External graph database** (Nebula/TuGraph) — a second system with its own consistency, cost and lineage problems. 3. **Query-time joins only** — not viable at 10B edges; this is the status quo the proposal replaces. 4. **Data-evolution row-id global index** — row-id addressing does not express "value → primary key" reverse lookup, mutable-row delete/insert, or cross-row reduce semantics. 5. **New index family / new file format** — rejected: PK btree/bitmap already covers the node side, aggregation merge engine covers the edge side; adding a new format would duplicate GraphAr's scope. ### Current status / POC A working proof of concept is on the fork branch [`lipengming/paimon:feature/graph-index`](https://github.com/lipengming/paimon/tree/feature/graph-index) (10 incremental commits), covering declaration + validation, both planners, create/backfill pipeline, `$graph_indexes`, the SDK primitives, streaming maintenance (core micro-batch + Flink job), two-hop/k-hop, full/detail modes, and Spark/Flink `create_graph_index`/`drop_graph_index` procedures. Test coverage on that branch: 98 core graph tests, 30 SDK tests, 7 Flink tests and 2 Spark tests, all green; checkstyle/spotless pass for the touched modules. Known v1 limitations: BIGINT node ids in the SDK; adjacency tables unpartitioned (full-history accumulation); node-map table backend backfill/diff maintenance not yet implemented; field-level node-map drop is binding-level; benchmark on LDBC SNB is still pending. Two implementation findings from this fork are worth reporting separately (Flink statement-set source reuse drops dynamic time-travel options; `Table` has no catalog reference, so a Table-level API needs a catalog argument). ### Open questions / feedback requested 1. **Scope**: is a first-class declarative graph index in scope for Paimon core, with the traversal SDK kept in a separate `paimon-graph` module (split-friendly), or should the whole thing live outside the project? 2. **PIP**: we believe this qualifies as a major change (new public API, config options, system table, procedures) and plan to open a PIP and a `[DISCUSS]` thread on `[email protected]`. Is this the right granularity and sequencing? 3. **Adjacency layout**: is a normal aggregation-merge-engine PK table the right carrier, or should multi-hop/analytics workloads be pushed to a CSR-like layout (potentially GraphAr) instead? Our target for v1 is one-hop/≤3-hop with pre-aggregated payload; deeper traversals go to batch engines. 4. **Naming/options**: feedback on the `graph.vertex.*` / `graph.edge.*` / `graph.index.*` surface and on `$graph_indexes` columns. 5. **GraphAr bridge**: would the community be interested in a follow-up Paimon → GraphAr export path (or a joint discussion with the GraphAr project) for deep graph analytics? ### Anything else? A detailed design document (expansion rules, validation matrix, consistency model, lifecycle, cost estimates) is prepared and will be submitted as the PIP; we are happy to share it earlier in the discussion thread. We are also willing to split the work into reviewable PRs (declaration/planner → create/backfill → system table → SDK → maintenance → procedures). - [x] I'm willing to submit a PR! -- 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]
