Incorrect ORDER-BY result

(1) By anonymous on 2024-09-05 19:09:10 [source]

CREATE TABLE foo (
    a INTEGER NOT NULL,
    b INTEGER NOT NULL,
    ref INTEGER,
    PRIMARY KEY(a, b)
) STRICT;
CREATE TABLE bar (
    a INTEGER NOT NULL,
    b INTEGER NOT NULL,
    c INTEGER NOT NULL,
    PRIMARY KEY(a, b, c)
) STRICT;

INSERT INTO foo VALUES (42,123,NULL), (42,567,123);
INSERT INTO bar VALUES (42,567,0), (42,567,1);

    SELECT foo.a, foo.b, bar.c
      FROM foo
 LEFT JOIN foo goo ON (goo.a = foo.a) AND (goo.b = foo.ref)
INNER JOIN bar ON (bar.a = foo.a) AND (bar.b = foo.b)
     WHERE foo.a = 42 AND foo.b = 567
  ORDER BY bar.c DESC;

produces

┌────┬─────┬───┐
│ a  │  b  │ c │
├────┼─────┼───┤
│ 42 │ 567 │ 0 │
│ 42 │ 567 │ 1 │
└────┴─────┴───┘

which, I'm quite sure, is not ordered descending by bar.c.

However, if we add goo.b to the SELECT clause, the result is correct. By the looks of the query plan, that inhibits join elision, which may be losing order-by information in the faulty case.

(2) By Richard Hipp (drh) on 2024-09-05 22:55:38 in reply to 1 [link] [source]

Thanks for the bug report.

Here is a simplified test case that involves no indexes and no self-joins:

CREATE TABLE t1(a1 INTEGER PRIMARY KEY, b1 INT);
CREATE TABLE t2(c2 INT, d2 INTEGER PRIMARY KEY);
CREATE TABLE t3(e3 INTEGER PRIMARY KEY);
INSERT INTO t1 VALUES(33,0);
INSERT INTO t2 VALUES(33,1),(33,2);
SELECT t1.a1, t2.d2
  FROM (t1 LEFT JOIN t3 ON t3.e3=t1.b1) JOIN t2 ON t2.c2=t1.a1
 WHERE t1.a1=33
 ORDER BY t2.d2 DESC;

The problem goes back to check-in 0cd82ee9a8413cf1 from 2017-11-21 (6 years and 9 months ago) and is associated with the optimization that tries to omit a useless LEFT JOIN. In other words, it is the optimization that removes the t3 table from the query above, rewriting it as just:

SELECT t1.a1, t2.d2
  FROM t1 JOIN t2 ON t2.c2=t1.a1
 WHERE t1.a1=33
 ORDER BY t2.d2 DESC;

Somehow, the transformation to get rid of the t3 table seems to be causing SQLite to lose track of the DESC flag on the ORDER BY. I don't have a solution yet.

(3) By Richard Hipp (drh) on 2024-09-05 23:31:35 in reply to 1 [link] [source]

Further analysis:

SQLite strives to avoid sorting by arranging queries in a way that the results naturally come out in the order specified by the ORDER BY clause. Sometimes to achieve that, terms of the FROM clause need to be run backwards to accommodate a "DESC" in the ORDER BY clause. SQLite uses an unsigned 64-bit integer to track which terms of the FROM clause need to be run backwards. (This is one of several reasons why SQLite is limited to 64-way joins.)

The Omit-Noop-Join optimization is applied after that run-in-reverse bitmap has been computed. But the bitmap was not being adjusted when terms of the FROM clause were removed.

That has now been fixed by check-in 22ca5a2ffb89ccb5.