I have a huge list of integer arrays (300,000,000 records) stored in Postgres 9.2 DB. I want to efficiently search these records for an exact match (equality only). I have heard of the intarray module and the corresponding gist-gin indexes. I would like to ask the following questions:

  • Does PostgreSQL uses a hash function for checking equality of integer arrays or does it perform a brute-force algorithm comparing one-by-one the elements of the array?
  • If PostgreSQL uses a hash function, is there some PostgreSQL function code to actually get the hash function result for a particular array?
  • Which index will be best for such a task? B-tree, or the gist - gin indexes provided by the intarray module? The dataset will be static, i.e, once all records are inserted there will no more insertions. So, building index / updating index time is not important to me.
  • How long are the arrays, out of interest? And do you only want exact matches (=), or also "contains", etc? Apr 9, 2014 at 12:37
  • @CraigRinger The arrays are big (100 - 1000). When I try to index them (b-tree) I get the "Index row requires 8200 bytes and maximum size is 8191).
    – Alexandros
    Apr 9, 2014 at 13:46

2 Answers 2


1) as you already have discovered, you can't use b-tree as the index size is bigger than the page size

2) given:

As a rule of thumb, a GIN index is faster to search than a GiST index, but slower to build or update; so GIN is better suited for static data and GiST for often-updated data.

You would have to use GIN. And no, GIN doesn't use hash functions nor a brute-force algorithm. It's a reverse index:

A GIN index stores a set of (key, posting list) pairs, where a posting list is a set of row IDs in which the key occurs. The same row ID can appear in multiple posting lists, since an item can contain more than one key. Each key value is stored only once, so a GIN index is very compact for cases where the same key appears many times.

Internally, a GIN index contains a B-tree index constructed over keys, where each key is an element of one or more indexed items (a member of an array, for example)

  • +1 @Leo I also had the same problem with the gist-index as well. So, gin-index will not have the 8191 limit?
    – Alexandros
    Apr 9, 2014 at 14:57
  • You know, there's theory and there's practice ;) Your case is not very "standard", so maybe you should give a try to the suggestions you're having and let us know? It would be very interesting to know the results!
    – Leo
    Apr 10, 2014 at 6:57
  • The gin index worked. Without a GIN index (seq-scan) 50sec. with the index 400ms (for 1,000,000 entries - a smaller DB table). So, the gin-index seems to work. Thanks
    – Alexandros
    Apr 10, 2014 at 10:18
  • what about @daniel's solution? it seems a good idea, I'm curious about the performance in that case
    – Leo
    Apr 10, 2014 at 12:40
  • I also tried Daniel's approach. Both give comparable performance but the GIN index seems a little bit faster. But needs more testing, to make sure
    – Alexandros
    Apr 10, 2014 at 14:04

Q: Does PostgreSQL uses a hash function for checking equality of integer arrays or does it perform a brute-force algorithm comparing one-by-one the elements of the array?

Not according to Array Functions and Operators in the doc:

Array comparisons compare the array contents element-by-element, using the default B-tree comparison function for the element data type

No mention of hashing.

intarray provides other operators but does not replace the equality operator between int[]. The closest function _int_same() that it exposes is semantically different (the order of elements does not matter) and is implemented as sorting+sequential comparison, not hashing.

Fortunately implementing fast hash-based search at the SQL level is not hard, and in your case (large arrays, no updates, exact match) it may even be the most effective method.


1) choose a hash function. I'd suggest md5 on the text representation of the array:

create function arr_hash(int[]) returns bytea as
$$ select digest($1::text, 'md5');$$
language sql immutable;

The function digest(text,text) is part of the pgcrypto extension. Compared to md5 it has the advantage of producing binary (16 bytes) instead of hexadecimal (32 bytes) for a leaner index.

2) create a functional index:

create index index_name on table_name(arr_hash(col_name));

It will be several orders of magnitude faster than a GIN index for the kind of dataset you have (actually I would worry about the GIN index creation taking a really unreasonable time, but do try it).

3) use it like this:

select 1 from table_name
 where arr_hash(col_name)=arr_hash('{10,20,30,...lot of values}'::int[])
 and   col_name='{10,20,30,...lot of values}'::int[];
  • +1 for your effort. Your suggestion seems logical. Still, although using text is an one time operation, I do not like the idea too much. Why not use something like what Java does for hashCode and int arrays? android.googlesource.com/platform/libcore/+/…
    – Alexandros
    Apr 10, 2014 at 3:18
  • @Alexandros: their hash function for int[] is essentially hash=1; foreach(elt) hash=31*hash+elt. md5 is expected to perform much better in terms of collisions. Apr 10, 2014 at 10:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.