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

21–30 of 38 posts

Re: Introducing HypoPG, hypothetical indexes for PostgreSQL

#21

Post by timdorr »

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.

Re: Introducing HypoPG, hypothetical indexes for PostgreSQL

#22

Post by yangyang »

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.

Well that's pretty much what a hash join is doing - scan a table creating a hash table (effectively an in-memory index), then scan the inner table looking up values in the hash table.

A hash table is a more effective data structure than a btree for in-memory search.

Re: Introducing HypoPG, hypothetical indexes for PostgreSQL

#23

Post by CaveTech »

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.

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.

Re: Introducing HypoPG, hypothetical indexes for PostgreSQL

#24

Post by postila »

willu wrote: post #20

One of my major hang-ups about transitioning away from SQL Server to Postgres is the productivity that comes from tools like Profiler and Database Engine Tuning Advisor (which uses hypothetical indexes to find performance improvements). Can anyone suggest analogous tools for Postgres?

You should a couple of years more.

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.

Re: Introducing HypoPG, hypothetical indexes for PostgreSQL

#25

Post by postila »

postila wrote: post #24
willu wrote: post #20

One of my major hang-ups about transitioning away from SQL Server to Postgres is the productivity that comes from tools like Profiler and Database Engine Tuning Advisor (which uses hypothetical indexes to find performance improvements). Can anyone suggest analogous tools for Postgres?

You should a couple of years more. 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.

*wait

Re: Introducing HypoPG, hypothetical indexes for PostgreSQL

#27

Post by ninkendo »

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 just enable an autoindexing mode in postgres using the query history as a heuristic?

Re: Introducing HypoPG, hypothetical indexes for PostgreSQL

#28

Post by hendzen »

CaveTech wrote: post #23
timdorr wrote: post #21

Earlier quoted context omitted.

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.

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.

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

Re: Introducing HypoPG, hypothetical indexes for PostgreSQL

#29

Post by Jweb_Guru »

CaveTech wrote: post #23
timdorr wrote: post #21

Earlier quoted context omitted.

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.

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) cases with its limited budget.

Re: Introducing HypoPG, hypothetical indexes for PostgreSQL

#30

Post by jackmaney »

hendzen wrote: post #28
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.

...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, I wonder if you could use frequency information--or even the proportion of distinct values--of columns to guess a bit more intelligently...

Post reply on HN