Why query with ORDER BY RANDOM() much slower than CTE version?
(1.1) By Keyka Vigiliant (kekavigi) on 2025-07-20 16:46:57 edited from 1.0 [source]
Hello, I am a SQL beginner, and I would like to ask why the following two SQL commands have much different execution times. Initially, I have the following database tables
PRAGMA journal_mode = wal;
PRAGMA synchronous = off;
PRAGMA temp_store = memory;
PRAGMA mmap_size = 30000000000;
PRAGMA busy_timeout = 10000;
PRAGMA wal_autocheckpoint;
CREATE TABLE IF NOT EXISTS board(
fen BLOB NOT NULL, -- compressed chess position
depth INTEGER NOT NULL, -- analysis depth
score INTEGER NOT NULL, -- in centipawn
move INTEGER, -- best move, if exist
PRIMARY KEY (fen)
) WITHOUT ROWID;
CREATE INDEX IF NOT EXISTS ix_covering
ON board (depth, score);
Then, I want to search 10 rows on the board randomly, with depth=35 and score>=100. I thought of the following SQL command
SELECT fen, score, depth, move
FROM board
WHERE depth=35 AND score >= 100
ORDER BY RANDOM()
LIMIT 10
The command took about 80 seconds to execute. But it also occurred to me that the command could also be written as
WITH eligible AS (
SELECT fen FROM board
WHERE depth=35 AND score >= 100
ORDER BY RANDOM()
LIMIT 10
)
SELECT fen, score, depth, move
FROM board
WHERE fen IN eligible
which only takes about 0.1 - 0.2 seconds. I have run ANALYZE, but the results are still the same. The difference in execution time is confusing, because I thought the two commands were doing the same thing. Why can't the first version of SELECT be as fast as the second version, even though the depth and score used in the WHERE condition are indexed?
I am using SQLite 3.47.2; there are about 701.5M rows in the board table, and here is a sample row in the table (displayed using Python):
{'fen': b'\xa3\xf1\x00g@\x00\x18`\x10\x10\x80\x00',
'score': 4083,
'depth': 35,
'move': 1800}
(2) By SeverKetor on 2025-07-17 18:58:56 in reply to 1.0 [link] [source]
Start by looking at the query plans (in the CLI, add EXPLAIN QUERY PLAN before your query and it'll give you a summary of what it'll do). You can post the results here too so people have more info to go on
(3) By Keyka Vigiliant (kekavigi) on 2025-07-17 23:38:31 in reply to 2 [link] [source]
Okay, here is the EXPLAIN QUERY PLAN result for the first version of SELECT:
QUERY PLAN
|--SEARCH board USING INDEX ix_covering (depth=? AND score>?)
`--USE TEMP B-TREE FOR ORDER BY
While the following is for SELECT with CTE:
QUERY PLAN
|--SEARCH board USING PRIMARY KEY (fen=?)
`--LIST SUBQUERY 2
|--SEARCH board USING COVERING INDEX ix_covering (depth=? AND score>?)
`--USE TEMP B-TREE FOR ORDER BY
I'm still unable to interpret why the CTE version is faster, even though it contains the same sub-plan(?) as the simple (first) version.
(4.1) By DrkShadow (drkshadow) on 2025-07-18 01:36:58 edited from 4.0 in reply to 1.0 [link] [source]
This is probably the optimization use-case: it doesn't need to read the table data if all of the data is in the index, and your WITHOUT ROWID probably makes this happen.
Disclaimer: I'm mostly guessing. I don't know.
Consider the CTE expression,
CREATE TABLE ... PRIMARY KEY (fen) WITHOUT ROWID
CREATE INDEX ... ON board (depth, score);
The CTE grabs things according to the depth and score - which you've indexed. It can use those to get the indexed row of the table -- which you've defined to be fen -- and order by fen. Then choose ten.
All of this can come from the one index that you've created, sqlite just pounces over the value-range of that index and sums together the rows that match your where clause. Yay. Put these in a list, order, and choose ten.
With those ten, do a table-lookup to get all four values: fen, score, depth, and move.
Compare instead the full query,
SELECT fen, score, depth, move
FROM board
WHERE <indexed>
ORDER BY..
Now you have to select move - which isn't in any index. You have to read the full row from the table, in a random-read fashion (if you ANALYZE the table it may give you a full table scan for speed) and this incurs your cost. It's a random table scan (SEARCH board USING PRIMARY KEY), and if the number of matches for the score-range are more than 25% of the table, it'll be slower than a full table scan. It does this so that it can read all requested values - scores, depth, fen, AND move, for all matching (scores, depth), AND THEN and only after reading all this data, from the table data on disk, selecting ten rows at random.
It's kind of an interesting case. If you made the table WITH rowid I suspect you would see similar (slower) performance with both queries. (Partly: fen, being a blob instead of an INTEGER PRIMARY KEY, would not be the rowid -- so it wouldn't be in the index. The CTE version would have to read the row from disk - all rows matching the range, by rowid, just as the full query does.) Again: I don't know, I'm just guessing.
(5) By punkish on 2025-07-19 13:55:47 in reply to 4.1 [link] [source]
Disclaimer: I'm mostly guessing. I don't know.
For a guess (and, even compared to most not-a-guess replies), this is one of the best darn explanations I've read and learned a few things for my own future table design. Thanks.
(7.1) By Keyka Vigiliant (kekavigi) on 2025-07-20 11:53:42 edited from 7.0 in reply to 4.1 [link] [source]
I got curious about your guess, and created an experiment to try it out; but first, I need to delete all rows with depth<20 as I don't have much storage left. Then I created the following new database
PRAGMA journal_mode = wal;
PRAGMA synchronous = off;
PRAGMA temp_store = memory;
PRAGMA mmap_size = 30000000000;
PRAGMA busy_timeout = 10000;
PRAGMA wal_autocheckpoint;
CREATE TABLE board(
fen BLOB NOT NULL,
depth INTEGER NOT NULL,
score INTEGER NOT NULL,
move INTEGER
);
ATTACH DATABASE 'original.sqlite' as orig;
INSERT INTO board (fen, depth, score, move)
SELECT fen, depth, score, move
FROM orig.board WHERE TRUE;
CREATE INDEX ix_covering ON board (depth, score);
After running ANALYZE, I tried to measure the execution time of full-query(?) SELECT, and SELECT using CTE, in both databases. Here are the results (time in seconds):
N=10
original db, full query mean:82.298 std:5.392
original db, using cte mean:0.156 std:0.005
db with rowid, full query mean:0.215 std:0.011
db with rowid, using cte mean:71.169 std:2.150
From these results it seems that the full query SELECT in the table with rowid is just as fast, as SELECT using CTE in the table without rowid.
The fast execution time for full-query SELECT on table with rowid makes sense to me. Reading the documentation pages Query Planning, I assume SQLite would perform a binary search(es?) on ix_covering to get a list of rowids with depth=35 AND score>100, then do a binary search on the board table of all rowids in that list, while extracting the fen, score, depth, move data.
My thinking is that SELECT using CTE on a table without rowid basically does the same thing (and this is supported by their similar execution times).
Query Planning ΒΆ WITHOUT ROWID tables also said "The basic principals described above apply to both ordinary rowid tables and WITHOUT ROWID tables. The only difference is that the rowid column that serves as the key for tables and that appears as the right-most term in indexes is replaced by the PRIMARY KEY." This makes sense because the EXPLAIN QUERY PLAN result for the full query SELECT on the table with rowid
QUERY PLAN
|--SEARCH board USING INDEX ix_covering (depth=? AND score>?)
`--USE TEMP B-TREE FOR ORDER BY
is same as the plan of the full query SELECT on the table without rowid (see post 99658a5440d6815e). But the fact that execution times of full-query SELECT on rowid vs without rowid are so different makes me confused.
(8.2) By DrkShadow (drkshadow) on 2025-07-20 15:20:09 edited from 8.1 in reply to 7.1 [link] [source]
Very nice. Admittedly, I don't understand all of it, but I did just notice one thing..
QUERY PLAN
|--SEARCH board USING INDEX ix_covering (depth=? AND score>?)
`--USE TEMP B-TREE FOR ORDER BY
is the "full" select, and indexed by lacking the CTE expression, and
|--SEARCH board USING PRIMARY KEY (fen=?)
`--LIST SUBQUERY 2
|--SEARCH board USING COVERING INDEX ix_covering (depth=? AND score>?)
`--USE TEMP B-TREE FOR ORDER BY
The difference here is: ix_covering. In the full select, it is, in fact, NOT a COVERING expression. However, in the CTE it is. This means that my theory is half right: it's getting all the information that it needs from the index, pulling together all of those values, sorting, taking the top-10, and then pulling full rows from the table-data (disk) to get fen and move.
In the full-select, it's doing the same, except without a covering index: read the index for matches, read the table-data(disk) data for *all of those rows, order all of those, and take the top-10.
I'm unsure how fen or the row-id works into this. I'm unsure why, when selecting fen, you get a covering index, when fen isn't in the index. (But fen is the rowid in the WITHOUT ROWID table, so it should be returned by the index .... but only if it's a without rowid table? which is why I don't understand your test. I don't doubt it, I just don't understand it.)
The output from EXPLAIN gives byte-code for the queries, and they're small so it shouldn't be too hard to parse, to see what it's doing differently (everything) or where it stops early in the CTE case, or where it gets that ROWID from in the WITH ROWID case. It would be interesting, but I'm personally not good with the byte-code, so I'd have to let someone else comment there.
Ohh I see, rather than making the full select fast with/without rowid (you can't -- it needs the move column, and it always fetches all matching rows, and it can't use a covering index for that), the CTE becomes slow WITH ROWID:
CREATE TABLE board(
fen BLOB NOT NULL,
);
CREATE INDEX..
WITH eligible AS (
SELECT fen FROM board
WHERE depth=35 AND score >= 100
ORDER BY RANDOM()
LIMIT 10
)
SELECT fen, score, depth, move
FROM board
WHERE fen IN eligible
---
-- I expect this query to now be slow, because fen is no longer part of the index,
-- and you will not get a COVERING INDEX in the query plan
You might also JOIN eligible ON board.fen=eligible.fen and see what happens, but I suspect it won't change anything.
(9) By Keyka Vigiliant (kekavigi) on 2025-07-20 16:20:05 in reply to 8.2 [link] [source]
Ah wow, thanks, I just realized the COVERING expression only appears in the query plan of SELECT using CTE. Thanks also for the theory you wrote, because it makes me curious and want to experiment.
Here are the results of EXPLAIN for both versions of SELECT, in each database:
original db (without rowid), full query select
addr opcode p1 p2 p3 p4 p5 comment
---- ------------- ---- ---- ---- ------------- -- -------------
0 Init 0 32 0 0 Start at 32
1 OpenEphemeral 1 6 0 k(1,B) 0 nColumn=6
2 Integer 10 1 0 0 r[1]=10; LIMIT counter
3 OpenRead 0 2 0 k(1,) 0 root=2 iDb=0; board
4 OpenRead 2 5161525 0 k(3,,,) 0 root=5161525 iDb=0; ix_covering
5 Integer 35 2 0 0 r[2]=35
6 Integer 100 3 0 0 r[3]=100
7 SeekGE 2 24 2 2 0 key=r[2..3]
8 IdxGT 2 24 2 1 0 key=r[2]
9 Column 2 2 4 0 r[4]= cursor 2 column 2
10 NotFound 0 23 4 1 0 key=r[4]
11 Function 0 0 5 random(0) 0 r[5]=func()
12 Sequence 1 6 0 0 r[6]=cursor[1].ctr++
13 IfNotZero 1 17 0 0 if r[1]!=0 then r[1]--, goto 17
14 Last 1 0 0 0
15 IdxLE 1 23 5 1 0 key=r[5]
16 Delete 1 0 0 0
17 Column 2 2 7 0 r[7]= cursor 2 column 2
18 Column 2 1 8 0 r[8]= cursor 2 column 1
19 Column 2 0 9 0 r[9]= cursor 2 column 0
20 Column 0 3 10 0 r[10]= cursor 0 column 3
21 MakeRecord 5 6 11 0 r[11]=mkrec(r[5..10])
22 IdxInsert 1 11 5 6 0 key=r[11]
23 Next 2 8 0 0
24 Sort 1 31 0 0
25 Column 1 5 10 0 r[10]=move
26 Column 1 4 9 0 r[9]=depth
27 Column 1 3 8 0 r[8]=score
28 Column 1 2 7 0 r[7]=fen
29 ResultRow 7 4 0 0 output=r[7..10]
30 Next 1 25 0 0
31 Halt 0 0 0 0
32 Transaction 0 0 8 0 1 usesStmtJournal=0
33 Goto 0 1 0 0
original db (without rowid), select using CTE
addr opcode p1 p2 p3 p4 p5 comment
---- ------------- ---- ---- ---- ------------- -- -------------
0 Init 0 42 0 0 Start at 42
1 OpenRead 3 2 0 k(1,) 2 root=2 iDb=0; sqlite_autoindex_board_1
2 BeginSubrtn 0 2 0 subrtnsig:2,A 0 r[2]=NULL
3 Once 0 29 0 0
4 OpenEphemeral 4 1 0 k(1,B) 0 nColumn=1; Result of SELECT 2
5 Noop 10000 3 0 0 Bloom filter
6 OpenEphemeral 5 3 0 k(1,B) 0 nColumn=3
7 Integer 10 4 0 0 r[4]=10; LIMIT counter
8 OpenRead 6 5161525 0 k(3,,,) 0 root=5161525 iDb=0; ix_covering
9 Integer 35 5 0 0 r[5]=35
10 Integer 100 6 0 0 r[6]=100
11 SeekGE 6 23 5 2 0 key=r[5..6]
12 IdxGT 6 23 5 1 0 key=r[5]
13 Function 0 0 7 random(0) 0 r[7]=func()
14 Sequence 5 8 0 0 r[8]=cursor[5].ctr++
15 IfNotZero 4 19 0 0 if r[4]!=0 then r[4]--, goto 19
16 Last 5 0 0 0
17 IdxLE 5 22 7 1 0 key=r[7]
18 Delete 5 0 0 0
19 Column 6 2 9 0 r[9]= cursor 6 column 2
20 MakeRecord 7 3 10 0 r[10]=mkrec(r[7..9])
21 IdxInsert 5 10 7 3 0 key=r[10]
22 Next 6 12 0 0
23 Sort 5 28 0 0
24 Column 5 2 12 0 r[12]=fen
25 MakeRecord 12 1 11 A 0 r[11]=mkrec(r[12])
26 IdxInsert 4 11 12 1 0 key=r[11]
27 Next 5 24 0 0
28 NullRow 4 0 0 0
29 Return 2 3 1 0
30 Rewind 4 41 0 0
31 Column 4 0 1 0 r[1]= cursor 4 column 0
32 IsNull 1 40 0 0 if r[1]==NULL goto 40
33 SeekGE 3 40 1 1 0 key=r[1]
34 IdxGT 3 40 1 1 0 key=r[1]
35 Column 3 0 13 0 r[13]= cursor 3 column 0
36 Column 3 2 14 0 r[14]= cursor 3 column 2
37 Column 3 1 15 0 r[15]= cursor 3 column 1
38 Column 3 3 16 0 r[16]= cursor 3 column 3
39 ResultRow 13 4 0 0 output=r[13..16]
40 Next 4 31 0 0
41 Halt 0 0 0 0
42 Transaction 0 0 8 0 1 usesStmtJournal=0
43 Goto 0 1 0 0
experiment db (with rowid), full query select
addr opcode p1 p2 p3 p4 p5 comment
---- ------------- ---- ---- ---- ------------- -- -------------
0 Init 0 31 0 0 Start at 31
1 OpenEphemeral 1 6 0 k(1,B) 0 nColumn=6
2 Integer 10 1 0 0 r[1]=10; LIMIT counter
3 OpenRead 0 2 0 4 0 root=2 iDb=0; board
4 OpenRead 2 5972116 0 k(3,,,) 0 root=5972116 iDb=0; ix_covering
5 Integer 35 2 0 0 r[2]=35
6 Integer 100 3 0 0 r[3]=100
7 SeekGE 2 23 2 2 0 key=r[2..3]
8 IdxGT 2 23 2 1 0 key=r[2]
9 DeferredSeek 2 0 0 0 Move 0 to 2.rowid if needed
10 Function 0 0 4 random(0) 0 r[4]=func()
11 Sequence 1 5 0 0 r[5]=cursor[1].ctr++
12 IfNotZero 1 16 0 0 if r[1]!=0 then r[1]--, goto 16
13 Last 1 0 0 0
14 IdxLE 1 22 4 1 0 key=r[4]
15 Delete 1 0 0 0
16 Column 0 0 6 0 r[6]= cursor 0 column 0
17 Column 2 1 7 0 r[7]= cursor 2 column 1
18 Column 2 0 8 0 r[8]= cursor 2 column 0
19 Column 0 3 9 0 r[9]= cursor 0 column 3
20 MakeRecord 4 6 10 0 r[10]=mkrec(r[4..9])
21 IdxInsert 1 10 4 6 0 key=r[10]
22 Next 2 8 0 0
23 Sort 1 30 0 0
24 Column 1 5 9 0 r[9]=move
25 Column 1 4 8 0 r[8]=depth
26 Column 1 3 7 0 r[7]=score
27 Column 1 2 6 0 r[6]=fen
28 ResultRow 6 4 0 0 output=r[6..9]
29 Next 1 24 0 0
30 Halt 0 0 0 0
31 Transaction 0 0 3 0 1 usesStmtJournal=0
32 Goto 0 1 0 0
experiment db (with rowid), select using CTE
(This query doesn't seem to be relevant to my question, but I included it for the sake of completeness.)
addr opcode p1 p2 p3 p4 p5 comment
---- ------------- ---- ---- ---- ------------- -- -------------
0 Init 0 44 0 0 Start at 44
1 OpenRead 0 2 0 4 0 root=2 iDb=0; board
2 Rewind 0 43 0 0
3 Noop 0 0 0 0 begin IN expr
4 BeginSubrtn 0 1 0 subrtnsig:2,A 0 r[1]=NULL
5 Once 0 33 0 0
6 OpenEphemeral 3 1 0 k(1,B) 0 nColumn=1; Result of SELECT 2
7 Noop 10000 2 0 0 Bloom filter
8 OpenEphemeral 4 3 0 k(1,B) 0 nColumn=3
9 Integer 10 3 0 0 r[3]=10; LIMIT counter
10 OpenRead 2 2 0 3 0 root=2 iDb=0; board
11 OpenRead 5 5972116 0 k(3,,,) 0 root=5972116 iDb=0; ix_covering
12 Integer 35 4 0 0 r[4]=35
13 Integer 100 5 0 0 r[5]=100
14 SeekGE 5 27 4 2 0 key=r[4..5]
15 IdxGT 5 27 4 1 0 key=r[4]
16 DeferredSeek 5 0 2 0 Move 2 to 5.rowid if needed
17 Function 0 0 6 random(0) 0 r[6]=func()
18 Sequence 4 7 0 0 r[7]=cursor[4].ctr++
19 IfNotZero 3 23 0 0 if r[3]!=0 then r[3]--, goto 23
20 Last 4 0 0 0
21 IdxLE 4 26 6 1 0 key=r[6]
22 Delete 4 0 0 0
23 Column 2 0 8 0 r[8]= cursor 2 column 0
24 MakeRecord 6 3 9 0 r[9]=mkrec(r[6..8])
25 IdxInsert 4 9 6 3 0 key=r[9]
26 Next 5 15 0 0
27 Sort 4 32 0 0
28 Column 4 2 11 0 r[11]=fen
29 MakeRecord 11 1 10 A 0 r[10]=mkrec(r[11])
30 IdxInsert 3 10 11 1 0 key=r[10]
31 Next 4 28 0 0
32 NullRow 3 0 0 0
33 Return 1 5 1 0
34 Column 0 0 12 0 r[12]= cursor 0 column 0
35 Affinity 12 1 0 A 0 affinity(r[12])
36 NotFound 3 42 12 1 0 key=r[12]; end IN expr
37 Column 0 0 13 0 r[13]= cursor 0 column 0
38 Column 0 2 14 0 r[14]= cursor 0 column 2
39 Column 0 1 15 0 r[15]= cursor 0 column 1
40 Column 0 3 16 0 r[16]= cursor 0 column 3
41 ResultRow 13 4 0 0 output=r[13..16]
42 Next 0 3 0 1
43 Halt 0 0 0 0
44 Transaction 0 0 3 0 1 usesStmtJournal=0
45 Goto 0 1 0 0
(6) By Mike Castle (nexushoratio) on 2025-07-19 15:25:03 in reply to 1.0 [link] [source]
When I first saw just the subject, my initial thought was RANDOM() was being called each time rows were compared and confusing things. But after reading your code, I'm less sure.
What I have done for similar results is:
SELECT
RANDOM() as r, fen, score, depth, move
FROM board
WHERE depth = 35 AND score >= 1000
ORDER BY r
LIMIT 10
;
(10) By anonymous on 2025-07-21 07:25:11 in reply to 1.1 [link] [source]
May I ask a stupid question, please?
Do all these queries really generate 701.5M random numbers, sort them, and then select just 10?
Is it possible to generate 10 random numbers between 1 and 701.5M, and then use row_number() over() to select those 10 out of the "board" table, and not sort?
Would that be expected to be quicker? I tried an example on 2 million rows and I think it works but it takes 1-2 full seconds. But I know very little.
I realize you have to get each table row assocaited with a random number; but to a novice it seems odd to generate all those numbers and sort compared to generating ten and just numbering the rows sequentially without sorting.
Does it work differently in SQL somehow that makes it more efficient? Thank you.
(11) By Bo Lindbergh (_blgl_) on 2025-07-21 14:17:43 in reply to 10 [link] [source]
You would need to generate all the rows twice: once to count them (so you know what the range of your random numbers should be) and once again to select some of them.