/ View Ticket
Login
Ticket UUID: ef9318757b152e3a26e95923e8fe8c178a7e629c
Title: Incorrect result due to the skip-ahead-distinct optimization
Status: Fixed Type: Code_Defect
Severity: Severe Priority: Immediate
Subsystem: Unknown Resolution: Fixed
Last Modified: 2017-11-23 00:48:00
Version Found In: 3.21.0
User Comments:
drh added on 2017-11-21 15:19:27:

The query in the SQL shown below gives an incorrect answer after ANALYZE has been run:

CREATE TABLE t1(a INTEGER PRIMARY KEY, b INTEGER);
CREATE INDEX t1b ON t1(b);
CREATE TABLE t2(x INTEGER PRIMARY KEY, y INTEGER);
CREATE INDEX t2y ON t2(y);
WITH RECURSIVE c(x) AS (VALUES(0) UNION ALL SELECT x+1 FROM c WHERE x<49)
  INSERT INTO t1(b) SELECT x/10 - 1 FROM c;
WITH RECURSIVE c(x) AS (VALUES(-1) UNION ALL SELECT x+1 FROM c WHERE x<19)
  INSERT INTO t2(x,y) SELECT x, 1 FROM c;
SELECT DISTINCT y FROM t1, t2 WHERE b=x AND b<>-1;
ANALYZE;
SELECT DISTINCT y FROM t1, t2 WHERE b=x AND b<>-1;

This problem seems to have been introduced by the skip-ahead-distinct optimization of check-in [f489b5bb6b35665], first included in SQLite version 3.19.0. The problem was reported on the public mailing list by David Raymond.


drh added on 2017-11-23 00:16:03:

Two more test cases:

CREATE TABLE t1(a INTEGER PRIMARY KEY, b INTEGER);
CREATE INDEX t1b ON t1(b);
CREATE TABLE t2(x INTEGER PRIMARY KEY, y INTEGER);
CREATE INDEX t2y ON t2(y);
WITH RECURSIVE c(x) AS (VALUES(0) UNION ALL SELECT x+1 FROM c WHERE x<49)
  INSERT INTO t1(b) SELECT -(x/10 - 1) FROM c;
WITH RECURSIVE c(x) AS (VALUES(-1) UNION ALL SELECT x+1 FROM c WHERE x<19)
  INSERT INTO t2(x,y) SELECT -x, 1 FROM c;
SELECT DISTINCT y FROM t1, t2 WHERE b=x AND b<>1 ORDER BY y DESC;
ANALYZE;
SELECT DISTINCT y FROM t1, t2 WHERE b=x AND b<>1 ORDER BY y DESC;
CREATE TABLE t1(a, b);
CREATE INDEX t1a ON t1(a, b);
-- Lots of rows of (1, 'no'), followed by a single (1, 'yes').
WITH RECURSIVE c(x) AS (VALUES(1) UNION ALL SELECT x+1 FROM c WHERE x<100)
  INSERT INTO t1(a, b) SELECT 1, 'no' FROM c;
INSERT INTO t1(a, b) VALUES(1, 'yes');
CREATE TABLE t2(x PRIMARY KEY);
INSERT INTO t2 VALUES('yes');
SELECT DISTINCT a FROM t1, t2 WHERE x=b;
ANALYZE;
SELECT DISTINCT a FROM t1, t2 WHERE x=b;