amduat/tier1/enc-asl-tgk-exec-plan-1.md

# ENC/ASL-TGK-EXEC-PLAN/1 — Execution Plan Encoding

Status: Draft
Owner: Architecture
Version: 0.1.0
SoT: No
Last Updated: 2025-01-17
Linked Phase Pack: N/A
Tags: [encoding, execution, tgk]

<!-- Source: /amduat-api/tier1/enc-asl-tgk-exec-plan-1.md | Canonical: /amduat/tier1/enc-asl-tgk-exec-plan-1.md -->

**Document ID:** `ENC/ASL-TGK-EXEC-PLAN/1`
**Layer:** L2 — Execution plan encoding (bytes-on-disk)

**Depends on (normative):**

* `ASL/TGK-EXEC-PLAN/1`

**Informative references:**

* `ENC/ASL-CORE-INDEX/1`

© 2025 Niklas Rydberg.

## License

Except where otherwise noted, this document (text and diagrams) is licensed under
the Creative Commons Attribution 4.0 International License (CC BY 4.0).

The identifier registries and mapping tables (e.g. TypeTag IDs, HashId
assignments, EdgeTypeId tables) are additionally made available under CC0 1.0
Universal (CC0) to enable unrestricted reuse in implementations and derivative
specifications.

Code examples in this document are provided under the Apache License 2.0 unless
explicitly stated otherwise. Test vectors, where present, are dedicated to the
public domain under CC0 1.0.

---

## 0. Conventions

The key words **MUST**, **MUST NOT**, **REQUIRED**, **SHOULD**, and **MAY** are to be interpreted as in RFC 2119.

ENC/ASL-TGK-EXEC-PLAN/1 defines the byte-level encoding for serialized execution plans. It does not define operator semantics.

**Implementation note:** The core library encodes/decodes plans but does not
ship a plan executor; execution is delegated to higher-layer components.

---

## 1. Operator Type Enumeration

```c
typedef enum {
    OP_SEGMENT_SCAN,
    OP_INDEX_FILTER,
    OP_MERGE,
    OP_PROJECTION,
    OP_TGK_TRAVERSAL,
    OP_AGGREGATION,
    OP_LIMIT_OFFSET,
    OP_SHARD_DISPATCH,
    OP_SIMD_FILTER,
    OP_TOMBSTONE_SHADOW
} operator_type_t;
```

---

## 2. Operator Flags

```c
typedef enum {
    OP_FLAG_NONE       = 0x00,
    OP_FLAG_PARALLEL   = 0x01, // shard or SIMD capable
    OP_FLAG_OPTIONAL   = 0x02  // optional operator (acceleration)
} operator_flags_t;
```

---

## 3. Snapshot Range Structure

```c
typedef struct {
    uint64_t logseq_min;  // inclusive
    uint64_t logseq_max;  // inclusive
} snapshot_range_t;
```

**Note:** `logseq_max` corresponds to the `LogPosition` upper bound referenced
by `ASL/TGK-EXEC-PLAN/1`.

---

## 4. Operator Parameter Union

```c
typedef struct {
    // SegmentScan parameters
    struct {
        uint8_t is_asl_segment;      // 1 = ASL, 0 = TGK
        uint64_t segment_start_id;
        uint64_t segment_end_id;
    } segment_scan;

    // IndexFilter parameters
    struct {
        uint32_t artifact_type_tag;
        uint8_t  has_type_tag;
        uint32_t edge_type_key;
        uint8_t  has_edge_type;
        uint8_t  role;               // 0=none, 1=from, 2=to, 3=both
    } index_filter;

    // Merge parameters
    struct {
        uint8_t deterministic;       // 1 = logseq ascending + canonical key
    } merge;

    // Projection parameters
    struct {
        uint8_t project_artifact_id;
        uint8_t project_tgk_edge_id;
        uint8_t project_node_id;
        uint8_t project_type_tag;
    } projection;

    // TGKTraversal parameters
    struct {
        uint64_t start_node_id;
        uint32_t traversal_depth;
        uint8_t direction;           // 1=from, 2=to, 3=both
    } tgk_traversal;

    // Aggregation parameters
    struct {
        uint8_t agg_count;
        uint8_t agg_union;
        uint8_t agg_sum;
    } aggregation;

    // LimitOffset parameters
    struct {
        uint64_t limit;
        uint64_t offset;
    } limit_offset;

    // ShardDispatch & SIMDFilter are handled via flags
} operator_params_t;
```

---

## 5. Operator Definition Structure

```c
typedef struct operator_def {
    uint32_t op_id;                     // unique operator ID
    operator_type_t op_type;            // operator type
    operator_flags_t flags;             // parallel/optional flags
    snapshot_range_t snapshot;          // snapshot bounds for deterministic execution
    operator_params_t params;           // operator-specific parameters

    uint32_t input_count;               // number of upstream operators
    uint32_t inputs[8];                 // list of op_ids for input edges (DAG)
} operator_def_t;
```

Notes:

* `inputs` defines DAG dependencies.
* The maximum input fan-in is 8 for v1.

---

## 6. Execution Plan Structure

```c
typedef struct exec_plan {
    uint32_t plan_version;              // version of plan encoding
    uint32_t operator_count;            // number of operators
    operator_def_t *operators;          // array of operator definitions
} exec_plan_t;
```

Operators SHOULD be serialized in topological order when possible.

---

## 7. Serialization Rules (Normative)

* All integers are little-endian.
* Operators MUST be serialized in a deterministic order.
* `operator_count` MUST match the serialized operator array length.
* `inputs[]` MUST reference valid `op_id` values within the plan.

---

## 8. Non-Goals

ENC-ASL-TGK-EXEC-PLAN/1 does not define:

* Runtime scheduling or execution
* Query languages or APIs
* Operator semantics beyond parameter layout