<?xml version="1.0" encoding="utf-8"?>

<!-- Copyright (c) 2007-2010 Nokia Corporation and/or its subsidiary(-ies) All rights reserved. -->

<!-- This component and the accompanying materials are made available under the terms of the License 

"Eclipse Public License v1.0" which accompanies this distribution, 

and is available at the URL "http://www.eclipse.org/legal/epl-v10.html". -->

<!-- Initial Contributors:

    Nokia Corporation - initial contribution.

Contributors: 

-->

<!DOCTYPE concept

  PUBLIC "-//OASIS//DTD DITA Concept//EN" "concept.dtd">

<concept id="GUID-2C60C1C3-82B5-5ED3-98DF-E787193E8797" xml:lang="en"><title>SQLite

Technology Guide</title><shortdesc>This document provides background information on the internal workings

of SQLite, the database engine used by Symbian SQL.</shortdesc><prolog><metadata><keywords/></metadata></prolog><conbody>

<section id="GUID-54B0C26F-873B-4FDD-9CB6-163B65789ABF"><title>Purpose</title> <p>SQLite is a fast efficient database engine

freely available to anyone to use in any way the want. The information in

this document provides important background information that you will need

to know in order to make the most of Symbian SQL and SQLite on Symbian platform. </p> </section>

<section id="GUID-ECAB0622-BF6B-43F8-ACC9-0E64E95A164E"><title>Intended audience:</title> <p>This document is intended to

be used by Symbian platform developrs and third party application developers. </p> </section>

<section id="GUID-612B113B-C89E-5870-A586-F163D333A19B"><title>The architecture

and operation of SQLite</title> <p>The figure below shows the major modules

within SQLite. SQL statements that are to be processed are sent to the SQL

Compiler module which does a syntactic and semantic analysis of the SQL statements

and generates bytecode for carrying out the work of each statement. The generated

bytecode is then handed over to a Virtual Machine for evaluation. </p> <fig id="GUID-370A849E-D1CC-5510-9211-D732C2D1DF6B">

<title>              Simplified SQLite Architecture            </title>

<image href="GUID-D3881E09-4519-5E3F-9978-C9FEFD123B85_d0e593157_href.png" placement="inline"/>

</fig> <p>The Virtual Machine considers the database to be a set of B-Trees,

one B-Tree for each table and one B-Tree for each index. The logic for creating,

reading, writing, updating, balancing and destroying B-Trees is contained

in the B-Tree module. </p> <p>The B-Tree module uses the Pager module to access

individual pages of the database file. The Pager module abstracts the database

file into zero or more fixed-sized pages with atomic commit and rollback semantics. </p> <p>All

interaction with the underlying file system and operating system occurs through

the OS Adaptation Layer. </p> <p id="GUID-9AEF6B71-B6B6-5A83-9ED2-547BB60A6752"><b>SQL Statements as Computer

Programs</b> </p> <p>A key to understanding the operation of SQLite, or any

other SQL relational database engine, is to recognize that each statement

of SQL is really a small computer program. </p> <p>Users of SQL database engines

sometimes fail to grasp this simple truth because SQL is a peculiar programming

language. In most other computer languages the programmer must specify exactly <i>how</i> a

computation is to take place. But in SQL the programmer specifies <i>what</i> results

are needed and lets the SQL Compiler worry about how to achieve them. </p> <p>All

SQL database engines contain a SQL Compiler of some kind. The job of this

compiler is to convert SQL statements into procedural programs for obtaining

the desired result. Most SQL database engines translate SQL statements into

tree structures. The Virtual Machine modules of these databases then walk

these tree structures to evaluate the SQL statements. A few SQL database engines

translate SQL statements into native machine code. </p> <p>SQLite takes an

intermediate approach and translates SQL statements into small programs written

in a bytecode language. The SQLite bytecode is similar in concept to Java

bytecode, the parrot bytecode of Perl, or to the p-code of the UCSD Pascal

implementation. SQLite bytecode consists of operators that work with values

contained in registers or on a stack. Typical bytecode operators do things

like: </p> <ul>

<li id="GUID-75B81AB2-56C8-5D76-AA4C-D2E1CBF3B868"><p>Push a literal value

onto the stack </p> </li>

<li id="GUID-4E4C868D-18BD-5B2C-9188-8303EEA062B7"><p>Pop two numbers off

of the stack, add them together and push the result back onto the stack </p> </li>

<li id="GUID-1B17CC17-D06C-5883-AC1C-768E87E60BF0"><p>Move the top element

of the stack into a specific memory register </p> </li>

<li id="GUID-B475E9E0-FE03-5C1F-9C2E-F35C866D53B3"><p>Jump to a specific instruction

if the top element of the stack is zero </p> </li>

</ul> <p>The SQLite bytecode supports about 125 different opcodes. There is

a remarkable resemblance between SQLite bytecode and assembly language. The

major difference is that SQLite bytecode contains a few specialized opcodes

designed to facilitate database operations that commonly occur in SQL. </p> <p>Just

as you do not need to understand the details of x86 or ARM7 assembly language

in order to make effective use of C++, so also you do not need to know any

of the details of SQLite bytecode in order to make the best use of SQLite.

The reader need only recognize that the bytecode is there and is being used

behind the scenes. </p> <p>Those who are interested can peruse the definitions

of the bytecodes in the SQLite documentation. But the details of the various

bytecodes are not important to making optimal use of SQLite and so no further

details on the bytecodes will be provided in this document. </p> <p id="GUID-AFB97D35-56B8-5B12-8B6A-0AC6A4DC9088"><b>The B-Tree Module</b> </p> <p>A

SQLite database file consists of one or more b-trees. Each table and each

index is a separate b-tree. </p> <p>A b-tree is a data structure discovered

in 1970 by Rudolf Bayer and Edward McCreight and is widely used in the implementation

of databases. B-trees provide an efficient means of organizing data stored

on an external storage device with fixed-sized blocks, such as a disk drive

or a flash memory card. Each entry in a b-tree has a unique key and arbitrary

data. The entries are ordered by their key which permits efficient lookup

using a binary search. The b-tree algorithm guarantees worst-case insert,

update, and access times of O(log N) where N is the number of entries. </p> <p>In

SQLite, each table is a separate b-tree and each row of the table is a separate

entry. The b-tree key is the RowID or INTEGER PRIMARY KEY for the row and

other columns in the row are stored in the data for the b-tree entry. Tables

use a variant of the b-tree algorithm call <i>b+trees</i> in which all data

is stored on the leaves of the tree. </p> <p>Indexes are also stored as b-trees

with one entry in the b-tree for each row of the table being indexed. The

b-tree key is composed of the values for the columns being indexed followed

by the RowID of the corresponding row in the table. Indexes do not use the

data part of the b-tree entry. Indexes use the original Bayer and McCreight

b-tree algorithm, not b+trees as tables do. </p> <p>The number of pages in

a b-tree can grow and shrink as information is inserted and removed. When

new information is inserted and the b-tree needs to grow, the B-Tree Module

may reuse pages in the database that have fallen into disuse or it may ask

the Pager module to allocate new pages at the end of the database file to

accommodate this growth. When a b-tree shrinks and pages are no longer needed,

the surplus pages are added to a <i>free-list</i> to be reused by future page

requests. The B-Tree module takes care of managing this free-list of unused

pages. </p> <p id="GUID-640FDE57-C615-55AF-9579-79B0D718A78E"><b>The Pager Module</b> </p> <p>The

Pager module (also called simply “the pager”) manages the reading and writing

of raw data from the database file such that reads are always consistent and

isolated and so that writes are atomic. </p> <p>The pager treats the database

file as a sequence of zero or more fixed-size pages. A typical page size might

be 1024 bytes. Within a single database all pages are the same size. The first

page of a database file is called page 1. The second is page 2. There is no

page 0. SQLite uses a page number of 0 internally to mean “no such page”. </p> <p>When

the B-Tree module needs a page of data from the database file, it asks for

the page by number from the pager. The pager then returns a pointer to the

requested data. The pager keeps a cache of recently accessed database pages

so in many cases no disk I/O has to occur to fulfil a page request. </p> <p>The

B-Tree module notifies the pager before making any changes to a page and the

pager then saves a copy of the original page content in a rollback journal

file. The rollback journal is used to restore the database to its original

state if a ROLLBACK occurs. </p> <p>After making changes to one or more pages,

the B-Tree Module may ask the pager to commit those changes. The pager then

goes through a carefully designed sequence of steps that ensure that changes

to the database are atomic. If the update process is interrupted by a program

crash, a system crash, or even a power failure, the next time the database

is accessed it will appear that either all the changes were made or else none

of them. </p> <p id="GUID-3C970D41-7611-5AF6-B5B4-C486B5DA3875"><b>Database File Format Summary</b> </p> <p>A

SQLite database file consists of one or more fixed-sized pages. The first

page contains a 100-byte header that identifies the file as a SQLite database

and which contains operating parameters such as the page size, a file format

version number, the first page of the free-list, flags indicating whether

or not autovacuum is enabled, and so forth. </p> <p>The content of the database

is stored in one or more b-trees. Each b-tree has <i>root </i> page which

never moves. If the table or index is small enough to fit entirely on the

root page, then that one page contains everything there is to know about the

table or index. But most tables and indexes require more space and additional

pages must be allocated. </p> <p>The root page contains pointers (actually

page numbers) to the other pages in the b-tree. So given the root page of

a b-tree that implements a table or index, the B-Tree module is able to follow

pointers to locate any entry in the b-tree and thus any row in the corresponding

table or index. </p> <p><note> Auxiliary pages of a b-tree can be allocated

from anywhere within the database file and so the pages numbers of auxiliary

pages will change as information is added and removed from the b-tree. But

the root page never moves. When a new table or index is created, its root

page is assigned and remains unchanged for the lifetime of the table or index.</note> </p> <p>Every

SQLite database contains a master table which stores the database schema.

Each row of the master table holds information about a single table, index,

view or trigger, including the original <codeph>CREATE</codeph> statement

that created that table, index, view or trigger. Rows that define tables and

indexes also record the root page number for the b-tree that stores the table

or index. The root page of the master table is always page 1 of the database

file, so SQLite always knows how to locate it. And from the master table it

can learn the root page of every other table and index in the database and

thus locate any information in the database. </p> <p id="GUID-72EACB86-5E22-5DF1-A7E6-1233DC647867"><b>An Example of SQLite in

Operation</b> </p> <p>This is what happens inside SQLite during a typical

usage scenario: When the SQL server instructs SQLite to open a database, the

SQLite library allocates a data structure to hold everything it will ever

need to know about that database connection. It also asks the pager to open

the database file, but does not immediately try to read anything or even verify

that the file is a valid database. </p> <p>The first time you actually try

to access the database, SQLite will look at the 100-byte header of the database

file to verify that the file is a SQLite database and to extract operating

parameters such as the database page size. </p> <p>After checking the header

SQLite opens and reads the entire master table. Recall that the master table

contains entries for every table, index, view and trigger in the database

and that each entry includes the complete text of the <codeph>CREATE</codeph> statement

that originally created the table, index, view or trigger. </p> <p>SQLite

parses these <codeph>CREATE</codeph> statements in order to rebuild an internal

symbol table holding the names and properties of all tables, indexes, triggers

and views in the database schema. </p> <p>Among the values stored in the header

of the database is a 32-bit <i>schema cookie</i>. The schema cookie is changed

whenever the database schema is modified by creating or dropping a table,

index, trigger, or view. </p> <p>When SQLite parses the database schema into

its internal symbol table, it remembers the schema cookie. Thereafter, whenever

SQLite goes to access the database file, it first compares the schema cookie

that it read when it parsed the schema to the current schema cookie value. </p> <p>If

they match, everything continues normally, but if the schema cookie has changed

that means that some other thread or process may have modified the database

schema. When that happens, SQLite has to throw out its internal symbol table

and reread and re-parse the entire database schema in order to figure out

what might have changed. </p> <p> <xref href="GUID-0176BF07-DF94-3259-8F90-DE030E35CE9A.dita"><apiname> RSqlStatement</apiname></xref> ’s <xref href="GUID-0176BF07-DF94-3259-8F90-DE030E35CE9A.dita#GUID-0176BF07-DF94-3259-8F90-DE030E35CE9A/GUID-DF9C2258-9BAA-38F0-9B11-21CD00316912"><apiname>RSqlStatement::Prepare()</apiname></xref> API

is used to interface with SQLite’s SQL Compiler. The <codeph>Prepare()</codeph> API

triggers tokenizing, parsing, and compilation of a SQL statement into the

internal bytecode representation that is used by the Virtual Machine. The

generated bytecode is stored in an object returned by SQLite often referred

to as a <i>prepared statement</i>. </p> <p>After compiling a SQL statement

into a prepared statement you can pass it to the Virtual Machine to be run.

This is the job of <xref href="GUID-0176BF07-DF94-3259-8F90-DE030E35CE9A.dita"><apiname>RSqlStatement</apiname></xref> ’s <xref href="GUID-0176BF07-DF94-3259-8F90-DE030E35CE9A.dita#GUID-0176BF07-DF94-3259-8F90-DE030E35CE9A/GUID-C8BBAAA8-0468-3330-B601-391443C1C410"><apiname>RSqlStatement::Next()</apiname></xref> and <xref href="GUID-0176BF07-DF94-3259-8F90-DE030E35CE9A.dita#GUID-0176BF07-DF94-3259-8F90-DE030E35CE9A/GUID-52E3CE72-D495-388F-8829-952E32F0F37D"><apiname>RSqlStatement::Exec()</apiname></xref> APIs.

These interfaces cause the bytecode contained in the prepared statement to

be run until it either completes or until it hits a breakpoint. </p> <p>A

breakpoint is hit whenever a <codeph>SELECT</codeph> statement generates a

row of result that needs to be returned. When a breakpoint is hit SQLite returns

control to the caller. </p> <p>The bytecode in a prepared statement object

is such that whenever a breakpoint occurs, a single row of the result of a

SELECT statement is contained on the stack of the Virtual Machine. At this

point column accessor functions can be used to retrieve individual column

values. </p> <p> <xref href="GUID-0176BF07-DF94-3259-8F90-DE030E35CE9A.dita#GUID-0176BF07-DF94-3259-8F90-DE030E35CE9A/GUID-F4D9F7EC-6FB5-3786-9C37-26ADEC1A6867"><apiname>RSqlStatement::Reset()</apiname></xref> can be called on

a prepared statement at any time. This rewinds the program counter of the

Virtual Machine back to the beginning and clears the stack, thus leaving the

prepared statement in a state where it is ready to start over again from the

beginning. </p> <p> <xref href="GUID-0176BF07-DF94-3259-8F90-DE030E35CE9A.dita"><apiname> RSqlStatement</apiname></xref> ’s <xref href="GUID-0176BF07-DF94-3259-8F90-DE030E35CE9A.dita#GUID-0176BF07-DF94-3259-8F90-DE030E35CE9A/GUID-916A5F7B-9B00-31D9-A945-075353D3915E"><apiname>RSqlStatement::Close()</apiname></xref> API

is merely a destructor for the prepared statement object. It calls <codeph>Reset()</codeph> to

clear the virtual machine stack if necessary, deallocates the generated bytecode,

and frees the container object. </p> <p>Similarly, <xref href="GUID-F3D1D883-6212-3276-9C1F-131A61F2B425.dita"><apiname>RSqlDatabase’</apiname></xref> s <codeph>Close()</codeph> API

is just a destructor for a server-side object created by SQLite when the database

was opened. SQLite asks the pager module to close the database file, clears

the symbol table, and de-allocates all associated memory. </p> </section>

</conbody><related-links>

<link href="GUID-22844C28-AB5B-5A6F-8863-7269464684B4.dita"><linktext>SQL Overview</linktext>

</link>

<link href="GUID-1F12E3F5-45B2-55EC-B021-00338277C608.dita"><linktext>SQL DB Overview</linktext>

</link>

<link href="GUID-78773BCA-ADF6-53E6-AC80-5CB2AE1F8BCC.dita"><linktext>SQL Server

Guide</linktext></link>

<link href="GUID-F8824165-4B33-50D1-9706-BD2438B5A2EE.dita"><linktext>Persistent

Storage</linktext></link>