1 files changed, 49 insertions, 0 deletions
diff --git a/doc/vdbesort-memory.md b/doc/vdbesort-memory.md
new file mode 100644
index 000000000000..5c3dd62d2fdd
--- /dev/null
+++ b/doc/vdbesort-memory.md
@@ -0,0 +1,49 @@
+
+20-11-2020
+
+# Memory Allocation In vdbesort.c
+
+Memory allocation is slightly different depending on:
+
+  * whether or not SQLITE_CONFIG_SMALL_MALLOC is set, and
+  * whether or not worker threads are enabled.
+
+## SQLITE_CONFIG_SMALL_MALLOC=0
+
+Assuming SQLITE_CONFIG_SMALL_MALLOC is not set, keys passed to the sorter are
+added to an in-memory buffer. This buffer is grown using sqlite3Realloc() as
+required it reaches the size configured for the main pager cache using "PRAGMA
+cache_size". i.e. if the user has executed "PRAGMA main.cache_size = -2048",
+then this buffer is allowed to grow up to 2MB in size.
+
+Once the buffer has grown to its threshold, keys are sorted and written to
+a temp file. If worker threads are not enabled, this is the only significant
+allocation the sorter module makes. After keys are sorted and flushed out to
+the temp file, the buffer is reused to accumulate the next batch of keys.
+
+If worker threads are available, then the buffer is passed to a worker thread
+to sort and flush once it is full, and a new buffer allocated to allow the
+main thread to continue to accumulate keys. Buffers are reused once they
+have been flushed, so in this case at most (nWorker+1) buffers are allocated
+and used, where nWorker is the number of configured worker threads.
+
+There are no other significant users of heap memory in the sorter module. 
+Once sorted buffers of keys have been flushed to disk, they are read back
+either by mapping the file (via sqlite3_file.xFetch()) or else read back
+in one page at a time.
+
+All buffers are allocated by the main thread. A sorter object is associated
+with a single database connection, to which it holds a pointer.
+
+## SQLITE_CONFIG_SMALL_MALLOC=1
+
+This case is similar to the above, except that instead of accumulating
+multiple keys in a single large buffer, sqlite3VdbeSorterWrite() stores
+keys in a regular heap-memory linked list (one allocation per element).
+List elements are freed as they are flushed to disk, either by the main
+thread or by a worker thread.
+
+Each time a key is added the sorter (and an allocation made),
+sqlite3HeapNearlyFull() is called. If it returns true, the current
+list of keys is flushed to a temporary file, even if it has not yet
+reached the size threshold.