Most existing content-based image retrieval systems built above a very large database typically compute a single descriptor per image, based for example on colour histograms. Therefore, these systems can only return images that are globally similar to the query image, but cannot return images that contain some of the objects that are in the query. Recent image processing techniques, however, focused on fine-grain image recognition to address the need of detecting similar objects in images. Fine-grain image recognition typically relies on computing many local descriptors per image. These techniques obviously increase the recognition power of retrieval systems, but also raise new problems in the design of fundamental lower-level functions such as indexes and secondary storage management. This paper addresses these problems: it shows that the three most efficient multi-dimensional indexing techniques known today do not efficiently cope with the deep changes in the retrieval process caused by the use of local descriptors. This paper also identifies several research directions to investigate before being able to build efficient image database systems supporting fine-grain recognition.