Re: [sqlite] Why is a b-tree sort required for this query?

[Simon Slavin]

On 20 Nov 2014, at 9:48pm, Oliver Smith  wrote:

> The t2c table has an index on id, name; I expected it would use that index so 
> that the data would be naturally in order.

As you've found, you cannot rely on this.  If you need an answer to a query to 
be in a specific order, specify it using ORDER BY.  It's the only way to be 
sure.

Don't try to second-guess the optimizer.  It occasionally does things that seem 
weird just because the numbers suggest they're optimal.

Simon.
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Why is a b-tree sort required for this query?

[Clemens Ladisch]

Oliver Smith wrote:
>> On Sun, Nov 16, 2014 at 2:18 PM, Oliver Smith  wrote:
>>> ...
>>> CREATE TABLE t2c (id INTEGER, name text, t2_id INTEGER, UNIQUE (t2_id, 
>>> name));
>>>
>>> EXPLAIN QUERY PLAN
>>> SELECT t1c.t1_id, t1c.id, t2c.t2_id, t2c.id
>>> FROM t1c,
>>>   t2 INNER JOIN t2c ON (t2c.t2_id = t2.id)
>>> ORDER BY t1c.t1_id, t1c.id, t2.name, t2c.name
>>>
>>> And yet the plan invokes a B-Tree to sort:
>>>
>>> "0""0""0""SCAN TABLE t1c USING COVERING INDEX 
>>> idx_t1c_by_t1_id"
>>> "0""1""2""SCAN TABLE t2c"
>>> "0""2""1""SEARCH TABLE t2 USING AUTOMATIC COVERING INDEX 
>>> (id=?)"
>>> "0""0""0""USE TEMP B-TREE FOR RIGHT PART OF ORDER BY"
>>>
>>> Is the temp b-tree redundant here?
>>
>> I don't think so.  What query plan are you thinking might be able to omit
>> the sorting pass in this query?
>
> The t2c table has an index on id, name; I expected it would use that
> index so that the data would be naturally in order.

If you had used "ORDER BY t2c.id, t2c.name, ...", it would be possible
to use this index.  How would a different order help?


Regards,
Clemens
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Why is a b-tree sort required for this query?

[Oliver Smith]

Date: Mon, 17 Nov 2014 21:29:21 -0500
From: Richard Hipp
To: General Discussion of SQLite Database
Subject: Re: [sqlite] Why is a b-tree sort required for this query?
Message-ID:

Re: [sqlite] Why is a b-tree sort required for this query?

[John Hascall]

​If you do
   ORDER BY t1c.t1_id, t1c.id;

then you won't have the b-tree step, but ​including the name fields means
it has the extra work to do to satisfy your order by.  Or am I missing
something?

John



On Sun, Nov 16, 2014 at 1:18 PM, Oliver Smith  wrote:

> In the following scenario:
>
>CREATE TABLE t1 (id INTEGER, name text, UNIQUE (name));
>CREATE TABLE t1c (id INTEGER, name text, t1_id INTEGER, UNIQUE (name));
>CREATE INDEX idx_t1c_by_t1_id ON t1c (t1_id, id);
>
>CREATE TABLE t2 (id INTEGER, name text, UNIQUE(name));
>CREATE TABLE t2c (id INTEGER, name text, t2_id INTEGER, UNIQUE
>(t2_id, name));
>
> I have a query designed to generate a row for t2c ordered by t2 for every
> instance of t1c ordered by t1 id and then t1c id.
>
> The query uses indexes and those should ensure that the results are in the
> order I am specifying:
>
>EXPLAIN QUERY PLAN
>SELECT t1c.t1_id, t1c.id, t2c.t2_id, t2c.id
>FROM t1c,
>  t2 INNER JOIN t2c ON (t2c.t2_id = t2.id)
>ORDER BY t1c.t1_id, t1c.id, t2.name, t2c.name
>;
>
> And yet the plan invokes a B-Tree to sort:
>
>"0""0""0""SCAN TABLE t1c USING COVERING INDEX
>idx_t1c_by_t1_id"
>"0""1""2""SCAN TABLE t2c"
>"0""2""1""SEARCH TABLE t2 USING AUTOMATIC COVERING INDEX
>(id=?)"
>"0""0""0""USE TEMP B-TREE FOR RIGHT PART OF ORDER BY"
>
> Is the temp b-tree redundant here?
>
> $ sqlite3 --version
> 3.8.5 2014-06-04 14:06:34 b1ed4f2a34ba66c29b130f8d13e9092758019212
>
> ___
> sqlite-users mailing list
> sqlite-users@sqlite.org
> http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
>
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Why is a b-tree sort required for this query?

[Richard Hipp]

On Sun, Nov 16, 2014 at 2:18 PM, Oliver Smith  wrote:

> In the following scenario:
>
>CREATE TABLE t1 (id INTEGER, name text, UNIQUE (name));
>CREATE TABLE t1c (id INTEGER, name text, t1_id INTEGER, UNIQUE (name));
>CREATE INDEX idx_t1c_by_t1_id ON t1c (t1_id, id);
>
>CREATE TABLE t2 (id INTEGER, name text, UNIQUE(name));
>CREATE TABLE t2c (id INTEGER, name text, t2_id INTEGER, UNIQUE
>(t2_id, name));
>
> I have a query designed to generate a row for t2c ordered by t2 for every
> instance of t1c ordered by t1 id and then t1c id.
>
> The query uses indexes and those should ensure that the results are in the
> order I am specifying:
>
>EXPLAIN QUERY PLAN
>SELECT t1c.t1_id, t1c.id, t2c.t2_id, t2c.id
>FROM t1c,
>  t2 INNER JOIN t2c ON (t2c.t2_id = t2.id)
>ORDER BY t1c.t1_id, t1c.id, t2.name, t2c.name
>;
>
> And yet the plan invokes a B-Tree to sort:
>
>"0""0""0""SCAN TABLE t1c USING COVERING INDEX
>idx_t1c_by_t1_id"
>"0""1""2""SCAN TABLE t2c"
>"0""2""1""SEARCH TABLE t2 USING AUTOMATIC COVERING INDEX
>(id=?)"
>"0""0""0""USE TEMP B-TREE FOR RIGHT PART OF ORDER BY"
>
> Is the temp b-tree redundant here?
>

I don't think so.  What query plan are you thinking might be able to omit
the sorting pass in this query?


>
> $ sqlite3 --version
> 3.8.5 2014-06-04 14:06:34 b1ed4f2a34ba66c29b130f8d13e9092758019212
>
> ___
> sqlite-users mailing list
> sqlite-users@sqlite.org
> http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
>



-- 
D. Richard Hipp
d...@sqlite.org
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

[sqlite] Why is a b-tree sort required for this query?

[Oliver Smith]

In the following scenario:

   CREATE TABLE t1 (id INTEGER, name text, UNIQUE (name));
   CREATE TABLE t1c (id INTEGER, name text, t1_id INTEGER, UNIQUE (name));
   CREATE INDEX idx_t1c_by_t1_id ON t1c (t1_id, id);

   CREATE TABLE t2 (id INTEGER, name text, UNIQUE(name));
   CREATE TABLE t2c (id INTEGER, name text, t2_id INTEGER, UNIQUE
   (t2_id, name));

I have a query designed to generate a row for t2c ordered by t2 for 
every instance of t1c ordered by t1 id and then t1c id.


The query uses indexes and those should ensure that the results are in 
the order I am specifying:


   EXPLAIN QUERY PLAN
   SELECT t1c.t1_id, t1c.id, t2c.t2_id, t2c.id
   FROM t1c,
 t2 INNER JOIN t2c ON (t2c.t2_id = t2.id)
   ORDER BY t1c.t1_id, t1c.id, t2.name, t2c.name
   ;

And yet the plan invokes a B-Tree to sort:

   "0""0""0""SCAN TABLE t1c USING COVERING INDEX
   idx_t1c_by_t1_id"
   "0""1""2""SCAN TABLE t2c"
   "0""2""1""SEARCH TABLE t2 USING AUTOMATIC COVERING INDEX
   (id=?)"
   "0""0""0""USE TEMP B-TREE FOR RIGHT PART OF ORDER BY"

Is the temp b-tree redundant here?

$ sqlite3 --version
3.8.5 2014-06-04 14:06:34 b1ed4f2a34ba66c29b130f8d13e9092758019212

___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users