Determine the minimal indices needed to cover all queries
This challenge is based on Mongo's handling of compound indices and index intersection, inspired by a problem that came up at work, but I'll restate the relevant details here.
In any database, relational or not, the primary purpose of indices is to optimize data lookup.
For example, if the task of finding all code-golf questions on this site had to be accomplished by looping through all posts and looking for the
code-golf tag, it would be unusably slow. An index, however, organizes this data in a way that enables fast and efficient lookup of the data we want, which drastically reduces the resource cost of queries in exchange for some more work and space in maintaining the index.
However, the cost of maintaining indices is not negligible, so it quickly becomes untenable to create 2^N indices for N fields. (Databases designed for this purpose do exist and are the better choice when this functionality is actually needed. I'm ignoring this fact because it's a more interesting challenge this way.) Thus, careful index construction and selection is important to get the most bang for your buck.
A simple index only organizes data based on one field but Mongo provides two ways to efficiently query on more than one field: compound indices and index intersection.
Compound indices organize data based on a sequence of fields, e.g.
[A, B, C]. Here, order matters. If data is sorted by
C, then doing a lookup based on
C first cannot be done efficiently since there are no guarantees on where the desired data might be located within the index (whereas one could do e.g. a binary search based on
Note: compound indices enable efficient queries on prefixes of that index as well. That is, a compound index on
[A, B, C] enables efficient queries that have
[A, B], or
[A, B, C]. However, as previously mentioned, it does not support queries that have
[A, C], or
Exactly two indices can be used to optimize a query if there does not already exist a compound index for the desired fields. That is, if there is an index on
[A] and an index on
[B], then a query on
[A, B] can be executed fairly efficiently (though not as efficiently as if there was a compound index, but let's ignore that). This also applies to prefixes of indices, so an index on
[A, B, C] and an index on
[C] can be intersected to support a query with
Given N fields, determine the minimal indices needed to make all possible queries on those fields efficient. That is, minimize the total number of fields indexed. There may be more than one minimal set.
Note: the order of fields in the query doesn't matter since the query analyzer can reorder these fields to be as optimal as possible before running the query.
Input is a single positive integer and the output should consist of clearly-delimited sequences.
A variety of output formats are shown here to demonstrate what I mean by "clearly-delimited sequences".
[['A', 'B', 'C'], ['B', 'C'], ['C']]
['AB', 'BC', 'CA']
To elaborate on the first example in this N=3 case, the first index covers a query with all three fields, index intersections cover all choices of two fields, and index prefixes cover all queries with one field.
Note: for N=5, the obvious pattern does not hold; the indices
ABCDE BCDE CDE DE E do not enable an efficient query on
A, C, E.
I am really hoping this doesn't boil down to
[A, B, ..., X], [B, ..., X], [C, ..., X], ... [X]. I haven't taken a look at the N=4 case yet though so I don't know if this pattern holds.
Thankfully, the pattern breaks down for N=5.