Sqlite3: Need to Cartesian On date

Question

I have a table which is a list of games that have been played in a sqlite3 database. The field "datetime" is the a datetime of when game ended. The field "duration" is the number of seconds the game lasted. I want to know what percent of the past 24 hours had at least 5 games running simutaniously. I figured out to tell how many games running at a given time are:

select count(*)
from games
where strftime('%s',datetime)+0 >= 1257173442 and
      strftime('%s',datetime)-duration <= 1257173442

If I had a table that was simply a list of every second (or every 30 seconds or something) I could do an intentional cartisian product like this:

select count(*)
from (
  select count(*) as concurrent, d.second
  from games g, date d
  where strftime('%s',datetime)+0 >= d.second and
        strftime('%s',datetime)-duration <= d.second and
        d.second >= strftime('%s','now') - 24*60*60 and
        d.second <= strftime('%s','now')
  group by d.second) x
where concurrent >=5

Is there a way to create this date table on the fly? Or that I can get a similar effect to this without having to actually create a new table that is simply a list of all the seconds this week?

Thanks

Answer 1

Why don't you trim the date and keep only the time, if you filter your data for any given date every time is unique. In this way you'll only need a table with numbers from 1 to 86400 (or less if you take bigger intervals), you may create two columns, "from" and "to" to define the intervals. I'm not familiar with SQLite functions but according to the manual you have to use the strftime function with this format: HH:MM:SS.

Answer 2

First, I can't think of a way to approach your problem by creating a table on the fly or without the aid of an extra table. Sorry.

My suggestion is for you to rely on a static Numbers table.

Create a fixed table with the format:

CREATE TABLE Numbers (
    number INTEGER PRIMARY KEY
);

Populate it with the number of seconds in 24h (24*60*60 = 84600). I would use any scripting language to do that using the insert statement:

insert into numbers default values;

Now the Numbers table has the numbers 1 through 84600. Your query will them be modified to be:

select count(*)
  from (
        select count(*) as concurrent, strftime('%s','now') - 84601 + n.number second
          from games g, numbers n
         where strftime('%s',datetime)+0 >= strftime('%s','now') - 84601 + n.number and
               strftime('%s',datetime)-duration <= strftime('%s','now') - 84601 + n.number
         group by second) x
 where concurrent >=5

Without a procedural language in the mix, that is the best you'll be able to do, I think.

Answer 3

Great question!

Here's a query that I think gives you what you want without using a separate table. Note this is untested (so probably contains errors) and I've assumed datetime is an int column with # of seconds to avoid a ton of strftime's.

select sum(concurrent_period) from (
  select min(end_table.datetime - begin_table.begin_time) as concurrent_period
  from (
    select g1.datetime, g1.num_end, count(*) as concurrent
    from (
      select datetime, count(*) as num_end
             from games group by datetime
    ) g1, games g2
    where g2.datetime >= g1.datetime and
          g2.datetime-g2.duration < g1.datetime and
          g1.datetime >= strftime('%s','now') - 24*60*60 and
          g1.datetime <= strftime('%s','now')+0
  ) end_table, (
    select g3.begin_time, g1.num_begin, count(*) as concurrent
    from (
      select datetime-duration as begin_time,
             count(*) as num_begin
             from games group by datetime-duration
    ) g3, games g4
    where g4.datetime >= g3.begin_time and
          g4.datetime-g4.duration < g3.begin_time and
          g3.begin_time >= strftime('%s','now') - 24*60*60 and
          g3.begin_time >= strftime('%s','now')+0
  ) begin_table
  where end_table.datetime > begin_table.begin_time
        and begin_table.concurrent < 5
        and begin_table.concurrent+begin_table.num_begin >= 5
        and end_table.concurrent >= 5
        and end_table.concurrent-end_table.num_end < 5
  group by begin_table.begin_time
) aah

The basic idea is to make two tables: one with the # of concurrent games at the begin time of each game, and one with the # of concurrent games at the end time. Then join the tables together and only take rows at "critical points" where # of concurrent games crosses 5. For each critical begin time, take the critical end time that happened soonest and that hopefully gives all the periods where at least 5 games were running concurrently.

Hope that's not too convoluted to be helpful!

Answer 4

Kevin rather beat me to the punchline there (+1), but I'll post this variation as it differs at least a little.

The key ideas are

• Map the data in to a stream of events with attributes time and 'polarity' (=start or end of game)
• Keep a running total of how many games are open at the time of each event (this is done by forming a self-join on the event stream)
• Find the event times where the number of games (as Kevin says) transitions up to 5, or down to 4
• A little trick: add up all the down-to-4 times and take away the up-to-5s - the order is not important
• The result is the number of seconds spent with 5 or more games open

I don't have sqllite, so I've been testing with MySQL, and I've not bothered to limit the time window to preserve some sanity. Shouldn't be difficult to revise.

Also, and more importantly, I've not considered what to do if games are open at the beginning or end of the period!

Something tells me there's a big simplification to be had here, but I've not spotted it yet.

SELECT SUM( event_time )  
FROM (
SELECT  -ga.event_type * ga.event_time AS event_time,
    SUM(  ga.event_type * gb.event_type ) event_type
FROM
    ( SELECT UNIX_TIMESTAMP( g1.endtime - g1.duration ) AS event_time
          , 1 event_type
      FROM    games g1
      UNION
      SELECT UNIX_TIMESTAMP( g1.endtime )
          , -1
      FROM    games g1 ) AS ga,
    ( SELECT UNIX_TIMESTAMP( g1.endtime - g1.duration ) AS event_time
          , 1 event_type
      FROM    games g1
      UNION
      SELECT UNIX_TIMESTAMP( g1.endtime )
          , -1
      FROM    games g1 ) AS gb
WHERE
    ga.event_time >= gb.event_time
GROUP BY ga.event_time
HAVING SUM( ga.event_type * gb.event_type ) IN ( -4, 5 )
) AS gr