Hands on: How to solve a speed-critical problem

Advertising exists to influence other people, not me. Yeah, right. A long while ago, I saw an elderly gentleman being interviewed about his preferred beverage and whether his choice was influenced by advertising. He said he drank Guinness not because of the advertising, but because it was good for him. Guinness’ PR agency must have been delighted.

I, however, feel able to confess: my eye was caught by the advertising campaign showing Vodafone’s Mobile Broadband USB stick zooming its rocket-powered way around the galaxy. So now I have one and have been playing with it, and it’s fabulous.

But what’s it got to do with databases? Client-server databases are great, because the required bandwidth is reduced: you send a tiny SQL string to a large complex database, the processing is done centrally and the database sends the answer back to you as a set of data. This is a huge advantage, especially for remote connectivity, and so the theory is that you don’t need much in the way of bandwidth to make a connection.

Unfortunately, though, the world is changing. First, databases often hold large collections of images. Several people have apparently died trying to download a 35MB image with a 56K modem. Second, it is increasingly common to administer and drive databases remotely, something I do all the time. All of which makes a high bandwidth connection essential no matter where you are ­ hence my interest in mobile broadband.

The VMBUSBS is a delightful device: it’s easy to install, works seamlessly with all the existing network gubbins on my laptop and picks up a signal automatically. For each session, all it asks is whether you want a connection: say ‘yes’ and away you rocket.

You can do all the usual tasks, such as pick up email and download files, as well as administer that database. The only problem with the VMBUSBS might be 3G coverage ­ where I live in the countryside, there is none ­ but in practice, it hasn’t been an issue because I only need mobile broadband when I’m away. In the cities I’ve visited, coverage has been good and the device is capable of swapping down to 2G if necessary.

You pay for the service, of course, starting from £15 per month for 3GB download (visit Vodafone for details). Still, the device could easily be worthwhile if you work away from base, especially given the variation in hotel internet connection prices (anything from free to £20 and more for a night). And however hard you try, you can’t use your hotel connection on a train.

I’m writing this at the enthusiastic early stage of our relationship, so I’ll also report on how it settles down in a month or three.

Slot machine
An interesting question came my way during some recent consultancy work. A factory has a heavily used machine, so its time is allocated using a booking system. (In practice, there are many machines, but we’ll simply consider one of them). Each eight-hour working day (9am to 5pm) is split into 32 quarter-hour slots.

The machine is bookable in multiples of 15 minutes, so, for example, it might be booked from 9.45am to 10am (slot four) or from 9.00am to 11am (slots one to eight). There is no requirement to record who has booked it, but an overriding requirement is that the speed of retrieval of the next available time slot must be blisteringly fast. In other words, people often ask: “When is it next available?” and/or “When is it next available for three-quarters of an hour?” and want the answer immediately.

A first design of the table is a nice normalised table, intuitively easy to understand and it’s very easy to query to find out, for example, if slot four is free or booked on the first of September. If the query:
SELECT BookingDate, SlotNo
FROM DefaultBookings
WHERE (BookingDate=#9/1/2008#) AND (SlotNo=4);
returns a value, then the slot is booked. (The SQL is using American date format.)

This works fine, but you have to know which slot you’re looking for before you run the query, and this isn’t the only sort of question outlined in the design brief. In fact, to answer the question “When is it next available?”, we have to query for values that aren’t in the table. A human can glance quickly at the table and see that the next free slot is three, but extrapolating missing values in a sequence will make for a slow query.

We could try inverting the logic behind the table design. We want to find free time slots, so let’s try storing the free slots and removing them from the table once they’re booked.

This makes it much easier to find the first empty slot. However, there is a second problem that neither solution solves. How do we answer the question: “When is it next available for three-quarters of an hour?” Suppose that we query the table and find that slot three is free. We then have to test to see if the subsequent two slots are also free.

The sticking point here is that there is no facility in standard SQL for identifying the ‘next’ row. Rows of data in a relational database are inherently unordered, so we cannot use the relative position of rows to retrieve the answers we need.

The solution I came up with is to stick with the idea of storing available slots, but change the way we store them.