Hi,
I'm having some problems understanding what the query planner is doing and
how to convince it to work in the way I want.
Sorry that this is such a long and involved eMail. I've tried to describe
my problem and show the steps I have taken in debugging it. I have made
some effort to present a minimal and basic illustration of the problem.
Either I'm in error and glad to be assisted, or there's some opportunities
that the query planner is not taking. Hopefully my detail helps someone who
knows more than me get to the bottom of the issue!
My GUI montior is reporting SQLite 3.8.11.1 and my app is using 3.17.0. I
get the same result with both.
I've included more complete details of my schema at the bottom of this
message but only introduced the bits I'm talking about as I go through.
I'm aiming to write a query that's good for feeding an iterator and for
pagination. i.e. I don't want a query that needs to compute the whole
result up-front, before returning the first row. I want something where I
can execute the query, consume a few rows for a while, close it and then
later start a new query with a parameter based on how far I got through and
then continue where I left off.
The structure of my dataset is such that once rows are written to the
database they are not changed, so there exist a set of parameters where I
can do this.
The data is an append only log. The log consists of entries (in the entrys
table) and they have monotonically increasing "entry-number"s. The table
can store more than one log so there's a "log-id" as well. These entries
have some data of their own and each point to zero or more items which are
stored in the "items" table. Thus there's a join table "entry-items" which
consists of 3 columns, all parts of the primary key, "log-d",
"entry-number" and "item-id".
Each entry has a "key". As entries are added to the log, the "latest" entry
for a particular key describes the current state of that key. The set of
keys and their current state is called "records" and they only exist as a
query on the tables. It is this query that I'm trying to plan well.
The idea is for the app user to be able to ask for a cursor on the records
and then consume them a page at a time. I'm not particularly bothered which
order they keys come out in but it has to be deterministic so that I can
restart the query again. It's nice if they come out in "key" order but
"entry-number" order will do too. The main property I want is to be able to
pass this app-defined cursor over my API boundary without holding open a
read transaction on SQLite.
I've started with a log that isn't huge but needs some attention to make it
work efficiently. This log has 54,272 entries and 42,737 records at the
latest version. I expect to have logs with a few tens of million active
records but probably nothing larger than 100 million. Not exactly Big Data
;-) but worthy of indexing.
So, here's my query, annotated with a few numbered points so that I can
talk about things. The bits that are commented out get commented in (and
out again!) as I discuss my problems with the query plan.
-----
explain query plan
SELECT
"entrys"."log-id" AS "log-id",
"entrys"."entry-number" AS "entry-number",
"entrys"."region" AS "region",
"entrys"."key" AS "key",
"entrys"."timestamp" AS "timestamp",
"entry-items"."item-id" AS "item-id",
"items"."blob" AS "blob"
FROM
(SELECT -- ** 1 **
MAX("entry-number") AS "entry-number",
"key"
FROM "entrys"
WHERE
"log-id" = 51 AND
"region" = "user" AND
"entry-number" <= 54272
-- AND key > "100009" -- ** 2 **
-- AND key > "145943"
GROUP BY "key"
-- order by key -- ** 3 **
) AS "specific-entrys"
LEFT OUTER JOIN "entrys"
ON
"specific-entrys"."entry-number" = "entrys"."entry-number"
AND "specific-entrys"."key" = "entrys"."key" -- ** 4 **
AND "user" = "entrys"."region"
LEFT OUTER JOIN "entry-items"
ON
51 = "entry-items"."log-id" AND -- ** 5 **
"specific-entrys"."entry-number" = "entry-items"."entry-number"
LEFT OUTER JOIN "items"
ON
"items"."item-id" = "entry-items"."item-id"
WHERE
"entrys"."log-id" = 51
-- order by key -- ** 6 **
;
-----
Here's the query plan for the query above:
-----
1|0|0|SEARCH TABLE entrys USING COVERING INDEX
entrys-log-id-region-key-entry-number-desc (log-id=? AND region=?)
0|0|0|SCAN SUBQUERY 1 AS specific-entrys
0|1|1|SEARCH TABLE entrys USING INDEX
entrys-log-id-region-key-entry-number-desc (log-id=? AND region=? AND key=?
AND entry-number=?)
0|2|2|SEARCH TABLE entry-items USING COVERING INDEX
entry-items-log-id-entry-number-item-id (log-id=? AND entry-number=?)
0|3|3|SEARCH TABLE items USING INTEGER PRIMARY KEY (rowid=?)
-----
The query uses a subselect (** 1 **) to get the latest entry number for
each and every key (i.e. to get the list of records). On my test workload
this produces 42,737 rows and takes 49ms. The efficiency of this query is
not a problem yet: If it has to precompute all the keys up-front then I'm
fine with that for now.
The query then joins the result back onto the "entrys" table to get the
rest of the per-entry metadata, onto the "entry-items" join table and then
onto the "items" table to get one row per entry per item. In my app I
coallesce these rows back together again.
The (non-explain version) query takes 679ms to run and produces 42,737 rows
because none of the entries in this particular log have more than one item
each.
Originally the two lines at (** 5 **) said
-----
"entrys"."log-id" = "entry-items"."log-id" AND
"entrys"."entry-number" = "entry-items"."entry-number"
-----
instead of
-----
51 = "entry-items"."log-id" AND -- ** 5 **
"specific-entrys"."entry-number" = "entry-items"."entry-number"
-----
As far as I can tell these are semantically equivalent but the original
version takes ~170 seconds rather than 679ms and the query plan looks like
this:
-----
1|0|0|SEARCH TABLE entrys USING COVERING INDEX
entrys-log-id-region-key-entry-number-desc (log-id=? AND region=?)
0|0|0|SCAN SUBQUERY 1 AS specific-entrys
0|1|1|SEARCH TABLE entrys USING INDEX
entrys-log-id-region-key-entry-number-desc (log-id=? AND region=? AND key=?
AND entry-number=?)
0|2|2|SCAN TABLE entry-items
0|3|3|SEARCH TABLE items USING INTEGER PRIMARY KEY (rowid=?)
-----
i.e. it does a SCAN TABLE in the loop rather than using the COVERING INDEX.
Do later version of SQLite manage to spot the constant propagation
opportunity?
Adding the lines at (** 4 **) allow the planner to use another index.
The query seems to produce rows ordered by "key". If I want to be able to
consume a few rows from the result set and then restart later (perhaps by
using something like the clauses at (** 2 **)) then I need to gurantee this
property.
Adding the WHERE clause at (** 6 **) does this but it changes the query
plan thus:
-----
1|0|0|SEARCH TABLE entrys USING COVERING INDEX
entrys-log-id-region-key-entry-number-desc (log-id=? AND region=?)
0|0|0|SCAN SUBQUERY 1 AS specific-entrys
0|1|1|SEARCH TABLE entrys USING INDEX
entrys-log-id-region-key-entry-number-desc (log-id=? AND region=? AND key=?
AND entry-number=?)
0|2|2|SEARCH TABLE entry-items USING COVERING INDEX
entry-items-log-id-entry-number-item-id (log-id=? AND entry-number=?)
0|3|3|SEARCH TABLE items USING INTEGER PRIMARY KEY (rowid=?)
0|0|0|USE TEMP B-TREE FOR ORDER BY
-----
i.e. now we have a "USE TEMP B-TREE FOR ORDER BY" which (I imagine!) causes
the whole result set to be generated up front before the first row is
returned.
Now, without the order by clause in (** 2 **), we're getting the rows out
in the correct order as a side effect of the group by clause in (** 1 **)
so let's uncomment the order by clause at (** 3 **) instead.
This gets us back to the original, iterative query plan. It's got a
subquery that we scan in (sorted) order and then some inner loops which
should preserve the ordering of the result set, even if the inner loops
produce more rows.
However, we still want to gurantee this property so I uncommented the order
by clause at (** 6 **) again. Once again, the "USE TEMP B-TREE FOR ORDER
BY" line appears in the query plan.
I think I need this order by clause so that I get the correct behaviour in
my app, even if later version of the engine change the query plan. Perhaps
I lose my performance properties but at least I still get the correct
answer!
How do I get SQLite to recognise that it's already done enough work in with
this plan to get the results out in the order I specified and therefore
elide the "USE TEMP B-TREE FOR ORDER BY" parts of its plan?
Also, is there a way to find out which order SQLite thinks it is returning
the rows in (if any) so that, if one exists, I can construct the order by
clause that will cause no change to the query plan?
Thanks for any insight and help you can offer me.
I've been a long time user of SQLite so thanks for all the great work and
documentation over the years!
Here's my schema:
-----
sqlite> .schema
CREATE TABLE IF NOT EXISTS "entry-items" ("log-id" NOT NULL ,
"entry-number" NOT NULL , "item-id" NOT NULL );
CREATE TABLE IF NOT EXISTS "entrys" ("log-id" INTEGER NOT NULL ,
"entry-number" INTEGER NOT NULL , "region" TEXT NOT NULL , "key" TEXT NOT
NULL , "timestamp" INTEGER NOT NULL , PRIMARY KEY ("log-id",
"entry-number"));
CREATE TABLE IF NOT EXISTS "item-digests" ("item-id" INTEGER NOT NULL ,
"algorithm" TEXT NOT NULL , "digest" BLOB NOT NULL , PRIMARY KEY
("item-id", "algorithm"));
CREATE TABLE IF NOT EXISTS "items" ("item-id" INTEGER PRIMARY KEY NOT NULL
UNIQUE , "blob" BLOB NOT NULL UNIQUE );
CREATE TABLE IF NOT EXISTS "registers" ("log-id" INTEGER PRIMARY KEY NOT
NULL UNIQUE , "index-of" INTEGER NOT NULL , "name" TEXT NOT NULL );
CREATE INDEX "entry-items-log-id-entry-number-item-id" ON "entry-items"
("log-id" ASC, "entry-number" ASC, "item-id" ASC);
CREATE UNIQUE INDEX "entrys-region-key-entry-number-log-id" ON "entrys" (
"region" ASC, "key" ASC, "entry-number" ASC, "log-id" ASC);
CREATE UNIQUE INDEX "item-digests-algorithm-digest" ON "item-digests"
("algorithm" ASC, "digest" ASC);
CREATE UNIQUE INDEX "registers-index-of-name" ON "registers" ("index-of"
ASC, "name" ASC);
CREATE UNIQUE INDEX "entrys-log-id-region-key-entry-number-desc" ON
"entrys" ( "log-id" ASC, "region" ASC, "key" ASC, "entry-number" DESC)
-----
Regards,
@ndy
--
andy...@ashurst.eu.org
http://www.ashurst.eu.org/
0x7EBA75FF
_______________________________________________
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
