I'm doing some fairly lightweight data massaging/cleaning and ran into a problem where one version of JOIN using a correlated sub-query (probably an erroneous one) ran much much slower than what I believe is the correct one. I'm not asking how to do the query (I believe I've now got that correct), but I'd like to know why the slow version is so slow.
The domain is a fairly simple database to manage a Lottery Syndicate (recording members payments, games played and wins). In moving to a new engine (SQLite) I'm trying to clean the data and improve the tables' structure.
_Winnings table records the amounts and dates won and the "game type" (there are multiple games that could be played):
CREATE TABLE [_Winnings]( [ID] integer primary key not null, [WinDate] date, [Amount] integer, [GameType] integer references _Games(ID) ); CREATE INDEX [_WinningsIndex] on _Winnings(GameType) ;
The main problem is that there is no link (other than the date of the win) to the actual game played. Those records have already been migrated and are now held in an
CREATE TABLE [EventHistory]( [ID] integer primary key not null, [EventType] integer references Events(ID), [GameType] integer references Games(ID), [EventDate] date ); CREATE INDEX [EventHistoryEventIndex] on EventHistory(EventType) ; CREATE INDEX [EventHistoryGameIndex] on EventHistory(GameType) ; CREATE INDEX [EventHistoryDateIndex] on EventHistory(EventDate) ;
The three tables
Events hold the "type" of game/event and have essentially the following content:
_Games Games Events ID GameType ID GameType ID Name -- --------- -- --------- -- ---------- 1 GameName1 1 GameName1 5 Dispersal 2 GameName2 1 GameName2 6 Withdrawal 3 GameName3 1 GameName3 7 GamePlayed 4 GameName4 1 GameName4 8 MissingGame 5 Dispersal 6 Withdrawal
where the new tables split the "real" and "pseudo" game-types into their own table.
Sample data, showing the requirements of the migration process are:
_Winnings ID WinDate Amount GameType (Notes) --- ---------- ------ -------- ------------------------------- 123 2016-04-20 1234 1 A. Ideal match to "game played" record 167 2017-08-20 1000 1 B. "Missing" game 189 2018-12-20 990 1 C. Matches two games 199 2019-02-01 -2000 6 D. A non-game event (withdrawal) EventHistory ID EventType GameType EventDate (Notes) --- --------- -------- --------- ------------------------------- 111 7 (Game) 1 2016-04-20 Perfect match for (A) 222 7 (Game) 1 2017-08-15 \ No entry matches (B) 223 7 (Game) 1 2017-08-25 / 333 7 (Game) 1 2018-12-20 \ Two matches for (C) 334 7 (Game) 1 2018-12-20 /
Case (A) is the "normal" case: a game has been played, and there was a win. I will want the new
Winnings entry to refer directly to the matched event record.
Case (B) would indicate some error in the data (probably a mis-entered date-of-win, which I want to identify and deal with later by creating a "MissingGame" record in
Case (C) is valid, representing a double-entry on the same day. Matching either record in
EventHistory to the new record in
Winnings would be acceptable.
Case (D) is a "pseduo" game: winnings are either withdrawn or used to buy extra lines. Whether or not there is an existing, matching date-entry in
EventHistory, a new event record will be created.
My first attempt at finding matches used a left join on the dates (left-join, because there isn't guaranteed to be a date-match), but didn't take cases like (C) into account: multiple matching entries in
EventHistory give rise to duplicated values for
_Winnings.ID, which I mustn't have.
select W.*, EH.ID as EID, G.ID as GID from _Winnings as W left join EventHistory as EH on W.WinDate = EH.EventDate left join Games as G on W.GameType = G.ID
I therefore changed it to use a correlated sub-query, ensuring only one record from
EventHistory would be used (it doesn't really matter which record). In my first attempt, I mistakenly left a reference to the main-select's alias (
select W.*, EH.ID as EID, G.ID as GID from _Winnings as W left join EventHistory as EH on EH.ID = ( select min(ID) from EventHistory where W.WinDate = EH.EventDate ) left join Games as G on W.GameType = G.ID
This seemed to work, but exceedingly slowly. Replacing the alias with the full table-name (
select W.*, EH.ID as EID, G.ID as GID from _Winnings as W left join EventHistory as EH on EH.ID = ( select min(ID) from EventHistory where W.WinDate = EventHistory.EventDate ) left join Games as G on W.GameType = G.ID
dramatically improved the speed. With 365 records in
_Winnings, and starting with 494 records in
EventHistory (rising to 581 as some new records were added), the overall speed (including performing some inserts) dropped from over 3 minutes to around 3 seconds.
The "fast" query plan:
QUERY PLAN |--SCAN TABLE _Winnings AS W |--SEARCH TABLE EventHistory AS EH USING INTEGER PRIMARY KEY (rowid=?) |--CORRELATED SCALAR SUBQUERY 1 | `--SEARCH TABLE EventHistory USING COVERING INDEX EventHistoryDateIndex (EventDate=?) `--SEARCH TABLE Games AS G USING INTEGER PRIMARY KEY (rowid=?)
The "slow" query plan
QUERY PLAN |--SCAN TABLE _Winnings AS W |--SCAN TABLE EventHistory AS EH USING COVERING INDEX EventHistoryDateIndex |--CORRELATED SCALAR SUBQUERY 1 | `--SEARCH TABLE EventHistory `--SEARCH TABLE Games AS G USING INTEGER PRIMARY KEY (rowid=?)
Clearly, these are different, but I don't have the skill to understand what they are telling me.
What I am actually doing is processing each row as it is returned by the query and sometimes creating a new record in the
EventHistory table (and always creating a row in the migrated
Winnings table). Roughly, the process is:
foreach row returned by the query if EID or GID is empty -- either there isn't an exact date match (EID="") or -- the "game-type" is a "pseudo" game (GID=""). In either -- case, I want to insert a new row in EventHistory. insert new row in EventHistory table endif insert new row in Winnings table endfor
I originally thought that doing the inserts into
EventHistory was affecting the speed, since when I timed just the raw query (doing nothing with the results), there was no appreciable difference in speed between the two versions.
However, in the light of CL.'s answer, which included "That you are inserting new rows into the tables has no effect on the speed" I investigated further, and it appears the version of SQLite used may be the biggest factor in the speed difference.
I am using Tcl to script my update process (including the inserts), and this was where I originally saw the dramatic difference in speed between the two versions of the query. Tcl has it's own version of SQLite, which in my case was somewhat old (18.104.22.168 from October 2014).
However, when I first timed just the queries, I used a newly-downloaded version of the standalone SQLite shell (3.27.2 from February 2019). With this version, both queries ran at essentially the same rate (sub-second).
When I repeated the "query only" test in Tcl, using the older version of SQLite, the difference in speed was, again, dramatic: 8ms vs 2 minutes according to Tcl's
My conclusion is that:
The two values are constant (as far as the subquery is concerned), so either all rows of the table match, or none. But the query optimizer is not smart enough to recognize this, so it goes through all rows of the table and evaluates the WHERE clause each time.
from CL's answer does apply in the case of SQLite 22.214.171.124 but no longer applies to SQLite 3.27.2.
explain query plan output for each query remains the same in both versions of SQLite, but the VDBE steps shown by
explain do differ between SQLite versions).