Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Introducing HypoPG, hypothetical indexes for PostgreSQL

postgresql.org

Post reply on HN
Print view View original

31–38 of 38 posts

Re: Introducing HypoPG, hypothetical indexes for PostgreSQL

#31

Post by hendzen »

jackmaney wrote: post #30
hendzen wrote: post #28

Earlier quoted context omitted.

...Except the number of query plans is O(n!), where n is the number of joins. MongoDB's query optimizer actually works like this, which is only tractable because it doesn't support joins.

I was about to write "Ummm...column order doesn't matter, so it's O(2^n)", but then I did some thinking and a bit of googling, and I guess it does. Yeah, O(n!). Although, in practice, most tables would only have a relatively small number of columns upon which you'd want to consider building an index (usually on columns (often IDs) that you'd use to join to other tables), so that'd cut it down to O(m!) where m Hmmmm,…

Perhaps one could even use histograms to estimate selectivity of the query's join predicates to pick a good ordering of joins?

This is actually pretty much how a basic relational query optimizer works in practice.

Re: Introducing HypoPG, hypothetical indexes for PostgreSQL

#32

Post by ankrgyl »

makmanalp wrote: post #2

I'd always wondered why query engines don't create such temporary indices, for example in the case of large subquery queries, where creating and index AND doing the query with an index runs way faster in total than waiting for it to run without the index. Any insights on this? I guess predicting the gain could be difficult.

Most relatively mature database implementations do in fact apply this optimization. These databases have a component which can estimate the cost and benefit of such operations before running the query. The optimization that you mentioned turns out to be a no-brainer in most cases.

Re: Introducing HypoPG, hypothetical indexes for PostgreSQL

#33

Post by thirdsun »

makmanalp wrote: post #2

I'd always wondered why query engines don't create such temporary indices, for example in the case of large subquery queries, where creating and index AND doing the query with an index runs way faster in total than waiting for it to run without the index. Any insights on this? I guess predicting the gain could be difficult.

As far as I understand it FileMaker does this based on your searches/queries.

Re: Introducing HypoPG, hypothetical indexes for PostgreSQL

#34

Post by developer1 »

ninkendo wrote: post #27

So presumably you could do the following on your entire database: 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 If EXPLAIN doesn't actually run a query, and creating hypothetical indexes doesn't actually write anything, the above could presumably done in milliseconds, no? Why not take this one step further and j…

For the typical larger project, you'd wind up with hundreds of indexes each used by a single application query. The optimal index arrangement for a database often does not result in all columns being indexed on a query. It's normal and desirable (for index size and performance) to have fewer indexes that may only partially cover your queries. For example, a query with a WHERE of "a AND b AND c" is more often than not better handled with an index on (a) or (a, b) rather than (a, b, c). Especially if you have a second query with "a AND b AND d", you're most likely going to wind up with a single index for (a, b) rather than one for (a, b, c) and another for (a, b, d).

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. :)

Re: Introducing HypoPG, hypothetical indexes for PostgreSQL

#35

Post by [deleted] »

timdorr wrote: post #21
jedberg wrote: post #16

Combining this with just a bit of programming loops could get you pretty far at automatically creating indexes. Basically take a query plan and then create all possibly indexes hypothetically until you get the most optimal query.

Except PG index usage in the query plan is dependant on stats about the table (row count, width, etc). So, you would need to continually run it against production data and have it forever chase the perfect set of indices. If you did end up making it, it should be named moby_dick.py.

[deleted]

Re: Introducing HypoPG, hypothetical indexes for PostgreSQL

#36

Post by silon3 »

Jweb_Guru wrote: post #29
CaveTech wrote: post #23

Earlier quoted context omitted.

Or you tune for the best average execution time. Sample your queries and run them all through each query plan. One has to be optimal, unless all changes are negligible.

Even for a single query, the optimal query plan changes over time with the distribution of data in the table (and in other tables), as well as things like database load. There literally is not one best query plan, even with perfect information. Also, keep in mind that an abundance of even fake indices like this can have adverse effects on planner results by forcing it to consider more (and therefore, more suboptimal)…

And that's why people use NOSQL. It's much more predictable in production use.

Re: Introducing HypoPG, hypothetical indexes for PostgreSQL

#37

Post by ufmace »

ninkendo wrote: post #27

So presumably you could do the following on your entire database: 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 If EXPLAIN doesn't actually run a query, and creating hypothetical indexes doesn't actually write anything, the above could presumably done in milliseconds, no? Why not take this one step further and j…

There's more to deciding whether to create any particular index than just whether it makes any of your queries faster. Each index can speed up SELECTs, but it also slows down any write queries on those tables. Each index also takes up space on disk and memory.

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.

Re: Introducing HypoPG, hypothetical indexes for PostgreSQL

#38

Post by Jweb_Guru »

silon3 wrote: post #36
Jweb_Guru wrote: post #29

Earlier quoted context omitted.

Even for a single query, the optimal query plan changes over time with the distribution of data in the table (and in other tables), as well as things like database load. There literally is not one best query plan, even with perfect information. Also, keep in mind that an abundance of even fake indices like this can have adverse effects on planner results by forcing it to consider more (and therefore, more suboptimal)…

And that's why people use NOSQL. It's much more predictable in production use.

Er, no. It isn't. NoSQL solutions have exactly the same problems. Most just don't have query planners or statistics capable of understanding how to properly deal with the ever-changing data (and also frequently don't even have the indexing capabilities required to do much more than a single get or set efficiently, anyway--these problems tend to come up with larger queries).
Post reply on HN