1
$\begingroup$

Say, I have a database table with $N$ columns. What is the (theoretical) maximum number of indices I can create on that table? For $N = 1,2,3$ it's easy enough to calculate the answer $(1, 4, 15)$, but is there any formula? Also, is there a "name" for this number?

$\endgroup$
  • $\begingroup$ This question is already asked, but on stackoverflow: stackoverflow.com/a/50025724/10502622 $\endgroup$ – NimaJan Jun 15 at 15:05
  • $\begingroup$ No, I'm not asking about "useful" indexes, I'm interested in maximum possible number of indexes. $\endgroup$ – planetp Jun 15 at 15:22
  • 1
    $\begingroup$ Where did you get 1,4,15 from? $\endgroup$ – D.W. Jun 15 at 20:05
  • $\begingroup$ @D.W. For 1 column, you can create one index apparently; for 2 columns, you can create indexes on columns 1 & 2 and combinations 1, 2 & 2, 1; and so on.. $\endgroup$ – planetp Jun 15 at 21:09
  • $\begingroup$ That sounds like it will lead to 1, 3, 15, not 1, 4, 15. $\endgroup$ – D.W. Jun 15 at 23:23
4
$\begingroup$

I assume you mean the following: given $N$ columns, there are

  • $N$ single columns, giving $N$ different indices
  • $N(N-1)/2$ pairs of columns, and 2 ways to combine each pair, giving $N(N-1)$ different indices
  • $\frac{N(N-1)(N-2)}{2 \cdot 3}$ triples of columns, and $3 \cdot 2$ ways to combine each triple, giving $N(N-1)(N-2)$ different indices

and so on. This number doesn't have a (well-known) name, but the sequence does have its own OEIS entry:

Eighteenth- and nineteenth-century combinatorialists call this the number of (nonnull) "variations" of n distinct objects, namely the number of permutations of nonempty subsets of {1,...,n}.

Various formulas are given to compute it, including a recurrence relation $a_n = n(a_{n-1} + 1)$ and the rather surprising $a_n = \lfloor{e \cdot n! - 1}\rfloor$.

One could argue that you can create more indices by taking into account that columns can be used in ascending and descending mode. For indices with more than one column, this even has an influence on which records are 'near' each other.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.