uqa-storage-sqlite 0.5.2

SQLite catalog, indexes, compressed storage, graph and key/value providers
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
//
// Unified Query Algebra
//
// Copyright (c) 2023-2026 Cognica, Inc.
//

use std::sync::Arc;

use rusqlite::{params, Connection, OptionalExtension, Transaction, TransactionBehavior};
use uqa_storage::mvcc::{DatabaseId, VersionError};

use super::{codec, connection_functions::ConnectionFunctions, PhysicalResult};

/// Record metadata certifies the synchronized prefix of autonomous sequence publications.
pub(super) const RECORD_FORMAT: i64 = 60;
const VERSION_METADATA_FORMAT: i64 = 55;

const PREVIOUS_METADATA: &str = "CREATE TABLE _uqa_mvcc_metadata (singleton INTEGER PRIMARY KEY CHECK(singleton = 1), format INTEGER NOT NULL CHECK(format = 42), database_id BLOB NOT NULL CHECK(typeof(database_id) = 'blob' AND length(database_id) = 16), allocated BLOB NOT NULL CHECK(typeof(allocated) = 'blob' AND length(allocated) = 8), sequence BLOB NOT NULL CHECK(typeof(sequence) = 'blob' AND length(sequence) = 8), mapping INTEGER NOT NULL DEFAULT 0 CHECK(mapping IN (0, 1)))";

const PREVIOUS_RESTORE_METADATA: &str = "CREATE TABLE _uqa_mvcc_metadata (singleton INTEGER PRIMARY KEY CHECK(singleton = 1), format INTEGER NOT NULL CHECK(format = 43), database_id BLOB NOT NULL CHECK(typeof(database_id) = 'blob' AND length(database_id) = 16), allocated BLOB NOT NULL CHECK(typeof(allocated) = 'blob' AND length(allocated) = 8), sequence BLOB NOT NULL CHECK(typeof(sequence) = 'blob' AND length(sequence) = 8), mapping INTEGER NOT NULL DEFAULT 0 CHECK(mapping IN (0, 1)), restore_target BLOB CHECK(restore_target IS NULL OR (typeof(restore_target) = 'blob' AND length(restore_target) = 16 AND restore_target != database_id)))";

pub(super) const PREVIOUS_TRANSACTIONS: &str = "CREATE TABLE _uqa_mvcc_transactions (allocation BLOB PRIMARY KEY CHECK(typeof(allocation) = 'blob' AND length(allocation) = 8 AND allocation > x'0000000000000000'), status INTEGER NOT NULL CHECK(status IN (0, 1, 2)), sequence BLOB, fingerprint BLOB, CHECK((status IN (0, 1) AND sequence IS NULL AND fingerprint IS NULL) OR (status = 2 AND typeof(sequence) = 'blob' AND length(sequence) = 8 AND typeof(fingerprint) = 'blob' AND length(fingerprint) = 32))) WITHOUT ROWID";

const PREVIOUS_HEADS: &str = "CREATE TABLE _uqa_mvcc_heads (key BLOB PRIMARY KEY CHECK(typeof(key) = 'blob'), sequence BLOB NOT NULL CHECK(typeof(sequence) = 'blob' AND length(sequence) = 8 AND sequence > x'0000000000000000')) WITHOUT ROWID";

const PREVIOUS_VALUE_METADATA: &str = "CREATE TABLE _uqa_mvcc_metadata (singleton INTEGER PRIMARY KEY CHECK(singleton = 1), format INTEGER NOT NULL CHECK(format = 59), database_id BLOB NOT NULL CHECK(typeof(database_id) = 'blob' AND length(database_id) = 16), allocated BLOB NOT NULL CHECK(typeof(allocated) = 'blob' AND length(allocated) = 8), sequence BLOB NOT NULL CHECK(typeof(sequence) = 'blob' AND length(sequence) = 8), mapping INTEGER NOT NULL DEFAULT 0 CHECK(mapping IN (0, 1)), restore_target BLOB CHECK(restore_target IS NULL OR (typeof(restore_target) = 'blob' AND length(restore_target) = 16 AND restore_target != database_id)), receipt_limit INTEGER NOT NULL DEFAULT 65536 CHECK(receipt_limit > 0))";

const TABLES: [(&str, &str); 7] = [
    ("_uqa_mvcc_metadata", "CREATE TABLE _uqa_mvcc_metadata (singleton INTEGER PRIMARY KEY CHECK(singleton = 1), format INTEGER NOT NULL CHECK(format = 60), database_id BLOB NOT NULL CHECK(typeof(database_id) = 'blob' AND length(database_id) = 16), allocated BLOB NOT NULL CHECK(typeof(allocated) = 'blob' AND length(allocated) = 8), sequence BLOB NOT NULL CHECK(typeof(sequence) = 'blob' AND length(sequence) = 8), mapping INTEGER NOT NULL DEFAULT 0 CHECK(mapping IN (0, 1)), restore_target BLOB CHECK(restore_target IS NULL OR (typeof(restore_target) = 'blob' AND length(restore_target) = 16 AND restore_target != database_id)), receipt_limit INTEGER NOT NULL DEFAULT 65536 CHECK(receipt_limit > 0), sequence_durable BLOB NOT NULL DEFAULT x'0000000000000000' CHECK(typeof(sequence_durable) = 'blob' AND length(sequence_durable) = 8 AND sequence_durable <= sequence))"),
    ("_uqa_mvcc_heads", "CREATE TABLE _uqa_mvcc_heads (key BLOB PRIMARY KEY CHECK(typeof(key) = 'blob'), sequence BLOB NOT NULL CHECK(typeof(sequence) = 'blob' AND length(sequence) = 8 AND sequence > x'0000000000000000'), compacted INTEGER NOT NULL DEFAULT 0 CHECK(compacted IN (0, 1))) WITHOUT ROWID"),
    super::version_metadata::VERSIONS_TABLE,
    ("_uqa_mvcc_transactions", "CREATE TABLE _uqa_mvcc_transactions (allocation BLOB PRIMARY KEY CHECK(typeof(allocation) = 'blob' AND length(allocation) = 8 AND allocation > x'0000000000000000'), status INTEGER NOT NULL CHECK(status IN (0, 1, 2, 3, 4)), sequence BLOB, fingerprint BLOB, managed INTEGER NOT NULL DEFAULT 0 CHECK(managed IN (0, 1)), CHECK((status IN (0, 1, 3) AND sequence IS NULL AND fingerprint IS NULL) OR (status IN (2, 4) AND typeof(sequence) = 'blob' AND length(sequence) = 8 AND typeof(fingerprint) = 'blob' AND length(fingerprint) = 32))) WITHOUT ROWID"),
    super::identifiers::TABLE,
    super::runs::TABLE,
    super::version_metadata::TABLE,
];

/// A connection-local admission token. Dropping it closes permission without any fallible SQL cleanup, including on unwind or commit failure.
pub(crate) struct WritePermit(Arc<ConnectionFunctions>);

impl WritePermit {
    pub(crate) fn for_native_restore(connection: &Connection) -> super::VersionResult<Self> {
        Self::acquire(connection).map_err(super::Error::into_version)
    }

    pub(super) fn acquire(connection: &Connection) -> PhysicalResult<Self> {
        if !connection.is_autocommit() {
            return Err(VersionError::InvalidEncoding(
                "record persistence requires an independent physical transaction",
            )
            .into());
        }
        let functions = ConnectionFunctions::of(connection)?;
        functions.require_full_synchronization(connection)?;
        functions.open_write_permit();
        Ok(Self(functions))
    }

    pub(super) fn functions(&self) -> &Arc<ConnectionFunctions> {
        &self.0
    }
}

impl Drop for WritePermit {
    fn drop(&mut self) {
        self.0.close_write_permit();
    }
}

pub(super) fn begin(connection: &Connection) -> PhysicalResult<Transaction<'_>> {
    Ok(Transaction::new_unchecked(
        connection,
        TransactionBehavior::Immediate,
    )?)
}

pub(super) fn definition_matches(
    connection: &Connection,
    name: &str,
    expected: &str,
) -> PhysicalResult<Option<bool>> {
    Ok(connection
        .query_row(
            "SELECT sql = ?2 FROM sqlite_schema WHERE name = ?1",
            params![name, expected],
            |row| row.get(0),
        )
        .optional()?)
}

pub(super) fn trigger(table: &str, action: &str) -> (String, String) {
    let name = format!("{table}_{action}_guard");
    let sql = format!("CREATE TRIGGER {name} BEFORE {action} ON {table} WHEN __uqa_mvcc_write_permit() != 1 BEGIN SELECT RAISE(ABORT, 'versioned records require commit admission'); END");
    (name, sql)
}

pub(super) fn initialize(connection: &Connection) -> PhysicalResult<DatabaseId> {
    let _permit = WritePermit::acquire(connection)?;
    let transaction = begin(connection)?;
    super::native::reject_mapped(&transaction)?;
    let initialized = initialize_in(&transaction)?;
    if initialized.created || initialized.upgraded {
        transaction.commit()?;
    }
    Ok(initialized.identity)
}

pub(super) struct Initialization {
    pub(super) identity: DatabaseId,
    pub(super) created: bool,
    pub(super) upgraded: bool,
}

pub(super) fn initialize_in(transaction: &Connection) -> PhysicalResult<Initialization> {
    let (present, predecessor) = validate_tables(transaction)?;
    if present == 0 {
        for (name, sql) in TABLES {
            transaction.execute_batch(sql)?;
            for action in ["INSERT", "UPDATE", "DELETE"] {
                transaction.execute_batch(&trigger(name, action).1)?;
            }
        }
        super::version_metadata::create_triggers(transaction)?;
        let mut identity = [0; 16];
        getrandom::fill(&mut identity).map_err(|error| {
            VersionError::Storage(
                crate::SQLiteError::Io(std::io::Error::other(error.to_string())).into(),
            )
        })?;
        transaction.execute(
            &format!("INSERT INTO _uqa_mvcc_metadata (singleton, format, database_id, allocated, sequence) VALUES (1, {RECORD_FORMAT}, ?1, ?2, ?2)"),
            params![identity.as_slice(), 0_u64.to_be_bytes().as_slice()],
        )?;
        return Ok(Initialization {
            identity: DatabaseId::from_bytes(identity),
            created: true,
            upgraded: false,
        });
    }
    validate_guards(transaction, predecessor)?;
    let upgraded = predecessor.is_some();
    if let Some(format) = predecessor {
        upgrade_metadata(transaction, format)?;
    }
    let identity = {
        let mut statement = transaction
            .prepare("SELECT database_id FROM _uqa_mvcc_metadata WHERE singleton = 1")?;
        let mut rows = statement.query([])?;
        let row = rows
            .next()?
            .ok_or(VersionError::InvalidEncoding("missing database identity"))?;
        codec::identity(codec::bytes(row, 0)?)?
    };
    codec::header(transaction, identity)?;
    // A verified existing format does not need another durable write.
    Ok(Initialization {
        identity,
        created: false,
        upgraded,
    })
}

fn validate_guards(transaction: &Connection, predecessor: Option<i64>) -> PhysicalResult<()> {
    for (name, _) in TABLES {
        if (predecessor.is_some_and(|format| format < 5) && name == super::identifiers::TABLE.0)
            || (predecessor.is_some_and(|format| format < 29) && name == super::runs::TABLE.0)
            || (predecessor.is_some_and(|format| format < VERSION_METADATA_FORMAT)
                && name == super::version_metadata::TABLE.0)
        {
            continue;
        }
        for action in ["INSERT", "UPDATE", "DELETE"] {
            let (name, expected) = trigger(name, action);
            if definition_matches(transaction, &name, &expected)? != Some(true) {
                return Err(
                    VersionError::InvalidEncoding("missing or changed record write guard").into(),
                );
            }
        }
    }
    if predecessor.is_none_or(|format| format >= VERSION_METADATA_FORMAT) {
        super::version_metadata::validate_triggers(
            transaction,
            predecessor.is_none_or(|format| format >= 59),
        )?;
    }
    Ok(())
}

fn validate_tables(transaction: &Connection) -> PhysicalResult<(usize, Option<i64>)> {
    let mut present = 0;
    let mut predecessor = None;
    for (name, expected) in TABLES {
        if let Some(matches) = definition_matches(transaction, name, expected)? {
            if !matches {
                if name == TABLES[0].0 {
                    for format in 44..RECORD_FORMAT {
                        if definition_matches(
                            transaction,
                            name,
                            &PREVIOUS_VALUE_METADATA.replace(
                                "CHECK(format = 59)",
                                &format!("CHECK(format = {format})"),
                            ),
                        )? == Some(true)
                        {
                            predecessor = Some(format);
                        }
                    }
                    if definition_matches(transaction, name, PREVIOUS_RESTORE_METADATA)?
                        == Some(true)
                    {
                        predecessor = Some(43);
                    }
                    for format in 1..=42 {
                        if definition_matches(
                            transaction,
                            name,
                            &PREVIOUS_METADATA.replace(
                                "CHECK(format = 42)",
                                &format!("CHECK(format = {format})"),
                            ),
                        )? == Some(true)
                        {
                            predecessor = Some(format);
                        }
                    }
                }
                let previous_heads = name == TABLES[1].0
                    && predecessor.is_some_and(|format| format < 28)
                    && definition_matches(transaction, name, PREVIOUS_HEADS)? == Some(true);
                let previous_transactions = name == TABLES[3].0
                    && predecessor.is_some_and(|format| format < 44)
                    && definition_matches(transaction, name, PREVIOUS_TRANSACTIONS)? == Some(true);
                let previous_versions = name == super::version_metadata::VERSIONS_TABLE.0
                    && predecessor.is_some_and(|format| format < 59)
                    && definition_matches(
                        transaction,
                        name,
                        super::version_metadata::PREVIOUS_VERSIONS_TABLE,
                    )? == Some(true);
                let previous_version_metadata = name == super::version_metadata::TABLE.0
                    && predecessor
                        .is_some_and(|format| (VERSION_METADATA_FORMAT..59).contains(&format))
                    && definition_matches(
                        transaction,
                        name,
                        super::version_metadata::PREVIOUS_TABLE,
                    )? == Some(true);
                if (name != TABLES[0].0 || predecessor.is_none())
                    && !previous_heads
                    && !previous_transactions
                    && !previous_versions
                    && !previous_version_metadata
                {
                    return Err(VersionError::InvalidEncoding(
                        "unexpected record table definition",
                    )
                    .into());
                }
            }
            present += 1;
        }
    }
    validate_record_table_set(transaction, present, predecessor)?;
    Ok((present, predecessor))
}

fn validate_record_table_set(
    transaction: &Connection,
    present: usize,
    predecessor: Option<i64>,
) -> PhysicalResult<()> {
    if predecessor.is_some_and(|format| format < 28)
        && definition_matches(transaction, TABLES[1].0, PREVIOUS_HEADS)? != Some(true)
    {
        return Err(VersionError::InvalidEncoding(
            "predecessor has an incompatible record head layout",
        )
        .into());
    }
    if predecessor.is_some_and(|format| format < 44)
        && definition_matches(transaction, TABLES[3].0, PREVIOUS_TRANSACTIONS)? != Some(true)
    {
        return Err(VersionError::InvalidEncoding(
            "predecessor has an incompatible transaction receipt layout",
        )
        .into());
    }
    if predecessor.is_some_and(|format| format < 59)
        && definition_matches(
            transaction,
            super::version_metadata::VERSIONS_TABLE.0,
            super::version_metadata::PREVIOUS_VERSIONS_TABLE,
        )? != Some(true)
    {
        return Err(VersionError::InvalidEncoding(
            "predecessor has an incompatible version payload layout",
        )
        .into());
    }
    if predecessor.is_some_and(|format| (VERSION_METADATA_FORMAT..59).contains(&format))
        && definition_matches(
            transaction,
            super::version_metadata::TABLE.0,
            super::version_metadata::PREVIOUS_TABLE,
        )? != Some(true)
    {
        return Err(VersionError::InvalidEncoding(
            "predecessor has an incompatible version metadata layout",
        )
        .into());
    }
    let identifier_table = definition_matches(
        transaction,
        super::identifiers::TABLE.0,
        super::identifiers::TABLE.1,
    )?;
    if predecessor.is_some_and(|format| format < 5) && identifier_table.is_some() {
        return Err(VersionError::InvalidEncoding(
            "predecessor contains unexpected identifier allocations",
        )
        .into());
    }
    if predecessor.is_some_and(|format| format < 29)
        && definition_matches(transaction, super::runs::TABLE.0, super::runs::TABLE.1)?.is_some()
    {
        return Err(
            VersionError::InvalidEncoding("predecessor contains unexpected record runs").into(),
        );
    }
    if predecessor.is_some_and(|format| format < VERSION_METADATA_FORMAT)
        && definition_matches(
            transaction,
            super::version_metadata::TABLE.0,
            super::version_metadata::TABLE.1,
        )?
        .is_some()
    {
        return Err(VersionError::InvalidEncoding(
            "predecessor contains unexpected version metadata",
        )
        .into());
    }
    let expected = TABLES.len()
        - usize::from(predecessor.is_some_and(|format| format < 5))
        - usize::from(predecessor.is_some_and(|format| format < 29))
        - usize::from(predecessor.is_some_and(|format| format < VERSION_METADATA_FORMAT));
    if present != 0 && present != expected {
        return Err(VersionError::InvalidEncoding("incomplete record table set").into());
    }
    Ok(())
}

/// A resumed restore validates and, when necessary, atomically upgrades the intent-bearing predecessor without admitting normal record access through its pending marker.
pub(super) fn initialize_restoration(connection: &Connection) -> PhysicalResult<()> {
    let (present, predecessor) = validate_tables(connection)?;
    if present
        != TABLES.len()
            - usize::from(predecessor.is_some_and(|format| format < VERSION_METADATA_FORMAT))
        || predecessor.is_some_and(|format| !(43..RECORD_FORMAT).contains(&format))
    {
        return Err(VersionError::InvalidEncoding("incomplete restoration record schema").into());
    }
    validate_guards(connection, predecessor)?;
    if let Some(format) = predecessor {
        upgrade_metadata(connection, format)?;
    }
    Ok(())
}

fn upgrade_metadata(transaction: &Connection, format: i64) -> PhysicalResult<()> {
    let valid: bool = transaction.query_row(
        "SELECT count(*) = 1 AND coalesce(min(format) = ?1, 0) FROM _uqa_mvcc_metadata",
        [format],
        |row| row.get(0),
    )?;
    if !valid {
        return Err(VersionError::InvalidEncoding("invalid predecessor record format").into());
    }
    if format < 59 {
        super::version_metadata::upgrade(transaction, format >= VERSION_METADATA_FORMAT)?;
    }
    if format < 28 {
        transaction.execute_batch("ALTER TABLE _uqa_mvcc_heads ADD COLUMN compacted INTEGER NOT NULL DEFAULT 0 CHECK(compacted IN (0, 1))")?;
    }
    if format < 29 {
        transaction.execute_batch(super::runs::TABLE.1)?;
        for action in ["INSERT", "UPDATE", "DELETE"] {
            transaction.execute_batch(&trigger(super::runs::TABLE.0, action).1)?;
        }
    }
    // Existing key/revision identities, histories, receipts and identifier reservations keep their commit boundaries.
    if format < 5 {
        let (name, sql) = super::identifiers::TABLE;
        transaction.execute_batch(sql)?;
        for action in ["INSERT", "UPDATE", "DELETE"] {
            transaction.execute_batch(&trigger(name, action).1)?;
        }
    }
    super::identifiers::consolidate_diskann_generations(transaction)?;
    transaction
        .execute_batch("ALTER TABLE _uqa_mvcc_metadata RENAME TO _uqa_mvcc_previous_metadata")?;
    transaction.execute_batch(TABLES[0].1)?;
    let pending = if format >= 43 {
        "restore_target"
    } else {
        "NULL"
    };
    let receipt_limit = if format >= 44 {
        "receipt_limit"
    } else {
        "65536"
    };
    transaction.execute_batch(&format!("INSERT INTO _uqa_mvcc_metadata SELECT singleton, {RECORD_FORMAT}, database_id, allocated, sequence, mapping, {pending}, {receipt_limit}, sequence FROM _uqa_mvcc_previous_metadata; DROP TABLE _uqa_mvcc_previous_metadata;"))?;
    if format >= 44 {
        for action in ["INSERT", "UPDATE", "DELETE"] {
            transaction.execute_batch(&trigger(TABLES[0].0, action).1)?;
        }
        return Ok(());
    }
    transaction.execute_batch(
        "ALTER TABLE _uqa_mvcc_transactions RENAME TO _uqa_mvcc_previous_transactions",
    )?;
    transaction.execute_batch(TABLES[3].1)?;
    transaction.execute_batch("INSERT INTO _uqa_mvcc_transactions (allocation, status, sequence, fingerprint) SELECT * FROM _uqa_mvcc_previous_transactions; DROP TABLE _uqa_mvcc_previous_transactions;")?;
    for action in ["INSERT", "UPDATE", "DELETE"] {
        transaction.execute_batch(&trigger(TABLES[3].0, action).1)?;
    }
    for action in ["INSERT", "UPDATE", "DELETE"] {
        transaction.execute_batch(&trigger(TABLES[0].0, action).1)?;
    }
    Ok(())
}