An improved policy enforcement architecture includes several components that improve the performance of policy enforcement in a hierarchical storage environment. A File System Query instruction permits a richer set of queries to be expressed by a policy engine, thereby permitting more complex policies to be implemented with ease. The File System result is generated at the file server, and only files of interest are forwarded to the policy engine. The file system query advantageously may be applied against a pre-generated index having one more characterizing attributes to further reduce the processing required to retrieve policy data. An Index Build instruction, added to a programming interface, allows a policy engine generate the characterizing indices in advance of use. Index maintenance techniques maintain consistency between the index and the file system to ensure that the policy can be enforced using accurate file information.