HiveBrain v1.2.0
Get Started
← Back to all entries
patternsqlMinor

Implementing a Circular Buffer (Sliding window) in MySQL

Submitted by: @import:stackexchange-dba··
0
Viewed 0 times
triggersqlstackoverflowmysqldba
slidingcircularmysqlwindowimplementingbuffer

Problem

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?

Solution

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 WH

Code Snippets

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;
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>
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 ;
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)

+----+-------+---------------------+------
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 ;

Context

StackExchange Database Administrators Q#20036, answer score: 3

Revisions (0)

No revisions yet.