4

I'm looking to create an index on a large table (~50 million rows) on a field with lots of non-unique values.

Table schema looks like:

 Column |         Type          | Modifiers | Storage  | Stats target | Description 
--------+-----------------------+-----------+----------+--------------+-------------
 gid    | character varying(20) |           | extended |              | 
 word   | character varying(30) |           | extended |              | 
 stat   | double precision      |           | plain    |              | 
Has OIDs: no

I want to create an index on the 'word' column. There is a fairly regular pattern where each word appears about 1000 times. I need to do fast SELECT * FROM mytable WHERE word='something';queries. Creating a regular B-Tree index on these tables takes a ton of time but does substantially improve performance.

I'm uncomfortable with my solution right now for several reasons

(1) The selection of a B-Tree index isn't particularly motivated. Are there alternative indexing schemes that perform better on fields with highly duplicated values?

(2) I'm in a production environment where these tables pop into and out of existence fairly regularly. Because not all tables will always be heavily queried I've opted to only build indexes on a table when certain (outside the DB) applications are triggered, such that I know 10k+ queries will be performed on the table+field. Waiting 20 minutes while an index is being created isn't ideal however. The situation is delicate; optimization gained by creating the index competes with the initial time-sink required to create the index. Are there 'cheaper' indexes to create? perhaps ones that will perform overall slightly worse than B-Tree but have less initial creation cost?

  • 2
    Regarding 2): unless you really see a problem with update/delete/insert performance you should keep that index in the database rather than dropping and re-creating it constantly. You can create the index using the CONCURRENTLY option. That will allow concurrent DML to the table but will increase the time to build the index even more. – a_horse_with_no_name Apr 28 '14 at 10:30
  • The issue here isn't about whether to drop and recreate an index. The issue is about judging whether the initial time sink of creating the index is worth it. The CONCURRENTLY option is interesting, but seems more suited for situation where I know that there will be many more future queries on a table. It is common in my cases that tables are queried 10K times in one session, then never again. – GrantD71 Apr 28 '14 at 12:07
  • Can you explain the "tables pop into and out of existence fairly regularly" part? Do you mean you have many tables like this one (with identical structure)? – ypercubeᵀᴹ Apr 28 '14 at 14:07
  • I mean that the tables don't stick around for very long, so often it is not worth it to automatically create an index when the table is created. Sometimes the massive tables are created but never utilized. Sometimes they are created but very few queries are run. Sometimes they are created and a massive string of queries are run at once, but then the table is subsequently deleted after the large burst of queries. – GrantD71 Apr 28 '14 at 22:22
6

For starters gid should probably be a numeric type. integer should be good enough or bigint if the key space shouldn't be big enough. Much smaller footprint, faster processing than with character data, faster and smaller indexes.

More importantly, to improve performance I suggest database normalization.

Quote:

There is a fairly regular pattern where each word appears about 1000 times.

Create a separate table for unique words:

CREATE TABLE word (
   word_id serial
 , word    text
);

Fill it with unique instances of word in your big_tbl:

INSERT INTO word (word)
SELECT DISTINCT word
FROM   big_tbl
ORDER  BY word;

ORDER BY is optional, not needed for query at hand. But it speeds up index creation and might be cheaper overall.

The table should be small in comparison: only ~ 50k rows for 50M rows in your big table.
Add indexes after filling the table:

ALTER TABLE word
    ADD CONSTRAINT word_word_uni UNIQUE (word) -- essential
  , ADD CONSTRAINT word_word_id_pkey PRIMARY KEY (word_id);  -- expendable?

If those are read-only tables, you can do without the pk. It's not relevant to the operations at hand.

Replace your big table with a much smaller new table. You may have to lock the big table to avoid concurrent writes. Concurrent reads are not a problem.

CREATE TABLE big_tbl_new AS
SELECT b.gid      -- or the suggested smaller, faster numeric replacement
     , w.word_id, b.stat
FROM   big_tbl b
JOIN   word w USING (word)
ORDER  BY word;   -- sorting by word helps query at hand

ORDER BY clusters the data (once) making the query at hand faster, because far fewer blocks have to be read (unless your data is clustered mostly already). The sort carries a cost, weigh cost and benefit once more.

DROP big_tbl;     -- make sure your new table has all data!
ALTER big_tbl_new RENAME TO big_tbl;

Recreate indexes:

ALTER TABLE big_tbl ADD CONSTRAINT big_tbl_gid_pkey PRIMARY KEY (gid);  -- expendable?
CREATE INDEX big_tbl_word_id_idx ON big_tbl (word_id);  -- essential

Your query looks like this now and should be faster:

SELECT b.*
FROM   word w
JOIN   big_tbl b USING (word_id)
WHERE  w.word = 'something';

Reorganization is meant to be a one-time operation to re-organize your data. Keep the new form and also consider keeping indexes permanently.

All of this together (including new indexes) should occupy about half of what you had before on disk, also cutting the time for creation in half (at least). Index creation should be considerably faster, the query as well. If RAM is a limiting factor, these modification pay double.

If you have to write to the table as well, it becomes more expensive (but you did not mention anything about that). You'd need to adjust your logic for DELETE / UPDATE / INSERT:
Example for INSERT: Fetch word_id for existing words or insert a new row in word returning the new word_id. Details for this:
How do I insert a row which contains a foreign key?

  • 1
    I appreciate the suggestions. I think there is some lack of clarification in my question. First, turning gid into an integer isn't possible because sometimes the id can be a mix of alphabetic and numerics. Second, doesn't your suggestion boil down to converting a char var to an integer? Is index creation that much faster for integers than char vars? I am skeptical that SELECT with an internal JOIN will outperform a simple Select on an indexed table, but I will test. This also complicates my DB load process, and involves populating a word table in addition to index creation. – GrantD71 Apr 28 '14 at 22:43
  • 2
    @GrantD71: If gid is just a global ID, as the name suggests, it carries no other information (you didn't provide anything to the contrary). Its only purpose: to be unique. integer covers 2G positive values and easily covers 50M rows. If that's not enough, bigint is. There may be other restrictions, but your question did not mention any. word_id: if your numbers hold up, the word table is smaller by ~ factor 2000, the index on word by ~ 1000. big_tbl_word_id_idx is ~ half the size of your original index and integer is faster. I added some more ideas. – Erwin Brandstetter Apr 29 '14 at 4:09

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.