Temp B-Tree not limited to right part when joining unclustered tables with virtual tables
(1) By anacrolix on 2022-10-26 00:28:29 [source]
When joining a rowid table with a virtual table and ordering by elements of the rowid table then the virtual table, the query plan generated fails to limit the temp b-tree to the right part of the order by.
This is demonstrated minimally by this reproducing code:
-- succeeds: regular tables when scanning using b
begin;
create table a(b);
create table c(a,d);
create index b on a(b);
explain query plan select * from a indexed by b join c on a=a.rowid order by b, a.rowid, d;
rollback;
-- succeeds: vtable with clustered table
begin;
create table a(a primary key, b) without rowid;
create index b on a(b);
explain query plan select * from a join generate_series(1, a) order by b, a, value;
rollback;
-- fails: vtable with rowid table
begin;
create table a(b);
create index b on a(b);
explain query plan select * from a join generate_series(1, a.rowid) order by b, a.rowid, value;
rollback;
repro.sql and ran it with sqlite3 :memory: < repro.sql. It outputs:
QUERY PLAN
|--SCAN a USING COVERING INDEX b
|--SCAN c
`--USE TEMP B-TREE FOR RIGHT PART OF ORDER BY
QUERY PLAN
|--SCAN a USING COVERING INDEX b
|--SCAN generate_series VIRTUAL TABLE INDEX 3:
`--USE TEMP B-TREE FOR RIGHT PART OF ORDER BY
QUERY PLAN
|--SCAN a USING COVERING INDEX b
|--SCAN generate_series VIRTUAL TABLE INDEX 3:
`--USE TEMP B-TREE FOR ORDER BY
I'm fairly certain there's some logic coming out of item 4 at https://www.sqlite.org/withoutrowid.html#differences_from_ordinary_rowid_tables, "ordinary rowid tables in SQLite violate the SQL standard and allow NULL values in PRIMARY KEY fields". I suspect that joins on regular tables have some logic that overlooks this, but against a table without a constraint, unless it's clustered, the optimization is being missed because the planner does not believe that a.rowid (or any other non-clustered alternative) is unique.
(2) By Gunter Hick (gunter_hick) on 2022-10-26 11:24:21 in reply to 1 [link] [source]
What ist the original problem? I don't think the queries are in any way equivalent. The first one is an equijoin of two tables. The other two create the cartesian product of each LH row with a sequence of numbers between 1 and the key value in the LH row. Should you not be using ... generate_series(1,10) ON a = value ...?
(3) By anacrolix on 2022-10-26 11:54:58 in reply to 2 [link] [source]
The point is that for each row in a, there's a set of rows from the right hand table that only exist for the primary key of a, and so ordering on the primary key of a before any column from the right hand table should only require sorting the rows coming from the right.
The equijoin is to force the regular tables to replicate the mapping of rows to a single primary key from a that the virtual table has. The use of generate_series is only to demonstrate this with a virtual table implementation provided by sqlite core. I have my own that shows the same behaviour.
The original problem is a 12.2M row table on the left joined with a virtual table on the right that results in 492M total rows that can either be sorted in entirety, or on the right part once for each of the 12.2M rows... An enormous difference in behaviour.
(4) By anacrolix on 2022-10-27 22:06:12 in reply to 1 [link] [source]
I guess this is too advanced for sqlite? I had similar query planning issues with FOR IN-OPERATOR optimization doesn't occur through view. Should I look at Postgres or libSQL instead?
(5) By Ryan Smith (cuz) on 2022-10-27 23:58:02 in reply to 4 [link] [source]
I guess this is too advanced for sqlite?
It's so advanced in fact, that none of us understand what you mean. The Query planner has very many AI tweaks to decide the best plan, and spoiler alert: It's often NOT by using the index.
Make a simple reproducible dataset that anyone here can test with (or DDL to create it) for a lot of data, then form the different queries which:
- A: Produce the same output, and
- B: Where one is demonstrably faster than the other in actual runtime, and
- C: Multiple test runs prove it to be consistently so.
Then, and only then, will we be able to weigh in and possibly show how to tweak it to get the fastest result.
At this point however, your assumptions are all circumstantial and your hypotheses are all theoretical and based on amounts of data where the time is inconsequential. At least, in so far as we can follow your thinking. Gunther already mentioned that the queries are not equivalent, to which you agree but then offer hypothetical reasoning for why it should treat it the same anyway, without any real proof over whether that makes one actual iota of difference or not, just assumptions (I mean you may well be correct, but at this point nobody can refute or confirm, so the exercise is pointless).
Should I look at Postgres or libSQL instead?
If you can create a dataset and queries for which the version running in PostGres (specifically) is much faster, even if only relative to the other query, but the same ratio does not hold for SQLite, then you would also have a real case and someone might look into it, perhaps even fix it, so you don't have to move to Postgres. Also, Postgres is a great DB, lots of us use it too, so I would definitely say go for it - but it solves a different problem than SQLite.
(6) By Gunter Hick (gunter_hick) on 2022-10-28 06:34:45 in reply to 3 [link] [source]
Maybe there is room for improvement in the data model and/or the query formulation that avoids duplicating the sorting work. Unfortunately, you do not provide any information that would allow such inspection.
(7) By anacrolix on 2022-11-01 01:45:32 in reply to 5 [link] [source]
I don't see how this isn't sufficient examples: I have 2 queries that are almost identical and for one it refuses to make use of any indexes etc. I understand that this might be affected by the amount of data etc., but I've described a case where with 12M rows it still makes this choice. (Clustered, correct. rowid, incorrect).
(8) By Ryan Smith (cuz) on 2022-11-01 07:02:14 in reply to 7 [link] [source]
I have 2 queries that are almost identical and for one it refuses to make use of any indexes...
That's the point I tried to make - in lots of cases, using the index is not faster at all, in fact quite the opposite. Assuming that the query will be slower just because the planner isn't using the index is a bad assumption.
An index isn't magic, it's a tool that helps under specific circumstances, and not all queries meet those circumstances.
Further to this, the QP might have inside knowledge for a specific query form that the rows will be produced in the order of the appropriate index anyway, and any sorting will merely be for the main table joined duplicate rows (if any) for which using the index again wouldn't help at all and standard Merge-sort algorithm would make quick work of.
Lot's of times people have posted query plans that they felt were not optimal, and when we measure it, the query performs excellently, to their total surprise. Other times, they were on to something and their reproducible test cases helped improve SQLite.
I've described a case where with 12M rows it still makes this choice
Again, you may be correct, but "describing" isn't useful to us. Give us the 12M row DB (or the DDL to create it) and the queries where one is shown to be significantly slower than the other (not caring what the QP thinks about using the index, but actually slower in measured time taken), and then we can reproduce, test, improve, or if need be, the devs can fix the Query planner.
Currently to us it seems (or to me at least) that your complaint is driven by the erroneous belief that using the index is always faster and your insistence to "describe" it rather than show it is akin to eyewitness testimony or hearsay. Nobody will take it serious until you supply an actual DB and actual query that is reproducible and demonstrates actual slowness.