Section 6.2. Record Format

SQLite Engine > Record Format

6.2. Record Format

The VM composes data values into records, and stores them in B/B+-trees. Each record consists of a key and optional data. The VM is solely responsible for maintaining internal structures of keys and data. (Although the B+-tree module may split a single record across tree (leaf or internal) and multiple overflow pages, the VM sees the record as a logically contiguous byte string.) The VM uses two different but similar record formats for table and index records.

There are two ways to format data/key records: fixed length and variable length. For fixed length format, the same amount of space is used for all records (of a table or index); the size of each individual field is known at table/index creation time. In variable-length formatting, the space for an individual field may vary from one record to another. SQLite uses a variant of variable length record formatting because this has several advantages. It results in smaller database files because there is no wasted padding. It also makes the system run faster, as there are fewer bytes to move between the main memory and disk. In addition, the use of variable-length records allows SQLite to employ manifest typing instead of static typing.

6.2.1. Manifest typing

Each primitive data value, stored in a database (or manipulated by the VM), has a data type associated with it. This is called the storage type of the data value. The operations that we can apply on the data value depend on the data type. Most SQL databases use static typing: A data type is associated with each column in a table, and only values of that particular data type are allowed to be stored in that column. SQLite relaxes this restriction by using manifest typing. In manifest typing, the data type is a property of the value itself, not of the column or variable in which the value is stored. SQLite uses manifest typing (even though the SQL language specification calls for static typing), where the storage type information is stored as a part of data value. SQLite allows users to store any value of any data type into any column regardless of the declared SQL type of that column. (There is an exception to this rule: an integer primary key column stores only integers.)

6.2.2. Table record format

Figure 6-1. Format of table record


Format of table record (row data) is given in Figure 6-1. The record has two parts: header and record image. The header starts with a size field, followed by type fields. The header is followed by individual data items of the record. The header size is the number of bytes before the Data 1 field. The size is represented as a variable-length 64-bit integer in Huffman code, and it includes the number of bytes occupied by itself. The size effectively acts as a pointer to the Data 1 item. After the header size field comes the data type fields, one for each data value in the record in the sequence of their appearance in the record. Each Type i field is a variable-length unsigned integer (the max value is 264) that encodes the storage type for Data i.

The VM supports five storage types: signed integer number, signed floating point number, character string, BLOB, and SQL NULL. Every data value stored in file or in-memory must be one of these five types. Note that some values may have multiple representations at a time. For example, 123 can be an integer number, a floating point number, and a string, all at once. BLOB and NULL values cannot have another representation. An implicit conversion from one type to another occurs as necessary.

The integer value encodings of the types are given in Table 6-2. The beauty of this encoding is that the data length becomes a part of the type encoding.

Table 6-2. Storage types and their meanings
Type value Meaning Length of data
0 NULL 0
N in {1..4} Signed integer N
5 Signed integer 6
6 Signed integer 8
7 IEEE float 8
8 Integer constant 0 0
9 Integer constant 1 0
10, 11 Reserved for expansion N/A
N>=12 and even Blob (N-12)/2
N>=13 and odd Text (N-13)/2


The NULL type represents the SQL NULL value. For the INTEGER type, the data value is a signed integer number, stored in 1, 2, 3, 4, 6, or 8 bytes depending on the magnitude of the value. For the REAL type, the data value is a floating point number that is stored in 8 bytes, as specified in the IEEE floating point number representation standards. The type encoding values 8 and 9 represent integer constants 0 and 1, respectively. For the TEXT type, the data value is a text string, stored using the default encoding (UTF-8, UTF-16BE, or UTF-16-LE) format of the database file; for the latter two, the native byte ordering is either big-endian or little-endian, respectively. (Each database file stores text data in only one UTF format.) For the BLOB type, the data value is a blob, stored exactly as it was input.

6.2.3. Table key format

In SQLite, every B+-tree must have a unique key. Although a relation (table), by definition, does not contain identical rows, in practice, users may store duplicate rows in the relation. The database system must have means to treat them as different, distinct rows. The system must be capable of associating additional information for the differentiation purpose. It means that the system provides a new (unique) attribute for the relation. Thus, internally, each table has a unique primary key, and the key is either defined by the creator of the table or by SQLite.

For every SQL table, SQLite designates one column as the rowid(or oid or _rowid_) whose value uniquely identifies each row in the table. It is the implicit primary key for the table, the unique search key for the table B+-tree. If any column of a table is declared as integer primary key, that column itself is treated (aliased) as the rowid for the table. Otherwise, SQLite creates a separate unique integer column for rowid, whose name is rowid itself. Thus, every table, with or without declaration of an integer primary key column, has a unique integer key, namely rowid. For this latter case, the rowid itself is internally treated as the integer primary key for the table. In either case, a rowid is a signed integer value in the range 263 . . . 263 1.

Table 6-3 displays the contents of a typical SQL table, where the table is created by SQL statement: create table t1(x ,y). The rowid column is added by SQLite. The rowid value is normally determined by SQLite. Nevertheless, you can insert any integer value for the rowid column, as in insert into t1(rowid, x, y) values(100, 'hello', 'world').

Table 6-3. A typical SQL table with rowid as key, and x and y as data
rowid x y
-5 abc xyz
1 abc 12345
2 456 def
100 hello world
54321 NULL 987


NOTE

If rowid is an alias column (i.e., declared as INTEGER PRIMARY KEY), database users are responsible for the column values. If the rowid column is added by SQLite, then SQLite is responsible for generating the values, and it guarantees their uniqueness. When a row, without specifying the rowid column value, is inserted into the table, SQLite visits the table B+-tree and finds an unused integer number for the rowid.

The rowid value, when stored as a part of data record, has an internal integer type. When stored as a key value, it is represented as a variable-length Huffman code. Negative rowids are allowed, but they always use nine bytes of storage, and so their use is discouraged. When rowids are generated by SQLite, they will always be non-negative, though you can explicitly give negative rowid values; the -5 in the previous table is an example.

6.2.4. Index key format

In the previous section, you have seen that the key to each table's B+-tree is an integer, and the data record is one row of the table. Indexes reverse this arrangement. For an index record, the key is the combined values of all indexing columns of the row being stored in the indexed table, and the data is an integer value that is the rowid of the row. To access a table row that has some particular values for indexing columns, SQLite first searches the index table to find the corresponding integer value, then uses that integer value to look up the complete record in the table's B+-tree.

Figure 6-2. Format of index record


SQLite treats an index as a kind of table, and stores the index in its own B-tree. It maps a search key to a rowid. It can have its own key comparison, i.e., ordering function to order index entries. Each index record contains copies of indexing column value(s) followed by the rowid of the row being indexed. The format of index records is given in Figure 6-2. The entire record serves as the B-tree key; there is no data part. The encoding for index records is the same as that for the indexed table records, except that the rowid is appended, and the type of rowid does not appear in the record header because the type is always signed integer and is represented in Huffman code (and not in an internal integer type). (The other data values and their storage types are copied from the indexed table.) The contents of an index on column x is given in Table 6-4.

Table 6-4. An index on column x
x rowid
NULL 54321
456 2
abc -5
abc 1
hello 100


SQLite also supports multicolumn indexing. Table 6-5 presents the contents of an index with columns y and x. The entries in the index are ordered by their first column values; the second and subsequent columns are used as a tie-breaker.

Table 6-5. An index on columns y and x
y x rowid
987 NULL 54321
12345 abc 1
def 456 2
xyz abc -5
world hello 100


Indexes are primarily used to speed up database search. For example, consider the following query: SELECT y FROM t1 WHERE x=456. SQLite does an index search on index tl(x), and finds all rowids for x=456; for each rowid it searches the table t1 B+-tree to obtain the value for the y column for the row that satisifies the search.



Inside SQLite
Inside Symbian SQL: A Mobile Developers Guide to SQLite
ISBN: 0470744022
EAN: 2147483647
Year: 2004
Pages: 29
Authors: Ivan Litovski, Richard Maynard
BUY ON AMAZON

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net