Documentation Source Text

<title>Dynamic Memory Allocation In SQLite</title>

<h1>Dynamic Memory Allocation In SQLite</h1>
<tcl>hd_keywords {memory allocation}</tcl>

<p>SQLite makes extensive use of dynamic memory allocation to obtain
the memory it needs to store various objects
(ex: [database connections] and [prepared statements]) and to build
a memory cache of the database file and to hold the results of queries.

<p>If SQLite needs a page-cache entry that is larger than "sz" bytes or
if it needs more than N entries, it falls back to using the
general-purpose memory allocator.</p>

<tcl>hd_fragment lookaside {lookaside memory allocator}</tcl>
<h3>3.4 Lookaside memory allocator</h3>

<p>SQLite [database connections] make numerous
small and short-lived memory allocations.
This occurs most commonly when compiling SQL statements using
[sqlite3_prepare_v2()] but also to a lessor extent when running
[prepared statements] using [sqlite3_step()].  These small memory
allocations are used to hold things such as the names of tables
and columns, parse tree nodes, individual query results values,
and b-tree cursor objects.  These small memory allocations result
in many calls to malloc() and free() - so many calls that malloc() and
free() end up using a significant fraction of the CPU time assigned
to SQLite.</p>

<p>SQLite [version 3.6.1] introduced the lookaside memory allocator to
help reduce the memory allocation load.  In the lookaside allocator,
each [database connection] preallocates a single large chunk of memory
(typically in the range of 50 to 100 kilobytes) and divides that chunk
up into small fixed-size "slots" of around 50 to 200 byte each.  This
becomes the lookaside memory pool.  Thereafter, memory allocations
associated with the [database connection] and that are small enough are
allocated as one of the pieces of the lookaside pool rather than by calling
the general-purpose memory allocator.  Larger allocations continue to
use the general-purpose memory allocator, as do allocations that occur
when all the lookaside pool slots are already checked out.  
But in many cases, the memory
allocations are small enough and there are few enough outstanding that
the new memory requests can be satisfied from the lookaside
pool.</p>

<p>Because lookaside allocations are always the same size, the allocation
and deallocation algorithms are fast and efficient.  There is no
need to coalesce adjacent free slots nor search for a slot
of a particular size.  Each [database connection] maintains a singly-linked
list of unused slots.  Allocation requests simply pull the first
element of this list.  Decallocations simply push the element back onto
the front of the list.
Furthermore, each [database connection] is assumed to already be
running in a single thread (and in fact there are mutexes already in
place to enforce this) so no mutexing is required to pull or push
entries from the lookaside freelist.  Consequently, lookaside memory
allocations and deallocations are very fast.  In speed tests on
Linux and Mac OS-X workstations, SQLite has shown overall performance
improvements as high as 10% and 15%, depending on the workload how
lookaside is configured.</p>

<p>The size of the lookaside memory pool has a global default value
but can also be configured on a connection-by-connection basis.
To change the default size of the lookaside memory pool use the 
following interface at start-time:</p>

<blockquote><pre>
[sqlite3_config]([SQLITE_CONFIG_LOOKASIDE], sz, cnt);
</pre></blockquote>

<p>The "sz" parameter is the size in bytes of each lookaside slot.
The default is 100 bytes.  The "cnt" parameter is
the total number of lookaside memory slots.  The default value is 500
slots. The total amount
of lookaside memory allocated to each [database connection] is
sz*cnt bytes.  Hence the lookaside memory pool allocated per database 
connection by default is 50 kilobytes in size.
(Note: these default values are for SQLite [version 3.6.1] and are subject
to changes in future releases.)
</p>

<p>The lookaside pool can be changed for an individual
[database connection] "db" using this call:</p>

<blockquote><pre>
[sqlite3_db_config](db, [SQLITE_DBCONFIG_LOOKASIDE], pBuf, sz, cnt);
</pre></blockquote>

<p>The "pBuf" parameter is a pointer to memory space that will be
used for the lookaside memory pool.  If pBuf is NULL, then SQLite
will obtain its own space for the memory pool using [sqlite3_malloc()].
The "sz" and "cnt" parameters are the size of each lookaside slot
and the number of slots, respectively.  If pBuf is not NULL, then it
must point to at least sz*cnt bytes of memory.</p>

<p>The lookaside configuration can only be changed while there are
no outstanding lookaside allocations for the database connection.
Hence, the configuration should be set immediately after creating the 
database connection using [sqlite3_open()] (or equivalent) and before
evaluating any SQL statements on the connection.</p>

<tcl>hd_fragment memstatus {memory statistics}</tcl>
<h3>3.5 Memory status</h3>

<p>By default, SQLite keeps statistics on its memory usage.  These
statistics are useful in helping to determine how much memory an

for <b>N</b> which will guarantee that no call to any SQLite interface
will ever return [SQLITE_NOMEM].  The memory pool will never become
so fragmented that a new memory allocation request cannot be satisfied.
This is an important property for
applications where a software fault could cause injury, physical harm,
loss of irreplaceable data, or significant financial loss.</p>

<h3>4.1 Computing and controlling parameters <b>M</b> and <b>n</b></h3>

<p>The Robson proof applies separately to each of the memory allocators
used by SQLite:</p>

<ul>
<li>The general-purpose memory allocator (usually [memsys5] for
    applications that care about the Robson proof.)</li>
<li>The [scratch memory allocator].</li>
<li>The [pagecache memory allocator].</li>
<li>The [lookaside memory allocator].</li>
</ul>

<p>For all memory allocators other than the general-purpose memory
allocator, all memory allocations are of the same size.  Hence, <b>n</b>=1
and therefore <b>N</b>=<b>M</b>.  In other words, the memory pool need
be no larger than the largest amount of memory in use at any given moment.</p>

<p>SQLite guarantees that no thread will ever use more than a single
scratch memory slot at one time.  So if an application allocates as many
scratch memory slots as there are threads, and assuming the the size of
each slot is large enough, there is never a chance of overflowing the
scratch memory allocator.  An upper bound on the size of scratch memory
allocations is six times the largest page size.  It is easy, therefore,
to guarantee breakdown-free operation of the scratch memory allocator.
Simply assign buffers shows size is larger than six times the maximum
page size and at least one buffer per thread.</p>

<p>The usage of pagecache memory is somewhat harder to control in
SQLite version 3.6.1, though mechanisms are planned for subsequent
releases that will make controlling pagecache memory much easier.
Prior to the introduction of these new mechanisms, the only way
to control pagecache memory is using the [cache_size pragma].</p>

<p>Safety-critical applications will usually want to modify the
default lookaside memory configuration so that when the initial
lookaside memory buffer is allocated during [sqlite3_open()] the
resulting memory allocation is not so large as to force the <b>n</b>
parameter to be too large.  In order to keep <b>n</b> under control,
it is best to try to keep the largest memory allocation below 2 or 4
kilobytes.  Hence, a reasonable default setup for the lookaside
memory allocator might any one of the following:</p>

<blockquote><pre>
sqlite3_config(SQLITE_CONFIG_LOOKASIDE, 32, 32);  /* 1K */
sqlite3_config(SQLITE_CONFIG_LOOKASIDE, 64, 32);  /* 2K */
sqlite3_config(SQLITE_CONFIG_LOOKASIDE, 32, 64);  /* 2K */
sqlite3_config(SQLITE_CONFIG_LOOKASIDE, 64, 64);  /* 4K */
</pre></blockquote>

<p>Another approach is to initially disable the lookaside memory
allocator:</p>

<blockquote><pre>
sqlite3_config(SQLITE_CONFIG_LOOKASIDE, 0, 0);
</pre></blockquote>

<p>Then let the application maintain a separate pool of larger
lookaside memory buffers that it can distribute to [database connections]
as they are created.  In the common case, the application will only
have a single [database connection] and so the lookaside memory pool
can consist of a single large buffer.</p>

<blockquote><pre>
sqlite3_db_config(db, SQLITE_DBCONFIG_LOOKASIDE, aStatic, 256, 500);
</pre></blockquote>

<p>The lookaside memory allocator is really intended as performance
optimization, not as a method for assuring breakdown-free memory allocation,
so it is not unreasonable to completely disable the lookaside memory
allocator for safety-critical opertions.</p>

<p>The general purpose memory allocator is the most difficult memory pool
to manage, since it support allocations of varying sizes.  Since 
<b>n</b> is a multiplier on <b>M</b> we want to keep <b>n</b> as small
as possible.  This argues for keeping the minimum allocation size for
[memsys5] as large as possible.  In most appliations, the
[lookaside memory allocator] is able to handle small allocations.  So
it is reasonable to set the minimum allocation size for [memsys5] to
2, 4 or even 8 times the maximum size of a lookaside allocation.  
A minimum allocation size of 512 is a reasonable setting.</p>

<p>Large memory allocations might come from several sources:</p>

<ol>
<li>SQL table rows that contain large strings or blobs.</li>
<li>Complex SQL queries that compile down to large [prepared statements].</li>
<li>SQL parser objects used internally by [sqlite3_prepare_v2()].</li>
<li>Storage space for [database connection] objects.</li>
<li>Scratch memory allocations that overflow into the general-purpose
    memory allocator.</li>
<li>Page cache memory allocations that overflow into the general-purpose
    memory allocator.</li>
<li>Lookaside buffer allocations for new [database connections].</li>
</ol>

<p>The last three allocations can be controlled and/or eliminated by
configuring the scratch memory allocator, pagecache memory allocator,
and lookaside memory allocator appropriate, as described above.
The storage space required for [database connection] objects depends
to some extent on the length of the filename of the database file, but
rarely exceeds 2KB on 32-bit systems.  (More space is required on
64-bit systems due to the increased size of pointers.)
Each parser object uses about 1.6KB of memory.  Thus, elements 3 through 7
above can easily be controlled to keep the maximum memory allocation
size below 2KB.</p>

<p>If the application is designed to manage data in small pieces,
then the database should never contain any large strings or BLOBs
and hence element 1 above should not be a factor.  If the database
does contain large strings or BLOBs, they should be read using
[sqlite3_blob | incremental BLOB I/O] and rows that contain the
large strings or BLOBs should never be update by any means other
than [sqlite3_blob | incremental BLOB I/O].  Otherwise, the 
[sqlite3_step()] routine will need to read the entire row into
contiguous memory at some point, and that will involve at least
one large memory allocation.</p>

<p>The final source of large memory allocations is the space to hold
the [prepared statements] that result from compiling complex SQL
operations.  Ongoing work by the SQLite developers is reducing the
amount of space required here.  But large and complex queries might
still require [prepared statements] that are several kilobytes in
size.  The only workaround at the moment is for the application to
break complex SQL operations up into two or smaller and simpler 
operations contained in separate [prepared statements].</p>

<p>All things considered, applications should normally be able to
hold their maximum memory allocation size below 2K or 4K.  This
gives a value for log<sub>2</sub>(<b>n</b>) of 2 or 3.  This will
limit <b>N</b> to between 2 and 2.5 times <b>M</b>.</p>

<p>The maximum amount of general-purpose memory needed by the application
is determined by such factors as how many simultaneous open 
[database connection] and [prepared statement] objects the application
uses, and on the complexity of the [prepared statements].  For any
given application, these factors are normally fixed and can be
determined experiementally using [SQLITE_STATUS_MEMORY_USED].
A typical application might only use about 40KB of general-purpose
memory.  This gives a value of <b>N</b> of about 100KB.</p>

<h3>4.2 Ductile failure</h3>

<p>Safety-critical appliations should include a safety margin
in memory sizing calculations and should monitor memory usage at
run-time using the [sqlite3_status()] and [sqlite3_db_status()] 
interfaces to make sure that memory usage does not exceed design 
limits.  Nevertheless, we observe that even if memory usage does
exceed limits, SQLite will usually continue to operate normally.
The [scratch memory allocator], the [pagecache memory allocator],
and the [lookaside memory allocator] all automatically failover
to the general-purpose memory allocator.  And it is usually the
case that the [memsys5] memory allocator will continue to function
without fragmentation even if <b>M</b> exceeds the <b>N/n</b> limit
imposed by the Robson proof.  It is possible for a memory allocation
to fail in this circumstance, but a failure requires an especially
dispicable sequence of allocations and deallocations - a sequence that
SQLite has never been observed to follow.  So it is often the case
that the limits imposed by Robson can be exceeded by a factor of
two with not ill effect. </p>

<a name="stability"></a>
<h2>5.0 Stability Of Memory Interfaces</h2>

<p>As of this writing (circa SQLite version 3.6.1) all of the alternative
memory allocators and mechanisms for manipulating, controlling, and
measuring memory allocation in SQLite are considered experimental and