crates/database/README.md
First, let's look at what the Database looks like at rest. The primary
structure is the SnapshotManager, which maintains many different Snapshots
at different Timestamps.
┌───────────────────────────┐
│ │
│ │
│ Database │
│ │
│ │
└───────────────────────────┘
│
│
│
│
▼
┌───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│SnapshotManager │
│ . │
│ . │
│ . │
│ │
│ ┌───────────────┬───────────────────────────────────────────────────────────────────────────────────────────────────┐ │
│ │ Timestamp │ Snapshot │ │
│ └───────────────┴───────────────────────────────────────────────────────────────────────────────────────────────────┘ │
│ ┌───────────────┬───────────────────────────────────────────────────────────────────────────────────────────────────┐ │
│ │ Timestamp │ Snapshot │ │
│ └───────────────┴───────────────────────────────────────────────────────────────────────────────────────────────────┘ │
│ ┌───────────────┬───────────────────────────────────────────────────────────────────────────────────────────────────┐ │
│ │ │Snapshot◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟│ │
│ │ │◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟┌──────────────────────────────────────────────────┐◟◟│ │
│ │ │◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟│DatabaseIndex │◟◟│ │
│ │ │◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟│ ┌──────────────────────────────────────────────┐ │◟◟│ │
│ │ │◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟│ │DatabaseIndexMetadata │ │◟◟│ │
│ │ │◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟│ │ ┌──────────────────────────────────────────┐ │ │◟◟│ │
│ │ │◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟│ │ │indexes: OrdMap │ │ │◟◟│ │
│ │ │◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟│ │ │ ┌────────────┬─────────────────────────┐ │ │ │◟◟│ │
│ │ │◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟│ │ │ │ │Index │ │ │ │◟◟│ │
│ │ │◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟│ │ │ │ │ ┌────────────────────┐ │ │ │ │◟◟│ │
│ │ │◟◟┌───────────────────────────────────────┐◟◟│ │ │ │ │ │ IndexId │ │ │ │ │◟◟│ │
│ │ │◟◟│DatabaseTableMetadata │◟◟│ │ │ │ │ └────────────────────┘ │ │ │ │◟◟│ │
│ │ │◟◟│ ┌───────────────────────────────────┐ │◟◟│ │ │ │ │ ┌────────────────────┐ │ │ │ │◟◟│ │
│ │ │◟◟│ │tables: OrdMap │ │◟◟│ │ │ │ │ │IndexMetadata │ │ │ │ │◟◟│ │
│ │ │◟◟│ │ ┌───────────┬───────────────────┐ │ │◟◟│ │ │ │ │ │ ┌────────────────┐ │ │ │ │ │◟◟│ │
│ │ │◟◟│ │ │ │TableSummary │ │ │◟◟│ │ │ │ IndexName │ │ │ IndexName │ │ │ │ │ │◟◟│ │
│ │ │◟◟│ │ │ │ ┌───────────────┐ │ │ │◟◟│ │ │ │ │ │ └────────────────┘ │ │ │ │ │◟◟│ │
│ │ │◟◟│ │ │ │ │ Shape │ │ │ │◟◟│ │ │ │ │ │ ┌────────────────┐ │ │ │ │ │◟◟│ │
│ │ │◟◟│ │ │ TableName │ └───────────────┘ │ │ │◟◟│ │ │ │ │ │ │ IndexedFields │ │ │ │ │ │◟◟│ │
│ │ │◟◟│ │ │ │ ┌───────────────┐ │ │ │◟◟│ │ │ │ │ │ └────────────────┘ │ │ │ │ │◟◟│ │
│ │ │◟◟│ │ │ │ │ total_size │ │ │ │◟◟│ │ │ │ │ │ ┌────────────────┐ │ │ │ │ │◟◟│ │
│ │ │◟◟│ │ │ │ └───────────────┘ │ │ │◟◟│ │ │ │ │ │ │ IndexState │ │ │ │ │ │◟◟│ │
│ │ │◟◟│ │ └───────────┴───────────────────┘ │ │◟◟│ │ │ │ │ │ └────────────────┘ │ │ │ │ │◟◟│ │
│ │ Timestamp │◟◟│ └───────────────────────────────────┘ │◟◟│ │ │ │ │ └────────────────────┘ │ │ │ │◟◟│ │
│ │ │◟◟│ ┌───────────────────────────────────┐ │◟◟│ │ │ └────────────┴─────────────────────────┘ │ │ │◟◟│ │
│ │ │◟◟│ │ num_documents │ │◟◟│ │ └──────────────────────────────────────────┘ │ │◟◟│ │
│ │ │◟◟│ └───────────────────────────────────┘ │◟◟│ │ ┌──────────────────────────────────────────┐ │ │◟◟│ │
│ │ │◟◟│ ┌───────────────────────────────────┐ │◟◟│ │ │ indexes_by_table │ │ │◟◟│ │
│ │ │◟◟│ │ user_size │ │◟◟│ │ └──────────────────────────────────────────┘ │ │◟◟│ │
│ │ │◟◟│ └───────────────────────────────────┘ │◟◟│ │ ┌──────────────────────────────────────────┐ │ │◟◟│ │
│ │ │◟◟│ ┌───────────────────────────────────┐ │◟◟│ │ │ num_user_indexes │ │ │◟◟│ │
│ │ │◟◟│ │ system_size │ │◟◟│ │ └──────────────────────────────────────────┘ │ │◟◟│ │
│ │ │◟◟│ └───────────────────────────────────┘ │◟◟│ └──────────────────────────────────────────────┘ │◟◟│ │
│ │ │◟◟└───────────────────────────────────────┘◟◟│ ┌──────────────────────────────────────────────┐ │◟◟│ │
│ │ │◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟│ │in_memory_indexes: OrdMap │ │◟◟│ │
│ │ │◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟│ │ ┌─────────┬────────────────────────────────┐ │ │◟◟│ │
│ │ │◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟│ │ │ │IndexMap: OrdMap │ │ │◟◟│ │
│ │ │◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟│ │ │ │ ┌───────────┬────────────────┐ │ │ │◟◟│ │
│ │ │◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟│ │ │ │ │ │ Timestamp │ │ │ │◟◟│ │
│ │ │◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟│ │ │ IndexId │ │ Vec<u8> ├────────────────┤ │ │ │◟◟│ │
│ │ │◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟│ │ │ │ │ │ PackedDocument │ │ │ │◟◟│ │
│ │ │◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟│ │ │ │ └───────────┴────────────────┘ │ │ │◟◟│ │
│ │ │◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟│ │ │ │ │ │ │◟◟│ │
│ │ │◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟│ │ └─────────┴────────────────────────────────┘ │ │◟◟│ │
│ │ │◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟│ └──────────────────────────────────────────────┘ │◟◟│ │
│ │ │◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟└──────────────────────────────────────────────────┘◟◟│ │
│ │ │◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟◟│ │
│ └───────────────┴───────────────────────────────────────────────────────────────────────────────────────────────────┘ │
│ ┌───────────────┬───────────────────────────────────────────────────────────────────────────────────────────────────┐ │
│ │ Timestamp │ Snapshot │ │
│ └───────────────┴───────────────────────────────────────────────────────────────────────────────────────────────────┘ │
│ ┌───────────────┬───────────────────────────────────────────────────────────────────────────────────────────────────┐ │
│ │ Timestamp │ Snapshot │ │
│ └───────────────┴───────────────────────────────────────────────────────────────────────────────────────────────────┘ │
│ │
│ . │
│ . │
│ . │
│ │
└───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
Each Snapshot has two important types of system metadata: table metadata and
index metadata.
Each table in the database has a row in the _tables table (including the
_tables table itself), and this information is always kept in memory within
the TableRegistry struct. Each table has its TableSummary, its current
Shape and total size, and we store the total number and size of all the
documents in the system.
Every index has an entry in the _index table, and every table (including the
_index table) has its default by_id index. Similar to tables, we store this
information in-memory in the IndexRegistry struct. Each index has its name,
index ID, indexed fields, and current backfill state.
The DatabaseIndexManager stores the index metadata along with a few indexes
for system tables we always keep in memory.
This in-memory state gives the system enough information to know how to query
the Persistence at a given snapshot. It's designed to be a small amount of
information in-memory that's quick to load at startup.
WIP.
WIP.