for each query in my codebase Q:
for each possible combination of indexes I for Q:
create hypothetical index I
run EXPLAIN query Q
if Q uses I, create I
Why not take this one step further and just enable an autoindexing mode in postgres using the query history as a heuristic?
What could be useful would be a generated report for all your queries with possible suggestions, grouping together queries with the same partial prefix columns, and the cardinality that each index would result in. Then one could manually review to look for the most significant improvements possible. I think a fully automated attempt (even built-in heuristics that modified indexes over time) would sometimes result in a bad decision being made that could theoretically crash your application. Perhaps with a few years of perfecting a solution this could become the norm. :)
Then there's the question of how often which queries are run, and how important their performance is. Maybe query X is run by some background process, so nobody will notice if it takes 10x longer, but indexing the table to speed it up will slow down the INSERT statements on that table, which are in the user's path and will be noticed. Maybe it would also tax limited disk space on the DB server and require a hardware upgrade or a complex multi-server setup to work.
Coming up with an optimal indexing scheme for any particular database is a series of complex trade-offs which include taking customer needs and business requirements into account. I don't think it will be practical to do it automatically anytime soon.
If you did end up making it, it should be named moby_dick.py.
What would be even cooler though is the ability to see multiple plans considered (and rejected) by the planner with all associated costs. It often takes a lot of painful guesswork to understand why particular superior plan is not used.
"When no indices are available to aid the evaluation of a query, SQLite might create an automatic index that lasts only for the duration of a single SQL statement. Since the cost of constructing the automatic index is O(NlogN) (where N is the number of entries in the table) and the cost of doing a full table scan is only O(N), an automatic index will only be created if SQLite expects that the lookup will be run more than logN times during the course of the SQL statement."
This is from the SQL server perspective so I apologize if all this doesn't translate 100%. Let's say the column you're filtering on is currently not in any index. That field then needs to be pulled out of the clustered index's leaf pages. Since it's unsorted, we'd need to read the entire table- a full scan.
To build the temporary index we'd also need to read in all of the data, so the same amount of work from that perspective, but then we'd have to sort it all, which is very intensive.
If there's a situation where we're doing something analogous to a inner loop join in SQL Server, but it's doing full scans for each iteration, that's a problem with the query optimizer.
Temporary index is a real index that's usually dynamically created by the optimizer to speed up a query. But it's kind of useless because most of the time the cost of creating a one-time index exceed the cost of not using it. Afaik only DB2 as this feature
http://www.centerfieldtechnology.com/PDFs/DB2%20Temp%20Index...
An hypotetical index is just a way to "trick" the planner into thinking that there's an index and see what the query plan would be if that index really existed. The cost of creating this is close to zero.
Obvious caveats: I would just have a 'top-level-post-id' so I could grab everything I need and use the foreign keys to arrange them in memory, not for discovering the rows I need, also wowzers doing _any_ joins without an index is silly, forget multiple in one query.
I'd love to see Postgres or MongoDB with an index-suggesting logger - I'd pay the cost of the logging to have it run on every query, then a background thread would figure out what the "hot spot" types of queries are, figure out what indices to create concurrently, and show it to me in a web interface where I can click a button and create the indices I need concurrently during a low-traffic period of time.
Does anything out there like this exist?
In postgres, a table's data is stored in the "heap" (a disk file representing the table, itself; indexes are separate disk files). Consequently, you can do a sequential pass through the table, and then calculate/build the index in RAM (assuming you have sufficient "maintenance_work_mem", in postgres configuration terms, otherwise you'll spill to disk at this step, too), and then write it out sequentially as well — and only then walk the index depth-first to get to the leaf page that points to the disk page in the heap that contains the row you're selecting.
(And even that random depth-first traversal of the index will probably actually happen in RAM, because postgres significantly defers to the kernel's buffer cache to mitigate IO costs, and the index you're traversing is pretty much guaranteed to be cached at this point.)
EDIT: It would apply to MySQL using InnoDB, however, as IIRC that does store table data on the leave pages of the primary key index. Can someone corroborate that?
SELECT ... FROM ... WHERE field IN ( SELECT field2 FROM ... )
MySQL doesn't acceptably optimize such queries (at v5.6, as far as I remember).
This is a more complex case than the one you're pointing - the field2 records may be an intermediate result, logically and/or physically.
For example of the latter, in a typical mysql execution with a relatively large number of records, the subquery records are likely to reside on a temporary swapped table. In this case, the optimizer would need to be able to create the intermediate table with optimal data structure[s], which (if I remember correctly) version 5.6 is not capable of.
It only creates virtual indices, whose only purpose is to observe how the query optimizer would behave, if they were real.
I find it quite a curious idea, although an important parameter of the indices is the cardinality, which I don't see customizable.
A hash table is a more effective data structure than a btree for in-memory search.
There is a LOT of efforts being made these days (like http://www.pgcon.org/2015/schedule/events/809.en.html for profiling) and eventually we'll see stuff not worse than commercial DBMSs have. I hope it will be soon.