[Discussion] Transactional Physical Storage for VECTOR Values in InnoDB

[zhaiwx1987]

[Discussion] Transactional Physical Storage for VECTOR Values in InnoDB

Executive Summary

MySQL already has a native VECTOR data type, and the Native Vector Index work is defining how vector indexes should integrate with InnoDB. This proposal focuses on a narrower layer:

How should the authoritative VECTOR column value itself be stored, versioned, recovered, reclaimed, and efficiently accessed inside InnoDB?

It does not propose an ANN algorithm, vector-index syntax, or a specific vector-index architecture.

The proposed model stores an opaque fixed-width VectorRef in the clustered record when a VECTOR value is externalized. The referenced value is stored in InnoDB-managed Vector Storage pages.

The main design principles are:

1. the base VECTOR value is independent of ANN index storage;
2. fixed-length and variable-length vector values reuse one page/slot allocation framework;
3. large values reuse one generalized chunked-object format;
4. VECTOR updates use copy-on-write;
5. normal InnoDB MVCC, undo, and purge remain the visibility and lifetime authority;
6. Buffer Pool, FSP/FSEG, MTR, redo, checksums, and normal crash recovery are reused;
7. exact-search and SIMD consumers should be able to access canonical vector bytes without mandatory decoding or repacking.

The goal is to provide a stable base-value storage contract that can support both the current fixed-dimension dense VECTOR and future vector value families such as half-precision, sparse, or multi-vector representations, without coupling the authoritative SQL value to a particular ANN index implementation.

---

1. Motivation

Current MySQL vector work is primarily focused on making VECTOR searchable and indexable. The architecture discussion in mysql/mysql-server#710 is evaluating different approaches for VECTOR INDEX storage, including specialized InnoDB-managed index structures and hidden relational objects.

Those are index-storage decisions.

The base VECTOR column value has a different responsibility. It must remain the durable source value even when:

• no VECTOR INDEX exists;
• an index is dropped or rebuilt;
• multiple vector indexes exist on the same column;
• the ANN algorithm changes;
• an index stores a quantized or otherwise derived representation;
• an old row version remains visible after an UPDATE.

The base-value layer should therefore be designed independently.

There is also a second motivation: not every future vector representation is necessarily fixed-size per row.

For example:

Dense VECTOR(N)
    -> fixed payload length for one column

Sparse VECTOR
    -> fixed logical dimension
    -> variable nnz
    -> variable payload length per row

Multi-vector value
    -> fixed child dimension
    -> variable child count
    -> variable payload length per row

A storage model optimized only for one fixed payload size would make future variable-length vector values unnecessarily expensive or force them into an unrelated LOB representation.

---

2. Scope

This proposal covers:

• the physical representation of an externalized VECTOR-family value;
• the reference from the clustered row to that value;
• fixed-size and variable-size value allocation;
• large/multi-page value storage;
• INSERT / UPDATE / DELETE lifecycle;
• rollback and purge integration;
• reuse of existing InnoDB MVCC, Buffer Pool, FSP/FSEG, MTR, redo, checksum, and recovery infrastructure;
• efficient logical-value access for exact execution and future index consumers.

It intentionally does not define:

• ANN algorithms;
• VECTOR INDEX page layout;
• CREATE VECTOR INDEX syntax;
• distance-function SQL syntax;
• optimizer costing;
• ANN query execution;
• index-specific quantization or compression;
• the final SQL syntax of future sparse or multi-vector types.

---

3. Proposed Physical Model

The proposed model is:

Clustered Record
      |
      | opaque VectorRef
      v

+------------------------------------------------+
| InnoDB Vector Storage                          |
|                                                |
|   FixedSlotAllocator                           |
|      |                                         |
|      +-- one size class   (fixed-length value) |
|      |                                         |
|      +-- multiple classes (variable value)     |
|                                                |
|   CHUNKED_OBJECT                               |
|      +-- Root                                  |
|      +-- Fragment Directory                    |
|      +-- Payload Fragments                     |
+------------------------------------------------+

The important point is that fixed-length and variable-length values are not separate storage subsystems.

They share the same basic fixed-slot page allocator.

Large values share one generalized CHUNKED_OBJECT mechanism.

---

3.1 VectorRef

When a VECTOR value is externalized, the clustered record stores a compact opaque VectorRef:

row
 |
 +-- VectorRef
        |
        v
   physical Vector object

The current design direction is a fixed-width reference identifying a Vector page and slot. An 8-byte representation appears sufficient for the current design, although the exact bit allocation should still be validated against InnoDB page-number and slot-count limits.

VectorRef remains an InnoDB implementation detail.

The Server, SQL expressions, client protocol, logical backup, and replication should see the logical VECTOR value, never physical page numbers, slot numbers, fragment identifiers, or allocation metadata.

The reference also does not need to encode:

dense / sparse / multi-vector
fixed / variable
inline / multi-page
element type
payload length

Those are resolved from column/storage metadata and the validated target physical page.

---

3.2 One Fixed-Slot Framework

The core page allocator is based on fixed-size slots.

A non-empty Vector page contains exactly one slot-size class:

Page(class = 256 B)

+----------------+
| bitmap         |
+----------------+
| slot 0  256 B  |
+----------------+
| slot 1  256 B  |
+----------------+
| slot 2  256 B  |
+----------------+
| ...            |
+----------------+

Mixed slot sizes inside one page are intentionally avoided.

This preserves:

• arithmetic slot addressing;
• bitmap allocation;
• O(1)-style slot lookup;
• O(1)-style reclaim;
• no free-space tree;
• no variable-record directory;
• no hole splitting/merging;
• no page compaction;
• no slot relocation.

Fixed-length columns

A fixed-length vector column is the simplest case:

SizeClassSet = { C }

All inline values use one slot class.

For example, a fixed-width dense vector may map to one physical slot geometry for the lifetime of that storage format.

Variable-length columns

A variable-length vector column uses the same allocator with multiple classes:

SizeClassSet = {
    C0,
    C1,
    C2,
    ...
}

For each new value:

required_bytes =
    aligned(
        physical inline header
        + logical payload length
    )

The allocator selects the smallest admitted class able to contain required_bytes.

Conceptually:

C0 owns [1, C0]
C1 owns (C0, C1]
C2 owns (C1, C2]
...

This is a deterministic lower-bound lookup, not a page scan.

After the class is selected:

payload length
      |
      v
size class
      |
      v
partial-page bucket for that class
      |
      v
bitmap free slot

Reads do not repeat the size-class search:

VectorRef
    |
    v
target page
    |
    v
page slot geometry
    |
    v
slot offset

So the extra size-class logic is primarily an allocation-time concern.

---

3.3 Page-Class Management

Each physical Vector Storage context can maintain a small directory of size classes:

FixedSlotClassDirectory
    |
    +-- class A
    |      +-- PARTIAL-page candidates
    |
    +-- class B
    |      +-- PARTIAL-page candidates
    |
    +-- class C
           +-- PARTIAL-page candidates

A normal allocation should not scan the entire FSEG looking for a matching page.

FULL pages leave the allocation hot path.

A completely EMPTY page may be returned to a generic empty-page pool and later reformatted for another size class:

occupied page
    -> size class is immutable

empty page
    -> recyclable
    -> may become another size class

This avoids both mixed-size page fragmentation and long-term fragmentation between size classes.

---

3.4 Unified Large-Value Storage: CHUNKED_OBJECT

Values too large for an admitted single-page slot use one generalized multi-page representation:

CHUNKED_OBJECT
     |
     +-- Object Root
     |
     +-- ordered FragmentRef inventory
     |
     +-- Directory pages if needed
     |
     +-- non-contiguous payload fragments

This is shared by:

large fixed Dense VECTOR
large Sparse VECTOR
large Multi-vector value
future large Vector-family values

There should not be separate:

DenseMultiPageManager
SparseChunkManager
MultiVectorChunkManager

The physical problem is the same: store one immutable logical byte sequence across multiple pages.

Root payload length

The root records the complete logical payload length:

payload_length

For a fixed-width dense value, this length can also be cross-checked against the descriptor-derived expected size.

For a variable-size value, it records the actual row-local payload length.

However, payload_length alone is not enough to establish correctness.

A readable object must also have:

• a complete ordered fragment inventory;
• valid fragment identifiers;
• valid fragment numbers and lengths;
• no missing or duplicate fragments;
• reconstructed byte count exactly equal to payload_length;
• a valid physical completeness state.

Therefore:

payload_length
    = how many bytes should exist

FragmentRef inventory
    = where those bytes are

physical object state
    = whether construction/publication completed

Any short read, missing fragment, duplicate fragment, extra fragment, or reconstructed-length mismatch is corruption and must fail closed.

A linked-list-only fragment chain should not be the correctness lookup structure. Directory lookup should remain bounded and suitable for sequential/prefetchable reads.

---

3.5 Mixed Inline and Chunked Values in One Column

A variable-length column may naturally contain both inline fixed-slot values and chunked values at the same time.

For example:

same sparse column

row A -> small payload -> 96 B slot
row B -> medium payload -> 1 KB slot
row C -> large payload -> CHUNKED_OBJECT

This is normal storage state, not a migration case.

The clustered row still contains the same opaque VectorRef.

On read, the target physical page role determines whether the reference resolves to:

fixed-slot payload

or:

CHUNKED_OBJECT root

No new SQL semantics or MVCC rules are required.

An UPDATE may also cross this boundary:

small inline value
    -> UPDATE
    -> large CHUNKED_OBJECT

or:

large CHUNKED_OBJECT
    -> UPDATE
    -> small inline value

Both remain ordinary copy-on-write updates.

---

4. Transaction Lifecycle

The proposal continues to reuse normal InnoDB transaction semantics.

4.1 INSERT

allocate physical Vector value
        |
write complete canonical payload
        |
establish complete physical ownership
        |
publish VectorRef in clustered row
        |
commit

A committed row must never reference a half-built object.

4.2 UPDATE

VECTOR UPDATE uses copy-on-write:

Before:

    Row V1 -> Ref A -> Value A

UPDATE:

    allocate Value B
    write Value B completely
    row -> Ref B

After commit:

    new readers -> Ref B
    old ReadViews may still -> Ref A

Purge:

    reclaim Ref A after normal reachability proof

A published VECTOR payload is immutable.

4.3 Non-VECTOR UPDATE

If the VECTOR column itself is unchanged:

old row -> Ref A
new row -> Ref A

No new VECTOR allocation is needed solely because another column changed.

4.4 DELETE

delete-mark
    |
old row may remain visible
    |
Purge determines it is no longer reachable
    |
reclaim Vector object

Vector Storage does not independently decide visibility.

4.5 Rollback

A newly allocated value that is undone belongs to normal row-undo cleanup.

Rollback and purge therefore have different targets:

ROLLBACK
    -> reclaim the new uncommitted value

PURGE
    -> reclaim an old committed value
       after row-version reachability disappears

No separate Vector undo subsystem is required.

---

5. Crash-Safe Physical Completeness

There is an unavoidable interval between allocating physical storage and safely linking it from a row.

The Vector storage layer therefore needs a small physical construction lifecycle, conceptually:

BUILDING
    |
    v
READY
    |
    v
row VectorRef installed
    |
    v
LINKED

These states describe physical construction and ownership linkage only.

They are not:

transaction visibility
MVCC state
commit state

SQL visibility continues to come exclusively from normal InnoDB row MVCC.

Crash recovery must guarantee:

no dangling committed reference
no lost committed Vector
no reusable child still referenced by a parent
no double reclaim
no half-readable payload

The implementation should reuse existing transaction identity, row undo, page redo, and InnoDB recovery infrastructure rather than introducing another transaction log.

---

6. Exact Search and SIMD Access

A useful point raised in this discussion is whether the storage model also helps exact vector processing when an ANN index is unavailable or approximation is not desired.

The proposal does not define SIMD execution itself, but the physical format should not make SIMD unnecessarily expensive.

The main storage requirement should be:

A resolved logical VECTOR value should expose canonical numeric bytes directly, without mandatory decoding, type conversion, or repacking before exact computation.

For a single-slot value, the payload can normally be exposed as one naturally aligned contiguous span.

For a chunked value, the storage provider should support both:

materialize_contiguous()

for consumers that truly require one buffer, and segmented/range access such as:

visit_segments()
read_range()

for consumers that can process the logical payload incrementally.

This allows exact metric implementations or index builders to process data without always performing:

all fragments
    -> memcpy into large temporary buffer
    -> compute

For sparse values in particular, storage and exact processing should remain proportional to the encoded non-zero payload rather than densifying to the full logical dimension.

This design does not imply that different rows encountered during a table scan are physically contiguous. A table scan may still involve:

row
 -> VectorRef
 -> another page/slot

Therefore the PoC should explicitly measure:

• SIMD compute throughput;
• VectorRef dereference overhead;
• Buffer Pool/cache locality;
• prefetch effectiveness;
• inline versus chunked access;
• comparison with inline-row and LOB-based storage.

This makes exact-search locality an explicit evaluation criterion rather than assuming fixed-size slots automatically solve it.

---

7. Relationship to Vector Index Work

This proposal remains independent of the VECTOR INDEX architecture:

                 authoritative Vector value
                          |
                          v
                 Base Vector Storage
                          |
             +------------+------------+
             |                         |
             v                         v
      Vector Index A             Vector Index B
      tree / IVF / ...           graph / Vamana / ...

Index structures may store:

centroids
posting lists
graph edges
quantized vectors
compressed vectors
primary-key references

Those are derived representations.

The base value remains rebuildable source data.

This separation means a future change in ANN algorithm does not require changing the SQL column's durable representation.

---

8. Why Not Simply Use Generic Variable-Length Records?

A general variable-length heap page could pack bytes more tightly, but it also introduces substantially more allocator machinery:

variable record directory
free-space tracking
hole splitting
hole merging
page compaction
record relocation

For Vector values, a segregated fixed-slot model offers a useful middle ground.

Variable-length values still choose among several fixed slot classes, while each individual page remains simple:

one page
    -> one slot size
    -> bitmap
    -> arithmetic slot addressing

This bounds internal fragmentation without introducing arbitrary intra-page fragmentation.

Whether this produces a better overall result than adapted InnoDB LOB storage remains something the PoC should measure rather than assume.

---

9. Alternatives to Validate

Existing / adapted InnoDB LOB storage

This remains the primary baseline.

If existing LOB infrastructure can provide comparable:

• reference size;
• allocation/reclaim cost;
• exact-read performance;
• update amplification;
• fragmented-value access;
• crash recovery;
• SIMD-friendly logical-value access;

then reusing it may be preferable.

Hidden base-value sub-table

This maximizes reuse of relational row semantics but adds another hidden row and lookup to every externalized base VECTOR value.

It may be appropriate for index structures while being unnecessary for base-value storage.

Full VECTOR payload in the clustered record

This avoids dereference cost for small values but reduces clustered-page density as vectors grow and increases physical copying.

A prototype should include this as a locality baseline.

---

10. Proposed Prototype / Validation Plan

The next useful step is a focused prototype comparing at least:

A. inline / clustered-record baseline

B. existing or adapted InnoDB LOB

C. VectorRef
   + fixed-slot page classes
   + unified CHUNKED_OBJECT

The prototype should cover both:

fixed-size dense values
variable-size values

The required lifecycle tests are:

INSERT
SELECT
UPDATE
non-VECTOR UPDATE
DELETE
ROLLBACK
SAVEPOINT rollback
PURGE
CRASH / RESTART

Large-value tests should cross the transition between:

single fixed slot
        and
CHUNKED_OBJECT

and variable-length tests should exercise multiple size classes in the same column.

Correctness should verify:

• old ReadViews continue to resolve the old value;
• rollback reclaims the new value, not the restored old value;
• purge never reclaims a still-reachable value;
• a committed row never references an incomplete object;
• fragment loss/duplication/order/length corruption fails closed;
• fixed-slot and chunked values round-trip to identical logical bytes.

Performance should measure:

• clustered-record size;
• page-space utilization;
• allocation/reclaim throughput;
• redo amplification;
• Buffer Pool hit/miss behavior;
• update amplification;
• long-ReadView retained space;
• random VectorRef dereference cost;
• sequential scan throughput;
• exact distance throughput;
• SIMD throughput where available;
• inline/chunked crossover behavior;
• fragmented-value prefetch efficiency.

---

11. Remaining Open Questions

The design direction is now more specific, but several implementation details should still be validated against InnoDB source and a PoC:

1. What exact fixed-width VectorRef encoding best matches InnoDB page addressing?
2. Which Vector page-type / page-role encoding should be reused or introduced?
3. What size-class set gives the best space/performance trade-off?
4. How should per-size-class PARTIAL-page buckets reuse existing FSEG/page-list machinery?
5. What exact object-root and FragmentRef layout gives bounded lookup with minimal metadata?
6. What physical construction state is necessary for crash-safe publication without duplicating MVCC?
7. How much alignment should the format guarantee for direct SIMD consumption?
8. At what point does adapted LOB storage outperform a dedicated Vector page format?
9. Should the fixed-slot / chunked crossover depend only on physical page geometry, or also on measured workload characteristics?

These are implementation/PoC questions; they should not change the higher-level transaction model.

---

Summary

The updated proposal can be summarized as:

Clustered Row
      |
      +-- opaque VectorRef
              |
              v
       InnoDB Vector Storage
              |
       +------+------+
       |             |
       v             v
 FixedSlotAllocator  CHUNKED_OBJECT
       |
  one class for fixed-size columns
  multiple classes for variable-size columns

with the following rules:

1. base Vector storage is independent of ANN index storage;
2. fixed-length and variable-length values reuse the same fixed-slot allocator;
3. one non-empty page contains one slot-size class;
4. large fixed and variable values share one CHUNKED_OBJECT representation;
5. VECTOR UPDATE is copy-on-write;
6. native InnoDB MVCC / undo / purge remain the lifetime authority;
7. Buffer Pool / FSP/FSEG / MTR / redo / recovery remain the physical infrastructure;
8. exact and SIMD consumers can access canonical logical bytes without mandatory repacking;
9. physical optimization must not become a second transaction, visibility, or indexing subsystem.

The goal remains deliberately narrow:

Give authoritative native Vector values a compact, transaction-safe, recoverable, and efficiently readable physical representation that future Vector indexes can build on without owning the base data themselves.

[henrikingo-oracle]

Does this format do anything towards efficiently processing Vector values with SIMD instructions? I mean for cases where we don't have a suitable ANN index, or do not want an approximate result set? I didn't see any reference to this topic.

[zhaiwx1987]

Good point. SIMD execution is outside the scope of this proposal, but the storage format should at least allow each resolved VECTOR payload to be processed directly with SIMD, without mandatory decoding or repacking.

Fixed-size slots do not mean vectors visited during a table scan are physically contiguous, since VectorRefs may point to different pages and slots. So this design does not automatically improve cross-vector batching or scan locality.

For exact search, the PoC should therefore measure both SIMD processing cost and the additional VectorRef dereference/cache locality cost against inline and LOB-based storage.