The "natural" order of the query results.

classic Classic list List threaded Threaded
14 messages Options
Reply | Threaded
Open this post in threaded view
|

The "natural" order of the query results.

John Found
Is there some relation between the indexes used in the query, the GROUP BY fields used
and the order of the result rows, when no "ORDER BY" clause is used?

I am asking, because I noticed, that on some queries, when I am using "ORDER BY" the query always
use temporary b-tree for ordering, but by including the needed fields in the "GROUP BY" clause
and removing the ORDER BY clause, the query returns the rows in the proper order without temp b-tree.

So, is it safe to use this implicit ordering, or this behavior can be changed in the future versions of SQLite?

Here is an example:

create table A (
  id integer primary key autoincrement,
  o1 integer,
  o2 integer
);

create table B (
  Aid integer references A(id),
  data text
);

create index idxA on A(o1 desc, o2 desc);

insert into A(o1, o2) values (1, 100), (2, 50), (3, 200), (5, 300);
insert into B(Aid, data) values (1, "b"), (1, "a"), (2, "c"), (2, "d"), (2, "e"), (3, "f"), (3, "g");

-- Always uses temp b-tree for order by
select
  group_concat(B.data), o1, o2
from
  A
left join
  B on A.id = B.Aid
group by
  A.id
order by
  A.o1 desc, A.o2 desc;

explain query plan:
id parent notused detail
8 0 0 SCAN TABLE A
19 0 0 SEARCH TABLE B USING AUTOMATIC COVERING INDEX (Aid=?)
58 0 0 USE TEMP B-TREE FOR ORDER BY


-- This one returns the rows in the needed order without ORDER BY
select
  group_concat(B.data), o1, o2
from
  A indexed by idxA
left join B on A.id = B.Aid
group by A.id, A.o1, A.o2;

explain query plan:
id parent notused detail
7 0 0 SCAN TABLE A USING COVERING INDEX idxA
18 0 0 SEARCH TABLE B USING AUTOMATIC COVERING INDEX (Aid=?)


-- But if I add ORDER BY it still begins to use temp b-tree
-- regardless that it does not change the order.
select
  group_concat(B.data), o1, o2
from
  A indexed by idxA
left join B on A.id = B.Aid
group by A.id, A.o1, A.o2
order by A.o1 desc, A.o2 desc;

explain query plan:
8 0 0 SCAN TABLE A
19 0 0 SEARCH TABLE B USING AUTOMATIC COVERING INDEX (Aid=?)
60 0 0 USE TEMP B-TREE FOR ORDER BY


All the above queries, returns the same result rows in the same order:

group_concat(B.data)  o1   o2
NULL                   5   300
f,g                    3   200
c,d,e                  2   50
a,b                    1   100



               
--
John Found <[hidden email]>
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: The "natural" order of the query results.

Barry Smith
Without an order by, sqlite can return the rows in any order it pleases. Likely whatever consumes the least resources. Although unlikely given your indices, it might be possible - for instance if some future micro-optimisation finds that it's quicker to read the index in reverse, then sqlite would give things in the opposite order. If you leave out a necessary order by you are very much exposing yourself to internal changes. So much so that there is a pragma reverse_unordered_selects (https://www.sqlite.org/pragma.html#pragma_reverse_unordered_selects) you can use to specifically find if your app makes invalid assumptions about order.

You might have found a missed optimisation opportunity here (although there's always the tradeoff of library size & cycles to optimise vs execution cycles saved to consider).

> On 16 Sep 2018, at 6:29 pm, John Found <[hidden email]> wrote:
>
> Is there some relation between the indexes used in the query, the GROUP BY fields used
> and the order of the result rows, when no "ORDER BY" clause is used?
>
> I am asking, because I noticed, that on some queries, when I am using "ORDER BY" the query always
> use temporary b-tree for ordering, but by including the needed fields in the "GROUP BY" clause
> and removing the ORDER BY clause, the query returns the rows in the proper order without temp b-tree.
>
> So, is it safe to use this implicit ordering, or this behavior can be changed in the future versions of SQLite?
>
> Here is an example:
>
> create table A (
>  id integer primary key autoincrement,
>  o1 integer,
>  o2 integer
> );
>
> create table B (
>  Aid integer references A(id),
>  data text
> );
>
> create index idxA on A(o1 desc, o2 desc);
>
> insert into A(o1, o2) values (1, 100), (2, 50), (3, 200), (5, 300);
> insert into B(Aid, data) values (1, "b"), (1, "a"), (2, "c"), (2, "d"), (2, "e"), (3, "f"), (3, "g");
>
> -- Always uses temp b-tree for order by
> select
>  group_concat(B.data), o1, o2
> from
>  A
> left join
>  B on A.id = B.Aid
> group by
>  A.id
> order by
>  A.o1 desc, A.o2 desc;
>
> explain query plan:
> id    parent    notused    detail
> 8    0    0    SCAN TABLE A
> 19    0    0    SEARCH TABLE B USING AUTOMATIC COVERING INDEX (Aid=?)
> 58    0    0    USE TEMP B-TREE FOR ORDER BY
>
>
> -- This one returns the rows in the needed order without ORDER BY
> select
>  group_concat(B.data), o1, o2
> from
>  A indexed by idxA
> left join B on A.id = B.Aid
> group by A.id, A.o1, A.o2;
>
> explain query plan:
> id    parent    notused    detail
> 7    0    0    SCAN TABLE A USING COVERING INDEX idxA
> 18    0    0    SEARCH TABLE B USING AUTOMATIC COVERING INDEX (Aid=?)
>
>
> -- But if I add ORDER BY it still begins to use temp b-tree
> -- regardless that it does not change the order.
> select
>  group_concat(B.data), o1, o2
> from
>  A indexed by idxA
> left join B on A.id = B.Aid
> group by A.id, A.o1, A.o2
> order by A.o1 desc, A.o2 desc;
>
> explain query plan:
> 8    0    0    SCAN TABLE A
> 19    0    0    SEARCH TABLE B USING AUTOMATIC COVERING INDEX (Aid=?)
> 60    0    0    USE TEMP B-TREE FOR ORDER BY
>
>
> All the above queries, returns the same result rows in the same order:
>
> group_concat(B.data)  o1   o2
> NULL                   5   300
> f,g                    3   200
> c,d,e                  2   50
> a,b                    1   100
>
>
>
>        
> --
> John Found <[hidden email]>
> _______________________________________________
> sqlite-users mailing list
> [hidden email]
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: The "natural" order of the query results.

John Found
On Sun, 16 Sep 2018 19:27:40 +1000
Barry Smith <[hidden email]> wrote:

> Without an order by, sqlite can return the rows in any order it pleases. Likely whatever consumes the least resources. Although unlikely given your indices, it might be possible - for instance if some future micro-optimisation finds that it's quicker to read the index in reverse, then sqlite would give things in the opposite order. If you leave out a necessary order by you are very much exposing yourself to internal changes. So much so that there is a pragma reverse_unordered_selects (https://www.sqlite.org/pragma.html#pragma_reverse_unordered_selects) you can use to specifically find if your app makes invalid assumptions about order.


Well, I was sure that the first answer will be this. But I asked the question in hope to get
some deeper information about the relations between order by, group by and the indices used.

It is not a coincidence that in the example case I used "INDEXED BY" clause.

With PRAGMA reverse_unordered_selects=1; all the queries in the example return the rows in exactly the same proper order.
I tryed to insert the values in random order in order to avoid the primary key influence on the ordering and the result
is still the same.

IMO, this somehow proves that I can use such implicit ordering in this very case. Or not?

>
> You might have found a missed optimisation opportunity here (although there's always the tradeoff of library size & cycles to optimise vs execution cycles saved to consider).
>
> > On 16 Sep 2018, at 6:29 pm, John Found <[hidden email]> wrote:
> >
> > Is there some relation between the indexes used in the query, the GROUP BY fields used
> > and the order of the result rows, when no "ORDER BY" clause is used?
> >
> > I am asking, because I noticed, that on some queries, when I am using "ORDER BY" the query always
> > use temporary b-tree for ordering, but by including the needed fields in the "GROUP BY" clause
> > and removing the ORDER BY clause, the query returns the rows in the proper order without temp b-tree.
> >
> > So, is it safe to use this implicit ordering, or this behavior can be changed in the future versions of SQLite?
> >
> > Here is an example:
> >
> > create table A (
> >  id integer primary key autoincrement,
> >  o1 integer,
> >  o2 integer
> > );
> >
> > create table B (
> >  Aid integer references A(id),
> >  data text
> > );
> >
> > create index idxA on A(o1 desc, o2 desc);
> >
> > insert into A(o1, o2) values (1, 100), (2, 50), (3, 200), (5, 300);
> > insert into B(Aid, data) values (1, "b"), (1, "a"), (2, "c"), (2, "d"), (2, "e"), (3, "f"), (3, "g");
> >
> > -- Always uses temp b-tree for order by
> > select
> >  group_concat(B.data), o1, o2
> > from
> >  A
> > left join
> >  B on A.id = B.Aid
> > group by
> >  A.id
> > order by
> >  A.o1 desc, A.o2 desc;
> >
> > explain query plan:
> > id    parent    notused    detail
> > 8    0    0    SCAN TABLE A
> > 19    0    0    SEARCH TABLE B USING AUTOMATIC COVERING INDEX (Aid=?)
> > 58    0    0    USE TEMP B-TREE FOR ORDER BY
> >
> >
> > -- This one returns the rows in the needed order without ORDER BY
> > select
> >  group_concat(B.data), o1, o2
> > from
> >  A indexed by idxA
> > left join B on A.id = B.Aid
> > group by A.id, A.o1, A.o2;
> >
> > explain query plan:
> > id    parent    notused    detail
> > 7    0    0    SCAN TABLE A USING COVERING INDEX idxA
> > 18    0    0    SEARCH TABLE B USING AUTOMATIC COVERING INDEX (Aid=?)
> >
> >
> > -- But if I add ORDER BY it still begins to use temp b-tree
> > -- regardless that it does not change the order.
> > select
> >  group_concat(B.data), o1, o2
> > from
> >  A indexed by idxA
> > left join B on A.id = B.Aid
> > group by A.id, A.o1, A.o2
> > order by A.o1 desc, A.o2 desc;
> >
> > explain query plan:
> > 8    0    0    SCAN TABLE A
> > 19    0    0    SEARCH TABLE B USING AUTOMATIC COVERING INDEX (Aid=?)
> > 60    0    0    USE TEMP B-TREE FOR ORDER BY
> >
> >
> > All the above queries, returns the same result rows in the same order:
> >
> > group_concat(B.data)  o1   o2
> > NULL                   5   300
> > f,g                    3   200
> > c,d,e                  2   50
> > a,b                    1   100
> >
> >
> >
> >        
> > --
> > John Found <[hidden email]>


--
John Found <[hidden email]>
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: The "natural" order of the query results.

Simon Slavin-3
In reply to this post by John Found
On 16 Sep 2018, at 9:29am, John Found <[hidden email]> wrote:

> Is there some relation between the indexes used in the query, the GROUP BY fields used
> and the order of the result rows, when no "ORDER BY" clause is used?

When you ask for GROUP BY, SQLite internally does the same sort of thing as it does when you ask for ORDER BY.  And if you have a useful index then it will use that index.

> [...]. So, is it safe to use this implicit ordering, or this behavior can be changed in the future versions of SQLite?

It is not safe.  There is nothing in the documentation that says that groups will be returned in COLLATE order.  As you suggest, a future version of SQLite may choose not to do so.

Simon.
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: The "natural" order of the query results.

John Found
On Sun, 16 Sep 2018 13:30:55 +0100
Simon Slavin <[hidden email]> wrote:

> On 16 Sep 2018, at 9:29am, John Found <[hidden email]> wrote:
>
> > Is there some relation between the indexes used in the query, the GROUP BY fields used
> > and the order of the result rows, when no "ORDER BY" clause is used?
>
> When you ask for GROUP BY, SQLite internally does the same sort of thing as it does when you ask for ORDER BY.  And if you have a useful index then it will use that index.
>
> > [...]. So, is it safe to use this implicit ordering, or this behavior can be changed in the future versions of SQLite?
>
> It is not safe.  There is nothing in the documentation that says that groups will be returned in COLLATE order.  As you suggest, a future version of SQLite may choose not to do so.

Is it means that in every query that uses GROUP BY and ORDER BY simultaneously, one of the operations will always be provided by using temporary b-tree?

>
> Simon.
> _______________________________________________
> sqlite-users mailing list
> [hidden email]
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users


--
John Found <[hidden email]>
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: The "natural" order of the query results.

Richard Hipp-3
On 9/16/18, John Found <[hidden email]> wrote:
>
> Is it means that in every query that uses GROUP BY and ORDER BY
> simultaneously, one of the operations will always be provided by using
> temporary b-tree?
>

no.

CREATE TABLE t1(a,b,c, PRIMARY KEY(a,b)) WITHOUT ROWID;
explain query plan
SELECT a, b, sum(c) FROM t1 GROUP BY a, b ORDER BY a, b;

--
D. Richard Hipp
[hidden email]
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: The "natural" order of the query results.

John Found
I know that the answer is "no", but in the below example, group by clause
is meaningless, because (a,b) is primary key and there is no two rows with equal
(a, b) that to be grouped.

Please, comment my example from the first email in the thread.
Is it possible to make this query to group by and order by simultaneously
without using temp b-tree?

On Sun, 16 Sep 2018 10:59:31 -0400
Richard Hipp <[hidden email]> wrote:

> On 9/16/18, John Found <[hidden email]> wrote:
> >
> > Is it means that in every query that uses GROUP BY and ORDER BY
> > simultaneously, one of the operations will always be provided by using
> > temporary b-tree?
> >
>
> no.
>
> CREATE TABLE t1(a,b,c, PRIMARY KEY(a,b)) WITHOUT ROWID;
> explain query plan
> SELECT a, b, sum(c) FROM t1 GROUP BY a, b ORDER BY a, b;
>
> --
> D. Richard Hipp
> [hidden email]
> _______________________________________________
> sqlite-users mailing list
> [hidden email]
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users


--
John Found <[hidden email]>
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: The "natural" order of the query results.

John Found
In reply to this post by Richard Hipp-3
On Sun, 16 Sep 2018 10:59:31 -0400
Richard Hipp <[hidden email]> wrote:

> On 9/16/18, John Found <[hidden email]> wrote:
> >
> > Is it means that in every query that uses GROUP BY and ORDER BY
> > simultaneously, one of the operations will always be provided by using
> > temporary b-tree?
> >
>
> no.
>
> CREATE TABLE t1(a,b,c, PRIMARY KEY(a,b)) WITHOUT ROWID;
> explain query plan
> SELECT a, b, sum(c) FROM t1 GROUP BY a, b ORDER BY a, b;
>
> --
> D. Richard Hipp
> [hidden email]

BTW, using your example and modifying it in order the GROUP BY to be needed
I got some not obvious results:

drop table t1;
CREATE TABLE t1(a,b,c);
insert into t1 values (1, 2, 3), (1,2,1), (1, 2, 2), (2, 2, 1), (2, 1, 2);
create index idxT1 on t1(a desc,b desc);

-- This one orders ascending by using descending index. Great.
explain query plan
SELECT a, b, sum(c) FROM t1 GROUP BY a, b ORDER BY a, b;

id parent notused detail
8 0 0 SCAN TABLE t1 USING INDEX idxT1

SELECT a, b, sum(c) FROM t1 GROUP BY a, b ORDER BY a, b;

a b sum(c)
1 2 6
2 1 2
2 2 1


-- The following can't order descending by using descending index... :?
explain query plan
SELECT a, b, sum(c) FROM t1 GROUP BY a, b ORDER BY a desc, b desc;

id parent notused detail
8 0 0 SCAN TABLE t1 USING INDEX idxT1
41 0 0 USE TEMP B-TREE FOR ORDER BY

SELECT a, b, sum(c) FROM t1 GROUP BY a, b ORDER BY a desc, b desc;

a b sum(c)
2 2 1
2 1 2
1 2 6


-- But this one orders properly descending, by using descending index, but without ORDER BY clause.
explain query plan
SELECT a, b, sum(c) FROM t1 GROUP BY a, b;

id parent notused detail
7 0 0 SCAN TABLE t1 USING INDEX idxT1

SELECT a, b, sum(c) FROM t1 GROUP BY a, b;

a b sum(c)
2 2 1
2 1 2
1 2 6


--
John Found <[hidden email]>
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: The "natural" order of the query results.

Darren Duncan
In reply to this post by John Found
On 2018-09-16 1:29 AM, John Found wrote:
> Is there some relation between the indexes used in the query, the GROUP BY fields used
> and the order of the result rows, when no "ORDER BY" clause is used?
>
> I am asking, because I noticed, that on some queries, when I am using "ORDER BY" the query always
> use temporary b-tree for ordering, but by including the needed fields in the "GROUP BY" clause
> and removing the ORDER BY clause, the query returns the rows in the proper order without temp b-tree.
>
> So, is it safe to use this implicit ordering, or this behavior can be changed in the future versions of SQLite?

The answer to your question, is no, never.  Using ORDER BY is the *only* safe
way to guarantee results come in a particular order.  When you don't use ORDER
BY you are explicitly saying that the order of result rows isn't significant and
so the DBMS can use whatever order it feels like at any time without any prior
notice of changes. -- Darren Duncan
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: [EXTERNAL] The "natural" order of the query results.

Hick Gunter
In reply to this post by John Found
SQLite handles GROUP BY and ORDER BY in basically the same way. If there is an apropirate index, then it will use this index and the rows will be returned in visitation order of this index. If, for exmaple by adding a new index or even an upgrade of the Query Planner, a different execution plan is constructed, then the order of the returned rows will "change".

Please note that GROUP BY id,o1,o2 and ORDER BY o1,o2 are DIFFERENT expressions and require reordering, which is the reason for an additional BTree step.

If you need the rows to be returned in a specific order, then you must say so explicitly with an ORDER BY clause; otherwise, SQLite is free to return rows in any order that happens to be convenient for the DB Engine. Relying on the "natural" order is a common way of creating code that breaks unexpectedly.

Similarly, if you need the result columns to have certain names, you must provide these via AS clauses.

-----Ursprüngliche Nachricht-----
Von: sqlite-users [mailto:[hidden email]] Im Auftrag von John Found
Gesendet: Sonntag, 16. September 2018 10:30
An: [hidden email]
Betreff: [EXTERNAL] [sqlite] The "natural" order of the query results.

Is there some relation between the indexes used in the query, the GROUP BY fields used and the order of the result rows, when no "ORDER BY" clause is used?

I am asking, because I noticed, that on some queries, when I am using "ORDER BY" the query always use temporary b-tree for ordering, but by including the needed fields in the "GROUP BY" clause and removing the ORDER BY clause, the query returns the rows in the proper order without temp b-tree.

So, is it safe to use this implicit ordering, or this behavior can be changed in the future versions of SQLite?

Here is an example:

create table A (
  id integer primary key autoincrement,
  o1 integer,
  o2 integer
);

create table B (
  Aid integer references A(id),
  data text
);

create index idxA on A(o1 desc, o2 desc);

insert into A(o1, o2) values (1, 100), (2, 50), (3, 200), (5, 300); insert into B(Aid, data) values (1, "b"), (1, "a"), (2, "c"), (2, "d"), (2, "e"), (3, "f"), (3, "g");

-- Always uses temp b-tree for order by
select
  group_concat(B.data), o1, o2
from
  A
left join
  B on A.id = B.Aid
group by
  A.id
order by
  A.o1 desc, A.o2 desc;

explain query plan:
id      parent  notused detail
8       0       0       SCAN TABLE A
19      0       0       SEARCH TABLE B USING AUTOMATIC COVERING INDEX (Aid=?)
58      0       0       USE TEMP B-TREE FOR ORDER BY


-- This one returns the rows in the needed order without ORDER BY select
  group_concat(B.data), o1, o2
from
  A indexed by idxA
left join B on A.id = B.Aid
group by A.id, A.o1, A.o2;

explain query plan:
id      parent  notused detail
7       0       0       SCAN TABLE A USING COVERING INDEX idxA
18      0       0       SEARCH TABLE B USING AUTOMATIC COVERING INDEX (Aid=?)


-- But if I add ORDER BY it still begins to use temp b-tree
-- regardless that it does not change the order.
select
  group_concat(B.data), o1, o2
from
  A indexed by idxA
left join B on A.id = B.Aid
group by A.id, A.o1, A.o2
order by A.o1 desc, A.o2 desc;

explain query plan:
8       0       0       SCAN TABLE A
19      0       0       SEARCH TABLE B USING AUTOMATIC COVERING INDEX (Aid=?)
60      0       0       USE TEMP B-TREE FOR ORDER BY


All the above queries, returns the same result rows in the same order:

group_concat(B.data)  o1   o2
NULL                   5   300
f,g                    3   200
c,d,e                  2   50
a,b                    1   100




--
John Found <[hidden email]>
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users


___________________________________________
 Gunter Hick | Software Engineer | Scientific Games International GmbH | Klitschgasse 2-4, A-1130 Vienna | FN 157284 a, HG Wien, DVR: 0430013 | (O) +43 1 80100 - 0

May be privileged. May be confidential. Please delete if not the addressee.
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: [EXTERNAL] The "natural" order of the query results.

John Found
On Mon, 17 Sep 2018 06:02:37 +0000
Hick Gunter <[hidden email]> wrote:

> SQLite handles GROUP BY and ORDER BY in basically the same way. If there is an apropirate index, then it will use this index and the rows will be returned in visitation order of this index. If, for exmaple by adding a new index or even an upgrade of the Query Planner, a different execution plan is constructed, then the order of the returned rows will "change".

Yes, of course, but you forgot about INDEXED BY clause. It will force using particular index. So, the query planner will always use exactly this index, regardless of how optimal it is and
as long as GROUP BY and ORDER BY are working the same way, this gives some guarantee for the ordering without ORDER BY clause. Or my logic is wrong?

Anyway, read my second response to the DRHs example. IMHO, there is some kind of misbehavior with the ORDER BY planning when ordering descending.

>
> Please note that GROUP BY id,o1,o2 and ORDER BY o1,o2 are DIFFERENT expressions and require reordering, which is the reason for an additional BTree step.
>
> If you need the rows to be returned in a specific order, then you must say so explicitly with an ORDER BY clause; otherwise, SQLite is free to return rows in any order that happens to be convenient for the DB Engine. Relying on the "natural" order is a common way of creating code that breaks unexpectedly.
>
> Similarly, if you need the result columns to have certain names, you must provide these via AS clauses.
>
> -----Ursprüngliche Nachricht-----
> Von: sqlite-users [mailto:[hidden email]] Im Auftrag von John Found
> Gesendet: Sonntag, 16. September 2018 10:30
> An: [hidden email]
> Betreff: [EXTERNAL] [sqlite] The "natural" order of the query results.
>
> Is there some relation between the indexes used in the query, the GROUP BY fields used and the order of the result rows, when no "ORDER BY" clause is used?
>
> I am asking, because I noticed, that on some queries, when I am using "ORDER BY" the query always use temporary b-tree for ordering, but by including the needed fields in the "GROUP BY" clause and removing the ORDER BY clause, the query returns the rows in the proper order without temp b-tree.
>
> So, is it safe to use this implicit ordering, or this behavior can be changed in the future versions of SQLite?
>
> Here is an example:
>
> create table A (
>   id integer primary key autoincrement,
>   o1 integer,
>   o2 integer
> );
>
> create table B (
>   Aid integer references A(id),
>   data text
> );
>
> create index idxA on A(o1 desc, o2 desc);
>
> insert into A(o1, o2) values (1, 100), (2, 50), (3, 200), (5, 300); insert into B(Aid, data) values (1, "b"), (1, "a"), (2, "c"), (2, "d"), (2, "e"), (3, "f"), (3, "g");
>
> -- Always uses temp b-tree for order by
> select
>   group_concat(B.data), o1, o2
> from
>   A
> left join
>   B on A.id = B.Aid
> group by
>   A.id
> order by
>   A.o1 desc, A.o2 desc;
>
> explain query plan:
> id      parent  notused detail
> 8       0       0       SCAN TABLE A
> 19      0       0       SEARCH TABLE B USING AUTOMATIC COVERING INDEX (Aid=?)
> 58      0       0       USE TEMP B-TREE FOR ORDER BY
>
>
> -- This one returns the rows in the needed order without ORDER BY select
>   group_concat(B.data), o1, o2
> from
>   A indexed by idxA
> left join B on A.id = B.Aid
> group by A.id, A.o1, A.o2;
>
> explain query plan:
> id      parent  notused detail
> 7       0       0       SCAN TABLE A USING COVERING INDEX idxA
> 18      0       0       SEARCH TABLE B USING AUTOMATIC COVERING INDEX (Aid=?)
>
>
> -- But if I add ORDER BY it still begins to use temp b-tree
> -- regardless that it does not change the order.
> select
>   group_concat(B.data), o1, o2
> from
>   A indexed by idxA
> left join B on A.id = B.Aid
> group by A.id, A.o1, A.o2
> order by A.o1 desc, A.o2 desc;
>
> explain query plan:
> 8       0       0       SCAN TABLE A
> 19      0       0       SEARCH TABLE B USING AUTOMATIC COVERING INDEX (Aid=?)
> 60      0       0       USE TEMP B-TREE FOR ORDER BY
>
>
> All the above queries, returns the same result rows in the same order:
>
> group_concat(B.data)  o1   o2
> NULL                   5   300
> f,g                    3   200
> c,d,e                  2   50
> a,b                    1   100
>
>
>
>
> --
> John Found <[hidden email]>
> _______________________________________________
> sqlite-users mailing list
> [hidden email]
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
>
>
> ___________________________________________
>  Gunter Hick | Software Engineer | Scientific Games International GmbH | Klitschgasse 2-4, A-1130 Vienna | FN 157284 a, HG Wien, DVR: 0430013 | (O) +43 1 80100 - 0
>
> May be privileged. May be confidential. Please delete if not the addressee.
> _______________________________________________
> sqlite-users mailing list
> [hidden email]
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users


--
John Found <[hidden email]>
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: [EXTERNAL] The "natural" order of the query results.

Simon Slavin-3
On 17 Sep 2018, at 7:19am, John Found <[hidden email]> wrote:

> Yes, of course, but you forgot about INDEXED BY clause. It will force using particular index. So, the query planner will always use exactly this index, regardless of how optimal it is and
> as long as GROUP BY and ORDER BY are working the same way, this gives some guarantee for the ordering without ORDER BY clause.

No.  Just because it works now doesn't mean it will continue to work that way in the future, unless the documentation says so.

Simon.
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: [EXTERNAL] The "natural" order of the query results.

Graham Holden
In reply to this post by John Found
In particular, there's a not implausible optimisation opportunity that could alter things...
In the general case, the execution of "GROUP BY a, b" will "naturally" involve a sort on "a, b" to bring all the "to be grouped" entries together. In the OP's case, there's a primary key on "a, b" so there can only be one entry per group. As I understand it, it would therefore be valid to just scan the table and emit the "groups" (of size one) in whatever order they happen to be stored.
Graham.
Sent from my Samsung Galaxy S7 - powered by Three
-------- Original message --------From: Simon Slavin <[hidden email]> Date: 17/09/2018  09:09  (GMT+00:00) To: SQLite mailing list <[hidden email]> Subject: Re: [sqlite] [EXTERNAL]  The "natural" order of the query results.
On 17 Sep 2018, at 7:19am, John Found <[hidden email]> wrote:

> Yes, of course, but you forgot about INDEXED BY clause. It will force using particular index. So, the query planner will always use exactly this index, regardless of how optimal it is and
> as long as GROUP BY and ORDER BY are working the same way, this gives some guarantee for the ordering without ORDER BY clause.

No.  Just because it works now doesn't mean it will continue to work that way in the future, unless the documentation says so.

Simon.
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: [EXTERNAL] The "natural" order of the query results.

Richard Damon
In reply to this post by John Found
On 9/17/18 2:19 AM, John Found wrote:
> On Mon, 17 Sep 2018 06:02:37 +0000
> Hick Gunter <[hidden email]> wrote:
>
>> SQLite handles GROUP BY and ORDER BY in basically the same way. If there is an apropirate index, then it will use this index and the rows will be returned in visitation order of this index. If, for exmaple by adding a new index or even an upgrade of the Query Planner, a different execution plan is constructed, then the order of the returned rows will "change".
> Yes, of course, but you forgot about INDEXED BY clause. It will force using particular index. So, the query planner will always use exactly this index, regardless of how optimal it is and
> as long as GROUP BY and ORDER BY are working the same way, this gives some guarantee for the ordering without ORDER BY clause. Or my logic is wrong?

I think the issue is that INDEXED BY forces the use of that index, but
does NOT imply a final result order, that still requires the use of an
ORDER BY clause. Please note the SQLite documentation for the INDEX BY
clause description of the purpose of the INDEX BY clause, to detect
unintended changes in Schema, not performance tuning, and is expected to
be added at the very end of development (and by implication, will have
no noticeable impact on the results).

--
Richard Damon

_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users