94
5
AT T R I B U T E S , I N D E X I N G , A N D Q U E R I E S
AND node
name = *.c
size > 35000
Figure 5-5 The parse tree for an AND query.
The process of iterating through all the values that match a particular
query piece (e.g., a simple expression like
size < 500
) begins by finding the
first matching item in the index associated with the query piece. In the case
of an expression like
size < 500
, the iteration routine first finds the value
500, then traverses backward through the leaf items of the index B+tree to
find the first value less than 500. If the traversal reaches the beginning of
the tree, there are no items less than 500, and the iterator returns an error
indicating that there are no more entries in this query piece. The iteration
over all the matching items of one query piece is complicated because only
one item is returned each iteration. This requires saving state between calls
to be able to restart the search.
Once a matching file is found for a given query piece, the query engine
must then travel back up the parse tree to see if the file matches the rest of
the query. If the query in question was
name == *.c && size > 35000
then the resulting parse tree would be as shown in Figure 5-5.
The query engine would first descend down the right half of the parse tree
because the
size > 35000
query piece is much less expensive to evaluate than
the
name = *.c
half. For each file that matches the expression
size > 35000
,
the query engine must also determine if it matches the expression
name =
*.c
. Determining if a file matches the rest of the parse tree does not use
other indices. The evaluation merely performs the comparison specified in
each query piece directly against a particular file by reading the necessary
attributes from the file.
The not-equal (
!=
) comparison operator presents an interesting difficulty
for the query iterator. The interpretation of what "not equal" means is nor-
mally not open to discussion: either a particular value is not equal to another
or it is. In the context of a query, however, it become less clear what the
meaning is.
Consider the following query:
MAIL:status == New && MAIL:reply_to != mailinglist@noisy.com
This is a typical filter query used to only display all email not from a mailing
list. The problem is that not all regular email messages will have a
Reply-To:
field in the message and thus will not have a
MAIL:reply to
attribute. Even if
Practical File System Design:The Be File System
, Dominic Giampaolo
page 94