Postgresql table with one ID column, sorted index, with duplicate primary key

Question

I want to use a PostgreSQL table as a kind of work queue for documents. Each document has an ID and is stored in another, normal table with lots of additional columns. But this question is about creating the table for the work queue.

I want to create a table for this queue without OIDs with just one column: The ID of the document as integer. If an ID of a document exists in this work queue table, it means that the document with that ID is dirty and some processing has to be done. The extra table shall avoid the VACUUM and dead tuple problems and deadlocks with transactions that would emerge if there was just a dirty bit on each document entry in the main document table.

Many parts of my system would mark documents as dirty and therefore insert IDs to process into that table. These inserts would be for many IDs in one transaction. I don't want to use any kind of nested transactions and there doesn't seem to be any kind of INSERT IF NOT EXISTS command. I'd rather have duplicate IDs in the table. Therefore duplicates must be possible for the only column in that table.

The process which processes the work queue will delete all processes IDs and therefore take care of duplicates. (BTW: There is another queue for the next step, so regarding race conditions the idea should be clean and have no problem)

But also I want the documents to be processed in order: Always shall documents with smaller IDs be processed first.

Therefore I want to have an index which aids LIMIT and ORDER BY on the ID column, the only column in the workqueue table. Ideally given that I have only one column, this should be the primary key. But the primary key must not have duplicates, so it seems I can't do that.

Without the index, ORDER BY and LIMIT would be slow.

I could add a normal, secondary index on that column. But I fear PostgreSQL would add a second file on disc (PostgreSQL does that for every additional index) and use the double amount of disc operations for that table.

What is the best thing to do? Add a dummy column with something random (like the OID) in order to make the primary key not complain about duplicates? Must I waste that space in my queue table?

Or is adding the second index harmless, would it become kind of the primary index which is directly in the primary tuple btree?

---

Shall I delete everything above this and just leave the following? The original question is distracting and contains too much unrelated information.

I want to have a table in PostgreSQL with these properties:

• One column with an integer
• Allow duplicates
• Efficient ORDER BY+LIMIT on the column
• INSERTs should not do any query in that table or any kind of unique index. INSERTs shall just locate the best page for the main file/main btree for this table and just insert the row in between to other rows, ordered by ID.
• INSERTs will happen in bulk and must not fail, expect for disc full, etc.
• There shall not be additional btree files for this table, so no secondary indexes
• The rows should occupy not much space, e.g. have no OIDs

I cannot think of a solution that solves all of this.

My only solution would compromise on the last bullet point: Add a PRIMARY KEY covering the integer and also a dummy column, like OIDs, a timestamp or a SERIAL.

Another solution would either use a hypothetical INSERT IF NOT EXISTS, or nested transaction or a special INSERT with a WHERE. All these solutions would add a query of the btree when inserting. Also they might cause deadlocks.

(Also posted here: https://dba.stackexchange.com/q/45126/7788)

Answer 1

You said

Many parts of my system would mark documents as dirty and therefore insert IDs to process into that table. Therefore duplicates must be possible.

and

5 rows with the same ID mean the same thing as 1 or 10 rows with that same ID: They mean that the document with that ID is dirty.

You don't need duplicates for that. If the only purpose of this table is to identify dirty documents, a single row containing the document's id number is sufficient. There's no compelling reason to allow duplicates.

A single row for each ID number is not sufficient if you need to track which process inserted that row, or order rows by the time they were inserted, but a single column isn't sufficient for that in the first place. So I'm sure a primary key constraint or unique constraint would work fine for you.

Other processes have to ignore duplicate key errors, but that's simple. Those processes have to trap errors anyway--there are a lot of things besides a duplicate key that can prevent an insert statement from succeeding.

---

An implementation that allows duplicates . . .

create table dirty_documents (
  document_id integer not null
);

create index on dirty_documents (document_id);

Insert 100k ID numbers into that table for testing. This will necessarily require updating the index. (Duh.) Include a bunch of duplicates.

insert into dirty_documents 
select generate_series(1,100000);

insert into dirty_documents
select generate_series(1, 100);

insert into dirty_documents
select generate_series(1, 50);

insert into dirty_documents
select generate_series(88000, 93245);

insert into dirty_documents
select generate_series(83000, 87245);

Took less than a second on my desktop, which isn't anything special, and which is running three different database servers, two web servers, and playing a Rammstein CD.

Pick the first dirty document ID number for cleaning up.

select min(document_id) 
from dirty_documents; 

document_id
--
1

Took only 0.136 ms. Now lets delete every row that has document ID 1.

delete from dirty_documents
where document_id = 1; 

Took 0.272 ms.

Let's start over.

drop table dirty_documents;
create table dirty_documents (
  document_id integer primary key
);

insert into dirty_documents 
select generate_series(1,100000); 

Took 500 ms. Let's find the first one again.

select min(document_id) 
from dirty_documents; 

Took .054 ms. That's about half the time it took using a table that allowed duplicates.

delete from dirty_documents
where document_id = 1;

Also took .054 ms. That's roughly 50 times faster than the other table.

Let's start over again, and try an unindexed table.

drop table dirty_documents;
create table dirty_documents (
  document_id integer not null
);

insert into dirty_documents 
select generate_series(1,100000);

insert into dirty_documents
select generate_series(1, 100);

insert into dirty_documents
select generate_series(1, 50);

insert into dirty_documents
select generate_series(88000, 93245);

insert into dirty_documents
select generate_series(83000, 87245);

Get the first document.

select min(document_id) 
from dirty_documents; 

Took 32.5 ms. Delete those documents . . .

delete from dirty_documents
where document_id = 1;

Took 12 ms.

All of this took me 12 minutes. (I used a stopwatch.) If you want to know what performance will be, build tables and write tests.

Answer 2

Reading between the lines, I think you're trying to implement a work-queueing system.

Stop. Now.

Work queueing is hard. Work queuing in a relational DBMS is very hard. Most of the "clever" solutions people come up with end up serializing work on a lock without them realising it, or they have nasty bugs in concurrent operation.

Use an existing message/task queueing system. ZeroMQ, RabbitMQ, PGQ, etc etc etc etc. There are lots to choose from and they have the significant advantages of (a) working and (b) being efficient. You'll most likely need to run an external helper process or server, but the limitations of the relational database model tend to make that necessary.

The scheme you seem to be envisioning, as best as I can guess, sounds like it'll suffer from hopeless concurrency problems when it comes to failure handling, insert/delete races, etc. Really, do not try to design this yourself, especially when you don't have a really good grasp of the underlying concurrency and performance issues.