How to automatically generate indexes and preaggregations from queries

Question

This question might be a little ill-specified, but the idea I want to explore is:

1. User writes a bunch of queries that they want to perform over some data (for concreteness, just consider it a read-only database table)

2. The schema for the data is specified

Using this input, what data structures need to be generated to "efficiently" query the table? The program would read the input data and then generate a bunch of indexess/pre-aggregations so that the queries will be ultra fast.

For a really simple example, say I have a table of logs:

(URL, IP address, user agent, response code)

And I input a queries like:

select * where URL = http://foo

Then it should know to automatically generate an index on the URL field.

If I also specify:

select count(*) from table group by IP_address desc limit 20

or however you specify the 20 most common IP addresses, then it should also generate some pre-aggregation that is efficient (think of having 100 million rows).

I'm sure I am not specifying the problem completely, but I found some papers that seem related, i.e. http://scholar.google.com/scholar?cluster=1230153639822613926&hl=en&as_sdt=0,5

Looking for more references in this area. This is a computer science/algorithm question; I'm not looking for ways implement to implement this with MySQL or anything like that. Thanks.

Answer 1

Hmm...

You could use undirected multigraphs or alternative graph structures stacks (epicly space inefficient).