# Implementing a Circular Buffer (Sliding window) in MySQL

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?
• Just as a curiosity, is there some business reason that you need the objects in the database, instead of cache? – MaddHacker Jul 5 '12 at 11:28
• It's an engineering dilemma, not a business. I favor a DB solution due to its persistence and native concurrency. – Adam Matan Jul 5 '12 at 12:13
• Yes, sorry. my mistake. – Adam Matan Jul 12 '12 at 5:36

Instead of a Trigger, how about a Stored Procedure?

Here is some sample data:

DROP DATABASE IF EXISTS 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.

• Thanks! Why did you add the SELECT SLEEP(10);? It's a big production drawback IMO. – Adam Matan Jul 8 '12 at 12:36
• Sorry about the Sleep call. I had 3 of these when I was debugging. I missed one. – RolandoMySQLDBA Jul 8 '12 at 12:46
• 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? – Adam Matan Jul 8 '12 at 13:24

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.