Multi argument indexing or indexing on single argument different from first?

The expectations to get equivalent or better performance in the
fill_table/search_table variant wrt fill_table1/search_table1 is unfounded?

Your hint is still to code manual hashing when we need a composed key?

$ cat q.pl
:- dynamic(p/3).

fill_table(0) :-
    !.
fill_table(N) :-
    succ(N1, N),
    A is random(1000),
    B is random(1000),
    C is random(1000),
    assertz(p(A, B, C)),
    assertion(p(A, B, C)),
    fill_table(N1).

search_table(0, C, C) :-
    !.
search_table(N, C, C1) :-
    succ(N1, N),
    A is random(1000),
    B is random(1000),
    (p(A, B, _C) ->
        succ(C, C0)
    ;
        C0 = C
    ),
    search_table(N1, C0, C1).

fill_table1(0) :-
    !.
fill_table1(N) :-
    succ(N1, N),
    A is random(1000),
    B is random(1000),
    C is random(1000),
    term_hash(A-B, H),
    assertz(q(H, A, B, C)),
    assertion(q(H, A, B, C)),
    fill_table1(N1).

search_table1(0, C, C) :-
    !.
search_table1(N, C, C1) :-
    succ(N1, N),
    A is random(1000),
    B is random(1000),
    term_hash(A-B, H),
    (q(H, A, B, _C) ->
        succ(C, C0)
    ;
        C0 = C
    ),
    search_table1(N1, C0, C1).

test(N) :-
    get_time(T),
    Seed is integer(T * 10000000),
    set_random(seed(Seed)),
    retractall(p(_, _, _)),
    time(fill_table(N)),
    time(search_table(N, 0, C)),
    writeln(C),
    set_random(seed(Seed)),
    retractall(q(_, _, _, _)),
    time(fill_table1(N)),
    time(search_table1(N, 0, C1)),
    writeln(C1).

$ swipl
Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 6.0.0)
Copyright (c) 1990-2011 University of Amsterdam, VU Amsterdam
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to redistribute it under certain conditions.
Please visit http://www.swi-prolog.org for details.

For help, use ?- help(Topic). or ?- apropos(Word).

?- [q].
% q compiled 0.00 sec, 11 clauses
true.

?- test(100000).
% 904,654 inferences, 1.396 CPU in 1.397 seconds (100% CPU, 648102 Lips)
% 509,530 inferences, 2.175 CPU in 2.178 seconds (100% CPU, 234254 Lips)
9529
% 1,000,001 inferences, 0.610 CPU in 0.610 seconds (100% CPU, 1640344 Lips)
% 609,530 inferences, 0.138 CPU in 0.138 seconds (100% CPU, 4429479 Lips)
9529
true.

?-