Why an incorrect JOIN using correlated sub-query is so much slower

performancequery-performancesqlitesubquery

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 Problem

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.

The existing _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 EventHistory table:

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 _Games, Games and 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 EventHistory.

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 (EH.EventDate):

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 (EventHistory.EventDate):

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 (3.8.7.1 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 time function.

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 3.8.7.1 but no longer applies to SQLite 3.27.2.

(The 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).

Best Answer

The difference is in how the correlated subquery does the search.

The fast subquery looks like this:

select min(ID)
from EventHistory
where EventHistory.EventDate = ?

-- SEARCH TABLE EventHistory USING COVERING INDEX EventHistoryDateIndex (EventDate=?)

There is an index on EventDate, so the database can look up the matching rows in that index, and then remember and return only the smallest ID value.

The slow subquery looks like this:

select min(ID)
from EventHistory
where ? = ?

-- SEARCH TABLE EventHistory

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.

(There is the MIN/MAX optimization, but it works only when there is no WHERE clause.)

That you are inserting new rows into the tables has no effect on the speed. However, SQLite computes result rows on demand, if possible, so modifying tables while you are reading them can make the results inconsistent. You should read all results of the query first, or use a temporary table.

Related Solutions

When do I use another type index than integer? (eg string) [integer vs string index]

There are a lot of places internally where it is possible to reference data using a user id, which is better than a string. For example, if you had 4 tables referencing the user table, they'd each have a string column which is less efficient than 4 integer indexed columns. This is the reason why most schemas use this layout; you're more likely to want to reference a user than to refer to the user by name.

However, you can also set username to be an index, which you might want to do if you are looking it up a lot.

To answer your edited question, a 24 character text field will require roughly 24 bytes. Depending on whether it's a varchar or a char it will be stored differently, but the full amount will be needed for searching, so let's consider them both to be 24.

An integer field will require 4 bytes.

You can see how this will add up over time. For comparisons, assume a linear time comparison, meaning 24 operations to compare two a string field, while only 4 operations to compare an integer field. In practice, they will probably take roughly the same amount of time, though the string comparison cannot be faster.

If you want to search by username, create a table with the schema of username | user_id. That'll let you search by username and join with the other data you are looking for while still being efficient.

MYSQL Multiple Join Query to Display Unique Column Values in One Field for Single Record

Following what's already written at How to use GROUP_CONCAT in a CONCAT in mysql...

Let's assume you have a schema and sample data equivalent to:

CREATE TABLE properties
(
    id integer PRIMARY KEY,
    property varchar(255) NOT NULL
) ;

CREATE TABLE recommended_providers
(
   id integer PRIMARY KEY,
   recommended_provider_name varchar(255) NOT NULL
) ;

CREATE TABLE properties_recommended_providers
(
   prop_id INTEGER NOT NULL REFERENCES properties(id),
   recommended_provider_id INTEGER NOT NULL REFERENCES providers(id),
   PRIMARY KEY (prop_id, recommended_provider_id)
) ;

INSERT INTO properties
VALUES (1, 'property 1'), (2, 'property 2') ;

INSERT INTO recommended_providers
VALUES (1, 'provider 1'), (2, 'provider 2'), (3, 'provider 3');

INSERT INTO properties_recommended_providers
VALUES (1, 1), (1, 2), (2, 3) ;

You can either have:

SELECT
  p.id AS property_id, property, 
  GROUP_CONCAT(recommended_provider_name SEPARATOR ', ') AS provider_names
FROM
  properties p
  LEFT JOIN properties_recommended_providers pr ON pr.prop_id = p.id
  LEFT JOIN recommended_providers rp ON rp.id = pr.recommended_provider_id
GROUP BY
  property_id
ORDER BY
  property_id ;

(Check it at SQL Fiddle)

SELECT
  p.id AS property_id, property, 
  (SELECT
      GROUP_CONCAT(recommended_provider_name SEPARATOR ', ')  
   FROM
       properties_recommended_providers pr
       LEFT JOIN recommended_providers rp ON rp.id =
                                         pr.recommended_provider_id
   WHERE
       pr.prop_id = p.id
   ORDER BY
       /* You can easily order by in this case */
       recommended_provider_name
   ) AS provider_names
FROM
  properties p
ORDER BY
  property_id ;

You can check the second one at SQL Fiddle

Best Answer

Related Solutions

When do I use another type index than integer? (eg string) [integer vs string index]

MYSQL Multiple Join Query to Display Unique Column Values in One Field for Single Record

Related Question