Determine sort order of query

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

Determine sort order of query

curmudgeon
Suppose you’re given an sql select statement that doesn’t contain an order by clause. Is there any way of accurately determining the order it will be sorted in. Trivial example

‘select * from Tbl’ will be ordered by RowID or some covering index if one exists.

I know the EXPLAIN (maybe even EXPLAIN QUERY PLAN) give hints but I’ve not used these enough to be sure of them.

e.g. I think the EXPLAIN ‘order’ column corresponds to the order the ‘from’ tables are accessed in. Would that order along with the index mentioned (none mentioned => RowID for with rowID tables) give the order?

If the bottom row in the EXPLAIN is ‘USE TEMP B-TREE FOR ORDER BY’ does that definitely mean there’s no indexes used?

If the bottom row in the EXPLAIN is ‘USE TEMP B-TREE FOR RIGHT PART OF ORDER BY’ does that imply the sort isn’t unique?

I know the output of EXPLAIN isn’t guaranteed and shouldn’t really be used so is there an alternative?

Tom.

_______________________________________________
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: Determine sort order of query

Richard Hipp-3
On 3/24/18, x <[hidden email]> wrote:
> Suppose you’re given an sql select statement that doesn’t contain an order
> by clause. Is there any way of accurately determining the order it will be
> sorted in.

No.  The database engine is free to return the rows in whatever order
it thinks will be most efficient.  This can change from one run to the
next, such that you can run the same query twice and get the rows in a
different order each time.  SQLite will normally return rows in the
same order unless there is an intervening ANALYZE command, but on
other SQL database engines a row order shift can happen at any time.
You can expect to sometimes see rows  in different orders if you run
the same query on two different versions of SQLite.

--
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: Determine sort order of query

curmudgeon
Thanks for the reply Richard. I don’t suppose it matters to me that it may change from one day to the next or one connection to another as long as I can determine the order it will be returned in milliseconds before the first sqlite3_step.





________________________________
From: sqlite-users <[hidden email]> on behalf of Richard Hipp <[hidden email]>
Sent: Saturday, March 24, 2018 5:38:53 PM
To: SQLite mailing list
Subject: Re: [sqlite] Determine sort order of query

On 3/24/18, x <[hidden email]> wrote:
> Suppose you’re given an sql select statement that doesn’t contain an order
> by clause. Is there any way of accurately determining the order it will be
> sorted in.

No.  The database engine is free to return the rows in whatever order
it thinks will be most efficient.  This can change from one run to the
next, such that you can run the same query twice and get the rows in a
different order each time.  SQLite will normally return rows in the
same order unless there is an intervening ANALYZE command, but on
other SQL database engines a row order shift can happen at any time.
You can expect to sometimes see rows  in different orders if you run
the same query on two different versions of SQLite.

--
D. Richard Hipp
[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: Determine sort order of query

curmudgeon
In reply to this post by Richard Hipp-3
I should have pointed out that I intended to append the ‘calculated’ order by to the sql string in any case.



________________________________
From: sqlite-users <[hidden email]> on behalf of Richard Hipp <[hidden email]>
Sent: Saturday, March 24, 2018 5:38:53 PM
To: SQLite mailing list
Subject: Re: [sqlite] Determine sort order of query

On 3/24/18, x <[hidden email]> wrote:
> Suppose you’re given an sql select statement that doesn’t contain an order
> by clause. Is there any way of accurately determining the order it will be
> sorted in.

No.  The database engine is free to return the rows in whatever order
it thinks will be most efficient.  This can change from one run to the
next, such that you can run the same query twice and get the rows in a
different order each time.  SQLite will normally return rows in the
same order unless there is an intervening ANALYZE command, but on
other SQL database engines a row order shift can happen at any time.
You can expect to sometimes see rows  in different orders if you run
the same query on two different versions of SQLite.

--
D. Richard Hipp
[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: Determine sort order of query

Simon Slavin-3
In reply to this post by curmudgeon
On 24 Mar 2018, at 6:00pm, x <[hidden email]> wrote:

> Thanks for the reply Richard. I don’t suppose it matters to me that it may change from one day to the next or one connection to another as long as I can determine the order it will be returned in milliseconds before the first sqlite3_step.

Can't be done without putting enough analysis in your program to completely understand the output of EXPLAIN QUERY PLAN.  And the output of that statement does not have a fixed form: lines can go up or down, ANALYZE can change what happens, whether a table is empty or has data can change what happens.

If you want to be able to predict the order of results from a SELECT, set it using ORDER BY.

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: Determine sort order of query

Richard Hipp-3
In reply to this post by curmudgeon
On 3/24/18, x <[hidden email]> wrote:
> Thanks for the reply Richard. I don’t suppose it matters to me that it may
> change from one day to the next or one connection to another as long as I
> can determine the order it will be returned in milliseconds before the first
> sqlite3_step.

The only practical way to determine the order is to run it and see.
--
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: Determine sort order of query

curmudgeon
In reply to this post by Simon Slavin-3
Simon, assume the sql will be input by the user. I suppose I could give them an error message but it would be good to just add the ‘calculated’ order by to the sql and display that.



________________________________
From: sqlite-users <[hidden email]> on behalf of Simon Slavin <[hidden email]>
Sent: Saturday, March 24, 2018 6:04:38 PM
To: SQLite mailing list
Subject: Re: [sqlite] Determine sort order of query

On 24 Mar 2018, at 6:00pm, x <[hidden email]> wrote:

> Thanks for the reply Richard. I don’t suppose it matters to me that it may change from one day to the next or one connection to another as long as I can determine the order it will be returned in milliseconds before the first sqlite3_step.

Can't be done without putting enough analysis in your program to completely understand the output of EXPLAIN QUERY PLAN.  And the output of that statement does not have a fixed form: lines can go up or down, ANALYZE can change what happens, whether a table is empty or has data can change what happens.

If you want to be able to predict the order of results from a SELECT, set it using ORDER BY.

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: Determine sort order of query

curmudgeon
In reply to this post by Richard Hipp-3
sqlite> create table t1(a, b text);
sqlite> create table t2(c, d text);
sqlite> create index b on t1(b);
sqlite> create index d on t2(d);
sqlite> explain query plan select * from t1,t2 order by b, d, t1.RowID, t2.RowID;
0|0|0|SCAN TABLE t1 USING INDEX b
0|1|1|SCAN TABLE t2
0|0|0|USE TEMP B-TREE FOR RIGHT PART OF ORDER BY

Is there a reason it uses TEMP B-TREE rather than index t2(d) ?

_______________________________________________
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: Determine sort order of query

Keith Medcalf

That index will not result in the ordering you asked for.


---
The fact that there's a Highway to Hell but only a Stairway to Heaven says a lot about anticipated traffic volume.


>-----Original Message-----
>From: sqlite-users [mailto:sqlite-users-
>[hidden email]] On Behalf Of x
>Sent: Saturday, 24 March, 2018 13:08
>To: SQLite mailing list
>Subject: Re: [sqlite] Determine sort order of query
>
>sqlite> create table t1(a, b text);
>sqlite> create table t2(c, d text);
>sqlite> create index b on t1(b);
>sqlite> create index d on t2(d);
>sqlite> explain query plan select * from t1,t2 order by b, d,
>t1.RowID, t2.RowID;
>0|0|0|SCAN TABLE t1 USING INDEX b
>0|1|1|SCAN TABLE t2
>0|0|0|USE TEMP B-TREE FOR RIGHT PART OF ORDER BY
>
>Is there a reason it uses TEMP B-TREE rather than index t2(d) ?
>
>_______________________________________________
>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: Determine sort order of query

Keith Medcalf
In reply to this post by curmudgeon

Hint:  Index entries must be unique.  They are made unique by having the rowid in the index (how else would you find the row from the index)?

if you asked for the data in an order that can be produced by an index without a sort, then you will get the output without a sort.

select * from t1, t2 order by b, t1.rowid, d, t2.rowid;

Index b can be used to get the initial column sorted, but a separate sorter is required to get the order you asked for, for each subgroup (next bunch of columns).


---
The fact that there's a Highway to Hell but only a Stairway to Heaven says a lot about anticipated traffic volume.


>-----Original Message-----
>From: sqlite-users [mailto:sqlite-users-
>[hidden email]] On Behalf Of x
>Sent: Saturday, 24 March, 2018 13:08
>To: SQLite mailing list
>Subject: Re: [sqlite] Determine sort order of query
>
>sqlite> create table t1(a, b text);
>sqlite> create table t2(c, d text);
>sqlite> create index b on t1(b);
>sqlite> create index d on t2(d);
>sqlite> explain query plan select * from t1,t2 order by b, d,
>t1.RowID, t2.RowID;
>0|0|0|SCAN TABLE t1 USING INDEX b
>0|1|1|SCAN TABLE t2
>0|0|0|USE TEMP B-TREE FOR RIGHT PART OF ORDER BY
>
>Is there a reason it uses TEMP B-TREE rather than index t2(d) ?
>
>_______________________________________________
>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: Determine sort order of query

curmudgeon
Nice one Keith. Thanks.

sqlite> create table t1 (a, b text, c);
sqlite> create table t2 (d, e text, f);
sqlite> create index b on t1(b);
sqlite> create index e on t2(e);
sqlite> explain query plan select * from t1,t2 order by b, t1.RowID, e, t2.RowID;
0|0|0|SCAN TABLE t1 USING INDEX b
0|1|1|SCAN TABLE t2 USING INDEX e

although I still don’t really understand why a TEMP B-TREE would be quicker than using index e for this

sqlite> explain query plan select * from t1,t2 order by b, e;
0|0|0|SCAN TABLE t1 USING INDEX b
0|1|1|SCAN TABLE t2
0|0|0|USE TEMP B-TREE FOR RIGHT PART OF ORDER BY

After all, it’s attaching an entire table to each row in t1 in an order that’s already been worked out.

From: Keith Medcalf<mailto:[hidden email]>
Sent: 24 March 2018 20:34
To: SQLite mailing list<mailto:[hidden email]>
Subject: Re: [sqlite] Determine sort order of query


Hint:  Index entries must be unique.  They are made unique by having the rowid in the index (how else would you find the row from the index)?

if you asked for the data in an order that can be produced by an index without a sort, then you will get the output without a sort.

select * from t1, t2 order by b, t1.rowid, d, t2.rowid;

Index b can be used to get the initial column sorted, but a separate sorter is required to get the order you asked for, for each subgroup (next bunch of columns).


---
The fact that there's a Highway to Hell but only a Stairway to Heaven says a lot about anticipated traffic volume.


>-----Original Message-----
>From: sqlite-users [mailto:sqlite-users-
>[hidden email]] On Behalf Of x
>Sent: Saturday, 24 March, 2018 13:08
>To: SQLite mailing list
>Subject: Re: [sqlite] Determine sort order of query
>
>sqlite> create table t1(a, b text);
>sqlite> create table t2(c, d text);
>sqlite> create index b on t1(b);
>sqlite> create index d on t2(d);
>sqlite> explain query plan select * from t1,t2 order by b, d,
>t1.RowID, t2.RowID;
>0|0|0|SCAN TABLE t1 USING INDEX b
>0|1|1|SCAN TABLE t2
>0|0|0|USE TEMP B-TREE FOR RIGHT PART OF ORDER BY
>
>Is there a reason it uses TEMP B-TREE rather than index t2(d) ?
>
>_______________________________________________
>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

_______________________________________________
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: Determine sort order of query

Keith Medcalf

It isn't.  In fact if you do a

SELECT b, e FROM t1, t2 ORDER BY b, e;

you get both the covering indexes being used and a temp sorter (although the temp sorter does nothing).  Perhaps an opportunity for future optimization?

---
The fact that there's a Highway to Hell but only a Stairway to Heaven says a lot about anticipated traffic volume.

>-----Original Message-----
>From: sqlite-users [mailto:sqlite-users-
>[hidden email]] On Behalf Of x
>Sent: Sunday, 25 March, 2018 02:40
>To: SQLite mailing list
>Subject: Re: [sqlite] Determine sort order of query
>
>Nice one Keith. Thanks.
>
>sqlite> create table t1 (a, b text, c);
>sqlite> create table t2 (d, e text, f);
>sqlite> create index b on t1(b);
>sqlite> create index e on t2(e);
>sqlite> explain query plan select * from t1,t2 order by b, t1.RowID,
>e, t2.RowID;
>0|0|0|SCAN TABLE t1 USING INDEX b
>0|1|1|SCAN TABLE t2 USING INDEX e
>
>although I still don’t really understand why a TEMP B-TREE would be
>quicker than using index e for this
>
>sqlite> explain query plan select * from t1,t2 order by b, e;
>0|0|0|SCAN TABLE t1 USING INDEX b
>0|1|1|SCAN TABLE t2
>0|0|0|USE TEMP B-TREE FOR RIGHT PART OF ORDER BY
>
>After all, it’s attaching an entire table to each row in t1 in an
>order that’s already been worked out.
>
>From: Keith Medcalf<mailto:[hidden email]>
>Sent: 24 March 2018 20:34
>To: SQLite mailing list<mailto:[hidden email]>
>Subject: Re: [sqlite] Determine sort order of query
>
>
>Hint:  Index entries must be unique.  They are made unique by having
>the rowid in the index (how else would you find the row from the
>index)?
>
>if you asked for the data in an order that can be produced by an
>index without a sort, then you will get the output without a sort.
>
>select * from t1, t2 order by b, t1.rowid, d, t2.rowid;
>
>Index b can be used to get the initial column sorted, but a separate
>sorter is required to get the order you asked for, for each subgroup
>(next bunch of columns).
>
>
>---
>The fact that there's a Highway to Hell but only a Stairway to Heaven
>says a lot about anticipated traffic volume.
>
>
>>-----Original Message-----
>>From: sqlite-users [mailto:sqlite-users-
>>[hidden email]] On Behalf Of x
>>Sent: Saturday, 24 March, 2018 13:08
>>To: SQLite mailing list
>>Subject: Re: [sqlite] Determine sort order of query
>>
>>sqlite> create table t1(a, b text);
>>sqlite> create table t2(c, d text);
>>sqlite> create index b on t1(b);
>>sqlite> create index d on t2(d);
>>sqlite> explain query plan select * from t1,t2 order by b, d,
>>t1.RowID, t2.RowID;
>>0|0|0|SCAN TABLE t1 USING INDEX b
>>0|1|1|SCAN TABLE t2
>>0|0|0|USE TEMP B-TREE FOR RIGHT PART OF ORDER BY
>>
>>Is there a reason it uses TEMP B-TREE rather than index t2(d) ?
>>
>>_______________________________________________
>>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
>
>_______________________________________________
>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