Skip to content

Ringbuffer in SQL

On a student platform we show on every page a random user in the upper right corner. Since we have over 11.000 users, the database has to select all matching users and sort them by random(). Thats very expensive and one of the longest running query in the current version.

Since we are currently redeveloping the whole platform, i decided to try something different for the random user. The user must not be really random, it should be enough to just display a different user every time the page is displayed. So my idea was to implement a ringbuffer in SQL and forward the pointer to the next user in the buffer if we need to search the next random user.


First some preparations:

CREATE SCHEMA ringbuffer;
-- create a dummy user table just for this example
CREATE TABLE ringbuffer.users (
id INT NOT NULL
UNIQUE
PRIMARY KEY,
username VARCHAR(20) NOT NULL
UNIQUE
) WITHOUT OIDS;
-- insert some dummy users into our dummy table
INSERT INTO ringbuffer.users (id, username) VALUES (6, 'user 6');
INSERT INTO ringbuffer.users (id, username) VALUES (1, 'user 1');
INSERT INTO ringbuffer.users (id, username) VALUES (2, 'user 2');
INSERT INTO ringbuffer.users (id, username) VALUES (3, 'user 3');
INSERT INTO ringbuffer.users (id, username) VALUES (4, 'user 4');
INSERT INTO ringbuffer.users (id, username) VALUES (5, 'user 5');


After this, create the ringbuffer:

-- now create the ringbuffer
-- we use a foreign key to the user table to assure we only insert
-- existing userIDs here
CREATE TABLE ringbuffer.ringbuffer (
id INT NOT NULL
UNIQUE
PRIMARY KEY,
value_id INT NOT NULL
REFERENCES ringbuffer.users(id),
next_id INT REFERENCES ringbuffer.ringbuffer(id)
) WITHOUT OIDS;

-- and an additional status table
CREATE TABLE ringbuffer.ringbuffer_data (
id INT NOT NULL
UNIQUE
PRIMARY KEY
CHECK (id = 1),
ringbuffer_id INT REFERENCES ringbuffer.ringbuffer(id),
max_id INT NOT NULL
DEFAULT 0
) WITHOUT OIDS;
INSERT INTO ringbuffer.ringbuffer_data
(id, ringbuffer_id, max_id)
VALUES (1, NULL, 0);
-- protect against deletes, nobody should delete your status entry
-- or the have more overhead in the functions
CREATE RULE ringbuffer_data_del
AS ON DELETE TO ringbuffer.ringbuffer_data
DO INSTEAD nothing;


And some supporting functions:

-- function for insert an user (respective the ID) into the buffer
CREATE OR REPLACE FUNCTION ringbuffer.insert_into_ringbuffer(insert_id INT)
RETURNS INTEGER
AS $$
DECLARE
query TEXT;
loop_record RECORD;
loop_record2 RECORD;
BEGIN
-- check that this entry is not yet in the ringbuffer table
query := 'SELECT COUNT(id) AS number_count
FROM ringbuffer.ringbuffer
WHERE value_id = ' || quote_literal(insert_id) || '';
EXECUTE query INTO loop_record;
IF loop_record.number_count > 0
THEN
RAISE NOTICE 'user is already in ringbuffer: %', insert_id;
ELSE
-- now check, if the data table is empty
query := 'SELECT *
FROM ringbuffer.ringbuffer_data
WHERE id = 1';
EXECUTE query INTO loop_record;
RAISE NOTICE 'max id: %', loop_record.max_id;
IF loop_record.max_id > 0
THEN
-- need the current last record
query := 'SELECT *
FROM ringbuffer.ringbuffer
WHERE id = ' || quote_literal(loop_record.max_id) || '';
EXECUTE query INTO loop_record2;
IF loop_record2.next_id < 1
THEN
RAISE EXCEPTION 'should have a next_id, but missing it';
END IF;
-- insert new record at end of table
RAISE NOTICE 'insert at end of table with id: %', loop_record.max_id + 1;
query := 'INSERT INTO ringbuffer.ringbuffer
(id, value_id, next_id)
VALUES (' || quote_literal(loop_record.max_id + 1) || ',
' || quote_literal(insert_id) || ',
' || quote_literal(loop_record2.next_id) || ')';
-- RAISE NOTICE 'query: %', query;
EXECUTE query;
-- update last record
query := 'UPDATE ringbuffer.ringbuffer
SET next_id=' || quote_literal(loop_record.max_id + 1) || '
WHERE id=' || quote_literal(loop_record.max_id) || '';
-- RAISE NOTICE 'query: %', query;
EXECUTE query;
-- update pointer table
query := 'UPDATE ringbuffer.ringbuffer_data
SET max_id = ' || quote_literal(loop_record.max_id + 1) || '
WHERE id = 1';
-- RAISE NOTICE 'query: %', query;
EXECUTE query;
ELSE
-- just insert as first value
RAISE NOTICE 'insert as first value into ringbuffer ...';
query := 'INSERT INTO ringbuffer.ringbuffer
(id, value_id, next_id)
VALUES (1, ' || quote_literal(insert_id) || ', 1)';
-- RAISE NOTICE 'query: %', query;
EXECUTE query;
-- update pointer table
query := 'UPDATE ringbuffer.ringbuffer_data
SET max_id = ' || quote_literal(loop_record.max_id + 1) || ',
ringbuffer_id = 1
WHERE id = 1';
-- RAISE NOTICE 'query: %', query;
EXECUTE query;
END IF;
END IF;

RETURN 1;
END;
$$
LANGUAGE 'plpgsql';

-- function for get next user from rungbuffer (the semi-random function)
CREATE OR REPLACE FUNCTION ringbuffer.get_next_ringbuffer()
RETURNS INTEGER
AS $$
DECLARE
query TEXT;
loop_record RECORD;
BEGIN
-- check, if the table is empty
query :='SELECT *
FROM ringbuffer.ringbuffer_data
WHERE id = 1';
EXECUTE query INTO loop_record;
-- RAISE NOTICE 'max id: %', loop_record.max_id;
IF loop_record.max_id IS NULL
THEN
RAISE NOTICE 'ringbuffer is empty!';
RETURN NULL;
ELSE
-- get the value the pointer is currently on
RAISE NOTICE 'get value from ringbuffer ...';
query := 'SELECT *
FROM ringbuffer.ringbuffer
WHERE id = (SELECT ringbuffer_id
FROM ringbuffer.ringbuffer_data
WHERE id = 1)';
-- RAISE NOTICE 'query: %', query;
EXECUTE query INTO loop_record;
RAISE NOTICE 'current value id: %', loop_record.value_id;
RAISE NOTICE 'next id: %', loop_record.next_id;
-- update pointer table
query := 'UPDATE ringbuffer.ringbuffer_data
SET ringbuffer_id=' || quote_literal(loop_record.next_id) || '
WHERE id = 1';
-- RAISE NOTICE 'query: %', query;
EXECUTE query;
-- return result
RETURN loop_record.value_id;
END IF;

RETURN NULL;
END;
$$
LANGUAGE 'plpgsql';

-- function for delete an user from ringbuffer
CREATE OR REPLACE FUNCTION ringbuffer.delete_from_ringbuffer(delete_id INT)
RETURNS INTEGER
AS $$
DECLARE
query TEXT;
loop_record_data RECORD;
loop_record RECORD;
loop_record2 RECORD;
BEGIN
-- check, if the table is empty
query :='SELECT *
FROM ringbuffer.ringbuffer_data
WHERE id = 1';
EXECUTE query INTO loop_record_data;
-- RAISE NOTICE 'max id: %', loop_record.max_id;
IF loop_record_data.max_id IS NULL
THEN
RAISE NOTICE 'ringbuffer is empty!';
RETURN NULL;
ELSE
-- get the value which should be deleted
-- RAISE NOTICE 'delete value from ringbuffer ...';
query := 'SELECT *
FROM ringbuffer.ringbuffer
WHERE value_id = ' || quote_literal(delete_id) || '';
-- RAISE NOTICE 'query: %', query;
EXECUTE query INTO loop_record;
IF loop_record.id IS NULL
THEN
-- nothing to delete
RETURN NULL;
END IF;
IF loop_record.id = loop_record.next_id
THEN
-- we only have this value, update pointer table
-- (next_id == id)
query := 'UPDATE ringbuffer.ringbuffer_data
SET ringbuffer_id = NULL,
max_id = 0
WHERE id = 1';
-- RAISE NOTICE 'query: %', query;
EXECUTE query;
ELSE
-- get the value which is referring us
query := 'SELECT *
FROM ringbuffer.ringbuffer
WHERE next_id = ' || quote_literal(loop_record.id) || '';
-- RAISE NOTICE 'query: %', query;
EXECUTE query INTO loop_record2;
-- now twist the pointer from last to the next record
query := 'UPDATE ringbuffer.ringbuffer
SET next_id = ' || quote_literal(loop_record.next_id) || '
WHERE id= ' || quote_literal(loop_record2.id) || '';
-- RAISE NOTICE 'query: %', query;
EXECUTE query;
IF loop_record_data.ringbuffer_id = loop_record.id
THEN
-- we are deleting the next entry
query := 'UPDATE ringbuffer.ringbuffer_data
SET ringbuffer_id = ' || quote_literal(loop_record.next_id) || ',
max_id = (SELECT MAX(next_id)
FROM ringbuffer.ringbuffer)
WHERE id = 1';
-- RAISE NOTICE 'query: %', query;
EXECUTE query;
ELSE
-- we are deleting another entry
query := 'UPDATE ringbuffer.ringbuffer_data
SET max_id = (SELECT MAX(next_id)
FROM ringbuffer.ringbuffer)
WHERE id = 1';
-- RAISE NOTICE 'query: %', query;
EXECUTE query;
END IF;

END IF;
-- delete the dataset
query := 'DELETE FROM ringbuffer.ringbuffer
WHERE id = ' || quote_literal(loop_record.id) || '';
-- RAISE NOTICE 'query: %', query;
EXECUTE query;
-- return deleted result
RETURN loop_record.value_id;
END IF;

RETURN NULL;
END;
$$
LANGUAGE 'plpgsql';


Now lets test this stuff:

SELECT ringbuffer.insert_into_ringbuffer((SELECT id
FROM ringbuffer.users
WHERE username='user 1'));
SELECT ringbuffer.insert_into_ringbuffer((SELECT id
FROM ringbuffer.users
WHERE username='user 2'));
SELECT ringbuffer.insert_into_ringbuffer((SELECT id
FROM ringbuffer.users
WHERE username='user 5'));
SELECT ringbuffer.insert_into_ringbuffer((SELECT id
FROM ringbuffer.users
WHERE username='user 4'));
SELECT ringbuffer.insert_into_ringbuffer((SELECT id
FROM ringbuffer.users
WHERE username='user 3'));
SELECT ringbuffer.insert_into_ringbuffer((SELECT id
FROM ringbuffer.users
WHERE username='user 6'));


SELECT * FROM ringbuffer.ringbuffer ORDER BY id;
SELECT * FROM ringbuffer.ringbuffer_data ORDER BY id;
SELECT ringbuffer.get_next_ringbuffer();
SELECT ringbuffer.get_next_ringbuffer();
SELECT ringbuffer.get_next_ringbuffer();
SELECT ringbuffer.get_next_ringbuffer();
SELECT ringbuffer.get_next_ringbuffer();
SELECT ringbuffer.get_next_ringbuffer();


As you can see, every time you call ringbuffer.get_next_ringbuffer(), you get another userID back, which will perfectly fit in a subselect to retrieve the actual userdata.

Neue Fischfabrik

Meine Freundin hat unser kleines Aquarium wieder in der Wohnstube aufgebaut. Seitdem wir das große Becken für unsere Schildkröten haben, stand dieses im Keller und war unbenutzt.

Nun, jetzt tummeln sich wieder einige Welse und Guppys dort drin, vor allem letztere sind ja für ein rasantes Wachstum bekannt ;-)

Invaluable treasures

Cleaning up the working room i found some old harddrives in a carton:

None of them was working on an USB-IDE connector (did not try the SCSI discs), but i will destroy them anyway. Smallest one is 1080 MB, biggest one 3400 MB.

Filterprobleme

Vor gar nicht allzulanger Zeit gab es ja ein neues Spielzeug, zusätzlich dazu hatten wir einen UV-Filter bestellt, so etwas will man ja haben.


Am Freitag kam nun der Anruf, das der Filter angekommen ist und ich den abholen könne. Marschierer Freundin und ich also abends in den Laden, die eine Verkäuferin sucht den Filter heraus und ich werde stutzig. Steht ein Aufkleber drauf mit einem Preis von 89,99€ ... Holla. Das sind nicht annähernd die "rund 35 Euro", die beim Bestellen meiner Freundin und mir gegenüber genannt wurden. Der Verkäufer, der das bestellt hat, hatte natürlich schon Feierabend. Also habe ich den Filter liegen gelassen mit der Bemerkung, dass sie ihrem Kollegen ausrichten kann, er solle zusehen, wie der Preis zu den 35€ wird.


Am Samstag erreicht mich nun ein weiterer Anruf, diesmal ist besagter Verkäufer persönlich am Telefon. Er hätte natürlich nie etwas von 35€ gesagt (wir waren auch nur zu zweit da und haben beide den Preis gehört) und könne mir den Filter höchstens für 49€ verkaufen, da würde ich noch ein Zitat: "absolutes Schnäppchen" machen.


Werde das wohl für den Preis kaufen, aber das habe ich davon, wenn man sich den Preis nicht gleich schriftlich zusichern lässt :-(

Die Sache mit dem Kleid

Freundin kommt mit ihrer Schwester nach Hause, setzt sich mir gegenüber hin und atmet durch. Denke ich mir schon: "Was kommt jetzt?"


"Schatz, bist du mir böse?" .o0( Auf was überhaupt)


"Wir haben ein Hochzeitskleid gesehen und das gleich gekauft."



Na nun gut, damit wäre dieses Problem wohl aus der Welt geschafft, zum Glück war ich beim Einkaufen nicht mit dabei.

f* Mysql

Today I woke up because the Nagios used by our isp sent me a sms: something does not work well on one of the association servers. According to the sms, the webserver was not responding. Ok, the webserver is never the cause of the problem, something else is going wrong.

 

Logged in over ssh, at least this works well. ps told me that the nightly database backup is hanging around, a script which fills some tables is also waiting. Mysql shell does not really work. Disc space? Ok, enough free space.

 

Shutting down webserver and database, killed all scripts hanging around and restarted the db. After a while, I got an error mail:

 

 

xxxxxxx.xxxxxx_gaestebuch
warning  : Table is marked as crashed and last repair failed
warning  : Size of indexfile is: 281307136      Should be: 267612160
error    : Found 5174283 keys of 5174282
error    : Corrupt

 

Nice ...

Ok, Let's repair the beast. myisamchk seems to work his way through the table, until I got this message:

 

myisamchk: warning: 301 records have been removed

 

So this wannabe database just deleted 301 datasets for whatever reason. Nice to see how data integrity is not handled at all.

 

I'm happy at all that the new platform is coming around, betatest just started yesterday. It's time to kick Mysql in the ass and use a real database.

Wo bekommt man Postkarten?

Wir wollen bei unseren Einladungen fertige Rückantwortkarten beilegen, bei denen die Gäste, die zur Hochzeit kommen wollen, nur noch ein paar Daten eintragen müssen.


Aber da begannen unsere Probleme: unser bevorzugter Büromaterialversand führt keine Postkarten. Die anderen beiden, die uns einfielen, ebenfalls nicht. Also sind wir losgezogen, die Schreibwarenläden zu erkunden. Im dritten Laden sind wir dann fündig geworden *puh*


Braucht denn niemand mehr ganz normale Postkarten oder erledigt man so etwas heute per Email?

Log Table Changes in PostgreSQL with tablelog

Ever had the need to know what happened with your data? Tablelog could be an answer.

The usage is easy: you create a second table which has the same format like your table you want to keep an eye on. Plus you need some additional columns to maintain the logged data.

But step by step:

First thing: you need the software. Get it from pgfoundry: http://pgfoundry.org/projects/tablelog/

Unpack the archive, join the table_log-version directory and type in:
"make -f Makefile.nocontrib".
This should work without problems. If you get an error about missing include files, please install the PostgreSQL development packages from your distribution.

If compilation was done successfully, install the library. You have to be a superuser to do that, so first become root with "su". Type in: "make -f Makefile.nocontrib install".
This will install the library into the PostgreSQL library directory.

Now we have to tell your database that we want to use tablelog, so make sure, you have support for plpgsql enabled (with createlang). Connect as a superuser to the database which contains your tables and execute the following commands (you can find them in the file table_log.sql):

-- create function
CREATE FUNCTION table_log ()
RETURNS TRIGGER
AS '$libdir/table_log' LANGUAGE 'C';
CREATE FUNCTION "table_log_restore_table" (VARCHAR, VARCHAR, CHAR, CHAR, CHAR, TIMESTAMPTZ, CHAR, INT, INT)
RETURNS VARCHAR
AS '$libdir/table_log', 'table_log_restore_table' LANGUAGE 'C';
CREATE FUNCTION "table_log_restore_table" (VARCHAR, VARCHAR, CHAR, CHAR, CHAR, TIMESTAMPTZ, CHAR, INT)
RETURNS VARCHAR
AS '$libdir/table_log', 'table_log_restore_table' LANGUAGE 'C';
CREATE FUNCTION "table_log_restore_table" (VARCHAR, VARCHAR, CHAR, CHAR, CHAR, TIMESTAMPTZ, CHAR)
RETURNS VARCHAR
AS '$libdir/table_log', 'table_log_restore_table' LANGUAGE 'C';
CREATE FUNCTION "table_log_restore_table" (VARCHAR, VARCHAR, CHAR, CHAR, CHAR, TIMESTAMPTZ)
RETURNS VARCHAR
AS '$libdir/table_log', 'table_log_restore_table' LANGUAGE 'C';


After this you may add some supporting functions which will make life more easy, you can find them in the file table_log_init.sql. Just paste the content into your database shell or include it using the \i command in psql.

Thats all, now you can use tablelog in your database.


Here's an example (taken from table_log.sql):

-- create demo table
CREATE TABLE test (
id INT NOT NULL
PRIMARY KEY,
name VARCHAR(20) NOT NULL
);

-- create the table without data from demo table
SELECT * INTO test_log FROM test LIMIT 0;
ALTER TABLE test_log ADD COLUMN trigger_mode VARCHAR(10);
ALTER TABLE test_log ADD COLUMN trigger_tuple VARCHAR(5);
ALTER TABLE test_log ADD COLUMN trigger_changed TIMESTAMPTZ;
ALTER TABLE test_log ADD COLUMN trigger_id BIGINT;
CREATE SEQUENCE test_log_id;
SELECT SETVAL('test_log_id', 1, FALSE);
ALTER TABLE test_log ALTER COLUMN trigger_id SET DEFAULT NEXTVAL('test_log_id');

-- create trigger
CREATE TRIGGER test_log_chg AFTER UPDATE OR INSERT OR DELETE ON test FOR EACH ROW
EXECUTE PROCEDURE table_log();

-- test trigger
INSERT INTO test VALUES (1, 'name');
SELECT * FROM test;
SELECT * FROM test_log;
UPDATE test SET name='other name' WHERE id=1;
SELECT * FROM test;
SELECT * FROM test_log;



You will see that the test_log table contains all changes which happened to the original table. If you want to avoid the overhead for creating the logtable, take a look into the support functions created by table_log_init.sql.

Ok, but what use would be the logging data if we have no good chance of using it?
So the next example will show you, how you can take a look into the state of your table at any time
in the past:

-- create restore table
SELECT table_log_restore_table('test', 'id', 'test_log', 'test_log_id', 'test_recover', NOW());
SELECT * FROM test_recover;


The meaning of the arguments, from left to right: name of the original table, primary key of the original table, name of the logging table, primary key of the logging table, recovery table to create by table_log_restore_table(), timestamp for the lookup. Some more arguments are available, take a look into the README for a full description.

Have fun with your table history.

If you want to provide feedback, you will find contact infos at the end of the README file.