[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Cost-based optimiser for find

From: James Youngman
Subject: Cost-based optimiser for find
Date: Thu, 5 Jan 2006 17:09:53 +0000
User-agent: Mutt/1.5.9i

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
  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

Feedback would be appreciated.


reply via email to

[Prev in Thread] Current Thread [Next in Thread]