Re: [sqlite] [EXTERNAL] Group-by and order-by-desc does not work as expected
On Sat, Sep 21, 2019 at 10:17 PM Fredrik Larsen 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 sqlite-users@mailinglists.sqlite.org http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Re: [sqlite] [EXTERNAL] Group-by and order-by-desc does not work as expected
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 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 > wrote: > > > >> See Dan's checkin on trunk for this issue. > >> > >> https://www.sqlite.org/src/info/20f7951bb238ddc0 > >> > >>> -Original Message- > >>> From: sqlite-users On > >>> Behalf Of Fredrik Larsen > >>> Sent: Saturday, 21 September, 2019 08:12 > >>> To: SQLite mailing list > >>> 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 > >>> 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 > sqlite-users@mailinglists.sqlite.org > http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users > > >>> ___ > >>> sqlite-users mailing list > >>>
Re: [sqlite] [EXTERNAL] Group-by and order-by-desc does not work as expected
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 wrote: See Dan's checkin on trunk for this issue. https://www.sqlite.org/src/info/20f7951bb238ddc0 -Original Message- From: sqlite-users On Behalf Of Fredrik Larsen Sent: Saturday, 21 September, 2019 08:12 To: SQLite mailing list 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 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 sqlite-users@mailinglists.sqlite.org http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users ___ sqlite-users mailing list sqlite-users@mailinglists.sqlite.org http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users ___ sqlite-users mailing list sqlite-users@mailinglists.sqlite.org http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users ___ sqlite-users mailing list sqlite-users@mailinglists.sqlite.org http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users ___ sqlite-users mailing list sqlite-users@mailinglists.sqlite.org http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Re: [sqlite] [EXTERNAL] Group-by and order-by-desc does not work as expected
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 wrote: > > See Dan's checkin on trunk for this issue. > > https://www.sqlite.org/src/info/20f7951bb238ddc0 > > >-Original Message- > >From: sqlite-users On > >Behalf Of Fredrik Larsen > >Sent: Saturday, 21 September, 2019 08:12 > >To: SQLite mailing list > >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 > >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 > >> sqlite-users@mailinglists.sqlite.org > >> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users > >> > >___ > >sqlite-users mailing list > >sqlite-users@mailinglists.sqlite.org > >http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users > > > > ___ > sqlite-users mailing list > sqlite-users@mailinglists.sqlite.org > http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users > ___ sqlite-users mailing list sqlite-users@mailinglists.sqlite.org http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Re: [sqlite] [EXTERNAL] Group-by and order-by-desc does not work as expected
See Dan's checkin on trunk for this issue. https://www.sqlite.org/src/info/20f7951bb238ddc0 >-Original Message- >From: sqlite-users On >Behalf Of Fredrik Larsen >Sent: Saturday, 21 September, 2019 08:12 >To: SQLite mailing list >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 >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 >> sqlite-users@mailinglists.sqlite.org >> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users >> >___ >sqlite-users mailing list >sqlite-users@mailinglists.sqlite.org >http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users ___ sqlite-users mailing list sqlite-users@mailinglists.sqlite.org http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Re: [sqlite] [EXTERNAL] Group-by and order-by-desc does not work as expected
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 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 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 >> sqlite-users@mailinglists.sqlite.org >> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users >> > ___ sqlite-users mailing list sqlite-users@mailinglists.sqlite.org http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
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 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 > sqlite-users@mailinglists.sqlite.org > http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users > ___ sqlite-users mailing list sqlite-users@mailinglists.sqlite.org http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Re: [sqlite] [EXTERNAL] Group-by and order-by-desc does not work as expected
>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 sqlite-users@mailinglists.sqlite.org http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Re: [sqlite] [EXTERNAL] Group-by and order-by-desc does not work as expected
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 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.1% 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 > sqlite-users@mailinglists.sqlite.org > http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users > ___ sqlite-users mailing list sqlite-users@mailinglists.sqlite.org http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Re: [sqlite] [EXTERNAL] Group-by and order-by-desc does not work as expected
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.1% 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 sqlite-users@mailinglists.sqlite.org http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Re: [sqlite] [EXTERNAL] Group-by and order-by-desc does not work as expected
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 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 > sqlite-users@mailinglists.sqlite.org > http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users > ___ sqlite-users mailing list sqlite-users@mailinglists.sqlite.org http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Re: [sqlite] [EXTERNAL] Group-by and order-by-desc does not work as expected
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 sqlite-users@mailinglists.sqlite.org http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Re: [sqlite] [EXTERNAL] Group-by and order-by-desc does not work as expected
On Fri, Sep 20, 2019 at 12:33 PM Hick Gunter 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 sqlite-users@mailinglists.sqlite.org http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Re: [sqlite] [EXTERNAL] Group-by and order-by-desc does not work as expected
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:sqlite-users-boun...@mailinglists.sqlite.org] Im Auftrag von Dominique Devienne Gesendet: Freitag, 20. September 2019 11:12 An: SQLite mailing list 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 wrote: > -Ursprüngliche Nachricht- > Von: sqlite-users > [mailto:sqlite-users-boun...@mailinglists.sqlite.org] > Im Auftrag von Fredrik Larsen > Gesendet: Donnerstag, 19. September 2019 17:29 > An: SQLite mailing list > 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 sqlite-users@mailinglists.sqlite.org 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 sqlite-users@mailinglists.sqlite.org http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
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 wrote: > -Ursprüngliche Nachricht- > Von: sqlite-users [mailto:sqlite-users-boun...@mailinglists.sqlite.org] > Im Auftrag von Fredrik Larsen > Gesendet: Donnerstag, 19. September 2019 17:29 > An: SQLite mailing list > 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 sqlite-users@mailinglists.sqlite.org http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Re: [sqlite] [EXTERNAL] Group-by and order-by-desc does not work as expected
-Ursprüngliche Nachricht- Von: sqlite-users [mailto:sqlite-users-boun...@mailinglists.sqlite.org] Im Auftrag von Fredrik Larsen Gesendet: Donnerstag, 19. September 2019 17:29 An: SQLite mailing list 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 sqlite-users@mailinglists.sqlite.org http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Re: [sqlite] [EXTERNAL] Group-by and order-by-desc does not work as expected
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 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:sqlite-users-boun...@mailinglists.sqlite.org] > Im Auftrag von Fredrik Larsen > Gesendet: Donnerstag, 19. September 2019 14:14 > An: sqlite-users@mailinglists.sqlite.org > 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 > sqlite-users@mailinglists.sqlite.org > 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 > sqlite-users@mailinglists.sqlite.org > http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users > ___ sqlite-users mailing list sqlite-users@mailinglists.sqlite.org http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Re: [sqlite] [EXTERNAL] Group-by and order-by-desc does not work as expected
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:sqlite-users-boun...@mailinglists.sqlite.org] Im Auftrag von Fredrik Larsen Gesendet: Donnerstag, 19. September 2019 14:14 An: sqlite-users@mailinglists.sqlite.org 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 sqlite-users@mailinglists.sqlite.org 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 sqlite-users@mailinglists.sqlite.org http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
