Documentation Source Text

<li> Fewer "stat()" system calls issued by the unix VFS.
<li> Query planner enhancements:
<ol type="a">
<li> Enhanced the [LIKE optimization] so that it works with an ESCAPE clause.
</ol>
<li> Enhanced the [CSV virtual table] so that it accepts the last row of
     input if the final new-line character is missing.



<li> Added the swarm virtual table to the existing union virtual table extension.
<li> Miscellaneous [microoptimizations] reduce CPU usage by about 1.6%.
<li> Bug fixes:
<ol type="a">
<li> Fix a faulty assert() statement discovered by OSSFuzz.
     Ticket [https://sqlite.org/src/info/cb91bf4290c211d|cb91bf4290c211d]
<li> Fix an obscure memory leak in [sqlite3_result_pointer()].

<li> Fewer "stat()" system calls issued by the unix VFS.
<li> Query planner enhancements:
<ol type="a">
<li> Enhanced the [LIKE optimization] so that it works with an ESCAPE clause.
</ol>
<li> Enhanced the [CSV virtual table] so that it accepts the last row of
     input if the final new-line character is missing.
<li> Remove the rarely-used "scratch" memory allocator.  Replace it with the
     [SQLITE_CONFIG_SMALL_MALLOC] configuration setting that gives SQLite
     a hint large memory allocations should be avoided when possible.
<li> Added the swarm virtual table to the existing union virtual table extension.
<li> Miscellaneous [microoptimizations] reduce CPU usage by about 1.6%.
<li> Bug fixes:
<ol type="a">
<li> Fix a faulty assert() statement discovered by OSSFuzz.
     Ticket [https://sqlite.org/src/info/cb91bf4290c211d|cb91bf4290c211d]
<li> Fix an obscure memory leak in [sqlite3_result_pointer()].

on systems that may not have malloc(), free(), or realloc() in their
standard library.
An application that is compiled with [SQLITE_ZERO_MALLOC] will need to
use [sqlite3_config()] together with [SQLITE_CONFIG_MALLOC] or
[SQLITE_CONFIG_HEAP] to specify a new alternative memory allocator
before beginning to use SQLite.</p>

<tcl>hd_fragment scratch {scratch memory allocator}</tcl>
<h2> Scratch memory</h2>

<p>SQLite occasionally needs a large chunk of "scratch" memory to
perform some transient calculation.  Scratch memory is used, for example,
as temporary storage when rebalancing a B-Tree.  These scratch memory
allocations are typically about 10 kilobytes in size and are
transient - lasting
only for the duration of a single, short-lived function call.</p>

<p>In older versions of SQLite, the scratch memory was obtained from
the processor stack.  That works great on workstations with a large stack.
But pulling large buffers from the stack 
caused problems on embedded systems with a 
small processor stack (typically 4K or 8K).  And so SQLite was modified
to allocate scratch memory from the heap.</p>

<p>However, doing occasional large transient allocations from the heap can
lead to memory fragmentation in embedded systems.  To work around this
problem, a separate memory allocation system for scratch memory has been
created.</p>

<p>The scratch memory allocator is set up as follows:</p>

<blockquote><pre>
[sqlite3_config]([SQLITE_CONFIG_SCRATCH], pBuf, sz, N);
</pre></blockquote>

<p>The pBuf parameter is a pointer to a contiguous range of bytes that
SQLite will use for all scratch memory allocations.  The buffer must be
at least sz*N bytes in size.  The "sz" parameter
is the maximum size of each scratch allocation.  N is the maximum 
number of simultaneous scratch allocations.  The "sz" parameter should
be approximately 6 times the maximum database page size.  N should
be twice the number of threads running in the system.  No single thread will
ever request more than two scratch allocation at a time so if there
are never more than N threads, then there will always be enough scratch
memory available.</p>

<p>If the scratch memory setup does not define enough memory, then
SQLite falls back to using the regular memory allocator for its scratch
memory allocations.  The default setup is sz=0 and N=0 so the use
of the regular memory allocator is the default behavior.</p>

<tcl>hd_fragment pagecache {pagecache memory allocator}</tcl>
<h2> Page cache memory</h2>

<p>In most applications, the database page cache subsystem within 
SQLite uses more dynamically allocated memory than all other parts
of SQLite combined.  It is not unusual to see the database page cache
consume over 10 times more memory than the rest of SQLite combined.</p>
................................................................................
<p>SQLite [version 3.6.1] ([dateof: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 60 to 120 kilobytes) and divides that chunk
up into small fixed-size "slots" of around 100 to 1000 byte each.  This
becomes the lookaside memory pool.  Thereafter, memory allocations
associated with the [database connection] and that are not too larger
are satisfied using one of the lookaside pool slots 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 the lookaside pool slots are all 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
................................................................................
ahead and allocates the extra memory and exceeds its limit.  This occurs
under the theory that it is better to use additional memory than to fail
outright.</p>

<p>As of SQLite [version 3.6.1] ([dateof:3.6.1]), 
the soft heap limit only applies to the
general-purpose memory allocator.  The soft heap limit does not know
about or interact with the [scratch memory allocator], 
the [pagecache memory allocator], or the [lookaside memory allocator].
This deficiency will likely be addressed in a future release.</p>

<tcl>hd_fragment nofrag {Robson proof}</tcl>
<h1> Mathematical Guarantees Against Memory Allocation Failures</h1>

<p>The problem of dynamic memory allocation, and specifically the
problem of a memory allocator breakdown, has been studied by
................................................................................
<h2> Computing and controlling parameters <b>M</b> and <b>n</b></h2>

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

<ul>
<li>The general-purpose memory allocator ([memsys5]).</li>
<li>The [scratch memory allocator].</li>
<li>The [pagecache memory allocator].</li>
<li>The [lookaside memory allocator].</li>
</ul>

<p>For allocators other than [memsys5],
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 two
scratch memory slots at one time.  So if an application allocates twice as many
scratch memory slots as there are threads, and assuming 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.</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
................................................................................
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] appropriately, 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
................................................................................

<h2> Ductile failure</h2>

<p>If the memory allocation subsystems within SQLite are configured
for breakdown-free operation but the actual memory usage exceeds
design limits set by the [Robson proof], 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 [memsys5] 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> and/or <b>n</b> exceeds the limits
imposed by the [Robson proof].  The [Robson proof] shows that it is 
possible for a memory allocation to break down and fail in this 
circumstance, but such a failure requires an especially
despicable sequence of allocations and deallocations - a sequence that

on systems that may not have malloc(), free(), or realloc() in their
standard library.
An application that is compiled with [SQLITE_ZERO_MALLOC] will need to
use [sqlite3_config()] together with [SQLITE_CONFIG_MALLOC] or
[SQLITE_CONFIG_HEAP] to specify a new alternative memory allocator
before beginning to use SQLite.</p>













































<tcl>hd_fragment pagecache {pagecache memory allocator}</tcl>
<h2> Page cache memory</h2>

<p>In most applications, the database page cache subsystem within 
SQLite uses more dynamically allocated memory than all other parts
of SQLite combined.  It is not unusual to see the database page cache
consume over 10 times more memory than the rest of SQLite combined.</p>
................................................................................
<p>SQLite [version 3.6.1] ([dateof: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 60 to 120 kilobytes) and divides that chunk
up into small fixed-size "slots" of around 100 to 1000 byte each.  This
becomes the lookaside memory pool.  Thereafter, memory allocations
associated with the [database connection] and that are not too large
are satisfied using one of the lookaside pool slots 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 the lookaside pool slots are all 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
................................................................................
ahead and allocates the extra memory and exceeds its limit.  This occurs
under the theory that it is better to use additional memory than to fail
outright.</p>

<p>As of SQLite [version 3.6.1] ([dateof:3.6.1]), 
the soft heap limit only applies to the
general-purpose memory allocator.  The soft heap limit does not know
about or interact with
the [pagecache memory allocator] or the [lookaside memory allocator].
This deficiency will likely be addressed in a future release.</p>

<tcl>hd_fragment nofrag {Robson proof}</tcl>
<h1> Mathematical Guarantees Against Memory Allocation Failures</h1>

<p>The problem of dynamic memory allocation, and specifically the
problem of a memory allocator breakdown, has been studied by
................................................................................
<h2> Computing and controlling parameters <b>M</b> and <b>n</b></h2>

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

<ul>
<li>The general-purpose memory allocator ([memsys5]).</li>

<li>The [pagecache memory allocator].</li>
<li>The [lookaside memory allocator].</li>
</ul>

<p>For allocators other than [memsys5],
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>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
................................................................................
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>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 two allocations can be controlled and/or eliminated by
configuring the [pagecache memory allocator],
and [lookaside memory allocator] appropriately, 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
................................................................................

<h2> Ductile failure</h2>

<p>If the memory allocation subsystems within SQLite are configured
for breakdown-free operation but the actual memory usage exceeds
design limits set by the [Robson proof], SQLite will usually continue 
to operate normally.
The the [pagecache memory allocator]
and the [lookaside memory allocator] automatically failover
to the [memsys5] 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> and/or <b>n</b> exceeds the limits
imposed by the [Robson proof].  The [Robson proof] shows that it is 
possible for a memory allocation to break down and fail in this 
circumstance, but such a failure requires an especially
despicable sequence of allocations and deallocations - a sequence that