tree: 150f0330418f924c718391190b9287be11bf7005 [path history] [tgz]
  1. BUILD.gn
  2. DEPS
  3. DIR_METADATA
  4. OWNERS
  5. README.md
  6. database.cc
  7. database.h
  8. database_memory_dump_provider.cc
  9. database_memory_dump_provider.h
  10. database_unittest.cc
  11. error_delegate_util.cc
  12. error_delegate_util.h
  13. init_status.h
  14. initialization.cc
  15. initialization.h
  16. internal_api_token.h
  17. meta_table.cc
  18. meta_table.h
  19. meta_table_unittest.cc
  20. recover_module/
  21. recovery.cc
  22. recovery.h
  23. recovery_unittest.cc
  24. sandboxed_vfs.cc
  25. sandboxed_vfs.h
  26. sandboxed_vfs_file.cc
  27. sandboxed_vfs_file.h
  28. sql_features.cc
  29. sql_features.h
  30. sql_memory_dump_provider.cc
  31. sql_memory_dump_provider.h
  32. sql_memory_dump_provider_unittest.cc
  33. sqlite_features_unittest.cc
  34. statement.cc
  35. statement.h
  36. statement_id.cc
  37. statement_id.h
  38. statement_id_unittest.cc
  39. statement_unittest.cc
  40. test/
  41. transaction.cc
  42. transaction.h
  43. transaction_unittest.cc
  44. vfs_wrapper.cc
  45. vfs_wrapper.h
  46. vfs_wrapper_fuchsia.cc
  47. vfs_wrapper_fuchsia.h
sql/README.md

SQLite abstraction layer

SQLite for system designers

SQLite is a relational database management system (RDBMS) that supports most of SQL.

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 and BerkeleyDB. By contrast, most popular RDMBSes, like PostgreSQL and MySQL, 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 and MySQL.

Data types

SQLite stores data using 5 major types, 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. These values are sorted according to a collating sequence or a collating function.

  5. BLOB represents sequences of bytes that are opaque to SQLite. These values are sorted using the bitwise binary comparison offered by memcmp.

SQLite stores index keys and row values (records / tuples) using a tightly packed format that makes heavy use of varints 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, 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 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. 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. 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, 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 to the CREATE TABLE instruction.

SQLite's B-tree page format has optimized special cases for tables clustered by rowid. This makes rowid the most efficient 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.

Query processing

At a high level, SQLite compiles SQL queries into bytecode executed by a virtual machine called the VDBE, or the bytecode engine. 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
  2. query optimizer overview
  3. EXPLAIN QUERY PLAN output description

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.

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.

  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 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 should list all the table columns by name, in the same order as the corresponding CREATE TABLE statements.

  • SELECT statements 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 that retrieve more than one row should include an ORDER BY clause to clarify the implicit ordering.

    • SELECTs whose outer loop is a table search or table scan implicitly order results by rowid or, in the case of WITHOUT ROWID 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 should immediately follow the CREATE TABLE statement for the indexed table.

  • Explicit CREATE UNIQUE INDEX statements should be preferred to UNIQUE constraints on CREATE TABLE.

  • Values must either be embedded in the SQL statement string literal, or bound using parameters.

  • 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

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 the NOT NULL constraint whenever possible. This saves maintainers from having to reason about the less intuitive cases of NULL handling.

Columns should avoid DEFAULT values. This moves the burden of checking that INSERT statements aren't missing any columns from the code reviewer to SQLite.

Surrogate primary keys should use the column type INTEGER PRIMARY KEY, to take advantage of SQLite's rowid optimizations. AUTOINCREMENT should only be used where primary key reuse would be unacceptable.

Discouraged features

PRAGMA statements

PRAGMA statements 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

CREATE VIRTUAL TABLE statements 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. 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.

Chrome's SQLite build has virtual table functionality reduced to the minimum needed to support FTS3 in WebSQL, and an internal feature. SQLite's run-time loading mechanism is disabled, and most built-in virtual tables are disabled as well.

After WebSQL is removed from Chrome, we plan to disable SQLite's virtual table support using SQLITE_OMIT_VIRTUALTABLE.

Foreign key constraints

SQL foreign key constraints 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 is removed from Chrome, we plan to disable SQLite's foreign key support using SQLITE_OMIT_FOREIGN_KEY.

CHECK constraints

SQL 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 is removed from Chrome, we plan to disable SQLite's CHECK constraint support using SQLITE_OMIT_CHECK.

Triggers

SQL triggers should not be used.

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

After WebSQL is removed from Chrome, we plan to disable SQLite's trigger support using SQLITE_OMIT_TRIGGER.

Common Table Expressions

SQL Common Table Expressions (CTEs) should not be used. Chrome's SQL schemas and queries should be simple enough that the factoring afforded by ordinary CTEs is not necessary. Recursive CTEs 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

SQL views, managed by the CREATE VIEW statement and the DROP VIEW statement, 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.

After WebSQL is removed from Chrome, we plan to disable SQLite's VIEW support using SQLITE_OMIT_VIEW.

Compound SELECT statements

Compound SELECT statements should not be used. Such statements should be broken down into simple SELECT statements, 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 is removed from Chrome, we plan to disable SQLite's compound SELECT support using SQLITE_OMIT_COMPOUND_SELECT.

ATTACH DATABASE statements

ATTACH DATABASE statements 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.