Logic programming provides an ideal framework for tackling complex data, such as the multi-dimensional vector-based data used
to represent spatial databases. Unfortunately, the usefulness of logic programming systems if often hampered by the fact that
most of these systems have to rely on a single unification-based mechanism as the only way to search in the database. While
unification can usually take effective advantage of hash-based indexing, it is often the case that queries over more complex
and structured data, such as the vectorial terms stored in spatial databases, cannot.
We propose a new extension to Prolog indexing: User Defined Indexing (UDI). In this mechanism, the programmer may add extra
information to Prolog indices so that only interesting fragments of the database will be selected. UDI provides a general
extension of indexing, and can be used for both instantiated and constrained variables. As a test case, we demonstrate how
UDI can be combined with a constraint system to provide an elegant and efficient mechanism to generate and execute range queries
and spatial queries. Experimental evaluation shows that this mechanism can achieve orders of magnitude speedups on non-trivial
datasets.