funidx(7)

💖 NAME 💖

funidx — using indexes to filter rows in a table, bestie. That's it, that's the vibe.

---

✨ SYNOPSIS ✨

This doc is basically a lil rundown of the user interface for filtering rows in binary tables with indexes. Lowkey important, highkey slay.

---

🦋 DESCRIPTION 🦋

Okay so Funtools Table Filtering lets you pick rows out of a table based on the values of one or more columns in that row. And because the actual filter code gets compiled on the fly, it's very efficient — like, no cap. BUT. For very large files (hundreds of Mb or larger), evaluating the filter expression on every single row can take forever 😭. So funtools supports index files for columns, and these get used automatically during filtering to dramatically reduce the number of row evaluations it has to do. The speed increase for indexed filtering can be an order of magnitude or more, depending on how big the file is. It's giving glow-up fr fr.

The funindex program creates an index on one or more columns in a binary table. So like, say you wanna create an index for the column pi in the file huge.fits — you'd do:

funindex huge.fits pi

And that creates an index named huge_pi.idx. Iconic. ✨

When a filter expression is initialized for row evaluation, funtools goes looking for an index file for each column in the filter expression. If it finds one — and if the file modification date of the index file is later than that of the data file — then the index gets used to reduce the number of rows evaluated in the filter. And when Spatial Region Filtering is part of the expression, the columns associated with the region get checked for index files too. 👑

Now. If an index file is not available for a given column, then in general, all rows have to be checked when that column is part of a filter expression. HOWEVER — that's not true when a non-indexed column is part of an AND expression. In that case, only the rows that pass the other part of the AND expression need to be checked. So in some cases, filtering speed can increase significantly even if not all the columns are indexed. We love a loophole. 💅

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 though — 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. Slay.

---

🌸 The Dramatic Speedup Showcase 🌸

For example, peep the dramatic speedup in searching a 1 Gb file using an AND filter, even when one of the columns (pha) has no index:

time fundisp \
huge.fits'[idx_activate=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%

time fundisp \
huge.fits'[idx_activate=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%

And when all the columns are indexed, the increase in speed can be even more dramatic:

time fundisp \
huge.fits'[idx_activate=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%

time fundisp \
huge.fits'[idx_activate=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 (yes we're calling it that) 🧚

The miracle of indexed filtering (and honestly, of any indexing at all) is the speed of the binary search on the index, which is of order log2(n) instead of n. Like, that's the whole flex. 💅

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 the larger the file, the better the performance. But conversely, it also means that for small files, using an index (and all the overhead that comes with it) can actually slow filtering down somewhat. 😭 Our tests indicate that on a file containing a few tens of thousands of rows, indexed filtering can be 10 to 20 percent slower than non-indexed filtering. Of course, your mileage will vary with conditions (disk access speed, amount of available memory, process load, etc.). Every situation is different, bestie.

---

🎀 Turning It Off & Debugging 🎀

Any problem encountered during index processing will result in indexing being turned off, and replaced by filtering all rows. So like, it won't explode, it'll just be slow. 💀

You can turn filtering off manually by setting the idx_activate variable to 0 (in a filter expression) or the FILTER_IDX_ACTIVATE 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). Perfect for when you're nosy about what's going on in there. 🙈

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. So like, don't come for me about your .txt files. 😌

---

🌈 SEE ALSO 🌈

See funtools(7) for a list of Funtools help pages. Go read the whole fam, it's giving knowledge. 📚✨

---

Okay that's the whole page, mwah 💖 — this was version 1.4.5, dated April 14, 2011, from the SAORD Documentation crew, and it was funidx(7) the entire time. Periodt. 💅👑