This analysis is a good candidate for inclusion in a FAQ or similar
document.
On 9/5/2012 7:28 PM, Keith Medcalf wrote:
sqlite> create table alpha (frequency, term);
sqlite> create table beta (term, frequency);
sqlite> create index betaterm on beta(term);
sqlite> .explain
sqlite> explain query plan update alpha set frequency = (select frequency from
beta where beta.term >= alpha.term);
sele order from deta
---- ------------- ---- ----
0 0 0 SCAN TABLE alpha (~1000000 rows)
0 0 0 EXECUTE CORRELATED SCALAR SUBQUERY 0
0 0 0 SEARCH TABLE beta USING INDEX betaterm (term>?)
(~250000 rows)
sqlite> explain update alpha set frequency = (select frequency from beta where
beta.term >= alpha.term);
addr opcode p1 p2 p3 p4 p5 comment
---- ------------- ---- ---- ---- ------------- -- -------------
0 Trace 0 0 0 00
1 Goto 0 38 0 00
2 Null 0 1 2 00
3 OpenRead 0 2 0 2 00
4 Rewind 0 8 0 00
5 Rowid 0 2 0 00
6 RowSetAdd 1 2 0 00
7 Next 0 5 0 01
8 Close 0 0 0 00
9 OpenWrite 0 2 0 2 00
10 RowSetRead 1 36 2 00
11 NotExists 0 10 2 00
12 Null 0 3 4 00
13 Null 0 5 0 00
14 Integer 1 6 0 00
15 OpenRead 1 3 0 2 00
16 OpenRead 2 4 0 keyinfo(1,BINARY) 00
17 Column 0 1 7 00
18 IsNull 7 28 0 00
19 SeekGe 2 28 7 1 00
20 Column 2 0 8 00
21 IsNull 8 27 0 00
22 IdxRowid 2 8 0 00
23 Seek 1 8 0 00
24 Column 1 1 9 00
25 Move 9 5 1 00
26 IfZero 6 28 -1 00
27 Next 2 20 0 00
28 Close 1 0 0 00
29 Close 2 0 0 00
30 SCopy 5 3 0 00
31 Column 0 1 4 00
32 NotExists 0 33 2 00
33 MakeRecord 3 2 8 bb 00
34 Insert 0 8 2 alpha 05
35 Goto 0 10 0 00
36 Close 0 0 0 00
37 Halt 0 0 0 00
38 Transaction 0 1 0 00
39 VerifyCookie 0 3 0 00
40 TableLock 0 2 1 alpha 00
41 TableLock 0 3 0 beta 00
42 Goto 0 2 0 00
sqlite>
sqlite> explain query plan select alpha.term, beta.frequency from alpha, beta
where beta.term >= alpha.term;
SELECT item[0] = {0:1}
item[1] = {1:1}
FROM {0,*} = alpha
{1,*} = beta
WHERE GE({1:0},{0:1})
END
sele order from deta
---- ------------- ---- ----
0 0 0 SCAN TABLE alpha (~1000000 rows)
0 1 1 SEARCH TABLE beta USING INDEX betaterm (term>?)
(~250000 rows)
sqlite> explain select alpha.term, beta.frequency from alpha, beta where beta.term
>= alpha.term;
SELECT item[0] = {0:1}
item[1] = {1:1}
FROM {0,*} = alpha
{1,*} = beta
WHERE GE({1:0},{0:1})
END
addr opcode p1 p2 p3 p4 p5 comment
---- ------------- ---- ---- ---- ------------- -- -------------
0 Trace 0 0 0 00
1 Goto 0 22 0 00
2 OpenRead 0 2 0 2 00
3 OpenRead 1 3 0 2 00
4 OpenRead 2 4 0 keyinfo(1,BINARY) 00
5 Rewind 0 18 0 00
6 Column 0 1 1 00
7 IsNull 1 17 0 00
8 SeekGe 2 17 1 1 00
9 Column 2 0 2 00
10 IsNull 2 16 0 00
11 IdxRowid 2 2 0 00
12 Seek 1 2 0 00
13 Column 0 1 3 00
14 Column 1 1 4 00
15 ResultRow 3 2 0 00
16 Next 2 9 0 00
17 Next 0 6 0 01
18 Close 0 0 0 00
19 Close 1 0 0 00
20 Close 2 0 0 00
21 Halt 0 0 0 00
22 Transaction 0 0 0 00
23 VerifyCookie 0 3 0 00
24 TableLock 0 2 0 alpha 00
25 TableLock 0 3 0 beta 00
26 Goto 0 2 0 00
sqlite>
exactly the same except the update copy's the values or sets null if the seek
fails, whereas the join returns the join of all the matching beta rows in the
join instead of just the first result.
Of course, if you do not want to set alpha.frequency to null if there is no
match, then you need:
sqlite> explain update alpha set frequency = coalesce((select frequency from beta
where beta.term >= alpha.term), alpha.frequency);
addr opcode p1 p2 p3 p4 p5 comment
---- ------------- ---- ---- ---- ------------- -- -------------
0 Trace 0 0 0 00
1 Goto 0 40 0 00
2 Null 0 1 2 00
3 OpenRead 0 2 0 2 00
4 Rewind 0 8 0 00
5 Rowid 0 2 0 00
6 RowSetAdd 1 2 0 00
7 Next 0 5 0 01
8 Close 0 0 0 00
9 OpenWrite 0 2 0 2 00
10 RowSetRead 1 38 2 00
11 NotExists 0 10 2 00
12 Null 0 3 4 00
13 Null 0 5 0 00
14 Integer 1 6 0 00
15 OpenRead 1 3 0 2 00
16 OpenRead 2 4 0 keyinfo(1,BINARY) 00
17 Column 0 1 7 00
18 IsNull 7 28 0 00
19 SeekGe 2 28 7 1 00
20 Column 2 0 8 00
21 IsNull 8 27 0 00
22 IdxRowid 2 8 0 00
23 Seek 1 8 0 00
24 Column 1 1 9 00
25 Move 9 5 1 00
26 IfZero 6 28 -1 00
27 Next 2 20 0 00
28 Close 1 0 0 00
29 Close 2 0 0 00
30 SCopy 5 3 0 00
31 NotNull 3 33 0 00
32 Column 0 0 3 00
33 Column 0 1 4 00
34 NotExists 0 35 2 00
35 MakeRecord 3 2 8 bb 00
36 Insert 0 8 2 alpha 05
37 Goto 0 10 0 00
38 Close 0 0 0 00
39 Halt 0 0 0 00
40 Transaction 0 1 0 00
41 VerifyCookie 0 3 0 00
42 TableLock 0 2 1 alpha 00
43 TableLock 0 3 0 beta 00
44 Goto 0 2 0 00
With an index on beta.term it is O(n). Without an index it would be O(n*m).
The straight join is O(n*m) with or without an index.
I don't think there is any magic. It is simply the only way to implement the
update expressed.
---
() ascii ribbon campaign against html e-mail
/\ www.asciiribbon.org
-----Original Message-----
From: sqlite-users-boun...@sqlite.org [mailto:sqlite-users-
boun...@sqlite.org] On Behalf Of Yuriy Kaminskiy
Sent: Wednesday, 05 September, 2012 19:53
To: sqlite-users@sqlite.org
Subject: Re: [sqlite] classic update join question
Igor Tandetnik wrote:
On 9/5/2012 12:38 PM, E. Timothy Uy wrote:
I have a column in table 'alpha' which I would like to populate with data
from table 'beta'. As far as I know, we cannot do an UPDATE using JOIN in
sqlite, but we can
UPDATE alpha SET frequency = (SELECT frequency FROM beta WHERE
beta.term =
alpha.term)
Will the database really be doing a select in beta for
every single line in alpha?
Yes - same as when implementing a join. How do you think a join is
performed - black magic?
Subquery: O(n*log(m)), join: O(n+m). Magic!
Of course, query optimizer sometimes can rewrite subquery as join (or
opposite),
but I believe (unverified!) sqlite optimizer cannot do this currently.
_______________________________________________
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
_______________________________________________
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
_______________________________________________
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users