Performing efficient searches over two columns Disclaimer: I am extremely inexperienced with databases, so forgive me if this is an ignorant question.

I have a table which contains several columns, but the ones that are important are the columns containing timestamps and MAC addresses. I need to be able to quickly determine if a certain MAC address appears within a certain range of timestamps. For example lets say I need to see if MAC address 01:02:03:04:05:06 appears in any record on last Monday. Can this be done in sublinear time?

My intuition says that we can construct the timestamp range of interest in logarithmic time, but would we then need to linearly search over this subset of the data to determine if the desired MAC address appears, or can we search for the desired MAC address in logarithmic time?

Does this have anything to do with creating indices? Thanks for any help.
An index in 2 columns in the order (MACAddress, TimeStamp) will benefit any reasonable query construct for both


for a specific MAC address
for a MAC address within a range


Why?


The first query uses "equality" (= MacAddress)
The second uses "equality" then "inequality" (= MacAddress AND TimeStamp BETWEEN X and Y)


An RDBMS should traverse the index to find the MACAddress quickly, then looks with the subset for the time range.

It should be sublinear performance

Some reading to explain more (SQL Server specific)


https://www.toadworld.com/platforms/sql-server/w/wiki/9635.index-selectivity-and-column-order
https://stackoverflow.com/questions/797830/how-to-order-fields-on-index-creation-sql-server-2005