Group-by and order-by-desc does not work as expected

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

Group-by and order-by-desc does not work as expected

Fredrik Larsen
I have a aggregate query that works as expected when the ordering is
ascending, but uses a TMP B-TREE when changing order to descending, see
stackoverflow link below.

Is there something I'm missing? I would expect same performance when
ordering both directions.

Link:
https://stackoverflow.com/questions/58009898/sqlite-group-by-with-sort-by-desc-does-not-work-as-expected


Fredrik Larsen
_______________________________________________
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: Group-by and order-by-desc does not work as expected

Simon Slavin-3
On 19 Sep 2019, at 1:14pm, Fredrik Larsen <[hidden email]> wrote:

> I have a aggregate query that works as expected when the ordering is
> ascending, but uses a TMP B-TREE when changing order to descending, see stackoverflow link below.

For experimental purposes, you might take a backup copy of your database and try executing ANALYZE before the query.  Also try

PRAGMA reverse_unordered_selects = YES

before the query.
_______________________________________________
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] Group-by and order-by-desc does not work as expected

Hick Gunter
In reply to this post by Fredrik Larsen
An ORDER BY clause will omit sorting only if the visitation order exactly fulfills the clause.

A GROUP BY clause is able to avoid creating a temporary table if the visitation order exactly fulfills the clause.

If a SELECT references only fields present in an index, that (covering) index may be used instead of the table.

In your case, the SELECT references fields x and y, both of which are present in the index, so the QP uses the covering index. This also happens to be sorted by x, allowing the GROUP BY to avoid a temporary table and producing rows odered by x.

The ORDER BY x in the first query is thus already fulfilled and so no sorting is required.

The ORDER BY x DESC in the second query is thus NOT fulfilled, so a sorting step is required.

Unfortunately, trying to be clever by creating an index on (x desc, y) does not help.

-----Ursprüngliche Nachricht-----
Von: sqlite-users [mailto:[hidden email]] Im Auftrag von Fredrik Larsen
Gesendet: Donnerstag, 19. September 2019 14:14
An: [hidden email]
Betreff: [EXTERNAL] [sqlite] Group-by and order-by-desc does not work as expected

I have a aggregate query that works as expected when the ordering is ascending, but uses a TMP B-TREE when changing order to descending, see stackoverflow link below.

Is there something I'm missing? I would expect same performance when ordering both directions.

Link:
https://stackoverflow.com/questions/58009898/sqlite-group-by-with-sort-by-desc-does-not-work-as-expected


Fredrik Larsen
_______________________________________________
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] Group-by and order-by-desc does not work as expected

Fredrik Larsen
Simen; ANALYZE and PRAGMA reverse_unordered_selects = YES does not affect
results.

Hick; ORDER BY x DESC >is< covered by index. Btree-indexes allows traversal
both ways. You can see this if you remove GROUP_BY.

Got an answer on StackOverflow that seems to be from somebody that knows
internal details of sqlite. Depressing if this is true as this optimization
seems trivial compared to other optimizations implemented in sqlite and
it effectively stops my sqlite-project

Fredrik



On Thu, Sep 19, 2019 at 5:13 PM Hick Gunter <[hidden email]> wrote:

> An ORDER BY clause will omit sorting only if the visitation order exactly
> fulfills the clause.
>
> A GROUP BY clause is able to avoid creating a temporary table if the
> visitation order exactly fulfills the clause.
>
> If a SELECT references only fields present in an index, that (covering)
> index may be used instead of the table.
>
> In your case, the SELECT references fields x and y, both of which are
> present in the index, so the QP uses the covering index. This also happens
> to be sorted by x, allowing the GROUP BY to avoid a temporary table and
> producing rows odered by x.
>
> The ORDER BY x in the first query is thus already fulfilled and so no
> sorting is required.
>
> The ORDER BY x DESC in the second query is thus NOT fulfilled, so a
> sorting step is required.
>
> Unfortunately, trying to be clever by creating an index on (x desc, y)
> does not help.
>
> -----Ursprüngliche Nachricht-----
> Von: sqlite-users [mailto:[hidden email]]
> Im Auftrag von Fredrik Larsen
> Gesendet: Donnerstag, 19. September 2019 14:14
> An: [hidden email]
> Betreff: [EXTERNAL] [sqlite] Group-by and order-by-desc does not work as
> expected
>
> I have a aggregate query that works as expected when the ordering is
> ascending, but uses a TMP B-TREE when changing order to descending, see
> stackoverflow link below.
>
> Is there something I'm missing? I would expect same performance when
> ordering both directions.
>
> Link:
>
> https://stackoverflow.com/questions/58009898/sqlite-group-by-with-sort-by-desc-does-not-work-as-expected
>
>
> Fredrik Larsen
> _______________________________________________
> 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
>
_______________________________________________
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] Group-by and order-by-desc does not work as expected

Hick Gunter
-----Ursprüngliche Nachricht-----
Von: sqlite-users [mailto:[hidden email]] Im Auftrag von Fredrik Larsen
Gesendet: Donnerstag, 19. September 2019 17:29
An: SQLite mailing list <[hidden email]>
Betreff: Re: [sqlite] [EXTERNAL] Group-by and order-by-desc does not work as expected
...
Hick; ORDER BY x DESC >is< covered by index. Btree-indexes allows traversal both ways. You can see this if you remove GROUP_BY.
...

True and nothing new, but not the point.

After doing GROUP BY x over the covering index, the result rows would be returned by x ASC. There is no index on the rowset returned by the GROUP BY, as the rows only exist one at a time. Therefore, the only way to get them into ORDER BY X DESC is to sort them.

Gunter


___________________________________________
 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] Group-by and order-by-desc does not work as expected

Dominique Devienne
On Thu, Sep 19, 2019 at 6:15 PM Hick Gunter <[hidden email]> wrote:

> -----Ursprüngliche Nachricht-----
> Von: sqlite-users [mailto:[hidden email]]
> Im Auftrag von Fredrik Larsen
> Gesendet: Donnerstag, 19. September 2019 17:29
> An: SQLite mailing list <[hidden email]>
> Betreff: Re: [sqlite] [EXTERNAL] Group-by and order-by-desc does not work
> as expected
> ...
> Hick; ORDER BY x DESC >is< covered by index. Btree-indexes allows
> traversal both ways. You can see this if you remove GROUP_BY.
> ...
> True and nothing new, but not the point.
>
> After doing GROUP BY x over the covering index, the result rows would be
> returned by x ASC.

There is no index on the rowset returned by the GROUP BY, as the rows only
> exist one at a time.

Therefore, the only way to get them into ORDER BY X DESC is to sort them.
>

But who says the GROUP BY must return rows in ASCending order?

A lot of us "oldies" of this ML well know the order is arbitrary and
subject to change w/o an explicit ORDER BY.
So the GROUP BY is allowed, AFAIK, to return rows in DESCending order just
the same. And to do so efficiently
as Fredrik points out, since indexes (or indices, I never know) work
equally well in both directions. In fact, it could
return rows in arbitrary / random order too!

The query-planner does see the ORDER BY that follows the GROUP BY after
all, so it could well decide
to group in DESCending order, thus avoiding the ordering completely, like
it already does for ASCending.
This would be a great optimisation, and from 30,000ft, it does indeed seem
like a "simple" one compared
to all the advanced optimisations already implements, as Fredrik mentioned.

I might even say that it looks like a "low-hanging-fruit", if I dared :).
Dunno, perhaps GROUP BY has some
requirement an ordering, or GROUP BY impls somehow can't easily work "in
reverse", I'm no expert of the
code. I wish the experts would chime in. Too often we never hear any
rational for doing or not doing things.
This is a "users" list and there's no "dev" list. I wish more was shared
about the internal structures, impls,
etc... explaining why something is harder to implement that it sounds. Oh
well... --DD
_______________________________________________
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] Group-by and order-by-desc does not work as expected

Hick Gunter
The dialogue from the stackoverflow discussion shows this quite clearly.

"The code for looping over an index goes backwards only when needed. For implementing GROUP BY itself, going backwards is never needed, so it is never tried.

It is possible that a future SQLite version might add code to the GROUP BY implementation to check for this special case.

Make the index DESC on x. – CL. 18 hours ago

Already tried some variations of DESC in index, same result as before. Declerative descriptions are nice until you hit some annoying thing that the fancy optimizer don't handle very well. If only I had a bit more control over the query-planner – frelars 18 hours ago "

-----Ursprüngliche Nachricht-----
Von: sqlite-users [mailto:[hidden email]] Im Auftrag von Dominique Devienne
Gesendet: Freitag, 20. September 2019 11:12
An: SQLite mailing list <[hidden email]>
Betreff: Re: [sqlite] [EXTERNAL] Group-by and order-by-desc does not work as expected

On Thu, Sep 19, 2019 at 6:15 PM Hick Gunter <[hidden email]> wrote:

> -----Ursprüngliche Nachricht-----
> Von: sqlite-users
> [mailto:[hidden email]]
> Im Auftrag von Fredrik Larsen
> Gesendet: Donnerstag, 19. September 2019 17:29
> An: SQLite mailing list <[hidden email]>
> Betreff: Re: [sqlite] [EXTERNAL] Group-by and order-by-desc does not
> work as expected ...
> Hick; ORDER BY x DESC >is< covered by index. Btree-indexes allows
> traversal both ways. You can see this if you remove GROUP_BY.
> ...
> True and nothing new, but not the point.
>
> After doing GROUP BY x over the covering index, the result rows would
> be returned by x ASC.

There is no index on the rowset returned by the GROUP BY, as the rows only
> exist one at a time.

Therefore, the only way to get them into ORDER BY X DESC is to sort them.
>

But who says the GROUP BY must return rows in ASCending order?

A lot of us "oldies" of this ML well know the order is arbitrary and subject to change w/o an explicit ORDER BY.
So the GROUP BY is allowed, AFAIK, to return rows in DESCending order just the same. And to do so efficiently as Fredrik points out, since indexes (or indices, I never know) work equally well in both directions. In fact, it could return rows in arbitrary / random order too!

The query-planner does see the ORDER BY that follows the GROUP BY after all, so it could well decide to group in DESCending order, thus avoiding the ordering completely, like it already does for ASCending.
This would be a great optimisation, and from 30,000ft, it does indeed seem like a "simple" one compared to all the advanced optimisations already implements, as Fredrik mentioned.

I might even say that it looks like a "low-hanging-fruit", if I dared :).
Dunno, perhaps GROUP BY has some
requirement an ordering, or GROUP BY impls somehow can't easily work "in reverse", I'm no expert of the code. I wish the experts would chime in. Too often we never hear any rational for doing or not doing things.
This is a "users" list and there's no "dev" list. I wish more was shared about the internal structures, impls, etc... explaining why something is harder to implement that it sounds. Oh well... --DD _______________________________________________
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] Group-by and order-by-desc does not work as expected

Dominique Devienne
On Fri, Sep 20, 2019 at 12:33 PM Hick Gunter <[hidden email]> wrote:

> The dialogue from the stackoverflow discussion shows this quite clearly.
>

Shows what clearly Gunter? I'm not sure to follow. I've read the SO post,
and I don't get your point.

We can observe GROUP BY works ASCending only as of now. Why it can't work
DESCending to avoid ordering,
that's a different question. From https://www.sqlite.org/lang_select.html we
can observe that GROUP BY takes an
expr on the RHS, while ORDER BY takes an expr followed by optional COLLATE
and ASC/DESC terms.

So given an GROUP BY expr followed by an ORDER BY with the same expr,
"pushing up" the ordering's
COLLATE and ASC/DESC terms on the GROUP BY itself, eliminates the need for
the separate ordering step.
That's a clear win in runtime performance. Hopefully SQLite can do that
sooner rather than later. Thanks, --DD
_______________________________________________
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] Group-by and order-by-desc does not work as expected

R Smith-2
In reply to this post by Dominique Devienne

On 2019/09/20 11:12 AM, Dominique Devienne wrote:
>
> But who says the GROUP BY must return rows in ASCending order?
>
> A lot of us "oldies" of this ML well know the order is arbitrary and
> subject to change w/o an explicit ORDER BY.
> So the GROUP BY is allowed, AFAIK, to return rows in DESCending order just
> the same. And to do so efficiently
> as Fredrik points out, since indexes (or indices, I never know) work

I had a post on here, about 7 years ago explaining how the correct
English is indeed "Indices", same as Matrix --> Matrices and Vortex -->
Vortices etc.  It was pointed out to me (correctly) that while we hold
that use in describing the Index multiples on books or catalogues or
such, when specifically talking about a Database, and because of naming
rigidity in SQL language, it is perfectly acceptable and even preferred
to use "Indexes" as the plural for "Index". I do it too now, like all
teh cool kids. :)

An area of contention is that it hides the value of the word "Indexes"
when used as a verb - as in
"What does he do here?"
"He indexes the cards".
Or present "Mary indexes the books" similar in meaning to present
continuous "Mary is indexing the books".

But, that whole whinge is irrelevant, it's very clear from context which
"Indexes" is meant.

The American-English Merriam-Webster seems quite more ok with this than
some older English dictionaries, but it has evolved now and I do not
hear anyone anymore insisting on "Indices".  My prediction is that this
will also not remain a "Database-Only" shift. I'm already hearing people
refer to "book Indexes".


> equally well in both directions. In fact, it could
> return rows in arbitrary / random order too!
>
> The query-planner does see the ORDER BY that follows the GROUP BY after
> all, so it could well decide
> to group in DESCending order, thus avoiding the ordering completely, like
> it already does for ASCending.
> This would be a great optimisation, and from 30,000ft, it does indeed seem
> like a "simple" one compared
> to all the advanced optimisations already implements, as Fredrik mentioned.
>
> I might even say that it looks like a "low-hanging-fruit", if I dared :).

Nothing wrong with your statement or assessment. I don't know how much
effort or code addition this would require, I'm guessing quite little -
but I would like to say that this is the very obscurest of use-cases
reported, and if it does require any increase in CPU cycles for the
normal case (which is how my stuff work) - I don't want it.

To be clear, the question (paraphrasing and shortening horribly) is
something like this:

The QP will automagically use an Index on Group By -
Which is nice as a side-benefit I don't have to explicit an index, which
saves my DB some space/effort,
But now I also want to use the side-benefit for reverse ordering, and it
doesn't work
(But it works perfectly well if I DO explicitly declare the Index).

Now it seems fine to suggest the optimization, but the problem is that
this requires possibly a lot of effort and (hopefully very little)
additional code, to facilitate a shortcut upon a shortcut for a thing
that is completely QP-specific, open to change in future if a better
grouping algorithm presents itself, and not within hard documented
design methodology.
It's probably not as smart an optimization as it would seem, and the
advice should always remain: USE AND INDEX when you want stuff indexed
and ordered. Don't rely on QP quirks for your business logic or speed of
execution.

In other words, EVEN if the devs do add the quirk (perhaps it's really
trivial), I would still say don't depend on it. Some future update may
find a better way to group and change this method, and that day might
slow down your code.


Cheers,
Ryan
_______________________________________________
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] Group-by and order-by-desc does not work as expected

Fredrik Larsen
Hi Ryan

Nobody is proposing that QP should automagically add an index, I'm only
asking why the QP does not use already added index, that is specially added
for this specific case. I don't thinks this is a very "obscurest of
use-case" or to much to ask for, in fact, this is the expected behavior for
even the simplest SQL engines, and so especially sqlite.

Fredrik

On Fri, Sep 20, 2019 at 2:36 PM R Smith <[hidden email]> wrote:

>
> On 2019/09/20 11:12 AM, Dominique Devienne wrote:
> >
> > But who says the GROUP BY must return rows in ASCending order?
> >
> > A lot of us "oldies" of this ML well know the order is arbitrary and
> > subject to change w/o an explicit ORDER BY.
> > So the GROUP BY is allowed, AFAIK, to return rows in DESCending order
> just
> > the same. And to do so efficiently
> > as Fredrik points out, since indexes (or indices, I never know) work
>
> I had a post on here, about 7 years ago explaining how the correct
> English is indeed "Indices", same as Matrix --> Matrices and Vortex -->
> Vortices etc.  It was pointed out to me (correctly) that while we hold
> that use in describing the Index multiples on books or catalogues or
> such, when specifically talking about a Database, and because of naming
> rigidity in SQL language, it is perfectly acceptable and even preferred
> to use "Indexes" as the plural for "Index". I do it too now, like all
> teh cool kids. :)
>
> An area of contention is that it hides the value of the word "Indexes"
> when used as a verb - as in
> "What does he do here?"
> "He indexes the cards".
> Or present "Mary indexes the books" similar in meaning to present
> continuous "Mary is indexing the books".
>
> But, that whole whinge is irrelevant, it's very clear from context which
> "Indexes" is meant.
>
> The American-English Merriam-Webster seems quite more ok with this than
> some older English dictionaries, but it has evolved now and I do not
> hear anyone anymore insisting on "Indices".  My prediction is that this
> will also not remain a "Database-Only" shift. I'm already hearing people
> refer to "book Indexes".
>
>
> > equally well in both directions. In fact, it could
> > return rows in arbitrary / random order too!
> >
> > The query-planner does see the ORDER BY that follows the GROUP BY after
> > all, so it could well decide
> > to group in DESCending order, thus avoiding the ordering completely, like
> > it already does for ASCending.
> > This would be a great optimisation, and from 30,000ft, it does indeed
> seem
> > like a "simple" one compared
> > to all the advanced optimisations already implements, as Fredrik
> mentioned.
> >
> > I might even say that it looks like a "low-hanging-fruit", if I dared :).
>
> Nothing wrong with your statement or assessment. I don't know how much
> effort or code addition this would require, I'm guessing quite little -
> but I would like to say that this is the very obscurest of use-cases
> reported, and if it does require any increase in CPU cycles for the
> normal case (which is how my stuff work) - I don't want it.
>
> To be clear, the question (paraphrasing and shortening horribly) is
> something like this:
>
> The QP will automagically use an Index on Group By -
> Which is nice as a side-benefit I don't have to explicit an index, which
> saves my DB some space/effort,
> But now I also want to use the side-benefit for reverse ordering, and it
> doesn't work
> (But it works perfectly well if I DO explicitly declare the Index).
>
> Now it seems fine to suggest the optimization, but the problem is that
> this requires possibly a lot of effort and (hopefully very little)
> additional code, to facilitate a shortcut upon a shortcut for a thing
> that is completely QP-specific, open to change in future if a better
> grouping algorithm presents itself, and not within hard documented
> design methodology.
> It's probably not as smart an optimization as it would seem, and the
> advice should always remain: USE AND INDEX when you want stuff indexed
> and ordered. Don't rely on QP quirks for your business logic or speed of
> execution.
>
> In other words, EVEN if the devs do add the quirk (perhaps it's really
> trivial), I would still say don't depend on it. Some future update may
> find a better way to group and change this method, and that day might
> slow down your code.
>
>
> Cheers,
> Ryan
> _______________________________________________
> 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] Group-by and order-by-desc does not work as expected

R Smith-2
On 2019/09/20 2:49 PM, Fredrik Larsen wrote:
> Hi Ryan
>
> Nobody is proposing that QP should automagically add an index, I'm only
> asking why the QP does not use already added index, that is specially added
> for this specific case. I don't thinks this is a very "obscurest of
> use-case" or to much to ask for, in fact, this is the expected behavior for
> even the simplest SQL engines, and so especially sqlite.

Apologies if I was unclear, I'm not shouting at you for asking - this is
not that kind of forum, and it's a perfectly good request.

To be clear, I did not mean you are asking for it to index, I am saying
that it already (automagically) makes an index to use for itself in
service of the group-by, which is grand because it also solves the
forward ordering without the need of an explicit index.

I further tried to make the case that It only makes this index as a
temporary index that cannot/will not currently be traversed in the
reverse, which is where it falls short to your specific (yes, very
obscure) use case.

However, my point was forged more towards you not depending on the Index
it makes for anything, upon reading DD's post, but after re-reading your
post, I see the question is not so much that you expect the behaviour to
get a certain output, but that the output comes at the cost of speed
where it should not carry any speed penalty.

In this regard, let me adjust my original statement more in the
direction of ambivalence. The optimization should be implemented if
easy. The use case is obscure, but definitely valid, and more
importantly, I don't think there is another way to fix it. If, on the
other hand, it is CPU heavy in some way, or IO heavy for very large
selects, avoid it rather. I doubt more than 0.00001% of all goup-by
output is DESC ordered[1].


Cheers,
Ryan

[1] - That is a completely made up statistic (obviously) and I will
happily abide by a higher figure if claimed, but that burden of proof is
not on me. :)


_______________________________________________
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] Group-by and order-by-desc does not work as expected

Fredrik Larsen
I´m not sure why you think group_by + order_by_desc + limit N queries are
so obscure? Useful for lots of tail-statistics (number of transactions last
N hours if group_key is time-based, etc).

In my case I'm implementing a event-store using sqlite, where I need to be
able to retrieve entity data at specific revision, ordered by id to allow
top/bottom type queries.

SELECT max(rev),* FROM db WHERE rev <=? GROUP BY id ORDER BY id ? LIMIT ?;
-- Very slow if ordering happens to be DESC :(

Yes, above query depend on a quirk of sqlite (bare data?)

Fredrik


On Fri, Sep 20, 2019 at 3:50 PM R Smith <[hidden email]> wrote:

> On 2019/09/20 2:49 PM, Fredrik Larsen wrote:
> > Hi Ryan
> >
> > Nobody is proposing that QP should automagically add an index, I'm only
> > asking why the QP does not use already added index, that is specially
> added
> > for this specific case. I don't thinks this is a very "obscurest of
> > use-case" or to much to ask for, in fact, this is the expected behavior
> for
> > even the simplest SQL engines, and so especially sqlite.
>
> Apologies if I was unclear, I'm not shouting at you for asking - this is
> not that kind of forum, and it's a perfectly good request.
>
> To be clear, I did not mean you are asking for it to index, I am saying
> that it already (automagically) makes an index to use for itself in
> service of the group-by, which is grand because it also solves the
> forward ordering without the need of an explicit index.
>
> I further tried to make the case that It only makes this index as a
> temporary index that cannot/will not currently be traversed in the
> reverse, which is where it falls short to your specific (yes, very
> obscure) use case.
>
> However, my point was forged more towards you not depending on the Index
> it makes for anything, upon reading DD's post, but after re-reading your
> post, I see the question is not so much that you expect the behaviour to
> get a certain output, but that the output comes at the cost of speed
> where it should not carry any speed penalty.
>
> In this regard, let me adjust my original statement more in the
> direction of ambivalence. The optimization should be implemented if
> easy. The use case is obscure, but definitely valid, and more
> importantly, I don't think there is another way to fix it. If, on the
> other hand, it is CPU heavy in some way, or IO heavy for very large
> selects, avoid it rather. I doubt more than 0.00001% of all goup-by
> output is DESC ordered[1].
>
>
> Cheers,
> Ryan
>
> [1] - That is a completely made up statistic (obviously) and I will
> happily abide by a higher figure if claimed, but that burden of proof is
> not on me. :)
>
>
> _______________________________________________
> 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] Group-by and order-by-desc does not work as expected

Keith Medcalf
In reply to this post by Dominique Devienne
>We can observe GROUP BY works ASCending only as of now. Why it can't work
>DESCending to avoid ordering, that's a different question.
>From https://www.sqlite.org/lang_select.html we can observe that
>GROUP BY takes an expr on the RHS, while ORDER BY takes an expr
>followed by optional COLLATE and ASC/DESC terms.

The GROUP BY clause does not imply ordering.  The fact that the output is ordered is an implementation detail -- the grouping could be implemented by a hash table, in which case the output would be ordered by hash value, for instance.  All that the expression in a GROUP BY does is determine the groupings, and therefore the expression is limited to a comparison compatible expression.  For example, you can GROUP BY x COLLATE NOCASE which implies that the groups are formed using case insensitive comparisons of x.  The ORDER BY clause determines the output ordering.

You will note that if you do the following:

create table x(x,y);
create index ix on x(x desc, y);
select x, someaggregate(y) from x group by x order by x desc;

then ix will be used as a covering index (which is good) however the group by x is treated as an ordering expression, not as simply a grouping expression.

In fact the code that implements the group by does indeed (perhaps erroneously) treat the group by expression as implying order, since it will traverse the covering index in reverse order so that the output from GROUP BY is in ascending order, and add an extra sort to do the ORDER BY.

That means the GROUP BY code generator is already capable of traversing the selected index in reverse order when necessary.  It appears that the optimizer however does not recognize that the "desc" attribute from the order by can be "pushed down" into the GROUP BY (which really is ordering as an implementation detail) thus eliminating the ORDER BY processing entirely.

Note that you cannot specify that the GROUP BY is ordering -- it will not accept the ASC or DESC keywords (which is correct), and this should not be changed, however, treating it as being ordering when it is not might perhaps be a defect ...



_______________________________________________
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] Group-by and order-by-desc does not work as expected

Fredrik Larsen
Your last sentence got me thinking. So I downloaded the source, modified
the ordering of the GROUP-BY expression to match ORDER-BY and it works!
This will offcourse only work if the GROUP-BY and ORDER-BY matches
generally expect for the direction. This fix only improves performance for
relevant cases and keeps other cases unaffected. Not sure if I introduced
some subtle bugs with this modification, but my test-cases runs fine.

Fredrik

On Fri, Sep 20, 2019 at 6:57 PM Keith Medcalf <[hidden email]> wrote:

> >We can observe GROUP BY works ASCending only as of now. Why it can't work
> >DESCending to avoid ordering, that's a different question.
> >From https://www.sqlite.org/lang_select.html we can observe that
> >GROUP BY takes an expr on the RHS, while ORDER BY takes an expr
> >followed by optional COLLATE and ASC/DESC terms.
>
> The GROUP BY clause does not imply ordering.  The fact that the output is
> ordered is an implementation detail -- the grouping could be implemented by
> a hash table, in which case the output would be ordered by hash value, for
> instance.  All that the expression in a GROUP BY does is determine the
> groupings, and therefore the expression is limited to a comparison
> compatible expression.  For example, you can GROUP BY x COLLATE NOCASE
> which implies that the groups are formed using case insensitive comparisons
> of x.  The ORDER BY clause determines the output ordering.
>
> You will note that if you do the following:
>
> create table x(x,y);
> create index ix on x(x desc, y);
> select x, someaggregate(y) from x group by x order by x desc;
>
> then ix will be used as a covering index (which is good) however the group
> by x is treated as an ordering expression, not as simply a grouping
> expression.
>
> In fact the code that implements the group by does indeed (perhaps
> erroneously) treat the group by expression as implying order, since it will
> traverse the covering index in reverse order so that the output from GROUP
> BY is in ascending order, and add an extra sort to do the ORDER BY.
>
> That means the GROUP BY code generator is already capable of traversing
> the selected index in reverse order when necessary.  It appears that the
> optimizer however does not recognize that the "desc" attribute from the
> order by can be "pushed down" into the GROUP BY (which really is ordering
> as an implementation detail) thus eliminating the ORDER BY processing
> entirely.
>
> Note that you cannot specify that the GROUP BY is ordering -- it will not
> accept the ASC or DESC keywords (which is correct), and this should not be
> changed, however, treating it as being ordering when it is not might
> perhaps be a defect ...
>
>
>
> _______________________________________________
> 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] Group-by and order-by-desc does not work as expected

Fredrik Larsen
To clarify; GROUP-BY does not really have ordering, but in the SQLite
implementation, GROUP-BY and ORDER-BY is very closely related as expected,
and it is possible to set a GROUP-BY direction in code (it is default 0 ->
ASC). So thats what I did. Also, some other modifications very required to
stop SQLite from assuming to much about GROUP-BY queries.

Fredrik

On Sat, Sep 21, 2019 at 4:12 PM Fredrik Larsen <[hidden email]> wrote:

> Your last sentence got me thinking. So I downloaded the source, modified
> the ordering of the GROUP-BY expression to match ORDER-BY and it works!
> This will offcourse only work if the GROUP-BY and ORDER-BY matches
> generally expect for the direction. This fix only improves performance for
> relevant cases and keeps other cases unaffected. Not sure if I introduced
> some subtle bugs with this modification, but my test-cases runs fine.
>
> Fredrik
>
> On Fri, Sep 20, 2019 at 6:57 PM Keith Medcalf <[hidden email]> wrote:
>
>> >We can observe GROUP BY works ASCending only as of now. Why it can't work
>> >DESCending to avoid ordering, that's a different question.
>> >From https://www.sqlite.org/lang_select.html we can observe that
>> >GROUP BY takes an expr on the RHS, while ORDER BY takes an expr
>> >followed by optional COLLATE and ASC/DESC terms.
>>
>> The GROUP BY clause does not imply ordering.  The fact that the output is
>> ordered is an implementation detail -- the grouping could be implemented by
>> a hash table, in which case the output would be ordered by hash value, for
>> instance.  All that the expression in a GROUP BY does is determine the
>> groupings, and therefore the expression is limited to a comparison
>> compatible expression.  For example, you can GROUP BY x COLLATE NOCASE
>> which implies that the groups are formed using case insensitive comparisons
>> of x.  The ORDER BY clause determines the output ordering.
>>
>> You will note that if you do the following:
>>
>> create table x(x,y);
>> create index ix on x(x desc, y);
>> select x, someaggregate(y) from x group by x order by x desc;
>>
>> then ix will be used as a covering index (which is good) however the
>> group by x is treated as an ordering expression, not as simply a grouping
>> expression.
>>
>> In fact the code that implements the group by does indeed (perhaps
>> erroneously) treat the group by expression as implying order, since it will
>> traverse the covering index in reverse order so that the output from GROUP
>> BY is in ascending order, and add an extra sort to do the ORDER BY.
>>
>> That means the GROUP BY code generator is already capable of traversing
>> the selected index in reverse order when necessary.  It appears that the
>> optimizer however does not recognize that the "desc" attribute from the
>> order by can be "pushed down" into the GROUP BY (which really is ordering
>> as an implementation detail) thus eliminating the ORDER BY processing
>> entirely.
>>
>> Note that you cannot specify that the GROUP BY is ordering -- it will not
>> accept the ASC or DESC keywords (which is correct), and this should not be
>> changed, however, treating it as being ordering when it is not might
>> perhaps be a defect ...
>>
>>
>>
>> _______________________________________________
>> 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] Group-by and order-by-desc does not work as expected

Keith Medcalf
In reply to this post by Fredrik Larsen

See Dan's checkin on trunk for this issue.

https://www.sqlite.org/src/info/20f7951bb238ddc0

>-----Original Message-----
>From: sqlite-users <[hidden email]> On
>Behalf Of Fredrik Larsen
>Sent: Saturday, 21 September, 2019 08:12
>To: SQLite mailing list <[hidden email]>
>Subject: Re: [sqlite] [EXTERNAL] Group-by and order-by-desc does not work
>as expected
>
>Your last sentence got me thinking. So I downloaded the source, modified
>the ordering of the GROUP-BY expression to match ORDER-BY and it works!
>This will offcourse only work if the GROUP-BY and ORDER-BY matches
>generally expect for the direction. This fix only improves performance
>for
>relevant cases and keeps other cases unaffected. Not sure if I introduced
>some subtle bugs with this modification, but my test-cases runs fine.
>
>Fredrik
>
>On Fri, Sep 20, 2019 at 6:57 PM Keith Medcalf <[hidden email]>
>wrote:
>
>> >We can observe GROUP BY works ASCending only as of now. Why it can't
>work
>> >DESCending to avoid ordering, that's a different question.
>> >From https://www.sqlite.org/lang_select.html we can observe that
>> >GROUP BY takes an expr on the RHS, while ORDER BY takes an expr
>> >followed by optional COLLATE and ASC/DESC terms.
>>
>> The GROUP BY clause does not imply ordering.  The fact that the output
>is
>> ordered is an implementation detail -- the grouping could be
>implemented by
>> a hash table, in which case the output would be ordered by hash value,
>for
>> instance.  All that the expression in a GROUP BY does is determine the
>> groupings, and therefore the expression is limited to a comparison
>> compatible expression.  For example, you can GROUP BY x COLLATE NOCASE
>> which implies that the groups are formed using case insensitive
>comparisons
>> of x.  The ORDER BY clause determines the output ordering.
>>
>> You will note that if you do the following:
>>
>> create table x(x,y);
>> create index ix on x(x desc, y);
>> select x, someaggregate(y) from x group by x order by x desc;
>>
>> then ix will be used as a covering index (which is good) however the
>group
>> by x is treated as an ordering expression, not as simply a grouping
>> expression.
>>
>> In fact the code that implements the group by does indeed (perhaps
>> erroneously) treat the group by expression as implying order, since it
>will
>> traverse the covering index in reverse order so that the output from
>GROUP
>> BY is in ascending order, and add an extra sort to do the ORDER BY.
>>
>> That means the GROUP BY code generator is already capable of traversing
>> the selected index in reverse order when necessary.  It appears that
>the
>> optimizer however does not recognize that the "desc" attribute from the
>> order by can be "pushed down" into the GROUP BY (which really is
>ordering
>> as an implementation detail) thus eliminating the ORDER BY processing
>> entirely.
>>
>> Note that you cannot specify that the GROUP BY is ordering -- it will
>not
>> accept the ASC or DESC keywords (which is correct), and this should not
>be
>> changed, however, treating it as being ordering when it is not might
>> perhaps be a defect ...
>>
>>
>>
>> _______________________________________________
>> 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: [EXTERNAL] Group-by and order-by-desc does not work as expected

Fredrik Larsen
Interesting, very similar change but not fully idenctial. In my patch, I
created a sqlite3ExprListCompareIgnoreButUpdateSort, and used this function
from line 6239. This function ignores the sort part when comparing
expressions, but will update the GroupBy sortOrder field if expressions are
found equal. I see dan modifies the sortFlag. Would be interesting to know
what effect this difference has. My change works in my test, but not sure
if it really works.

Anyway, super-nice that this issue is fixed officially. No I don't have to
wonder if my fix is really correct, or will suddenly corrupt something :)

Fredrik

On Sat, Sep 21, 2019 at 8:49 PM Keith Medcalf <[hidden email]> wrote:

>
> See Dan's checkin on trunk for this issue.
>
> https://www.sqlite.org/src/info/20f7951bb238ddc0
>
> >-----Original Message-----
> >From: sqlite-users <[hidden email]> On
> >Behalf Of Fredrik Larsen
> >Sent: Saturday, 21 September, 2019 08:12
> >To: SQLite mailing list <[hidden email]>
> >Subject: Re: [sqlite] [EXTERNAL] Group-by and order-by-desc does not work
> >as expected
> >
> >Your last sentence got me thinking. So I downloaded the source, modified
> >the ordering of the GROUP-BY expression to match ORDER-BY and it works!
> >This will offcourse only work if the GROUP-BY and ORDER-BY matches
> >generally expect for the direction. This fix only improves performance
> >for
> >relevant cases and keeps other cases unaffected. Not sure if I introduced
> >some subtle bugs with this modification, but my test-cases runs fine.
> >
> >Fredrik
> >
> >On Fri, Sep 20, 2019 at 6:57 PM Keith Medcalf <[hidden email]>
> >wrote:
> >
> >> >We can observe GROUP BY works ASCending only as of now. Why it can't
> >work
> >> >DESCending to avoid ordering, that's a different question.
> >> >From https://www.sqlite.org/lang_select.html we can observe that
> >> >GROUP BY takes an expr on the RHS, while ORDER BY takes an expr
> >> >followed by optional COLLATE and ASC/DESC terms.
> >>
> >> The GROUP BY clause does not imply ordering.  The fact that the output
> >is
> >> ordered is an implementation detail -- the grouping could be
> >implemented by
> >> a hash table, in which case the output would be ordered by hash value,
> >for
> >> instance.  All that the expression in a GROUP BY does is determine the
> >> groupings, and therefore the expression is limited to a comparison
> >> compatible expression.  For example, you can GROUP BY x COLLATE NOCASE
> >> which implies that the groups are formed using case insensitive
> >comparisons
> >> of x.  The ORDER BY clause determines the output ordering.
> >>
> >> You will note that if you do the following:
> >>
> >> create table x(x,y);
> >> create index ix on x(x desc, y);
> >> select x, someaggregate(y) from x group by x order by x desc;
> >>
> >> then ix will be used as a covering index (which is good) however the
> >group
> >> by x is treated as an ordering expression, not as simply a grouping
> >> expression.
> >>
> >> In fact the code that implements the group by does indeed (perhaps
> >> erroneously) treat the group by expression as implying order, since it
> >will
> >> traverse the covering index in reverse order so that the output from
> >GROUP
> >> BY is in ascending order, and add an extra sort to do the ORDER BY.
> >>
> >> That means the GROUP BY code generator is already capable of traversing
> >> the selected index in reverse order when necessary.  It appears that
> >the
> >> optimizer however does not recognize that the "desc" attribute from the
> >> order by can be "pushed down" into the GROUP BY (which really is
> >ordering
> >> as an implementation detail) thus eliminating the ORDER BY processing
> >> entirely.
> >>
> >> Note that you cannot specify that the GROUP BY is ordering -- it will
> >not
> >> accept the ASC or DESC keywords (which is correct), and this should not
> >be
> >> changed, however, treating it as being ordering when it is not might
> >> perhaps be a defect ...
> >>
> >>
> >>
> >> _______________________________________________
> >> 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
Reply | Threaded
Open this post in threaded view
|

Re: [EXTERNAL] Group-by and order-by-desc does not work as expected

Dan Kennedy-4

On 22/9/62 02:25, Fredrik Larsen wrote:
> Interesting, very similar change but not fully idenctial. In my patch, I
> created a sqlite3ExprListCompareIgnoreButUpdateSort, and used this function
> from line 6239. This function ignores the sort part when comparing
> expressions, but will update the GroupBy sortOrder field if expressions are
> found equal. I see dan modifies the sortFlag.

That sounds equivalent to me. The sortOrder/sortFlag thing is probably
just because you patched the last release (3.29.0) or earlier. The field
has changed names since then.

Dan.



> Would be interesting to know
> what effect this difference has. My change works in my test, but not sure
> if it really works.
>
> Anyway, super-nice that this issue is fixed officially. No I don't have to
> wonder if my fix is really correct, or will suddenly corrupt something :)
>
> Fredrik
>
> On Sat, Sep 21, 2019 at 8:49 PM Keith Medcalf <[hidden email]> wrote:
>
>> See Dan's checkin on trunk for this issue.
>>
>> https://www.sqlite.org/src/info/20f7951bb238ddc0
>>
>>> -----Original Message-----
>>> From: sqlite-users <[hidden email]> On
>>> Behalf Of Fredrik Larsen
>>> Sent: Saturday, 21 September, 2019 08:12
>>> To: SQLite mailing list <[hidden email]>
>>> Subject: Re: [sqlite] [EXTERNAL] Group-by and order-by-desc does not work
>>> as expected
>>>
>>> Your last sentence got me thinking. So I downloaded the source, modified
>>> the ordering of the GROUP-BY expression to match ORDER-BY and it works!
>>> This will offcourse only work if the GROUP-BY and ORDER-BY matches
>>> generally expect for the direction. This fix only improves performance
>>> for
>>> relevant cases and keeps other cases unaffected. Not sure if I introduced
>>> some subtle bugs with this modification, but my test-cases runs fine.
>>>
>>> Fredrik
>>>
>>> On Fri, Sep 20, 2019 at 6:57 PM Keith Medcalf <[hidden email]>
>>> wrote:
>>>
>>>>> We can observe GROUP BY works ASCending only as of now. Why it can't
>>> work
>>>>> DESCending to avoid ordering, that's a different question.
>>>> >From https://www.sqlite.org/lang_select.html we can observe that
>>>>> GROUP BY takes an expr on the RHS, while ORDER BY takes an expr
>>>>> followed by optional COLLATE and ASC/DESC terms.
>>>> The GROUP BY clause does not imply ordering.  The fact that the output
>>> is
>>>> ordered is an implementation detail -- the grouping could be
>>> implemented by
>>>> a hash table, in which case the output would be ordered by hash value,
>>> for
>>>> instance.  All that the expression in a GROUP BY does is determine the
>>>> groupings, and therefore the expression is limited to a comparison
>>>> compatible expression.  For example, you can GROUP BY x COLLATE NOCASE
>>>> which implies that the groups are formed using case insensitive
>>> comparisons
>>>> of x.  The ORDER BY clause determines the output ordering.
>>>>
>>>> You will note that if you do the following:
>>>>
>>>> create table x(x,y);
>>>> create index ix on x(x desc, y);
>>>> select x, someaggregate(y) from x group by x order by x desc;
>>>>
>>>> then ix will be used as a covering index (which is good) however the
>>> group
>>>> by x is treated as an ordering expression, not as simply a grouping
>>>> expression.
>>>>
>>>> In fact the code that implements the group by does indeed (perhaps
>>>> erroneously) treat the group by expression as implying order, since it
>>> will
>>>> traverse the covering index in reverse order so that the output from
>>> GROUP
>>>> BY is in ascending order, and add an extra sort to do the ORDER BY.
>>>>
>>>> That means the GROUP BY code generator is already capable of traversing
>>>> the selected index in reverse order when necessary.  It appears that
>>> the
>>>> optimizer however does not recognize that the "desc" attribute from the
>>>> order by can be "pushed down" into the GROUP BY (which really is
>>> ordering
>>>> as an implementation detail) thus eliminating the ORDER BY processing
>>>> entirely.
>>>>
>>>> Note that you cannot specify that the GROUP BY is ordering -- it will
>>> not
>>>> accept the ASC or DESC keywords (which is correct), and this should not
>>> be
>>>> changed, however, treating it as being ordering when it is not might
>>>> perhaps be a defect ...
>>>>
>>>>
>>>>
>>>> _______________________________________________
>>>> 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
_______________________________________________
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] Group-by and order-by-desc does not work as expected

Fredrik Larsen
Good to know that I was not to far off target then. But fixing issues in
less than a day of reporting? On a Saturday? Who does that? I was planning
to feel happy about solving this issue.. :)

Fredrik

On Sat, Sep 21, 2019 at 9:31 PM Dan Kennedy <[hidden email]> wrote:

>
> On 22/9/62 02:25, Fredrik Larsen wrote:
> > Interesting, very similar change but not fully idenctial. In my patch, I
> > created a sqlite3ExprListCompareIgnoreButUpdateSort, and used this
> function
> > from line 6239. This function ignores the sort part when comparing
> > expressions, but will update the GroupBy sortOrder field if expressions
> are
> > found equal. I see dan modifies the sortFlag.
>
> That sounds equivalent to me. The sortOrder/sortFlag thing is probably
> just because you patched the last release (3.29.0) or earlier. The field
> has changed names since then.
>
> Dan.
>
>
>
> > Would be interesting to know
> > what effect this difference has. My change works in my test, but not sure
> > if it really works.
> >
> > Anyway, super-nice that this issue is fixed officially. No I don't have
> to
> > wonder if my fix is really correct, or will suddenly corrupt something :)
> >
> > Fredrik
> >
> > On Sat, Sep 21, 2019 at 8:49 PM Keith Medcalf <[hidden email]>
> wrote:
> >
> >> See Dan's checkin on trunk for this issue.
> >>
> >> https://www.sqlite.org/src/info/20f7951bb238ddc0
> >>
> >>> -----Original Message-----
> >>> From: sqlite-users <[hidden email]> On
> >>> Behalf Of Fredrik Larsen
> >>> Sent: Saturday, 21 September, 2019 08:12
> >>> To: SQLite mailing list <[hidden email]>
> >>> Subject: Re: [sqlite] [EXTERNAL] Group-by and order-by-desc does not
> work
> >>> as expected
> >>>
> >>> Your last sentence got me thinking. So I downloaded the source,
> modified
> >>> the ordering of the GROUP-BY expression to match ORDER-BY and it works!
> >>> This will offcourse only work if the GROUP-BY and ORDER-BY matches
> >>> generally expect for the direction. This fix only improves performance
> >>> for
> >>> relevant cases and keeps other cases unaffected. Not sure if I
> introduced
> >>> some subtle bugs with this modification, but my test-cases runs fine.
> >>>
> >>> Fredrik
> >>>
> >>> On Fri, Sep 20, 2019 at 6:57 PM Keith Medcalf <[hidden email]>
> >>> wrote:
> >>>
> >>>>> We can observe GROUP BY works ASCending only as of now. Why it can't
> >>> work
> >>>>> DESCending to avoid ordering, that's a different question.
> >>>> >From https://www.sqlite.org/lang_select.html we can observe that
> >>>>> GROUP BY takes an expr on the RHS, while ORDER BY takes an expr
> >>>>> followed by optional COLLATE and ASC/DESC terms.
> >>>> The GROUP BY clause does not imply ordering.  The fact that the output
> >>> is
> >>>> ordered is an implementation detail -- the grouping could be
> >>> implemented by
> >>>> a hash table, in which case the output would be ordered by hash value,
> >>> for
> >>>> instance.  All that the expression in a GROUP BY does is determine the
> >>>> groupings, and therefore the expression is limited to a comparison
> >>>> compatible expression.  For example, you can GROUP BY x COLLATE NOCASE
> >>>> which implies that the groups are formed using case insensitive
> >>> comparisons
> >>>> of x.  The ORDER BY clause determines the output ordering.
> >>>>
> >>>> You will note that if you do the following:
> >>>>
> >>>> create table x(x,y);
> >>>> create index ix on x(x desc, y);
> >>>> select x, someaggregate(y) from x group by x order by x desc;
> >>>>
> >>>> then ix will be used as a covering index (which is good) however the
> >>> group
> >>>> by x is treated as an ordering expression, not as simply a grouping
> >>>> expression.
> >>>>
> >>>> In fact the code that implements the group by does indeed (perhaps
> >>>> erroneously) treat the group by expression as implying order, since it
> >>> will
> >>>> traverse the covering index in reverse order so that the output from
> >>> GROUP
> >>>> BY is in ascending order, and add an extra sort to do the ORDER BY.
> >>>>
> >>>> That means the GROUP BY code generator is already capable of
> traversing
> >>>> the selected index in reverse order when necessary.  It appears that
> >>> the
> >>>> optimizer however does not recognize that the "desc" attribute from
> the
> >>>> order by can be "pushed down" into the GROUP BY (which really is
> >>> ordering
> >>>> as an implementation detail) thus eliminating the ORDER BY processing
> >>>> entirely.
> >>>>
> >>>> Note that you cannot specify that the GROUP BY is ordering -- it will
> >>> not
> >>>> accept the ASC or DESC keywords (which is correct), and this should
> not
> >>> be
> >>>> changed, however, treating it as being ordering when it is not might
> >>>> perhaps be a defect ...
> >>>>
> >>>>
> >>>>
> >>>> _______________________________________________
> >>>> 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
> _______________________________________________
> 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] Group-by and order-by-desc does not work as expected

Dominique Devienne
On Sat, Sep 21, 2019 at 10:17 PM Fredrik Larsen <[hidden email]> wrote:

> [...] But fixing issues in less than a day of reporting? [...]
>

That's not unusual at all for SQLite. Either it gets "fixed" quickly, or it
doesn't.

The hard part is making the case with Richard (and Dan) about the merit of
the
change, especially if it's not a bug-fix like here, but a missed
optimization. They
care a lot about performance, and do try to respond to community input, even
though they participate very little in this ML in such request-for-changes
threads.

If we named SQLite optimizations, that new one would be the Fredrik's :).
--DD
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users