Cost-based optimiser for find

[James Youngman]

Find now has a rudimentary cost-based optimiser in findutils-4.3.1 and
later releases; you can see it in the current CVS code.  It is not
turned on by default.

The cost-based optimiser has an idea of the basic cost of each test
(i.e. that -name is very cheap while -size is more expensive).  It
re-orders tests bearing in mind the cost of each test and its likely
success.  Predicates with side effects (for example -delete or -exec)
are not reordered.  The optimiser is not yet enabled by default, but
the new option -O controls the query optimisation level.

To see this in action, try
  find -D opt -O3 . -type f -o -type c -o -size 555 -name Z
and compare the optimised query with:
  find -D opt -O3 . -size 555 -o -type c -o -type f -name Z
and
  find -D opt     . -size 555 -o -type c -o -type f -name Z

Over time, as optimisations are proven to be robust and correct, they
will be moved to lower optimisation levels.  Some optimisations have
always been performed by find (for example -name is always done early
if possible).

If these optimisations prove to be ineffective or it turns out that
the speed gain is negligible compared to the complexity, the
cost-based optimiser may be removed again.  However, the current
complexity is artificially inflated to a degree since the current code
needs to preserve the traditional behaviour when the -O option is not
used.

Feedback would be appreciated.

James.