33

We are designing a system that is known to be read-heavy (on the order of tens of thousands of reads per minute).

  • There is a table names that serves as a sort of central registry. Each row has a text field representation and a unique key that is an MD5 hash of that representation.1 This table currently has tens of millions of records and is expected to grow into the billions over the lifetime of the application.
  • There are dozens of other tables (of highly varying schemas and record counts) that make reference to the names table. Any given record in one of these tables is guaranteed to have a name_key, which is functionally a foreign key to the names table.

1: Incidentally, as you might expect, records in this table are immutable once written.

For any given table other than the names table, the most common query will follow this pattern:

SELECT list, of, fields 
FROM table 
WHERE name_key IN (md5a, md5b, md5c...);

I would like to optimize for read performance. I suspect that my first stop should be to minimize the size of the indices (though I wouldn't mind being proven wrong there).

The Question:
What is/are the optimal data types for the key and name_key columns?
Is there a reason to use hex(32) over bit(128)? BTREE or GIN?

39
+100

The data type uuid is perfectly suited for the task. It only occupies 16 bytes as opposed to 37 bytes in RAM for the varchar or text representation. (Or 33 bytes on disk, but the odd number would require padding in many cases to make it 40 bytes effectively.) And the uuid type has some more advantages.

Example:

SELECT md5('Store hash for long string, maybe for index?')::uuid AS md5_hash

Details and more explanation:

You might consider other (cheaper) hashing functions if you don't need the cryptographic component of md5, but I would go with md5 for your use case (mostly read-only).

A word of warning: For your case (immutable once written) a functionally dependent (pseudo-natural) PK is fine. But the same would be a pain where updates on text are possible. Think of correcting a typo: the PK and all depending indexes, FK columns in dozens of other tables and other references would have to change as well. Table and index bloat, locking issues, slow updates, lost references, ...

If text can change in normal operation, a surrogate PK would be a better choice. I suggest a bigserial column (range -9223372036854775808 to +9223372036854775807 - that's nine quintillion two hundred twenty-three quadrillion three hundred seventy-two trillion thirty-six something billion) distinct values for billions of rows. Might be a good idea in any case: 8 instead of 16 bytes for dozens of FK columns and indexes!). Or a random UUID for much bigger cardinalities or distributed systems. You can always store said md5 (as uuid) additionally to find rows in the main table from the original text quickly. Related:

As for your query:


To address @Daniel's comment: If you prefer a representation without hyphens, remove the hyphens for display:

SELECT replace('90b7525e-84f6-4850-c2ef-b407fae3f271', '-', '')

But I wouldn't bother. The default representation is just fine. And the problem's really not the representation here.

If other parties should have a different approach and throw strings without hyphens into the mix, that's not a problem either. Postgres accepts several reasonable text representations as input for a uuid. The documentation:

PostgreSQL also accepts the following alternative forms for input: use of upper-case digits, the standard format surrounded by braces, omitting some or all hyphens, adding a hyphen after any group of four digits. Examples are:

A0EEBC99-9C0B-4EF8-BB6D-6BB9BD380A11
{a0eebc99-9c0b-4ef8-bb6d-6bb9bd380a11}
a0eebc999c0b4ef8bb6d6bb9bd380a11
a0ee-bc99-9c0b-4ef8-bb6d-6bb9-bd38-0a11
{a0eebc99-9c0b4ef8-bb6d6bb9-bd380a11}

What's more, the md5() function returns text, you would use decode() to convert to bytea and the default representation of that is:

SELECT decode(md5('Store hash for long string, maybe for index?'), 'hex')

\220\267R^\204\366HP\302\357\264\007\372\343\362q

You would have to encode() again to get the original text representation:

SELECT encode(my_md5_as_bytea, 'hex');

To top it off, values stored as bytea would occupy 20 bytes in RAM (and 17 bytes on disk, 24 with padding) due to the internal varlena overhead, which is particularly unfavourable for size and performance of simple indexes.

Everything works in favor of a uuid here.

  • 1
    Is this legit for "uuid"? Please excuse me if I'm too pedantic, but I think what I'm seeing is that the "uuid" data type is oriented towards storing numbers that are 16 octets in length in binary format. But the term "uuid" suggests a particular generation/hashing algorithm as well as the conventional textual representation in 5 blocks of dash-separated hexadecimal characters. If this type name strongly suggests the UUID/GUID generation, isn't it a bit misleading, for programmers at least, to use this type for storing a hash? – Andrew Wolfe Jan 7 '16 at 16:43
  • 2
    @AndrewWolfe: Totally legit, IMO. Don't get carried away by the name. It's a 16-byte entity with a convenient set of provided type casts and input / output logic. The case at hand even actually requires a "unique identifier". You can store all kinds of character data in text columns as well - even if it's not a "text" at all. – Erwin Brandstetter Jan 8 '16 at 5:42
2

I would store the MD5 in a text or varchar column. There is no performance difference between the various character data types. You might want to constrain the length of the md5 values by using varchar(xxx) to make sure the md5 value never exceeds a certain length.

Large IN lists are usually not really fast, it's better to do something like this:

with md5vals (md5) as (
  values ('one'), ('two'), ('three')
)
select t.*
from the_table t
  join md5vals m on t.name_key  = m.md5;

Another option that is sometimes said to be faster is to use an array:

select t.*
from the_table t
where name_key = ANY (array['one', 'two', 'three']);

As you are just comparing for equality, a regular BTree index should be fine. Both queries should be able to make use of such an index (especially if the are selecting only a small fraction of the rows.

  • Any particular reason not to use bit(128) or hex(32)? Values are guaranteed to fit neatly into such a field, and I'd like to protect from bad values being assigned. – bobocopy Sep 17 '15 at 0:36
  • 3
    @bobocopy: there is no "hex" data type in Postgres. I have never used the bit type so I can't comment on that. Given your expected number of rows, Erwin's suggestion seems to be better because of the space saving you get with storing this as UUID – a_horse_with_no_name Sep 17 '15 at 5:39
-1

Another option is to use 4 INTEGER or 2 BIGINT columns.

  • 2
    In terms of storage size, either option would fit, of course, but how convenient would it be to work with? Perhaps you could expand your answer to show an example or otherwise explain that. – Andriy M May 18 '16 at 16:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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