SQLite Internals – Records

database-internalsrecordsqlitestorage

Hey I'm trying to wrap my head around SQLite data storage, specifically how it is storing Records. I've found a book The Definitive guide to SQLlite, where the author explains internal record format (Figure 9-5, page 351):

Given table:

sqlite> SELECT * FROM episodes ORDER BY id LIMIT 1;
id   season  name
---  ------  --------------------
0    1       Good News Bad News

Its internal record format is:

| 04 | 01 | 01 | 49 |   | 00 | 01 | Good News Bad News |

"The header is 4 bytes long. The header size reflects this and itself is encoded as a single byte. The first type, corresponding to the id field, is a 1-byte signed integer. The second type, corresponding to the season field, is as well. The name type entry is an odd number, meaning it is a text value. Its size is therefore given by (49-13)/2=18 bytes."

Specifically I'm curious about TEXT attribute, in the example above we have a string of length 18 characters. And the rule for TEXT in SQLite is as follows:

Type Value     Meaning   Length of Data
----------     -------   --------------------
N>13 and odd   TEXT      (N-13)/2

What hapenns though when the string is longer ? It'll get out of range of that one byte.

Best Answer

Either the book authors describe some really ancient version of SQLite, or they make a mistake when they say "[t]he header size [...] is encoded as a single byte."

Documentation that "describes and defines the on-disk database file format used by all releases of SQLite since version 3.0.0 (2004-06-18)" states that

The record format makes extensive use of the variable-length integer or varint representation of 64-bit signed integers[...]

A record contains a header and a body, in that order. The header begins with a single varint which determines the total number of bytes in the header. [...] Following the size varint are one or more additional varints, one per column.

while

A variable-length integer or "varint" is a static Huffman encoding of 64-bit twos-complement integers that uses less space for small positive values. A varint is between 1 and 9 bytes in length.

The serial type varints for large strings and BLOBs might extend to two or three byte varints

which certainly allows them to represent pretty long values.

Related Solutions

Query for fetching records from SQLite database on Blackberry

It's not very clear what you are after. So, this guess may be wrong:

SELECT *
FROM Messages
WHERE ( fromUserID = @From AND toUserID = @To )
   OR ( fromUserID = @To AND toUserID = @From )
ORDER BY TimeSent DESC
  LIMIT 20 ;

Postgresql – the overhead for varchar(n)

Unsurprisingly, the manual is right. But there is more to it.

For one, size on disk (in any table, even when not actually stored on disk) can be different from size in memory. On disk, the overhead for short varchar values up to 126 bytes is reduced to a 1 byte as stated in the manual. But the overhead in memory is always 4 bytes (once individual values are extracted).

The same is true for text, varchar, varchar(n) or char(n) - except that char(n) is blank-padded to n characters and you normally don't want to use it. Its effective size can still vary in multi-byte encodings because n denotes a maximum of characters, not bytes:

strings up to n characters (not bytes) in length.

All of them use varlena internally.
"char" (with double-quotes) is a different creature and always occupies a single byte.
Untyped string literals ('foo') have a single byte overhead. Not to be confused with typed values!

Test with pg_column_size().

CREATE TEMP TABLE t (id int, v_small varchar, v_big varchar);
INSERT INTO t VALUES (1, 'foo', '12345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890');

SELECT pg_column_size(id)        AS id
     , pg_column_size(v_small)   AS v_small
     , pg_column_size(v_big)     AS v_big
     , pg_column_size(t)         AS t
FROM   t
UNION ALL  -- 2nd row measuring values in RAM
SELECT pg_column_size(1)
     , pg_column_size('foo'::varchar)
     , pg_column_size('12345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890'::varchar)
     , pg_column_size(ROW(1, 'foo'::varchar, '12345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890'::varchar));

 id | v_small | v_big |  t
----+---------+-------+-----
  4 |       4 |   144 | 176
  4 |       7 |   144 | 176

As you can see:

The 3-byte string 'foo' occupies 4 bytes on disk and 7 bytes in RAM (so 1 byte vs. 4 bytes of overhead).
The 140-byte string '123...' occupies 144 bytes both on disk and in RAM (so always 4 bytes of overhead).
Storage of integer has no overhead (but it has alignment requirements that can impose padding).
The row has an additional overhead of 24 bytes for the tuple header (plus an additional 4 bytes per tuple for the item identifier in the page header).
And last but not least: The overhead of the small varchar is still just 1 byte while it has not been extracted from the row - as can be seen from the row size. (That's why it's sometimes a bit faster to select whole rows.)

Best Answer

Related Solutions

Query for fetching records from SQLite database on Blackberry

Postgresql – the overhead for varchar(n)

Related Question