Please apply this patch:

--- src/where.c
+++ src/where.c
@@ -3590,17 +3590,17 @@
         ** of X is smaller for views and subqueries so that the query planner
         ** will be more aggressive about generating automatic indexes for
         ** those objects, since there is no opportunity to add schema
         ** indexes on subqueries and views. */
         pNew->rSetup = rLogSize + rSize;
         if( !IsView(pTab) && (pTab->tabFlags & TF_Ephemeral)==0 ){
           pNew->rSetup += 28;
         }else{
-          pNew->rSetup -= 10;
+          pNew->rSetup -= 21;
         }
         ApplyCostMultiplier(pNew->rSetup, pTab->costMult);
         if( pNew->rSetup<0 ) pNew->rSetup = 0;
         /* TUNING: Each index lookup yields 20 rows in the table.  This
         ** is more than the usual guess of 10 rows, since we have no way
         ** of knowing how selective the index will ultimately be.  It would
         ** not be unreasonable to make this value much larger. */
         pNew->nOut = 43;  assert( 43==sqlite3LogEst(20) );

Rerun your query and let me know the timings:

1. Timing for version 3.38.5
2. Timing for version 3.40.0 or later
3. Timing for version 3.40.0 or later plus the patch above.

Update to the above.....

I created random test data and was able to confirm that the patch seems to clear the problem without causing any other regressions, at least not in our test data. The change has been checked in.

Thanks for the quick reply!

    13.1 seconds - 3.38.5 
12,488   seconds - 3.40.1 Unpatched (3hr 28m 8s)
   130.3 seconds - 3.40.1 Patched

So...a lot better, but 10 times worse than 3.38.5

On the random data I generated, I got 3.40.1 patched as being faster than 3.38.5. The difference must be in the data.

Please send me your data so that I can run experiments. You can reach me directly at drh at sqlite dot org to arrange transfer of data that you do not want to make public.

I should have added the query plan: It still does not use the index at all (and the date range stuff is a pretty tight limit):

Patched 3.40.1 query plan:

QUERY PLAN
|--MATERIALIZE mult
|  |--MATERIALIZE sums
|  |  |--MATERIALIZE vals
|  |  |  |--MATERIALIZE src
|  |  |  |  |--MATERIALIZE raw
|  |  |  |  |  `--SCAN summary
|  |  |  |  |--MATERIALIZE init
|  |  |  |  |  |--SCAN raw
|  |  |  |  |  `--USE TEMP B-TREE FOR GROUP BY
|  |  |  |  |--SCAN i
|  |  |  |  `--SEARCH raw USING AUTOMATIC COVERING INDEX (country=?)
|  |  |  |--SCAN src
|  |  |  `--SEARCH raw USING AUTOMATIC PARTIAL COVERING INDEX (country=?)
|  |  |--SCAN vals
|  |  `--USE TEMP B-TREE FOR GROUP BY
|  `--SCAN sums
|--SCAN mult
|--SEARCH sums USING AUTOMATIC COVERING INDEX (country=? AND date=?)
|--SEARCH mult USING AUTOMATIC COVERING INDEX (country=? AND date=?)
|--SEARCH sums USING AUTOMATIC COVERING INDEX (country=? AND date=?)
`--SEARCH i USING AUTOMATIC COVERING INDEX (country=?)

Please also try rewriting the "fit" subquery as follows:

  -- Calculate the coefficients for the least squares fit
  fit(country, date, a, b) AS (
    SELECT inv.country, inv.date, a * xy + b * y, c * xy + d * y
      FROM sums, mult, inv
     WHERE sums.country = mult.country AND sums.date = mult.date
       AND mult.country = inv.country AND mult.date = inv.date
  )

For my random test data, this "fit" rewrite runs about twice as fast on an unpatched 3.40.1 as it does under 3.38.5.

Revised times:

Version		Run time	Query
Unpatched 3.40.1		2m 11s (131s)	revised query
3.38.5		15.3 seconds	revised query
3.38.5		13.3 seconds	original query

Would you like me to send the data? Compressed it's about 16MB (in xz).

Note to the public: Gurnthos sent me the database via a private side channel.

I think this issue has now been resolved, as of check-in 66f29c403d28630b. The query should be fast again using the latest trunk check-in, or using the "Prerelease Snapshot" on the Download page. In my tests, the latest trunk is a little faster (though not dramatically so) than 3.38.5.

Please report back if you see otherwise.

This issue arose coincident with the addition of MATERIALIZED and NOT MATERIALIZED keywords for CTEs. When a CTE is tagged as MATERIALIZED, then it is always materialized as-is and is not subject to the query flattening optimization. This is a way of overriding the query optimizer. I copied this from PostgreSQL.

However, if a CTE was being used more than once, I was marking it as if it had had the MATERIALIZED keyword, to prevent it from being implemented using a co-routine. But this had the adverse side effect of disabling the query flattening optimization for the CTE. Without query flattening, the query ran more slowly.

The fix was enhance the function that decides whether or not to implement a CTE as a co-routine so that it became unnecessary to tag such CTEs as if they had the MATERIALIZED keyword. Now the query flattener optimization is permitted and the overall query is fast again.

Would that all query planner fixes were this simple...

Wonderful work, wonderful explanation. Also, wonderful result: It is indeed slightly faster than 3.38.5!

Thank you for your assistance in this.

As due diligence, I compared the output and it seems to produce differing results in the final digits for many rows, but for some rows the digits are significantly different (I used printf("%.4e") for all fp values to look for gross differences).

I am still investigating the reasons (probably rounding, maybe algorithm).

You haven't specified any ordering, so that's not particularly surprising.

Have you tried the original setup but specifying

PRAGMA reverse_unordered_selects = 1;

just to make sure you aren't implicitly relying on a certain order of results?

I just tried that, but did add an 'order by' to the final select (to make comparison easier), and the numbers were identical in reversed/non-reversed runs using 3.38.5. Ditto the reversed/non-reversed runs using the snapshot.

Comparing these (sorted) results, what I'm seeing are near-zero values in the snapshot version, vs actual zeroes in 3.38.5.

It is (I think) my logic: For example, in the new version, for one row, I get a value for 'a' of -2.22044604925031e-16, whereas in 3.38.5, it comes out as exactly 0. This results in a slight discrepancy between 'nFin' and 'nPrev' in the new version, which means that 'growth' is a tiny negative value (-2.22044604925031e-16), which results in 'doubling' being -3.12165738408268e+15. Whereas in 3.38.5, they are 0 and NaN, respectively.

I am still looking into exact causes, but this almost-zero values occur in exactly the same places in 3.38.5 and 3.40.1, but in different places in the snapshot, so I believe it is just a minor artifact.