2

Suppose that I have a schema like the following:

-- Many rows
CREATE TABLE t1(i INTEGER PRIMARY KEY, c1 INTEGER, c2 INTEGER);

-- t1's rows with c1 even
CREATE VIEW t1_filtered(i, c1, c2) AS
  SELECT i, c1, c2 FROM t1 WHERE c1 % 2 == 0;
-- The real WHERE clause is slightly more complex.

Suppose that table t1 contains some millions of rows:

INSERT INTO t1(i, c1, c2)
  SELECT value, random(), random() FROM generate_series(1, 5000000);

Suppose that I want to get both the index of the row in t1 that has the highest even c1 and the count of rows with even c1 that also have even c2:

SELECT
  (SELECT i FROM t1_filtered ORDER BY c1 DESC LIMIT 1),
  (SELECT count(*) FROM t1_filtered WHERE c2 % 2 == 0);

The real ORDER BY clause is much more complex, but this is sufficient to illustrate my problem.

It seems to me that this ought to be possible with only one scan through t1, but EXPLAIN QUERY PLAN says that this query scans t1 twice:

QUERY PLAN
|--SCAN CONSTANT ROW
|--SCALAR SUBQUERY 1
|  |--SCAN t1
|  `--USE TEMP B-TREE FOR ORDER BY
`--SCALAR SUBQUERY 2
   `--SCAN t1

If I join the two subqueries rather than write them as result-columns, then the query plan is different but still has two scans of t1:

QUERY PLAN
|--CO-ROUTINE (subquery-1)
|  |--SCAN t1
|  `--USE TEMP B-TREE FOR ORDER BY
|--MATERIALIZE (subquery-2)
|  `--SCAN t1
|--SCAN (subquery-1)
`--SCAN (subquery-2)

Imperatively, I would expect this query to be something like this pseudocode:

var top_row = {i: NULL, c1: 0};
var count = 0;
for each {i, c1, c2} in t1:
  if c1 % 2 == 0:
    if c1 > top_row.c1:
      top_row = {i, c1};
    if c2 % 2 == 0:
      count = count + 1;
return {top_row.i, count};

How can I get the query planner to see that this needs only one scan?

Update, 2024-05-09: I tried Charlieface's proposed query. According to EXPLAIN QUERY PLAN, it does make the query planner use only one scan of t1...

QUERY PLAN
|--CO-ROUTINE t
|  |--CO-ROUTINE (subquery-4)
|  |  |--SCAN t1
|  |  `--USE TEMP B-TREE FOR ORDER BY
|  `--SCAN (subquery-4)
`--SCAN t

...but it runs significantly more slowly than my original SELECT (...), (...) query: testing both queries in the SQLite REPL with .timer on, I find that (for my example table t1 with 5 million rows of random data) my original query has a mean running time of 2.22 seconds with sample standard deviation of 0.03 s and this proposed query takes mean 5.57 s with st. dev. 0.23 s.

Something that my imperative intuition had not suggested to me but that studying the query plans' "USE TEMP B-TREE FOR ORDER BY" did suggest was adding an index on t1(c1). This indeed speeds up my original query, making it take mean 1.09 s with st. dev. 0.02 s. However, to my surprise, the index apparently makes Charlieface's query take much longer or possibly even makes it non-terminating — I interrupted it after waiting for 108 seconds, and then I interrupted it after trying again for 32 s, and then I didn't try again.

Charlieface's query does literally answer my question by reducing the number of scans of t1 to one, but its poor practical performance relative to my original query makes me reluctant to accept it as the answer. I hope that's not "moving the goal posts" too much. I did tag this as query-performance, so performance was part of my question from the start.

Update, 2024-05-09 #2: With CREATE INDEX t1_c1 ON t1(c1), the query plan for my original query became

QUERY PLAN
|--SCAN CONSTANT ROW
|--SCALAR SUBQUERY 1
|  `--SCAN t1 USING COVERING INDEX t1_c1
`--SCALAR SUBQUERY 2
   `--SCAN t1

and the query plan for Charlieface's query became

QUERY PLAN
|--CO-ROUTINE t
|  |--CO-ROUTINE (subquery-4)
|  |  `--SCAN t1 USING INDEX t1_c1
|  `--SCAN (subquery-4)
`--SCAN t

With CREATE INDEX index_per_comment660077_339327 ON t1 (c1 DESC) WHERE (c1 % 2 = 0) per Charlieface's comment (SQLite does not support INCLUDE), the query plans become, respectively,

QUERY PLAN
|--SCAN CONSTANT ROW
|--SCALAR SUBQUERY 1
|  `--SCAN t1 USING COVERING INDEX index_per_comment660077_339327
`--SCALAR SUBQUERY 2
   `--SCAN t1 USING INDEX index_per_comment660077_339327

QUERY PLAN
|--CO-ROUTINE t
|  |--CO-ROUTINE (subquery-4)
|  |  `--SCAN t1 USING INDEX index_per_comment660077_339327
|  `--SCAN (subquery-4)
`--SCAN t
3
  • You have two subqueries, so it performs two scan, because it if you have an index that fits, the second scan would be repalce, but basically as long you make twio subqueries, you will need to process it
    – nbk
    Commented May 7 at 22:24
  • An index t1 (c1 DESC) INCLUDE (i, c2) WHERE (c1 % 2 = 0) may help. There shouldn't be a need for a sort, can you show the plan after adding that? Commented May 9 at 0:54
  • @Charlieface: updated
    – user570286
    Commented May 9 at 1:26

2 Answers 2

1

With SQLite if an aggregate query contains a single min() or max() function, then the values of columns used in the output are taken from the row where the min() or max() value was achieved. It's a feature.

SELECT i, MAX(c1), COUNT(*) FILTER (WHERE c2 % 2 = 0) 
FROM t1_filtered;

The query doesn't need an index and it has this simple query plan:

EXPLAIN QUERY PLAN
SELECT i, MAX(c1), COUNT(*) FILTER (WHERE c2 % 2 = 0) 
FROM t1_filtered;

QUERY PLAN
`--SCAN t1

The query will compute MAX(c1) and COUNT(*) in a single scan and will return the value of i that was found in the same row where MAX(c1) was achieved.

An EXPLAIN will show the compiled query in SQLite OPcodes and you can see that the generated code is exactly the same pseudocode you wanted.

EXPLAIN
SELECT i, MAX(c1), COUNT(*) FILTER (WHERE c2 % 2 = 0) 
FROM t1_filtered;

addr  opcode         p1    p2    p3    p4             p5  comment
----  -------------  ----  ----  ----  -------------  --  -------------
0     Init           0     23    0                    0   Start at 23
1     Null           0     1     5                    0   r[1..5]=NULL
2     OpenRead       1     2     0     3              0   root=2 iDb=0; t1
3     Rewind         1     17    0                    0
4       Column         1     1     7                    0   r[7]= cursor 1 column 1
5       Remainder      8     7     6                    0   r[6]=r[7]%r[8]
6       Ne             9     16    6                    80  if r[6]!=r[9] goto 16
7       Column         1     1     6                    0   r[6]= cursor 1 column 1
8       CollSeq        10    0     0     BINARY-8       0
9       AggStep        0     6     4     max(1)         1   accum=r[4] step(r[6])
10      Column         1     2     7                    0   r[7]= cursor 1 column 2
11      Remainder      8     7     6                    0   r[6]=r[7]%r[8]
12      Ne             9     14    6                    80  if r[6]!=r[9] goto 14
13      AggStep        0     0     5     count(0)       0   accum=r[5] step(r[0])
14      If             10    16    0                    0
15      Rowid          1     1     0                    0   r[1]=t1.rowid
16    Next           1     4     0                    1
17    AggFinal       4     1     0     max(1)         0   accum=r[4] N=1
18    AggFinal       5     0     0     count(0)       0   accum=r[5] N=0
19    Copy           1     11    0                    0   r[11]=r[1]
20    Copy           4     12    1                    0   r[12..13]=r[4..5]
21    ResultRow      11    3     0                    0   output=r[11..13]
22    Halt           0     0     0                    0
23    Transaction    0     0     2     0              1   usesStmtJournal=0
24    Integer        2     8     0                    0   r[8]=2
25    Integer        0     9     0                    0   r[9]=0
26    Goto           0     1     0                    0
0

You can use row-numbering and conditional aggregation

SELECT
  MIN(t.i) FILTER (WHERE t.rn = 1),
  COUNT(*) FILTER (WHERE t.c2 % 2 = 0)
FROM (
    SELECT *,
      ROW_NUMBER() OVER (ORDER BY t.c1 DESC) AS rn
    FROM t1_filtered t
) t;
1
  • Thank you, but see my updated post.
    – user570286
    Commented May 9 at 0:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.