Subject: Table Sort Keyword

From: pence at tetra.gsfc.nasa.gov (William Pence)
Date: Fri, 25 Jun 93 16:01:49 EDT

FITS tables (ASCII or BINTABLE) are often sorted on the value of one
or more columns in the table.  In order to most efficiently access the
data in these tables some software may need to know how the table was
sorted.  Thus it would be useful if we can define a header keyword(s)
which will specify how the table is sorted.

This subject has been discussed internally at the HEASARC (plus a
few others) and this posting is an attempt to summarize our preliminary
ideas.  We would appreciate further comments or ideas on this topic
from the the FITS community.

The basic idea is to have a keyword like:

TSORTKEY = 'X, Y, TIME'

Which lists the primary and secondary sort keys.  In this example, the
table is primarily sorted by the value of the X column, then all the
rows that have the same X value are sorted by Y, and finally all the
rows that have the same X and the same Y values are sorted by the TIME
values.

There was some discussion of alternate keyword names, e.g., TSORT, or
SORT, or SORTKEY, but TSORTKEY seemed to be acceptable to most people.

There was also some discussion of whether is was required to separate
the list of column names with commas, or whether just spaces would be
sufficient.  Most of us felt that it was safer to require commas.

Clive Page added that it was also necessary to specify whether the rows
were sorted in increasing, or decreasing order of the column value.  He
suggested the convention of placing a minus sign in front of the column
name to denote a descenting order sort, as in

TSORTKEY = '-X, Y, TIME'    / table is sorted in decreasing order of X

Tom McGlynn then offered alternative sorting keyword conventions
of the form

TSORT1   = 'FIELD1, DESCENDING'			/ Sort in descending order
TSORT2   = 'FIELD2  '
TSORT3   = 'FIELD3, SKIP=3,LENGTH=5'               / Use bytes 4-8 for the sort
..  here any information after the comma is ignored unless the reader
     knows how to handle it.

    or

SORT1   = 'FIELD1  '
SRTOP1  = 'DESCENDING'
..  here a reader can interpret the sort fields and need not worry 
     about parsine the options unles they are of interest.

While this is less concise than the original suggestion, it is perhaps
more generally extensible and more in keeping with existing FITS
conventions.

The previous example also raises the issue how one would specify that the
table was sorted on a substring of characters in an ASCII column, such as
sorting an 8A column on the last 4 character in the field. 
In the original scheme, perhaps this could be specified by:

TSORTKEY = 'NAME(5:8), X, Y' /sorted on the 5th thru 8th characters of the NAME column

A more basic question is whether it should even be allowed to sort a
column on a subpart of the field.  I don't think this is allowed in
general in relational databases.

A related issue is whether sorting of vector columns (with numeric
data) should be allowed.  Is there a well defined way to sort vectors?

Tom McGlynn also raised the question of whether one should have the
option to sort a numeric column in an ASCII table either by the
numerical order, OR by the ASCII sort order of the internal ASCII string
representation of the column.  Personnally, I don't think this option
should be allowed, and a table column should be sorted only based on
the implied data type of the TFORM column, and not by it's ASCII
internal representation.

Finally, one issue that was not discussed by us but would need to be
resolved is how to handle undefined elements in a table.  Presumably
all the NUL value fields should all appear either first or last in the
sorted order.

Any comments??