Introduction

When dealing with very large FITS tables it may be useful to provide an index on the table contents so that FITS reading software can more quickly locate the rows in the table that contain the desired subset of information. This proposal describes a convention that may be used to define and store an index for any FITS binary or ASCII table. Strictly speaking this implementation deals only with sparse indexes to already sorted datasets; the provision of more general indexes, such as dense ones, or secondary indexes to a separate table, is beyond the current scope.

In the following discussion the FITS table that is being indexed is considered to contain a list of events where each row of the table corresponds to a single event and the columns of the table represent attributes which describe each event. In typical astrophysics applications the columns may give the time, spatial coordinate, and energy associated with each event. This proposal is intended to be very general and supports all of the following features:

• a 1-dimensional index on any single column of a table.
• a 2-dimensional index where the table events are sorted into a 2-D grid of bins based on the values in any 2 columns of the table.
• a n-dimensional index on an arbitrary number of event columns. In practice, there are probably few applications that will benefit from more than a 2-D index.
• the minimum and maximum value of any other table columns for all the events within each index bin may be specified. This is analogous to the feature in IRAF QPOE files which stores the minimum and maximum value of each attribute (e.g., X, Y, TIME, PHA, etc.) in large fixed-size 'buckets' of events. This allows software to quickly check if there are any events within the bin which meet a given search criterion without having to check every individual event. This feature may be espically useful in tables that are otherwise not indexed or sorted by any column except for the virtual 'row number' column which all tables inherently possess. (See example 6, below).
• tables need not be physically sorted, but instead may contain another column in the table which contains a pointer to the next event in that index bin (i.e., a linked list structure). Doubly-linked tables, with both forward and backward links, are also supported.
• the indexed event list does not need to be entirely contained in a single FITS table extension. The events may instead be sorted and subdivided into multiple FITS tables.
• the size of the index may be compressed by deleting any index bins which contain no events. This can make the index less convenient to use, but in some cases the space savings may be a more important consideration.