diff options
Diffstat (limited to 'funtools/doc/pod/funindexes.pod')
| -rw-r--r-- | funtools/doc/pod/funindexes.pod | 215 |
1 files changed, 215 insertions, 0 deletions
diff --git a/funtools/doc/pod/funindexes.pod b/funtools/doc/pod/funindexes.pod new file mode 100644 index 0000000..e4cabaa --- /dev/null +++ b/funtools/doc/pod/funindexes.pod @@ -0,0 +1,215 @@ +=pod + +=head1 NAME + + + +B<Funindexes: Using Indexes to Filtering Rows in a Table> + + + +=head1 SYNOPSIS + + + + + +This document contains a summary of the user interface for +filtering rows in binary tables with indexes. + + + +=head1 DESCRIPTION + + + + + +Funtools Table Filtering allows rows in a +table to be selected based on the values of one or more columns in the +row. Because the actual filter code is compiled on the fly, it is very +efficient. For very large files (hundreds of Mb or larger), however, +evaluating the filter expression on each row can take a long time. Therefore, +funtools supports index files for columns, which are used automatically during +filtering to reduce dramatically the number of row evaluations performed. +The speed increase for indexed filtering can be an order of magnitude or +more, depending on the size of the file. + + +The funindex program creates a +index on column in a binary table. For example, to create an index +for the column pi in the file huge.fits, use: + + funindex huge.fits pi + +This will create an index named huge_pi.idx. + + +When a filter expression is initialized for row evaluation, funtools +looks for an index file for each column in the filter expression. If +found, and if the file modification date of the index file is later +than that of the data file, then the index will be used to reduce the +number of rows that are evaluated in the filter. When <A +HREF="./regions.html">Spatial Region Filtering is part of the +expression, the columns associated with the region checked for index +files. + + +If an index file is not available for a given column, then in general, +all rows must be checked when that column is part of a filter +expression. This is not true, however, when a non-indexed column is +part of an AND expression. In this case, only the rows that pass the +other part of the AND expression need to be checked. Thus, in some cases, +filtering speed can increase significantly even if all columns are not +indexed. + + +Also note that certain types of filter expression syntax cannot make +use of indices. For example, calling functions with column names as +arguments implies that all rows must be checked against the function +value. Once again, however, if this function is part of an AND +expression, then a significant improvement in speed still is possible +if the other part of the AND expression is indexed. + + +As an example, note below the dramatic speedup in searching a 1 Gb +file using an AND filter, even when one of the columns (pha) has no +index: + + +bynars-16: time fundisp huge.fits'[idx_use=0,idx_debug=1,pha=2348&&cir 4000 4000 1]' "x y pha" + x y pha +----------- ----------- ---------- + 3999.48 4000.47 2348 + 3999.48 4000.47 2348 + 3999.48 4000.47 2348 + 3999.48 4000.47 2348 + 3999.48 4000.47 2348 + 3999.48 4000.47 2348 + 3999.48 4000.47 2348 + 3999.48 4000.47 2348 + 3999.48 4000.47 2348 + 3999.48 4000.47 2348 + 3999.48 4000.47 2348 + 3999.48 4000.47 2348 + 3999.48 4000.47 2348 + 3999.48 4000.47 2348 + 3999.48 4000.47 2348 + 3999.48 4000.47 2348 +42.36u 13.07s 6:42.89 13.7% + +bynars-17: time fundisp huge.fits'[idx_use=1,idx_debug=1,pha=2348&&cir 4000 4000 1]' "x y pha" + x y pha +----------- ----------- ---------- +idxeq: [INDEF] +idxand sort: x[ROW 8037025:8070128] y[ROW 5757665:5792352] +idxand(1): INDEF [IDX_OR_SORT] +idxall(1): [IDX_OR_SORT] + 3999.48 4000.47 2348 + 3999.48 4000.47 2348 + 3999.48 4000.47 2348 + 3999.48 4000.47 2348 + 3999.48 4000.47 2348 + 3999.48 4000.47 2348 + 3999.48 4000.47 2348 + 3999.48 4000.47 2348 + 3999.48 4000.47 2348 + 3999.48 4000.47 2348 + 3999.48 4000.47 2348 + 3999.48 4000.47 2348 + 3999.48 4000.47 2348 + 3999.48 4000.47 2348 + 3999.48 4000.47 2348 + 3999.48 4000.47 2348 +1.55u 0.37s 1:19.80 2.4% + + +When all columns are indexed, the increase in speed can be even more dramatic: + +bynars-20: time fundisp huge.fits'[idx_use=0,idx_debug=1,pi=770&&cir 4000 4000 1]' "x y pi" + x y pi +----------- ----------- ---------- + 3999.48 4000.47 770 + 3999.48 4000.47 770 + 3999.48 4000.47 770 + 3999.48 4000.47 770 + 3999.48 4000.47 770 + 3999.48 4000.47 770 + 3999.48 4000.47 770 + 3999.48 4000.47 770 + 3999.48 4000.47 770 + 3999.48 4000.47 770 + 3999.48 4000.47 770 + 3999.48 4000.47 770 + 3999.48 4000.47 770 + 3999.48 4000.47 770 + 3999.48 4000.47 770 + 3999.48 4000.47 770 +42.60u 12.63s 7:28.63 12.3% + +bynars-21: time fundisp huge.fits'[idx_use=1,idx_debug=1,pi=770&&cir 4000 4000 1]' "x y pi" + x y pi +----------- ----------- ---------- +idxeq: pi start=9473025,stop=9492240 => pi[ROW 9473025:9492240] +idxand sort: x[ROW 8037025:8070128] y[ROW 5757665:5792352] +idxor sort/merge: pi[ROW 9473025:9492240] [IDX_OR_SORT] +idxmerge(5): [IDX_OR_SORT] pi[ROW] +idxall(1): [IDX_OR_SORT] + 3999.48 4000.47 770 + 3999.48 4000.47 770 + 3999.48 4000.47 770 + 3999.48 4000.47 770 + 3999.48 4000.47 770 + 3999.48 4000.47 770 + 3999.48 4000.47 770 + 3999.48 4000.47 770 + 3999.48 4000.47 770 + 3999.48 4000.47 770 + 3999.48 4000.47 770 + 3999.48 4000.47 770 + 3999.48 4000.47 770 + 3999.48 4000.47 770 + 3999.48 4000.47 770 + 3999.48 4000.47 770 +1.67u 0.30s 0:24.76 7.9% + + + +The miracle of indexed filtering (and indeed, of any indexing) is due +to the speed of the binary search on the index, which is of order +log2(n) instead of n. (The funtools binary search method is taken from +http://www.tbray.org/ongoing/When/200x/2003/03/22/Binary, to whom +grateful acknowledgement is made.) This means that the larger the +file, the better the performance. Conversely, it also means that +for small files, using an index (and the overhead involved) can slow +filtering down somewhat. Our tests indicate that on a file containing +a few tens of thousands of rows, indexed filtering can be 10-20 +percent slower. Of course, your mileage will vary with conditions +(disk access speed, amount of available memory, process load, etc.) + + +Any problem encountered during index processing is supposed to result in +indexing being turned off, replaced by filtering all rows. You can turn +filtering off manually by setting the idx_use variable to 0 (in a filter +expression) or the FILTER_IDX_USE environment variable to 0 (in the global +environment). Debugging output showing how the indexes are being processed can +be displayed to stderr by setting the idx_debug variable to 1 (in a filter +expression) or the FILTER_IDX_DEBUG environment variable to 1 (in the global +environment). + + +Currently, indexed filtering only works with FITS binary tables and raw +event files. It does not work with text files. This restriction might be +removed in a future release. + + + +=head1 SEE ALSO + + + +See funtools(n) for a list of Funtools help pages + + + +=cut |