Present-day file systems do not provide an adequate interface for today’s petabyte scale data collections. File systems this large often contain many thousands of files in a single directory or have deep directory trees with excessively long paths. The commonly used POSIX file system interface was standardized in 1988 (as of this writing 21 years ago) and designed for file systems where the number of files per directory and the depth of directory trees were multiple orders of magnitude lower than today. Furthermore, just as on every large information system (such as the Web), finding and organizing files is becoming critical as the sizes of file systems grow. Common standard file system interfaces do not provide or support indexing and searching. Instead, search and navigation functionalities are typically implemented on the application level. In this paper, we present our case for addressing these problems on the file system interface level, introducing a new file system interface and query language. Changing current file system interfaces has to occur gradually, and any new file system interface design has to enable a gradual and backward-compatible transition from the current interface to the new one. We show that such a transition is built into our query language design.