SQLite

This branch adds a new pragma, "PRAGMA analysis_limit=N", where N is a non-negative 32-bit integer. If N is zero, everything works as it always has. But if N is postive, then the ANALYZE command omits computing sqlite_stat4 and uses a sample of each index to compute sqlite_stat1. The size of the sample is usually N rows or less, but can be as large as 2*N in some cases.

Setting N to 100 or 200 will compute sqlite_stat1 much faster with results that are nearly as good. The idea here is that developers who do not run "PRAGMA optimize" on their databases because "it is too expensive" now have less of an excuse. Simply set "PRAGMA analysis_limit=200" prior to running "PRAGMA optimize" and then even hundred-megabyte databases with lots of indexes will run in milliseconds.

The analysis_limit works by only scanning a prefix of each index. The size of the prefix is initially N rows. If the left-most column of the index has not changed in the first N rows, then it skips ahead to the first row with a different left-most column and scans N more rows. The number of rows in the index is estimated by positioning the cursor on the first row and then taking the product of the number of cells on each page starting with the page on which the cursor is positioned and going back up the b-tree to the root page.

The result of an approximate analysis is usually pretty good - certainly good enough for query planning. But it can be off for misshapen indexes. For example, if the left most column of the first 100 rows of an index (with N=100) holds consecutive integers, but the remaining 1,000,000 rows are all 9999, then the approximate scan will think that most entries in the index are unique and that it is a very selective index, when in fact the index his horrid and should be avoided. This error could have been avoided, perhaps, by sampling multiple bands along the whole length of the index. But there could still be cases where the selective parts of the index happen to be sampled while the non-selective parts were not. The only certain way to know that you haven't missed a particular index value with many repeats is to read the entire index. For most cases, using N=100 or N=200 yields excellent statistics. For the rare counter-examples, one can always set N=0 and do a complete scan.

The computation of sqlite_stat4 requires reading the entire index, and so stat4 statistics gathering is disabled when N is positive.