Rework the way trees of MergeEngine objects are built in vdbesort.c to make it easier to follow. Fix memory leaks that could follow an OOM or IO error. Add various comments to explain functions in vdbesort.c.

FossilOrigin-Name: 69026ec7dc3bd3e33bbe17c221a53cf1dd0f8945

Fix some problems to do with OOM conditions in vdbesort.c. Some problems remain.

FossilOrigin-Name: 2f94f9ce9bf11f1599bbc640b3fc8c15da588416

Fix further code and documentation issues in vdbesort.c.

FossilOrigin-Name: d03f5b8622d304f029f73c7cd0bee3182a81d081

Allow the sorter to begin returning data to the VDBE as soon as it is available, instead of waiting until all keys have been sorted.

FossilOrigin-Name: cb0ab20c48962cdee03115efa93d7d501780ac73

Improve performance in single-threaded mode by having the final merge pass keys directly to the VDBE, instead of going via a final PMA.

FossilOrigin-Name: 02610cd9b77caa2c181210056088beb3ad6ce30f

Minor fixes so that builds with SQLITE_MAX_WORKER_THREADS=0 work.

FossilOrigin-Name: e400bbbf26cdfe88f6cb231e96cdcddb9a6bcc0f

Improve use of multiple threads in sqlite3VdbeSorterRewind().

FossilOrigin-Name: e1bdc4b810907cc0e55e0c923c8ebc777068cfe0

Fix many issues with new code.

FossilOrigin-Name: 62c406a042d7246f6df6b943421182a88483b2e3

Avoid having the sorter merge too many PMAs at a time when incrementally merging data following a SorterRewind().

FossilOrigin-Name: 98bf0307b121b0776a7170108cc8d3f948a7ebfe

Experimental multi-threaded sorting changes to allow the sorter to begin returning items to the VDBE before all data is sorted.

FossilOrigin-Name: f9d5e09afaf64d68a0e461c1c2f38179bcea4b1f

Fix harmless compiler warnings.

FossilOrigin-Name: e54dded2012f0ab486ee138e9bd57c528af33980

Fix typo in a Windows threading support routine.

FossilOrigin-Name: 5e3dfa27c71a666e122e3cf64897038ff8424800

Merge the latest trunk changes into the threads branch.

FossilOrigin-Name: 39ac79cffe716f88af0871bdd206231b6a6511ff

Merge changes to the query planner that strive to ensure that any index
usage that is a proper subset of some other index usage always has a slightly
higher cost.

FossilOrigin-Name: 683dd379a293b2f330e1e4cd746f190527fe48ee

Ensure the "PRAGMA journal_mode=WAL" works coming from any other journal_mode
with ATTACH-ed databases.

FossilOrigin-Name: e54330b43127e46fc6494748cbb353a6fc91cfd7

Add test file sort3.test, which should have been part of commit [9d3351b8d7].

FossilOrigin-Name: dceed2c803fca23c83c02c448d5ae7c4698efee1

Change vdbeSorterExtendFile() so that it makes a best effort to create the
PMA file of the desired size, but does not return an error if unable.

FossilOrigin-Name: 217814bc4b53fab7bdad433e24e8aef8998c38fe

Merge all recent changes from trunk.

FossilOrigin-Name: a0910079adde95245680dee59b43613b60903f10

Use OP_Copy instead of OP_SCopy when moving results out of a subquery,
to prevent the subquery results from changing out from under the outer
query.  Fix for ticket [1e64dd782a126f48d78].

FossilOrigin-Name: d5513dfa23baa0b0a095aaf17d19aacd30dcef61

Fix an integer overflow problem in the sorter.

FossilOrigin-Name: 9d3351b8d713232133dad149c73fb2a27c72abb1

Fix a typo in the "Synopsis:" comment for the OP_VFilter opcode.

FossilOrigin-Name: 48ecdd4aff03741f96c070dced69c3c273b652cb

Fix minor errors causing compilation to fail with SQLITE_MAX_WORKER_THREADS set to a value greater than zero.

FossilOrigin-Name: 0561272abf357a2f4709f6c02866e570d19cd344

Refactor local object and method names in vdbesort.c so that their names
more closely reflect their actual use.

FossilOrigin-Name: d284e30eb1db144965fa85566e4234e30464350b

In the command-line shell, run set writable_schema before running the
".clone" command.

FossilOrigin-Name: 9d2ae6342c8afa904bec591ebe134ff7f536b71c

Add a big introductory comment to vdbesort.c explaining its operation at a
high level.  Also adjust some symbolic names and fix other comment issues in
that file.

FossilOrigin-Name: eef60f1bf54fcdc7b32f96ebb87a9a0bf0776e8b

Fix some problems with OOM handling in vdbesort.c.

FossilOrigin-Name: 47e702bd8392bc50c4edaf6a2c8c499af87b520e

Change the name of the SorterThread object to "SortSubtask" to avoid confusion
with the SQLiteThread object.

FossilOrigin-Name: 4ee2d910fbbed8d4def15e4e99ee225839f3a739

When sorting data for a CREATE INDEX statement in single-threaded mode, assume that keys are delivered to the sorter in primary key order. Also fix various comments that had fallen out of date.

FossilOrigin-Name: 821d1ac4504243fa13b9e3c0d56361ad9fb80d78

Even if compile time option SQLITE_MAX_WORKER_THREADS is set to one or greater, set the default number of worker threads to zero. Distribute data more evenly between threads in sqlite3VdbeSorterWrite() to improve performance when sorting large amounts of data. Add new test file sort2.test.

FossilOrigin-Name: 643c86a056168e39fcb7f39b8a72731f1eb246db

Fix a problem with OOM handling in the sorter code.

FossilOrigin-Name: 59cd5229e2b5be5272cf57c7e7d09e97d16a5425

Remove an unnecessary conditional.

FossilOrigin-Name: 7473c4dfc10a47594affa6f4e071a08dc8838c0c

Add the SQLITE_MAX_WORKER_THREADS compile time option. And the SQLITE_CONFIG_WORKER_THREADS sqlite3_config() switch.

FossilOrigin-Name: 2774710df8cd2bfaca49888c69f1b01c0ddadf9a

Also make sure an index that is a proper subset of some other index has a
higher cost than that other index.  Add test cases.

FossilOrigin-Name: b7830d232b073a197aa1092e78cb24e88cb10fd3

Make sure that an index that covers a proper superset of the WHERE clause
terms of some other index has a lower cost than the other index.

FossilOrigin-Name: ea8b0910040198751551b0b960e6b783913607df

Avoid a (harmless) buffer overread that is possible on an OOM when
MEMSYS5 is engaged.

FossilOrigin-Name: b3296267fb67b9f59719a37093253062edde3746

Experiments in picking better query plans, especially when the usage of one
index is a subset of another.

FossilOrigin-Name: 8f869ca7a6eaa9ca7a08102290e6c606735f9090

Fix a broken assert() in vdbesort.c.

FossilOrigin-Name: 18d1b402f2dbe78f1a1113bb356b710e348365ef

Fix a problem in vdbesort.c causing spurious SQLITE_NOMEM errors when using memsys3 or memsys5.

FossilOrigin-Name: a683c05f6250389e84b980b16559e162ba1a27c2

Add the optimization to avoid some unnecessary calls to sqlite3VdbeRecordUnpack() added to the trunk by [707ea170b3].

FossilOrigin-Name: fc4d04e6b039ea5aeb47739e38c5926e63a4b01b

Merge latest changes from orderby-planning branch.

FossilOrigin-Name: 4c7fb5423430f3b936befaa7c309f8e1968ee7d8

Merge the latest changes from trunk.

FossilOrigin-Name: 3047a25f1c41e83f0b4772f7c36fbfec0f12dc7e

Disable the wal64k.test script for non-unix systems since it depends on
unix-only features.

FossilOrigin-Name: 27deb6e49bcc76714dbdc61b34748603155ac770

Fix a harmless compiler warning.

FossilOrigin-Name: a4e47150f32b3a4120b1f89ccc66d633d829e3bb

Enhance the sqlite3VdbeRecordCompare() routines so that if they encounter
database corruption, they will set the UnpackedRecord.isCorrupt field and
return 0.  The sqlite3BtreeMovetoUnpacked() routine detects this and returns
SQLITE_CORRUPT, causing the corruption to be reported back to the top-level.

FossilOrigin-Name: 7fa85eaaaf6d211378620d728a759fdfe30a15b0

Instead of allocating a single large buffer at the beginning of each sort operation, start with a small buffer and extend it using realloc() as required.

FossilOrigin-Name: 81987c8ceb64f051528a6ca42673821d9ab7c0ff

Minor cleanup of the code in the query planner that computes the costs
estimates for the various plans.  There are no changes to the costs at this
time.  But the code is slightly more readable now and that might facilitate
future enhancements.

FossilOrigin-Name: 9b4d7226bcee38be5ac68a54bee03b4179cb69fc

Use xFetch() to access temporary files in vdbesort.c. Use a single large allocation instead of many small allocations when accumulating records in vdbesort.c. This is an interim commit - it allocates a buffer the size of the page-cache every time data is sorted.

FossilOrigin-Name: f4ac1bf28c4ba395ccab8f1c9df72614a61095a7

Enhance the logest.c utility with new operators: "dup", "inv", "log", and
"nlogn".  Provide help on an invalid input.

FossilOrigin-Name: b4bd2a062c4baf5f622d61b7411f00de5904ef56

Merge the latest trunk changes and the fix for the crash on a corrupt
database.

FossilOrigin-Name: 0b35346c32dba14963c85ec178f2b46aa2bbf6dc

Merge from trunk the fix for the crash on a corrupt database.

FossilOrigin-Name: 8cb2b02baa7ef9aa96319e977f0315328f944237

Add an extra test case for the potential buffer overread patched by [28ddecff04].

FossilOrigin-Name: f585f5d7a0f9bf8c590388654a3638231eba8892

Add a test case to verify that the previous change avoids excess buffer
overread in sqlite3VdbeRecordCompare().

FossilOrigin-Name: 2b28e8d582cf10936fa1faca04a16ca2eeead66f

Earlier detection of corruption in sqlite3VdbeRecordCompare() in order to
avoid a potential buffer overread.

FossilOrigin-Name: 28ddecff044dbc2dff50a7d8406ab67dfe06587f

Add an assert() and a comment to clarify the operation of the
vdbeRecordCompareInt() routine.

FossilOrigin-Name: 851abdb8fd9b5a8a6ce21db53d30dbac3c430cc7

Adjust the repeat counts on several tests in speedtest1 so that the relative
time spent on the test is roughly the same regardless of --size.

FossilOrigin-Name: 7922809ee0d3978ce9221fbb7df63aa0684d0c4d

Merge enhancements and fixes from trunk.

FossilOrigin-Name: e005f2d6dd9faf38cc8fdb9428b5aa6192a6adae

Add another performance test case to speedtest1.  This case is another
ORDER BY test but this time without LIMIT.

FossilOrigin-Name: 9ab7ffd59209aef0ffbf384b3902a93fd3b86a6d

Fix a problem in the code added by [707ea170b3] causing vdbesort.c to sort unstably.

FossilOrigin-Name: d3e640afe611b6ae0b7f2cff5b00900d7e4d5ee3

Remove the sequence values from sorter records used by ORDER BY as well.

FossilOrigin-Name: c3ae3697832a00d4d5758988a8766bdbb691e6b8

Add an ORDER BY test case to speedtest1.c

FossilOrigin-Name: 588122641e57e957813d329ea071e13ccbde5acd

Enable four sorting threads by default in the command-line shell.

FossilOrigin-Name: 1cab83577c814feb35b4fb91af0d52a9751d99bc

Merge all fixes and enhancements from trunk.

FossilOrigin-Name: b415dfb6cb0df0c69992ca2bb700c15664f158e6

Detect when a VdbeCursor is still pointing at a valid row but that row has
moved, and invalidated the return from prior sqlite3BtreeDataFetch() or
sqlite3BtreeKeyFetch() calls.

FossilOrigin-Name: e6798871ce94961135762669af418cd78540c121

Omit the sequence value from sorter records used by GROUP BY queries that cannot use an index.

FossilOrigin-Name: 3f90abddc31ac20739778c235a834c33f7057997

Avoid unnecessary moving of content between registers during an ORDER BY.

FossilOrigin-Name: 4f472accf072d9cb64f209923924b26f21b13d27

Remove unused variables Parse.nColCache and Parse.iColCache.

FossilOrigin-Name: 4d7551ce464c8038147e81667368924f2a7485a6

Fix arithmetic operators so that they do not change the affinity of their
input operands.  Ticket [a8a0d2996a].

FossilOrigin-Name: 221f8f944703108e47d789fa8ce6c00fe2abcbb6

Avoid attempting to mmap memory from an offset that is not a multiple of the system page size on systems with page sizes larger than 32KB.

FossilOrigin-Name: db7d62c8d58eb1e8654a762c9b199ae4e2759038

Remove an unnecessary temporary register allocation.

FossilOrigin-Name: 5d506743f541b022cde04a9606baa4680cdfd70b

Remove a pointless OP_Once operation in ORDER BY clauses with LIMIT.

FossilOrigin-Name: e6c59d23316c83b318b1a94d9b28a5d321737fa5

Further enhancements to geneverated VDBE code for ORDER BY.

FossilOrigin-Name: e7188fad87ec82d36a39b80ccaf8006bf45a9bcd

merge fixes from trunk

FossilOrigin-Name: faf7f9caf526ab33a6fdb9c89b45a0483510db21

Use only a single OP_MakeRecord instead of two when constructing entries
to go onto a sorter.

FossilOrigin-Name: d696cdedacd39075aa7fc407ab7c7e50f01d9f39

Avoid a possible use of an uninitialized variable following an I/O or OOM
error.

FossilOrigin-Name: 641408a1395bfc911ca619ef9e5f073b913d856b

Clear the sort-order flags on the KeyInfo object associated with the
OP_Compare/OP_Jump of the block-sort logic, in order to make the OP_Jump
fully testable.

FossilOrigin-Name: 9b2838f23e5f52369eeb078f60bd231cc54362f8

Increase the version number to 3.8.5.

FossilOrigin-Name: 9760879d086b61476890927f01806a93798d4eee

Fix the ORDER BY optimization logic so that it will do a block-sort on
a partial DESC ORDER BY.  This enhancement uncovered a memory leak in
pushUntoSorter() which is also fixed.

FossilOrigin-Name: c36f74611cf17ad2ff198a2ac2054d7ab451a72c

Add the ability to use indices for the first few terms of an ORDER BY clause,
then sort in batches to handle the later terms.

FossilOrigin-Name: fa06a6fed9f48322d9b89721799ba12c46efa898

Change the names of SRT_DistTable and SRT_Table used by CTE to more
meaningful SRT_DistFifo and SRT_Fifo, respectively.  Simplify the
IgnorableOrderby() macro in the process.

FossilOrigin-Name: 45d8cc678d128f1dda6469864215a8ed9de4366a

Avoid leaking memory in an obscure case where the flattener adds an ORDER BY clause to the recursive part of a recursive query.

FossilOrigin-Name: 1f413aca00015100224273480e1ce39a76bf93ab

Merge the OFFSET-on-query-without-FROM fix from trunk.

FossilOrigin-Name: 71e9ae72c272dc86720b2bfe719f57de437c400b

Fix the OFFSET clause so that it works correctly on queries that lack
a FROM clause.  Ticket [07d6a0453d4ed8].

FossilOrigin-Name: 179ef81648b0ad557df78b7712f216b876b6fb65

New test case for block-sorting.

FossilOrigin-Name: e70cfa28aa393661ccc742ecd5e672d807bdd0a9

Merge trunk fixes for "x IN (?)" handling.

FossilOrigin-Name: eca35871c34374ca9189c7c9b6d490ac3c30357f

Remove a testcase() that is now always true due to the "x IN (?)" optimization.
Add an ALWAYS() around a conditional in the parser that cannot be false.

FossilOrigin-Name: d5a1530bdc7ace053d05d1a037551110021d3758

Fix the EXPLAIN indenter in the command-line shell to correctly
handle NextIfOpen and PrevIfOpen opcodes.

FossilOrigin-Name: 01944c53f5c129f48ce8842faaedcf5607dd381e

The "x IN (?)" optimization in check-ins [2ff3b25f40] and [e68b427afb] is
incorrect, as demonstrated by the in4-5.1 test case in this check-in.
The "COLLATE binary" that was being added to the RHS of IN was overriding
the implicit collating sequence of the LHS.  This change defines the EP_Generic
expression node property that blocks all affinity or collating sequence
information in the expression subtree and adds that property to the expression
taken from RHS of the IN operator.

FossilOrigin-Name: 2ea4a9f75f46eaa928ba17e9e91bc0432750d46d

Fix harmless compiler warnings.

FossilOrigin-Name: b1435f26b07b2208cfcca557f96342a5bd0d5328

Previous check-in is not quite correct.  "x IN (?)" is not exactly the same
as "x==?" do to collation and affinity issues.  The correct converstion should
be to "x==(+? COLLATE binary)".  The current check-in fixes this problem and
provides test cases.  Ticket [e39d032577df69]

FossilOrigin-Name: 2ff3b25f40fd117c8a2da1d1a3625f6b167b7b16

Convert expressions of the form "X IN (?)" with exactly one value on the
RHS of the IN into equality tests:  "X=?".  Add test cases to verify that
statements work correctly on this corner case.
Fix for ticket [e39d032577df6942].

FossilOrigin-Name: e68b427afbc82e201c64474117851aa4c9eb0c92

Fix an unnecessarily obtuse use of a bitmask flag.

FossilOrigin-Name: ca3140813198ab7ce470cf86334e55207f3461f9

Add a test to ensure os_unix.c works with 64KiB OS pages.

FossilOrigin-Name: e3d2be3ba47cdaafd26347620ae3bc2813203f16

Add an experimental fix to avoid attempting to mmap memory from an offset that is not a multiple of the system page size on systems with page sizes larger than 32KB.

FossilOrigin-Name: 6f3a5c24d254fc6faf607b505bdef4a7aafc21af

Merge the vdbesort.c optimization from trunk.

FossilOrigin-Name: e4bfffb988283c077778c60696be0d285ad66c3c

Fix query planner weights associated with choosing block-sorting.  Fix
block sorting of tables with collating functions.  Fix various test cases.
All "veryquick" tests are now passing, though more tests need to be added.

FossilOrigin-Name: 01afbf97c0ff29667806e9a7c4d74ca717819de5

Avoid some unnecessary calls to sqlite3VdbeRecordUnpack() that were being made when merging data from two or more temp files together in vdbesort.c

FossilOrigin-Name: 707ea170b3e26965b7e3982f7554d122d130b9a6

Make it possible for block-sort to use the OP_SorterOpen sorter in addition
to a generic OP_OpenEphemeral.

FossilOrigin-Name: 7ce2daafd39a117041bfdd0a7132e2764fe7a74b

Fix a problem in the block-sort logic that can arise if the VDBE opcode
array is resized while the block-sort logic is being coded.  "make test"
now runs to completion, though there are still 17 failures.

FossilOrigin-Name: 62f3a22050e0f11c789374f8a3785df0a84c24cb

Avoid reusing temporary registers in co-routines when doing
block-sorting.

FossilOrigin-Name: 463d921b519b08648a715e987c430f06b06bae84

Make sure the where.c query planner never reports that the number of ORDER BY
terms that are satisfied by indices is negative.

FossilOrigin-Name: b186d8d15a10d5e8fcae9ae72e8624d71831f5bd