SQLite

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.

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;