2.18.1 Deep indexing

As introduced in section 2.18, deep indexing creates hash tables distinguish clauses that share a compound with the same name and arity. Deep indexes allow for efficient lookup of arbitrary terms. Without it is advised to flatten the term, i.e., turn F(X) into two arguments for the fact, one argument denoting the functor F and the second the argument X. This works fine as long as the arity of the each of the terms is the same. Alternatively we can use term_hash/2 or term_hash/4 to add a column holding the hash of the term. That approach can deal with arbitrary arities, but requires us to know that the term is ground (term_hash/2) or up to which depth we get sufficient selectivity (term_hash/4).

Deep indexing does not require this knowledge and leads to efficient lookup regardless of the instantiation of the query and term. The current version does come with some limitations:

• The decision which index to use is taken independently at each level. Future versions may be smarter on this.
• Deep indexing only applies to a single argument indexes (on any argument).
• Currently, the depth of indexing is limited to 7 levels.

Note that, when compiling DCGs (see section 4.13) and the first body term is a literal, it is included into the clause head. See for example the grammar and its plain Prolog representation below.

det(det(a), sg)  --> "a".
det(det(an), pl) --> "an".
det(det(the), _) --> "the".

?- listing(det).
det(det(a), sg, [97|A], A).
det(det(an), pl, [97, 110|A], A).
det(det(the), _, [116, 104, 101|A], A).

Deep argument indexing will create indexes for the 3rd list argument, providing speedup and making clause selection deterministic if all rules start with a literal and all literals are unique in the first 6 elements. Note that deep index creation stops as soon as a deterministic choice can be made or there are no two clauses that have the same name/arity combination.