1. A computer-implemented method of generating statistics concerning index usage, the method comprising; receiving two or more queries against a relational database, the two or more queries received concurrently; executing a query plan corresponding to each of the received queries, each query plan having an associated index; incrementing a value of a first index counter of a plurality of index counters of the index every time the index is used during execution of a first query, each index counter of the plurality of index counters storing a value, wherein a total value obtained by adding the values of all of the plurality of index counters indicates a usage of the index, and wherein execution of the first query locks and holds the first index counter; incrementing a value of a second index counter of the plurality of index counters of the index when the index is used during execution of a second query, wherein the first query and the second query are concurrently executed, wherein contention between increments to any of the plurality of index counters is avoided such that multiple usages of the index may be recorded simultaneously; determining index usage statistics responsive to incrementing by adding the values of all of the plurality of index counters of the index, wherein index usage statistics include at least one of user seeks, user scans, user lookup, user updates, last user seek, last user scan, last user lookup, last user update, system seeks, system scan, system lookup or system update; and storing, in a memory, the index usage statistics in a header of the query plan.