So I just did the bisect and I narrowed it down to this change: https://www.sqlite.org/cgi/src/info/609fbb94b8f01d6792e5941ab23ce041313d359f6788c4dde6b1ca749ab

So I just did the bisect and I narrowed it down to this change: https://www.sqlite.org/cgi/src/info/609fbb94b8f01d6792e5941ab23ce041313d359f6788c4dde6b1ca749ab49137 https://www.sqlite.org/cgi/src/info/609fbb94b8f01d6792e5941a... This seems to have had a wider fallout, from there (thanks Fossil, cool feature!) I found the reference back to https://sqlite.org/forum/forumpost/64d36440e473516c https://sqlite.org/forum/forumpost/64d36440e473516c, which reports another similar regression. Simply patching 3.43 to remove this cost adjustment doesn't fix the regression though, so I'll keep digging. Edit: a workaround seems to be an ultra-agressive use of ANALYZE to give the autoindexing a better chance. Setting the analyze limit to -1 (unlimited) and forcing all pool connections to ANALYZE on close (i.e. not relying on PRAGMA optimize) does "fix" the regression the next time the service runs.