doc/vdbesort-memory.md

   1
   2 20-11-2020
   3
   4 # Memory Allocation In vdbesort.c
   5
   6 Memory allocation is slightly different depending on:
   7
   8   * whether or not SQLITE_CONFIG_SMALL_MALLOC is set, and
   9   * whether or not worker threads are enabled.
  10
  11 ## SQLITE_CONFIG_SMALL_MALLOC=0
  12
  13 Assuming SQLITE_CONFIG_SMALL_MALLOC is not set, keys passed to the sorter are
  14 added to an in-memory buffer. This buffer is grown using sqlite3Realloc() as
  15 required it reaches the size configured for the main pager cache using "PRAGMA
  16 cache_size". i.e. if the user has executed "PRAGMA main.cache_size = -2048",
  17 then this buffer is allowed to grow up to 2MB in size.
  18
  19 Once the buffer has grown to its threshold, keys are sorted and written to
  20 a temp file. If worker threads are not enabled, this is the only significant
  21 allocation the sorter module makes. After keys are sorted and flushed out to
  22 the temp file, the buffer is reused to accumulate the next batch of keys.
  23
  24 If worker threads are available, then the buffer is passed to a worker thread
  25 to sort and flush once it is full, and a new buffer allocated to allow the
  26 main thread to continue to accumulate keys. Buffers are reused once they
  27 have been flushed, so in this case at most (nWorker+1) buffers are allocated
  28 and used, where nWorker is the number of configured worker threads.
  29
  30 There are no other significant users of heap memory in the sorter module.
  31 Once sorted buffers of keys have been flushed to disk, they are read back
  32 either by mapping the file (via sqlite3_file.xFetch()) or else read back
  33 in one page at a time.
  34
  35 All buffers are allocated by the main thread. A sorter object is associated
  36 with a single database connection, to which it holds a pointer.
  37
  38 ## SQLITE_CONFIG_SMALL_MALLOC=1
  39
  40 This case is similar to the above, except that instead of accumulating
  41 multiple keys in a single large buffer, sqlite3VdbeSorterWrite() stores
  42 keys in a regular heap-memory linked list (one allocation per element).
  43 List elements are freed as they are flushed to disk, either by the main
  44 thread or by a worker thread.
  45
  46 Each time a key is added the sorter (and an allocation made),
  47 sqlite3HeapNearlyFull() is called. If it returns true, the current
  48 list of keys is flushed to a temporary file, even if it has not yet
  49 reached the size threshold.