Priority Queue with a Twist

Recently I needed a variation of a Priority Queue in C# that supported concurrency.

My requirement for a Priority Queue

  • I would receive a lot of jobs in a random order
  • A job would contain a JobNumber indicating in which order they should be executed
  • The first JobNumber would be zero
  • All JobNumbers would be present (e.g. number 7 would not be missing)
  • Several worker threads would¬†simultaneously¬†be retrieving jobs from the queue, hence the need for concurrency

The Solution

For the clarity of the example, I have simplified the Job class to look like:

public class Job
{
	public int jobNumber;
}

My Concurrent Priority Queue would look like:

class ConPQueue
{
	private const int TIMEOUT = 10000; // 10 seconds
	private SortedList<int, Job> list;
	private int nextJobNumber;
	private static EventWaitHandle waitHandle = new AutoResetEvent(false);
	private Boolean completeAdding = false;

	public ConPQueue()
	{
		this.list = new SortedList<int, Job>();
		this.nextJobNumber = 0;
	}

	public Boolean add(Job job)
	{
		Boolean status = false;
		if (Monitor.TryEnter(this.list, TIMEOUT))
		{
			try
			{
				this.list.Add(job.jobNumber, job);
				// Notify the take() method that new values are present
				waitHandle.Set();
			}
			finally
			{
				Monitor.Exit(this.list);
			}
		}
		return status;
	}

	public Job take()
	{
		Job job = null;
		while (job == null)
		{
			// If next job is not present, wait until notified
			// that new jobs have been added to the list
			while (!hasKey(this.nextJobNumber))
			{
				waitHandle.WaitOne();
			}
			if (Monitor.TryEnter(this.list, TIMEOUT))
			{
				try
				{
					this.list.TryGetValue(this.nextJobNumber, out job);
					if (job != null)
					{
						// Only remove item on successfull retrieval
						this.list.Remove(this.nextJobNumber++);
					}
				}
				finally
				{
					Monitor.Exit(this.list);
				}
			}
		}
		return job;
	}

	public Boolean hasKey(int Key)
	{
		Boolean exists = false;
		if (Monitor.TryEnter(this.list, TIMEOUT))
		{
			try
			{
				exists = this.list.ContainsKey(Key);
			}
			finally
			{
				Monitor.Exit(this.list);
			}
		}
		return exists;
	}

	public void addingComplete()
	{
		completeAdding = true;
	}

	public Boolean isCompleted
	{
		get { return completeAdding && list.Count == 0; }
	}
}

To add a Job to the Queue:

queue.take();

To retrieve a Job from the Queue:

queue.add(myJob);

Hope this can inspire fellow developers :-)

Mimicking a Materialized View in Oracle

I had a quite complex View in an Oracle database that performed quite badly and I needed to improve performance. I tried making a Materialized View, but didn’t like the restrictions, so I decided to mimic the behavior using a table.

Materialized Views

I decided to look at Materialized Views, but soon realized that there were a lot of restrictions for the SQL that can be used to generate a Materialized View. A Materialized View is great for replication of data and simple queries, but for complex queries there were too many restrictions – so I decided to mimic the functionality of a Materialized View…and it turned out to be quite simple. I know it is not the best solution since it is vulnerable to coding errors, but besides that, I think it is quite elegant :-)

I had six tables (Table_A, Table_B….Table_F) and one view to create a summary – let us call it “View_ABCDEF”.

Improve Performance

To improve performance, I did the following:

I create a new table named “Mimick_ABCDEF” with the same structure as View_ABCDEF and then changed by code to search in Mimick_ABCDEF instead of View_ABCDEF.

I then updated all locations that performs UPDATE, INSERT or DELETE on Table_A through Table_F to run the following two queries after the original query:

DELETE FROM Mimick_ABCDEF WHERE (col1, col2, .... coln) IN 
(SELECT * FROM Mimick_ABCDEF MINUS SELECT * FROM View_ABCDEF);

This query removes all rows present in the table but not in the view (happens on update and delete). This query does not work when some on the values are null, but should be quite simple to fix.

INSERT INTO Mimick_ABCDEF (SELECT * FROM View_ABCDEF MINUS SELECT * FROM Mimick_ABCDEF);

This query inserts all rows in the view, but not in the table, into the table.

Quite simple :-)