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