Implementing a Circular Buffer (Sliding window) in MySQL

Question

I intend to store some Java objects in a MySQL database, accompanied by a timestamp. These objects should be kept in a Sliding Window fashion (also known as Circular Buffer), meaning that only the last N items from a specific type should be kept.

My general idea is a an INSERT trigger:

DELETE FROM pixels WHERE type="type_of_new_pixel"
 AND id NOT IN 
 (SELECT id FROM pixels 
 WHERE type="type_of_new_pixel"
 ORDER BY timestamp DESC LIMIT N);

• Is triggger the right way to go? How do I add the trigger to the table?
• In order to increase performance, I would like to activate the trigger every M INSERTs. I will have some extra items in my list, but that's OK. How do I implement this? Will a id % 100 == 0 check do?

• MaddHacker: Just as a curiosity, is there some business reason that you need the objects in the database, instead of cache?
• Adam Matan: It's an engineering dilemma, not a business. I favor a DB solution due to its persistence and native concurrency.
• Adam Matan: Yes, sorry. my mistake.

Answer 1

Instead of a Trigger, how about a Stored Procedure?

Here is some sample data:

DROP DATABASE IF EXISTS adam_matan;
CREATE DATABASE adam_matan;
use adam_matan
CREATE TABLE pixels
(
 id int not null auto_increment,
 type VARCHAR(30),
 timestamp timestamp DEFAULT CURRENT_TIMESTAMP,
 pixel_data BLOB,
 PRIMARY KEY (id),
 KEY type_timestamp_id_ndx (type,timestamp,id)
);
INSERT INTO pixels (type,timestamp,pixel_data) VALUES
('type1',now() - INTERVAL FLOOR(RAND()*86400) SECOND,CONCAT('px',FLOOR(RAND()*899)+100)),
('type2',now() - INTERVAL FLOOR(RAND()*86400) SECOND,CONCAT('px',FLOOR(RAND()*899)+100)),
('type3',now() - INTERVAL FLOOR(RAND()*86400) SECOND,CONCAT('px',FLOOR(RAND()*899)+100)),
('type1',now() - INTERVAL FLOOR(RAND()*86400) SECOND,CONCAT('px',FLOOR(RAND()*899)+100)),
('type2',now() - INTERVAL FLOOR(RAND()*86400) SECOND,CONCAT('px',FLOOR(RAND()*899)+100)),
('type3',now() - INTERVAL FLOOR(RAND()*86400) SECOND,CONCAT('px',FLOOR(RAND()*899)+100)),
('type1',now() - INTERVAL FLOOR(RAND()*86400) SECOND,CONCAT('px',FLOOR(RAND()*899)+100)),
('type2',now() - INTERVAL FLOOR(RAND()*86400) SECOND,CONCAT('px',FLOOR(RAND()*899)+100)),
('type3',now() - INTERVAL FLOOR(RAND()*86400) SECOND,CONCAT('px',FLOOR(RAND()*899)+100)),
('type1',now() - INTERVAL FLOOR(RAND()*86400) SECOND,CONCAT('px',FLOOR(RAND()*899)+100)),
('type2',now() - INTERVAL FLOOR(RAND()*86400) SECOND,CONCAT('px',FLOOR(RAND()*899)+100)),
('type3',now() - INTERVAL FLOOR(RAND()*86400) SECOND,CONCAT('px',FLOOR(RAND()*899)+100)),
('type1',now() - INTERVAL FLOOR(RAND()*86400) SECOND,CONCAT('px',FLOOR(RAND()*899)+100)),
('type2',now() - INTERVAL FLOOR(RAND()*86400) SECOND,CONCAT('px',FLOOR(RAND()*899)+100)),
('type3',now() - INTERVAL FLOOR(RAND()*86400) SECOND,CONCAT('px',FLOOR(RAND()*899)+100)),
('type1',now() - INTERVAL FLOOR(RAND()*86400) SECOND,CONCAT('px',FLOOR(RAND()*899)+100)),
('type2',now() - INTERVAL FLOOR(RAND()*86400) SECOND,CONCAT('px',FLOOR(RAND()*899)+100)),
('type3',now() - INTERVAL FLOOR(RAND()*86400) SECOND,CONCAT('px',FLOOR(RAND()*899)+100)),
('type1',now() - INTERVAL FLOOR(RAND()*86400) SECOND,CONCAT('px',FLOOR(RAND()*899)+100)),
('type2',now() - INTERVAL FLOOR(RAND()*86400) SECOND,CONCAT('px',FLOOR(RAND()*899)+100)),
('type3',now() - INTERVAL FLOOR(RAND()*86400) SECOND,CONCAT('px',FLOOR(RAND()*899)+100)),
('type1',now() - INTERVAL FLOOR(RAND()*86400) SECOND,CONCAT('px',FLOOR(RAND()*899)+100)),
('type2',now() - INTERVAL FLOOR(RAND()*86400) SECOND,CONCAT('px',FLOOR(RAND()*899)+100)),
('type3',now() - INTERVAL FLOOR(RAND()*86400) SECOND,CONCAT('px',FLOOR(RAND()*899)+100));
SELECT * FROM pixels;

Here is it executed

mysql> SELECT * FROM pixels;
+----+-------+---------------------+------------+
| id | type | timestamp | pixel_data |
+----+-------+---------------------+------------+
| 1 | type1 | 2012年07月05日 00:47:02 | px338 |
| 2 | type2 | 2012年07月05日 07:20:24 | px178 |
| 3 | type3 | 2012年07月05日 09:03:07 | px337 |
| 4 | type1 | 2012年07月05日 06:34:06 | px323 |
| 5 | type2 | 2012年07月05日 15:58:22 | px403 |
| 6 | type3 | 2012年07月05日 01:00:47 | px267 |
| 7 | type1 | 2012年07月05日 16:08:21 | px541 |
| 8 | type2 | 2012年07月05日 06:10:06 | px687 |
| 9 | type3 | 2012年07月04日 16:35:29 | px994 |
| 10 | type1 | 2012年07月05日 16:21:52 | px116 |
| 11 | type2 | 2012年07月05日 14:14:51 | px449 |
| 12 | type3 | 2012年07月05日 00:03:50 | px307 |
| 13 | type1 | 2012年07月05日 13:37:46 | px890 |
| 14 | type2 | 2012年07月05日 15:01:37 | px676 |
| 15 | type3 | 2012年07月05日 15:29:27 | px334 |
| 16 | type1 | 2012年07月05日 11:43:37 | px266 |
| 17 | type2 | 2012年07月05日 08:02:11 | px261 |
| 18 | type3 | 2012年07月04日 19:47:46 | px771 |
| 19 | type1 | 2012年07月05日 12:26:28 | px619 |
| 20 | type2 | 2012年07月05日 06:51:44 | px323 |
| 21 | type3 | 2012年07月05日 15:03:14 | px575 |
| 22 | type1 | 2012年07月05日 04:54:36 | px821 |
| 23 | type2 | 2012年07月05日 02:26:48 | px543 |
| 24 | type3 | 2012年07月04日 22:56:23 | px236 |
+----+-------+---------------------+------------+
24 rows in set (0.00 sec)
mysql>

Here is the Stored Procedure

DELIMITER $$
DROP PROCEDURE IF EXISTS `adam_matan`.`AddPixel` $$
CREATE PROCEDURE `adam_matan`.`AddPixel`
(
 GivenType VARCHAR(20),
 GivenPixelData BLOB
)
BEGIN
 DECLARE KeepPixels INT;
 SET KeepPixels = 5;
 INSERT INTO pixels (type,pixel_data)
 VALUES (GivenType,GivenPixelData);
 DROP TABLE IF EXISTS pixel_window;
 CREATE TEMPORARY TABLE pixel_window
 (id INT NOT NULL PRIMARY KEY) ENGINE=MyISAM;
 SET @sqlstmt= CONCAT('INSERT INTO pixel_window ',
 'SELECT id FROM pixels WHERE type=''',GivenType,
 ''' ORDER BY id DESC LIMIT ',KeepPixels);
 PREPARE st FROM @sqlstmt;
 EXECUTE st;
 DEALLOCATE PREPARE st;
 SELECT * FROM pixels WHERE type=GivenType ORDER BY id; SELECT SLEEP(10);
 DELETE A.* FROM pixels A LEFT JOIN pixel_window B USING (id)
 WHERE A.type=GivenType AND B.id IS NULL;
 SELECT * FROM pixels WHERE type=GivenType ORDER BY id;
 DROP TABLE IF EXISTS pixel_window;
END $$
DELIMITER ;

Let's INSERT four rows of pixel data into type2

mysql> CALL AddPixel('type2',CONCAT('px',FLOOR(RAND()*899)+100));
+----+-------+---------------------+------------+
| id | type | timestamp | pixel_data |
+----+-------+---------------------+------------+
| 2 | type2 | 2012年07月05日 07:20:24 | px178 |
| 5 | type2 | 2012年07月05日 15:58:22 | px403 |
| 8 | type2 | 2012年07月05日 06:10:06 | px687 |
| 11 | type2 | 2012年07月05日 14:14:51 | px449 |
| 14 | type2 | 2012年07月05日 15:01:37 | px676 |
| 17 | type2 | 2012年07月05日 08:02:11 | px261 |
| 20 | type2 | 2012年07月05日 06:51:44 | px323 |
| 23 | type2 | 2012年07月05日 02:26:48 | px543 |
| 25 | type2 | 2012年07月05日 16:31:59 | px638 |
+----+-------+---------------------+------------+
9 rows in set (0.08 sec)
+----+-------+---------------------+------------+
| id | type | timestamp | pixel_data |
+----+-------+---------------------+------------+
| 14 | type2 | 2012年07月05日 15:01:37 | px676 |
| 17 | type2 | 2012年07月05日 08:02:11 | px261 |
| 20 | type2 | 2012年07月05日 06:51:44 | px323 |
| 23 | type2 | 2012年07月05日 02:26:48 | px543 |
| 25 | type2 | 2012年07月05日 16:31:59 | px638 |
+----+-------+---------------------+------------+
5 rows in set (10.23 sec)
Query OK, 0 rows affected (10.27 sec)
mysql> CALL AddPixel('type2',CONCAT('px',FLOOR(RAND()*899)+100));
+----+-------+---------------------+------------+
| id | type | timestamp | pixel_data |
+----+-------+---------------------+------------+
| 14 | type2 | 2012年07月05日 15:01:37 | px676 |
| 17 | type2 | 2012年07月05日 08:02:11 | px261 |
| 20 | type2 | 2012年07月05日 06:51:44 | px323 |
| 23 | type2 | 2012年07月05日 02:26:48 | px543 |
| 25 | type2 | 2012年07月05日 16:31:59 | px638 |
| 26 | type2 | 2012年07月05日 16:32:36 | px102 |
+----+-------+---------------------+------------+
6 rows in set (0.08 sec)
+----+-------+---------------------+------------+
| id | type | timestamp | pixel_data |
+----+-------+---------------------+------------+
| 17 | type2 | 2012年07月05日 08:02:11 | px261 |
| 20 | type2 | 2012年07月05日 06:51:44 | px323 |
| 23 | type2 | 2012年07月05日 02:26:48 | px543 |
| 25 | type2 | 2012年07月05日 16:31:59 | px638 |
| 26 | type2 | 2012年07月05日 16:32:36 | px102 |
+----+-------+---------------------+------------+
5 rows in set (10.25 sec)
Query OK, 0 rows affected (10.29 sec)
mysql> CALL AddPixel('type2',CONCAT('px',FLOOR(RAND()*899)+100));
+----+-------+---------------------+------------+
| id | type | timestamp | pixel_data |
+----+-------+---------------------+------------+
| 17 | type2 | 2012年07月05日 08:02:11 | px261 |
| 20 | type2 | 2012年07月05日 06:51:44 | px323 |
| 23 | type2 | 2012年07月05日 02:26:48 | px543 |
| 25 | type2 | 2012年07月05日 16:31:59 | px638 |
| 26 | type2 | 2012年07月05日 16:32:36 | px102 |
| 27 | type2 | 2012年07月05日 16:32:55 | px293 |
+----+-------+---------------------+------------+
6 rows in set (0.07 sec)
+----+-------+---------------------+------------+
| id | type | timestamp | pixel_data |
+----+-------+---------------------+------------+
| 20 | type2 | 2012年07月05日 06:51:44 | px323 |
| 23 | type2 | 2012年07月05日 02:26:48 | px543 |
| 25 | type2 | 2012年07月05日 16:31:59 | px638 |
| 26 | type2 | 2012年07月05日 16:32:36 | px102 |
| 27 | type2 | 2012年07月05日 16:32:55 | px293 |
+----+-------+---------------------+------------+
5 rows in set (0.15 sec)
Query OK, 0 rows affected (0.19 sec)
mysql> CALL AddPixel('type2',CONCAT('px',FLOOR(RAND()*899)+100));
+----+-------+---------------------+------------+
| id | type | timestamp | pixel_data |
+----+-------+---------------------+------------+
| 20 | type2 | 2012年07月05日 06:51:44 | px323 |
| 23 | type2 | 2012年07月05日 02:26:48 | px543 |
| 25 | type2 | 2012年07月05日 16:31:59 | px638 |
| 26 | type2 | 2012年07月05日 16:32:36 | px102 |
| 27 | type2 | 2012年07月05日 16:32:55 | px293 |
| 28 | type2 | 2012年07月05日 16:32:56 | px162 |
+----+-------+---------------------+------------+
6 rows in set (0.08 sec)
+----+-------+---------------------+------------+
| id | type | timestamp | pixel_data |
+----+-------+---------------------+------------+
| 23 | type2 | 2012年07月05日 02:26:48 | px543 |
| 25 | type2 | 2012年07月05日 16:31:59 | px638 |
| 26 | type2 | 2012年07月05日 16:32:36 | px102 |
| 27 | type2 | 2012年07月05日 16:32:55 | px293 |
| 28 | type2 | 2012年07月05日 16:32:56 | px162 |
+----+-------+---------------------+------------+
5 rows in set (0.16 sec)
Query OK, 0 rows affected (0.19 sec)
mysql>

If you want to keep another number, change the line KeepPixels = 5; to whatever number you need.

Give it a Try !!!

UPDATE 2012年07月05日 17:52 EDT

If you want to limit the DELETEs to every 100 INSERTs, here it is:

DELIMITER $$
DROP PROCEDURE IF EXISTS `adam_matan`.`AddPixel` $$
CREATE PROCEDURE `adam_matan`.`AddPixel`
(
 GivenType VARCHAR(20),
 GivenPixelData BLOB
)
TheStoredProcedure:BEGIN
 DECLARE KeepPixels,DeleteLimit,MaxID INT;
 SET KeepPixels = 5;
 SET DeleteLimit = 100;
 INSERT INTO pixels (type,pixel_data)
 VALUES (GivenType,GivenPixelData);
 SELECT MAX(ID) INTO MaxID FROM pixels;
 IF MOD(MaxID,DeleteLimit) > 0 THEN
 LEAVE TheStoredProcedure;
 END IF;
 DROP TABLE IF EXISTS pixel_window;
 CREATE TEMPORARY TABLE pixel_window
 (id INT NOT NULL PRIMARY KEY) ENGINE=MyISAM;
 SET @sqlstmt= CONCAT('INSERT INTO pixel_window ',
 'SELECT id FROM pixels WHERE type=''',GivenType,
 ''' ORDER BY id DESC LIMIT ',KeepPixels);
 PREPARE st FROM @sqlstmt; EXECUTE st; DEALLOCATE PREPARE st;
 SELECT * FROM pixels WHERE type=GivenType ORDER BY id; SELECT SLEEP(10);
 DELETE A.* FROM pixels A LEFT JOIN pixel_window B USING (id)
 WHERE A.type=GivenType AND B.id IS NULL;
 SELECT * FROM pixels WHERE type=GivenType ORDER BY id;
 DROP TABLE IF EXISTS pixel_window;
END $$
DELIMITER ;

You can change DeleteLimit to throttle DELETEs at any interval you want.

• Adam Matan: Thanks! Why did you add the SELECT SLEEP(10);? It's a big production drawback IMO.
• RolandoMySQLDBA: Sorry about the Sleep call. I had 3 of these when I was debugging. I missed one.
• Adam Matan: Great, thanks, I will remove it. Could you please elaborate on the CREATE TEMPORARY TABLE part - why is it preferred over a simple DELETE from the original table?

Answer 2

If your list of pixeltypes is fixed (or suppose you had an INSERT trigger on a table of pixeltypes), then you could use only UPDATEs instead of INSERT/DELETE. The trick is to know which row to update, but that would be done by updating the oldest one(s) each time.

So your INSERT trigger would insert N rows in your pixels table, just placeholders, with slightly different times.

Then when you need to change one of the pixels, you don't INSERT it, you UPDATE pixels SET... where lastupdatetime = (SELECT MIN(p_min.lastupdatetime) from pixels as p_min where p_min.type = pixels.type)

So now you don't have to think about having a separate DELETE process at all.