Re: Thinking About Correlated Columns (again) - Mailing list pgsql-performance

It's a very hard problem.  There's no way you can keep statistics about all possible correlations since the number of possibilities is O(N^2) with the number of columns.

We have an external search engine (not part of Postgres) for a domain-specific problem that discovers correlations dynamically and does on-the-fly alterations to its search plan.  Our queries are simple conjunctions (A & B & C ...), which makes "planning" easy: you can do indexes in any order you like.  So, the system watches each index's performance:

  1.  An index that's rarely rejecting anything gets demoted and eventually is discarded.
  2.  An index that's rejecting lots of stuff gets promoted.

Rule 1: If two indexes are strongly correlated, which ever happens to be first in the plan will do all the work, so the second one will rarely reject anything.  By demoting it to later in the plan, it allows more selective indexes to be examined first.  If  an index ends up rejecting almost nothing, it is discarded.

Rule 2: If an index rejects lots of stuff and you promote it to the front of the plan, then "anti-correlated" indexes (those that reject different things) tend to move to the front of the plan, resulting in very efficient indexing.

Typically, our query plans start with roughly 20-100 indexes.  The nature of our domain-specific problem is that the indexes are highly correlated (but it's impossible to predict in advance; each query causes unique correlations.)  Within a few thousand rows, it usually has dropped most of them, and finishes the query with 5-10 indexes that are about 95% as selective, but much faster, than the original plan.

But there are two caveats.  First, our particular query is a simple conjunction (A & B & C ...).  It's easy to shuffle the index orders around.

Second, databases tend to be non-homogeneous.  There are clusters of similar rows.  If you blindly optimize by going through a table in storage order, you may optimize strongly for a highly similar group of rows, then discover once you get out of that section of the database that your "optimization" threw out a bunch of indexes that would be selective in other sections of the database.  To solve this, you have to add a mechanism that examines the database rows in random order.  This tends to minimize the problem (although in theory it could still happen).

A more typical query (i.e. anything past a simple conjunction) would be much more difficult for a dynamic optimizer.