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]

Reply via email to