System Catalog and SysCatalog

Loading…

System Catalog and SysCatalog

Relevant source files

• llkv-table/src/lib.rs

Purpose and Scope

The System Catalog (SysCatalog) is LLKV’s metadata repository that stores all table definitions, column schemas, indexes, constraints, triggers, and custom types. It provides a self-describing, bootstrapped metadata system where all metadata is stored as structured records in Table 0 using the same columnar storage infrastructure as user data.

This page covers the system catalog’s architecture, metadata structures, and how it integrates with DDL operations. For the higher-level catalog management API, see CatalogManager API. For custom type definitions and aliases, see Custom Types and Type Registry.

Sources: llkv-table/src/lib.rs:1-32

Self-Describing Architecture

The system catalog is implemented as Table 0, a special reserved table that stores metadata about all other tables (including itself). This creates a bootstrapped, self-referential system where the catalog uses the same storage mechanisms it documents.

Key architectural characteristics:

graph TB
    subgraph "Table 0 - System Catalog"
        SysCatalog["SysCatalog struct\n(sys_catalog.rs)"]
Table0["Underlying Table\ntable_id = 0"]
ColumnStore0["ColumnStore\nPhysical Storage"]
end
    
    subgraph "Metadata Record Types"
        TableMeta["TableMeta Records\ntable_id, name, schema"]
ColMeta["ColMeta Records\nfield_id, table_id, name, type"]
CustomTypeMeta["CustomTypeMeta Records\nCustom type definitions"]
IndexMeta["Index Metadata\nSingle & Multi-Column"]
TriggerMeta["TriggerMeta Records\nBEFORE/AFTER triggers"]
end
    
    subgraph "User Tables"
        Table1["User Table 1\ntable_id = 1"]
Table2["User Table 2\ntable_id = 2"]
TableN["User Table N\ntable_id = N"]
end
    
 
   SysCatalog --> Table0
 
   Table0 --> ColumnStore0
    
 
   TableMeta --> Table0
 
   ColMeta --> Table0
 
   CustomTypeMeta --> Table0
 
   IndexMeta --> Table0
 
   TriggerMeta --> Table0
    
    TableMeta -.describes.-> Table1
    TableMeta -.describes.-> Table2
    TableMeta -.describes.-> TableN
    
    ColMeta -.describes columns.-> Table1
    ColMeta -.describes columns.-> Table2

Sources: llkv-table/src/lib.rs:7-31 llkv-table/src/sys_catalog.rs

Table ID Ranges and Reservations

LLKV partitions the table ID space into reserved ranges for different purposes:

Constants and predicates:

graph LR
    subgraph "Table ID Ranges"
        Range0["ID 0\nCATALOG_TABLE_ID\n(System Catalog)"]
Range1["IDs 1-999\n(User Tables)"]
Range2["IDs 1000+\nINFORMATION_SCHEMA_TABLE_ID_START\n(Information Schema)"]
Range3["IDs 10000+\nTEMPORARY_TABLE_ID_START\n(Temporary Tables)"]
end
    
 
   Range0 --> SysCheck{is_reserved_table_id}
Range1 --> UserCheck{User table}
Range2 --> InfoCheck{is_information_schema_table}
Range3 --> TempCheck{Temporary table}

This partitioning allows the system to quickly identify table categories and apply appropriate handling (e.g., temporary tables are not persisted across sessions).

Sources: llkv-table/src/lib.rs:23-27 llkv-table/src/lib.rs:75-78 llkv-table/src/reserved.rs

Core Metadata Structures

The system catalog stores multiple types of metadata records, each represented by a specific struct that defines a schema for that metadata type.

TableMeta Structure

TableMeta records describe table-level metadata:

Key operations:

Sources: llkv-table/src/sys_catalog.rs llkv-table/src/metadata.rs

ColMeta Structure

ColMeta records describe individual column metadata:

Each ColMeta record associates a FieldId (the internal column identifier) with a TableId and provides the column’s name, type, nullability, and position within the table schema.

Sources: llkv-table/src/sys_catalog.rs llkv-table/src/metadata.rs

Index Metadata Structures

Index metadata is stored in two forms:

Index metadata types:

Sources: llkv-table/src/sys_catalog.rs llkv-table/src/metadata.rs llkv-table/src/catalog.rs

Trigger Metadata Structures

Triggers are stored with timing and event specifications:

Each trigger is identified by name and associated with a specific table, timing (BEFORE/AFTER), and event (INSERT/UPDATE/DELETE).

Sources: llkv-table/src/sys_catalog.rs

Custom Type Metadata

Custom types and type aliases are stored as CustomTypeMeta records:

This enables user-defined type aliases (e.g., CREATE TYPE email AS VARCHAR(255)) to be persisted and resolved during schema parsing.

Sources: llkv-table/src/sys_catalog.rs llkv-table/src/metadata.rs

graph TB
    subgraph "SysCatalog API"
        Constructor["new(table: Table)\nWraps Table 0"]
subgraph "Table Metadata"
            InsertTable["insert_table_meta(meta)\nAdd new table"]
GetTable["get_table_meta(id)\nRetrieve table info"]
ListTables["list_tables()\nGet all tables"]
UpdateTable["update_table_meta(meta)\nModify table"]
DeleteTable["delete_table_meta(id)\nRemove table"]
end
        
        subgraph "Column Metadata"
            InsertCol["insert_col_meta(meta)\nAdd column"]
GetCols["get_col_metas(table_id)\nGet table columns"]
end
        
        subgraph "Index Metadata"
            InsertIdx["insert_index_meta(meta)\nRegister index"]
GetIdxs["get_indexes(table_id)\nGet table indexes"]
end
        
        subgraph "Trigger Metadata"
            InsertTrigger["insert_trigger_meta(meta)\nCreate trigger"]
GetTriggers["get_triggers(table_id)\nList triggers"]
end
    end
    
 
   Constructor --> InsertTable
 
   Constructor --> GetTable
 
   Constructor --> InsertCol
 
   Constructor --> InsertIdx
 
   Constructor --> InsertTrigger

SysCatalog API and Operations

The SysCatalog struct provides methods for reading and writing metadata records:

Core methods:

All operations are implemented as append operations on the underlying Table struct, leveraging the same MVCC and transactional semantics as user data.

Sources: llkv-table/src/sys_catalog.rs

Bootstrap Process

The system catalog must be initialized before any other tables can be created. The bootstrap process creates Table 0 with a predefined schema:

Bootstrap steps:

sequenceDiagram
    participant Init as "Initialization"
    participant CM as "CatalogManager"
    participant SysCat as "SysCatalog::new()"
    participant Table0 as "Table ID 0"
    participant CS as "ColumnStore"
    
    Init->>CM: Create database
    CM->>SysCat: Initialize system catalog
    
    Note over SysCat: Define catalog schema\n(TableMeta, ColMeta, etc.)
    
    SysCat->>Table0: Create Table 0 with catalog schema
    Table0->>CS: Initialize column storage for catalog
    
    SysCat->>Table0: Insert TableMeta for Table 0\n(self-reference)
    
    Note over SysCat: Catalog is now operational
    
    SysCat-->>CM: Return initialized catalog
    CM-->>Init: Ready for user tables

1. Schema definition : The catalog schema is hardcoded in SysCatalog, defining the fields for TableMeta, ColMeta, and other metadata types
2. Table 0 creation : A Table struct is created with table_id = 0 and the catalog schema
3. Self-registration : The first metadata record inserted is TableMeta for Table 0 itself, creating the self-referential loop
4. Ready state : Once initialized, the catalog can accept metadata for user tables

Sources: llkv-table/src/sys_catalog.rs llkv-table/src/catalog.rs

Metadata Queries and Resolution

The system catalog supports various query patterns for metadata resolution:

Resolution functions:

These resolution operations enable the query planner to translate SQL identifiers (table names, column names) into internal identifiers (TableId, FieldId) used throughout the execution pipeline.

Sources: llkv-table/src/resolvers.rs llkv-table/src/catalog.rs llkv-table/src/sys_catalog.rs

sequenceDiagram
    participant SQL as "SQL Engine"
    participant DDL as "DDL Handler\n(CatalogManager)"
    participant SysCat as "SysCatalog"
    participant Table0 as "Table 0"
    
    SQL->>DDL: CREATE TABLE users (...)
    
    DDL->>DDL: Parse schema\nAllocate TableId
    DDL->>DDL: Assign FieldIds to columns
    
    DDL->>SysCat: insert_table_meta(TableMeta)
    SysCat->>Table0: Append TableMeta record
    
    loop For each column
        DDL->>SysCat: insert_col_meta(ColMeta)
        SysCat->>Table0: Append ColMeta record
    end
    
    DDL->>DDL: Create user Table with allocated ID
    
    DDL-->>SQL: CreateTableResult
    
    Note over SQL,Table0: Table now visible to queries

Integration with DDL Operations

All DDL operations (CREATE TABLE, ALTER TABLE, DROP TABLE) modify the system catalog:

DDL operation flow:

1. CREATE TABLE :

   • Parse schema and allocate TableId
   • Assign FieldId to each column
   • Insert TableMeta and ColMeta records into catalog
   • Create the physical Table with the assigned ID

2. ALTER TABLE :

   • Retrieve current TableMeta and ColMeta records
   • Validate operation (see validate_alter_table_operation())
   • Update metadata records (append new versions due to MVCC)
   • Modify the physical table schema

3. DROP TABLE :

   • Mark TableMeta as deleted (MVCC soft delete)
   • Mark associated ColMeta records as deleted
   • Remove indexes and constraints
   • Free physical storage pages

Sources: llkv-table/src/ddl.rs llkv-table/src/catalog.rs llkv-table/src/constraints.rs

graph TB
    subgraph "Constraint Types"
        PK["PrimaryKeyConstraint\nUnique, Not Null"]
Unique["UniqueConstraint\nSingle or Multi-Column"]
FK["ForeignKeyConstraint\nReferential Integrity"]
Check["CheckConstraint\nExpression Validation"]
end
    
    subgraph "Constraint Metadata"
        ConstraintRecord["ConstraintRecord\nid, table_id, kind"]
ConstraintService["ConstraintService\nEnforcement Logic"]
end
    
    subgraph "Storage"
        MetaManager["MetadataManager"]
SysCatalog["SysCatalog Table 0"]
end
    
 
   PK --> ConstraintRecord
 
   Unique --> ConstraintRecord
 
   FK --> ConstraintRecord
 
   Check --> ConstraintRecord
    
 
   ConstraintRecord --> MetaManager
 
   MetaManager --> SysCatalog
    
 
   ConstraintService --> ConstraintRecord

Constraints and Validation Metadata

The system catalog also stores constraint definitions that enforce data integrity:

Constraint structures:

The ConstraintService validates constraint satisfaction during INSERT, UPDATE, and DELETE operations, querying the catalog for relevant constraint definitions.

Sources: llkv-table/src/constraints.rs llkv-table/src/metadata.rs

graph TB
    subgraph "MetadataManager API"
        MM["MetadataManager\n(metadata.rs)"]
IndexReg["register_single_column_index()\nregister_multi_column_index()"]
IndexGet["get_single_column_indexes()\nget_multi_column_indexes()"]
FKReg["register_foreign_key()"]
FKGet["get_foreign_keys()"]
FKValidate["validate_foreign_key_rows()"]
ConstraintReg["register_constraint()"]
ConstraintGet["get_constraints()"]
end
    
    subgraph "SysCatalog Operations"
        SysCat["SysCatalog"]
TableMetaOps["Table/Column Metadata"]
IndexMetaOps["Index Metadata"]
ConstraintMetaOps["Constraint Metadata"]
end
    
 
   MM --> SysCat
    
 
   IndexReg --> IndexMetaOps
 
   IndexGet --> IndexMetaOps
    
 
   FKReg --> ConstraintMetaOps
 
   FKGet --> ConstraintMetaOps
    
 
   ConstraintReg --> ConstraintMetaOps
 
   ConstraintGet --> ConstraintMetaOps
    
 
   IndexMetaOps --> SysCat
 
   ConstraintMetaOps --> SysCat

Metadata Manager Integration

The MetadataManager provides a higher-level interface over SysCatalog for managing complex metadata like indexes and constraints:

The MetadataManager coordinates between the catalog and the runtime enforcement logic, ensuring that metadata changes are properly persisted and that constraints are consistently enforced.

Sources: llkv-table/src/metadata.rs llkv-table/src/catalog.rs

graph LR
    subgraph "Transaction T1"
        T1Create["CREATE TABLE users"]
T1Meta["Insert TableMeta\ncreated_by = T1"]
end
    
    subgraph "Transaction T2 (concurrent)"
        T2Query["SELECT FROM users"]
T2Scan["Scan catalog\nFilter: created_by <= T2\ndeleted_by > T2 OR NULL"]
end
    
    subgraph "Table 0 Storage"
        Metadata["TableMeta Records\nwith MVCC columns"]
end
    
 
   T1Meta --> Metadata
 
   T2Scan --> Metadata
    
    T1Create -.commits.-> T1Meta
    T2Query -.reads snapshot.-> T2Scan

MVCC and Transactional Metadata

Because the system catalog is implemented as Table 0 using the same storage layer as user tables, all metadata operations are automatically transactional with MVCC semantics:

MVCC characteristics:

This ensures that concurrent DDL and DML operations do not interfere with each other, and that queries always see a consistent view of the schema.

Sources: llkv-table/src/table.rs llkv-table/src/sys_catalog.rs

Schema Evolution and Compatibility

The system catalog schema itself is versioned and can evolve over time:

Schema migrations add new columns to the catalog tables (e.g., adding constraint metadata) while maintaining backward compatibility with existing metadata records.

Sources: llkv-table/src/sys_catalog.rs llkv-table/src/metadata.rs

Summary

The System Catalog (SysCatalog) provides:

• Self-describing metadata : All metadata stored in Table 0 using the same columnar storage as user data
• Comprehensive tracking : Tables, columns, indexes, triggers, constraints, and custom types
• Transactional semantics : MVCC ensures consistent metadata reads and atomic DDL operations
• Efficient resolution : Fast lookup of table names to IDs, field names to IDs
• Extensibility : New metadata types can be added by extending the catalog schema

The catalog bridges the gap between SQL identifiers and internal identifiers, enabling the query processor to operate on TableId and FieldId rather than string names throughout the execution pipeline.

Sources: llkv-table/src/lib.rs llkv-table/src/sys_catalog.rs llkv-table/src/catalog.rs llkv-table/src/metadata.rs

Dismiss

Refresh this wiki

Enter email to refresh