Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

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.
share|improve this question
    
How long are the arrays, out of interest? And do you only want exact matches (=), or also "contains", etc? –  Craig Ringer Apr 9 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 at 13:46

2 Answers 2

up vote 2 down vote accepted

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)

share|improve this answer
    
+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 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 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 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 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 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.

Steps:

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[];
share|improve this answer
    
+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 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. –  Daniel Vérité Apr 10 at 10:23

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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