As introduced in section
2.17, 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.
