sql/README.md

# SQLite abstraction layer

[TOC]

## SQLite for system designers

[SQLite](https://www.sqlite.org/) is a
[relational database management system (RDBMS)](https://en.wikipedia.org/wiki/Relational_database#RDBMS)
that [supports most of SQL](https://www.sqlite.org/lang.html).

SQLite is architected as a library that can be embedded in another application,
such as Chrome. SQLite runs in the application's process, and shares its memory
and other resources. This is similar to embedded databases like
[LevelDB](https://github.com/google/leveldb) and
[BerkeleyDB](https://en.wikipedia.org/wiki/Berkeley_DB). By contrast, most
popular RDMBSes, like [PostgreSQL](https://www.postgresql.org/) and
[MySQL](https://www.mysql.com/), are structured as standalone server processes
that accept queries from client processes.

TODO: Explain the process model and locking

TODO: Explain Chrome decisions -- exclusive locking, full per-feature isolation
(separate databases and page caches)


## SQLite for database designers

The section summarizes aspects of SQLite that are relevant to schema and
query design, and may be surprising to readers with prior experience in other
popular SQL database systems, such as
[PostgreSQL](https://www.postgresql.org/) and [MySQL](https://www.mysql.com/).


### Data types

SQLite stores data using [5 major types](https://www.sqlite.org/datatype3.html),
which are summarized below.

1. NULL is a special type for the `NULL` value.

2. INTEGER represents big-endian twos-complement integers. Boolean values
   (`TRUE` and `FALSE`) are represented as the integer values 1 and 0.

3. REAL represents IEEE 754-2008 64-bit floating point numbers.

4. TEXT represents strings (sequences of characters) encoded using a
   [supported SQLite encoding](https://www.sqlite.org/c3ref/c_any.html). These
   values are
   [sorted](https://www.sqlite.org/datatype3.html#sort_order) according to
   [a collating sequence](https://www.sqlite.org/datatype3.html#collation) or
   [a collating function](https://www.sqlite.org/c3ref/create_collation.html).

5. BLOB represents sequences of bytes that are opaque to SQLite. These values are
   sorted using the bitwise binary comparison offered by
   [memcmp](https://en.cppreference.com/w/cpp/string/byte/memcmp).

SQLite stores index keys and row values (records / tuples) using
[a tightly packed format](https://sqlite.org/fileformat2.html#record_format)
that makes heavy use of [varints](https://sqlite.org/fileformat2.html#varint)
and variable-length fields. The column types have almost no influence on the
encoding of values. This has the following consequences.

* All SQL integer types, such as `TINYINT` and `BIGINT`, are treated as aliases
  for `INTEGER`.
* All SQL non-integer numeric types, such as `DECIMAL`, `FLOAT`, and
  `DOUBLE PRECISION` are treated as aliases for `REAL`.
* Numeric precision and scale specifiers, such as `DECIMAL(5,2)` are ignored.
* All string types, such as `CHAR`, `CHARACTER VARYING`, `VARCHAR`, and `CLOB`,
  are treated as aliases for `TEXT`.
* Maximum string length specifiers, such as `CHAR(255)` are ignored.

SQLite uses clever heuristics, called
[type affinity](https://www.sqlite.org/datatype3.html#type_affinity),
to map SQL column types such as `VARCHAR` to the major types above.

Chrome database schemas should avoid type affinity, and should not include any
information ignored by SQLite.


### Indexing

SQLite [uses B-trees](https://www.sqlite.org/fileformat2.html#pages) to store
both table and index data.

The exclusive use of B-trees reduces the amount of schema design decisions.
Notable examples:

* There is no equivalent to
  [PostgreSQL's index types](https://www.postgresql.org/docs/13/indexes-types.html).
  In particular, since there are no hashed indexes, the design does not need to
  consider whether the index only needs to support equality queries, as opposed
  to greater/smaller than comparisons.

* There is no equivalent to
  [PostgreSQL's table access methods](https://www.postgresql.org/docs/13/tableam.html).
  Each table is clustered by a primary key index, which is implicitly stored in
  the table's B-tree.

By default, table rows (records / tuples) are stored in a B-tree keyed by
[rowid](https://sqlite.org/lang_createtable.html#rowid), an automatically
assigned 64-bit integer key. Effectively, these tables are clustered by rowid,
which acts as an implicit primary key. Opting out of this SQLite-specific
default requires appending
[`WITHOUT ROWID`](https://sqlite.org/withoutrowid.html) to the `CREATE TABLE`
instruction.

SQLite's [B-tree page format](https://sqlite.org/fileformat2.html#b_tree_pages)
has optimized special cases for tables clustered by rowid. This makes rowid the
most efficient [surrogate key](https://en.wikipedia.org/wiki/Surrogate_key)
implementation in SQLite. To make this optimization easier to use, any column
that is a primary key and has an `INTEGER` type is considered an alias for
rowid.

Each SQLite index
[is stored in a B-tree](https://sqlite.org/fileformat2.html#representation_of_sql_indices).
Each index entry is stored as a B-tree node whose key is made up of the record's
index key column values, followed by the record's primary key column values.

`WITHOUT ROWID` table indexes can include primary key columns without additional
storage costs. This is because indexes for `WITHOUT ROWID` tables enjoy
[a space optimization](https://sqlite.org/fileformat2.html#representation_of_sql_indices)
where columns in both the primary key and the index key are not stored twice in
B-tree nodes.


### Query processing

[At a high level](https://www.sqlite.org/arch.html), SQLite compiles SQL queries
into bytecode executed by a virtual machine called the VDBE, or
[the bytecode engine](https://www.sqlite.org/opcode.html). A compiled query can
be executed multiple times, amortizing the costs of query parsing and planning.
Chrome's SQLite abstraction layer makes it easy to use compiled queries.

The following SQLite documentation pages cover the query planner and
optimizer.

1. [query planner overview](https://www.sqlite.org/queryplanner.html)
2. [query optimizer overview](https://www.sqlite.org/optoverview.html)
3. [`EXPLAIN QUERY PLAN` output description](https://www.sqlite.org/eqp.html)

TODO: Present a simplified model that's sufficient for most database design.


## General advice

The following pieces of advice usually come up in code reviews.


### Quickly iterating on SQL statements

[The SQLite shell](https://sqlite.org/cli.html) offers quick feedback for
converging on valid SQL statement syntax, and avoiding SQLite features that are
disabled in Chrome. In addition, the
[`EXPLAIN`](https://www.sqlite.org/lang_explain.html) and
[`EXPLAIN QUERY PLAN`](https://www.sqlite.org/eqp.html) statements show the
results of SQLite's query planner and optimizer, which are very helpful for
reasoning about the performance of complex queries. The SQLite shell directive
`.eqp on` automatically issues `EXPLAIN QUERY PLAN` for all future commands.


The following commands set up SQLite shells using Chrome's build of SQLite.

```sh
autoninja -C out/Default sqlite_shell sqlite_dev_shell
```

* `sqlite_shell` runs the SQLite build that we ship in Chrome. It offers the
  ground truth on whether a SQL statement can be used in Chrome code or not.
* `sqlite_dev_shell` enables the `EXPLAIN` and `EXPLAIN QUERY PLAN` statements,
  as well as a few features used by [Perfetto](https://perfetto.dev/)'s analysis
  tools.


### SQL style

SQLite queries are usually embedded as string literals in C++ code. The
advice here has the following goals.

1. Easy to read queries. The best defense against subtle bugs is making the
   queries very easy to read, so that any bugs become obvious at code review
   time. SQL string literals don't benefit from our code analysis
   infrastructure, so the only lines of defense against bugs are testing and
   code review.

2. Simplify crash debugging. We will always have a low volume of non-actionable
   crash reports, because Chrome runs on billions of devices, some of which have
   faulty RAM or processors.

3. No unnecessary performance overheads. The C++ optimizer doesn't understand
   SQL query literals, so the queries end up as written in the Chrome binary.
   Extra characters cost binary size, as well as CPU time (which turns into
   battery usage) during query parsing.

4. Match the embedding language (C++) style guide. This reduces the mental
   context switch overhead for folks who write and/or review C++ code that
   contains SQL.

Format statements like so.

```cc
  static constexpr char kOriginInfoSql[] =
      // clang-format off
      "CREATE TABLE origin_infos("
        "origin TEXT NOT NULL,"
        "last_modified INTEGER NOT NULL,"
        "secure INTEGER NOT NULL)";
      // clang-format on

  static constexpr char kInsertSql[] =
     // clang-format off
     "INSERT INTO infos(origin,last_modified,secure) "
       "VALUES (?,?,?)";
     // clang-format on

  static constexpr char kSelectSql[] =
     // clang-format off
     "SELECT origin,last_modified,secure FROM origins "
       "WHERE last_modified > ? "
       "ORDER BY last_modified";
     // clang-format on
```

* [SQLite keywords](https://sqlite.org/lang_keywords.html) should use ALL CAPS.
  This makes SQL query literals easier to distinguish and search for.

* Identifiers, such as table and row names, should use snake_case.

* Identifiers, keywords, and parameter placeholders (`?`) should be separated by
  exactly one character. Separators may be spaces (` `), commas (`,`), or
  parentheses (`(`, `)`).

* Statement-ending semicolons (`;`) are omitted.

* SQL statements are stored in variables typed `static constexpr char[]`, or in
  string literals passed directly to methods.

* [`INSERT` statements](https://sqlite.org/lang_insert.html) should list all the
  table columns by name, in the same order as the corresponding `CREATE TABLE`
  statements.

* [`SELECT` statements](https://sqlite.org/lang_select.html) should list the
  desired table columns by name, in the same order as the corresponding
  `CREATE TABLE` statements. `SELECT *` is strongly discouraged, at least until
  we have schema checks on database opens.

* [`SELECT` statements](https://sqlite.org/lang_select.html) that retrieve more
  than one row should include an
  [`ORDER BY` clause](https://sqlite.org/lang_select.html#the_order_by_clause)
  to clarify the implicit ordering.
  * SELECTs whose outer loop is a table search or table scan implicitly order
    results by [rowid](https://sqlite.org/lang_createtable.html#rowid) or, in
    the case of [`WITHOUT ROWID`](https://sqlite.org/withoutrowid.html) tables,
    by the table's primary key.
  * SELECTs whose outer loop is an index scan or index search order results
    according to that index.

* [`CREATE INDEX` statements](https://sqlite.org/lang_createindex.html) should
  immediately follow the
  [`CREATE TABLE` statement](https://sqlite.org/lang_createtable.html) for the
  indexed table.

* Explicit `CREATE UNIQUE INDEX` statements should be preferred to
  [`UNIQUE` constraints on `CREATE TABLE`](https://sqlite.org/lang_createtable.html#unique_constraints).

* Values must either be embedded in the SQL statement string literal, or bound
  using [parameters](https://www.sqlite.org/lang_expr.html#varparam).

* Parameter placeholders should always use the `?` syntax. Alternative syntaxes,
  such as `?NNN` or `:AAAA`, have few benefits in a codebase where the `Bind`
  statements are right next to the queries, and are less known to readers.

* Do not execute multiple SQL statements (e.g., by calling `Step()` or `Run()`
  on `sql::Statement`) on the same C++ line. It's difficult to get more than
  line numbers from crash reports' stack traces.


### Schema style

Identifiers (table / index / column names and aliases) must not be
[current SQLite keywords](https://sqlite.org/lang_keywords.html). Identifiers
may not start with the `sqlite_` prefix, to avoid conflicting with the name of a
[SQLite internal schema object](https://www.sqlite.org/fileformat2.html#storage_of_the_sql_database_schema).

Column types should only be one of the the SQLite storage types (`INTEGER`,
`REAL`, `TEXT`, `BLOB`), so readers can avoid reasoning about SQLite's type
affinity.

Columns that will store boolean values should have the `INTEGER` type.

Columns that will store `base::Time` values should have the `INTEGER` type.
Values should be serialized using `sql::Statement::BindTime()` and deserialized
using `sql::Statement::ColumnTime()`.

Column types should not include information ignored by SQLite, such as numeric
precision or scale specifiers, or string length specifiers.

Columns should have
[`NOT NULL` constraints](https://sqlite.org/lang_createtable.html#not_null_constraints)
whenever possible. This saves maintainers from having to reason about the less
intuitive cases of [`NULL` handling](https://sqlite.org/nulls.html).

`NOT NULL` constraints must be explicitly stated in column definitions that
include `PRIMARY KEY` specifiers. For historical reasons, SQLite
[allows NULL primary keys](https://sqlite.org/lang_createtable.html#the_primary_key)
in most cases.  When a table's primary key is composed of multiple columns,
each column's definition should have a `NOT NULL` constraint.

Columns should avoid `DEFAULT` values. Columns that have `NOT NULL` constraints
and lack a `DEFAULT` value are easier to review and maintain, as SQLite takes
over the burden of checking that `INSERT` statements aren't missing these
columns.

Surrogate primary keys should use the column type `INTEGER PRIMARY KEY`, to take
advantage of SQLite's rowid optimizations.
[`AUTOINCREMENT`](https://www.sqlite.org/autoinc.html) should only be used where
primary key reuse would be unacceptable.


### Discouraged features

SQLite exposes a vast array of functionality via SQL statements. The following
features are not a good match for SQL statements used by Chrome feature code.

#### PRAGMA statements {#no-pragmas}

[`PRAGMA` statements](https://www.sqlite.org/pragma.html) should never be used
directly. Chrome's SQLite abstraction layer should be modified to support the
desired effects instead.

Direct `PRAGMA` use limits our ability to customize and secure our SQLite build.
`PRAGMA` statements may turn on code paths with less testing / fuzzing coverage.
Furthermore, some `PRAGMA` statements invalidate previously compiled queries,
reducing the efficiency of Chrome's compiled query cache.

#### Virtual tables {#no-virtual-tables}

[`CREATE VIRTUAL TABLE` statements](https://www.sqlite.org/vtab.html) should not
be used. The desired functionality should be implemented in C++, and access
storage using standard SQL statements.

Virtual tables are [SQLite's module system](https://www.sqlite.org/vtab.html).
SQL statements on virtual tables are essentially running arbitrary code, which
makes them very difficult to reason about and maintain. Furthermore, the virtual
table implementations don't receive the same level of fuzzing coverage as the
SQLite core.

Access to virtual tables is disabled by default for SQLite databases opened with
Chrome's `sql::Database` infrastructure. This is intended to steer feature
developers away from the discouraged feature.

Chrome's SQLite build has virtual table functionality reduced to the minimum
needed to support [FTS3](https://www.sqlite.org/fts3.html) in WebSQL, and an
internal feature.
[SQLite's run-time loading mechanism](https://www.sqlite.org/loadext.html) is
disabled, and most
[built-in virtual tables](https://www.sqlite.org/vtablist.html) are disabled as
well.

After
[WebSQL](https://www.w3.org/TR/webdatabase/) is removed from Chrome, we plan
to disable SQLite's virtual table support using
[SQLITE_OMIT_VIRTUALTABLE](https://sqlite.org/compile.html#omit_virtualtable).

#### Foreign key constraints {#no-foreign-keys}

[SQL foreign key constraints](https://sqlite.org/foreignkeys.html) should not be
used. All data validation should be performed using explicit `SELECT` statements
(generally wrapped as helper methods) inside transactions. Cascading deletions
should be performed using explicit `DELETE` statements inside transactions.

Chrome features cannot rely on foreign key enforcement, due to the
possibility of data corruption. Furthermore, foreign key constraints make it
more difficult to reason about system behavior (Chrome feature code + SQLite)
when the database gets corrupted. Foreign key constraints also make it more
difficult to reason about query performance.

After
[WebSQL](https://www.w3.org/TR/webdatabase/) is removed from Chrome, we plan
to disable SQLite's foreign key support using
[SQLITE_OMIT_FOREIGN_KEY](https://sqlite.org/compile.html#omit_foreign_key).

#### CHECK constraints {#no-checks}

[SQL CHECK constraints](https://sqlite.org/lang_createtable.html#check_constraints)
should not be used, for the same reasons as foreign key constraints. The
equivalent checks should be performed in C++, typically using `DCHECK`.

After
[WebSQL](https://www.w3.org/TR/webdatabase/) is removed from Chrome, we plan
to disable SQLite's CHECK constraint support using
[SQLITE_OMIT_CHECK](https://sqlite.org/compile.html#omit_check).

#### Triggers {#no-triggers}

[SQL triggers](https://sqlite.org/lang_createtrigger.html) should not be used.

Triggers significantly increase the difficulty of reviewing and maintaining
Chrome features that use them.

Triggers are not executed on SQLite databases opened with Chrome's
`sql::Database` infrastructure. This is intended to steer feature developers
away from the discouraged feature.

After [WebSQL](https://www.w3.org/TR/webdatabase/) is removed from Chrome, we
plan to disable SQLite's trigger support using
[SQLITE_OMIT_TRIGGER](https://sqlite.org/compile.html#omit_trigger).

#### Common Table Expressions {#no-ctes}

[SQL Common Table Expressions (CTEs)](https://sqlite.org/lang_with.html) should
not be used. Chrome's SQL schemas and queries should be simple enough that
the factoring afforded by
[ordinary CTEs](https://sqlite.org/lang_with.html#ordinary_common_table_expressions)
is not necessary.
[Recursive CTEs](https://sqlite.org/lang_with.html#recursive_common_table_expressions)
should be implemented in C++.

Common Table Expressions do not open up any query optimizations that would not
be available otherwise, and make it more difficult to review / analyze queries.

#### Views {#no-views}

SQL views, managed by the
[`CREATE VIEW` statement](https://www.sqlite.org/lang_createview.html) and the
[`DROP VIEW` statement](https://www.sqlite.org/lang_dropview.html), should not
be used. Chrome's SQL schemas and queries should be simple enough that the
factoring afforded by views is not necessary.

Views are syntactic sugar, and do not open up any new SQL capabilities. SQL
statements on views are more difficult to understand and maintain, because of
the extra layer of indirection.

Access to views is disabled by default for SQLite databases opened with Chrome's
`sql::Database` infrastructure. This is intended to steer feature developers
away from the discouraged feature.

After
[WebSQL](https://www.w3.org/TR/webdatabase/) is removed from Chrome, we plan
to disable SQLite's VIEW support using
[SQLITE_OMIT_VIEW](https://www.sqlite.org/compile.html#omit_view).

#### Double-quoted string literals {#no-double-quoted-strings}

String literals should always be single-quoted. That being said, string literals
should be rare in Chrome code, because any user input must be injected using
statement parameters and the `Statement::Bind*()` methods.

Double-quoted string literals are non-standard SQL syntax. The SQLite authors
[currently consider this be a misfeature](https://www.sqlite.org/quirks.html#double_quoted_string_literals_are_accepted).

SQLite support for double-quoted string literals is disabled for databases
opened with Chrome's `sql::Database` infrastructure. This is intended to steer
feature developers away from this discouraged feature.

After
[WebSQL](https://www.w3.org/TR/webdatabase/) is removed from Chrome, we plan
to disable SQLite's support for double-quoted string literals using
[SQLITE_DQS=0](https://www.sqlite.org/compile.html#dqs).

#### Compound SELECT statements {#no-compound-queries}

[Compound SELECT statements](https://www.sqlite.org/lang_select.html#compound_select_statements)
should not be used. Such statements should be broken down into
[simple SELECT statements](https://www.sqlite.org/lang_select.html#simple_select_processing),
and the operators `UNION`, `UNION ALL`, `INTERSECT` and `EXCEPT` should be
implemented in C++.

A single compound SELECT statement is more difficult to review and properly
unit-test than the equivalent collection of simple SELECT statements.
Furthermore, the compound SELECT statement operators can be implemented more
efficiently in C++ than in SQLite's bytecode interpreter (VDBE).

After
[WebSQL](https://www.w3.org/TR/webdatabase/) is removed from Chrome, we plan
to disable SQLite's compound SELECT support using
[SQLITE_OMIT_COMPOUND_SELECT](https://www.sqlite.org/compile.html#omit_compound_select).

#### Built-in functions {#no-builtin-functions}

SQLite's [built-in functions](https://sqlite.org/lang_corefunc.html) should be
only be used in SQL statements where they unlock significant performance
improvements. Chrome features should store data in a format that leaves the most
room for query optimizations, and perform any necessary transformations after
reading / before writing the data.

* [Aggregation functions](https://sqlite.org/lang_aggfunc.html) are best
  replaced with C++ code that iterates over rows and computes the desired
  results.
* [Date and time functions](https://sqlite.org/lang_datefunc.html) are best
  replaced by `base::Time` functionality.
* String-processing functions, such as
  [`printf()`](https://sqlite.org/printf.html) and `trim()` are best replaced
  by C++ code that uses the helpers in `//base/strings/`.
* Wrappers for [SQLite's C API](https://sqlite.org/c3ref/funclist.html), such as
  `changes()`, `last_insert_rowid()`, and `total_changes()`, are best replaced
  by functionality in `sql::Database` and `sql::Statement`.
* SQLite-specific functions, such as  `sqlite_source_id()` and
  `sqlite_version()` should not be necessary in Chrome code, and may suggest a
  problem in the feature's design.

[Math functions](https://sqlite.org/lang_mathfunc.html) and
[Window functions](https://sqlite.org/windowfunctions.html#biwinfunc) are
disabled in Chrome's SQLite build.

#### ATTACH DATABASE statements {#no-attach}

[`ATTACH DATABASE` statements](https://www.sqlite.org/lang_attach.html) should
not be used. Each Chrome feature should store its data in a single database.
Chrome code should not assume that transactions across multiple databases are
atomic.

We plan to remove all existing `ATTACH DATABASE` use from Chrome.