The indexing capabilities of
SWI-Prolog are described in
section 2.17.
Summarizing, SWI-Prolog creates indexes for any applicable argument,
pairs of arguments and indexes on the arguments of compound terms when
applicable. Extended JIT indexing is not widely supported among Prolog
implementations. Programs that aim at portability should consider using term_hash/2
and term_hash/4
to design their database such that indexing on constant or functor
(name/arity reference) on the first argument is sufficient. In some
cases, using the predicates below to add one or more additional columns
(arguments) to a database predicate may improve performance. The overall
design of code using these predicates is given below. Note that as term_hash/2
leaves the hash unbound if Term is not ground. This causes
the lookup to be fast if Term is ground and correct (but
slow) otherwise.
:- dynamic
x/2.
assert_x(Term) :-
term_hash(Term, Hash),
assertz(x(Hash, Term)).
x(Term) :-
term_hash(Term, Hash),
x(Hash, Term).
- [det]term_hash(+Term,
-HashKey)
- If Term is a ground term (see ground/1), HashKey
is unified with a positive integer value that may be used as a hash key
to the value. If Term is not ground, the predicate leaves HashKey
an unbound variable. Hash keys are in the range 0 ... 16,777,215,
the maximal integer that can be stored efficiently on both 32 and 64 bit
platforms.
This predicate may be used to build hash tables as well as to exploit
argument indexing to find complex terms more quickly.
The hash key does not rely on temporary information like addresses of
atoms and may be assumed constant over different invocations and
versions of SWI-Prolog.92Last
change: version 5.10.4 Hashes differ between big and little
endian machines. The term_hash/2
predicate is cycle-safe.bugAll
arguments that (indirectly) lead to a cycle have the same hash key.
- [det]term_hash(+Term,
+Depth, +Range, -HashKey)
- As term_hash/2,
but only considers Term to the specified
Depth. The top-level term has depth 1, its arguments have
depth 2, etc. That is, Depth = 0 hashes nothing; Depth
= 1 hashes atomic values or the functor and arity of a compound
term, not its arguments; Depth = 2 also indexes
the immediate arguments, etc.
HashKey is in the range [0 ...Range-1]. Range
must be in the range [1 ... 2147483647].
- [det]variant_sha1(+Term,
-SHA1)
- Compute a SHA1-hash from Term. The hash is represented as a
40-byte hexadecimal atom. Unlike term_hash/2
and friends, this predicate produces a hash key for non-ground terms.
The hash is invariant over variable-renaming (see =@=/2)
and constants over different invocations of Prolog.bugThe
hash depends on word order (big/little-endian) and the wordsize (32/64
bits).
This predicate raises an exception when trying to compute the hash on
a cyclic term or attributed term. Attributed terms are not handled
because subsumes_chk/2
is not considered well defined for attributed terms. Cyclic terms are
not supported because this would require establishing a canonical cycle.
That is, given A=[a|A] and B=[a,a|B],
A and B should produce the same hash. This is not
(yet) implemented.
This hash was developed for lookup of solutions to a goal stored in a
table. By using a cryptographic hash, heuristic algorithms can often
ignore the possibility of hash collisions and thus avoid storing the
goal term itself as well as testing using =@=/2.
- [det]variant_hash(+Term,
-HashKey)
- Similar to variant_sha1/2,
but using a non-cryptographic hash and produces an integer result like term_hash/2.
This version does deal with attributed variables, processing them as
normal variables. This hash is primarily intended to speedup finding
variant terms in a set of terms.
bugAs variant_sha1/2,
cyclic terms result in an exception.
