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 table with 7.2 million tuples which looks like this:

                               table public.methods
 column |          type         |                      attributes
--------+-----------------------+----------------------------------------------------
 id     | integer               | not null DEFAULT nextval('methodkey'::regclass)
 hash   | character varying(32) | not null
 string | character varying     | not null
 method | character varying     | not null
 file   | character varying     | not null
 type   | character varying     | not null
Indexes:
    "methods_pkey" PRIMARY KEY, btree (id)
    "methodhash" btree (hash)

Now I want to select some values but the query is incredibly slow:

db=# explain 
    select hash, string, count(method) 
    from methods 
    where hash not in 
          (select hash from nostring) 
    group by hash, string 
    order by count(method) desc;
                                            QUERY PLAN
----------------------------------------------------------------------------------------
 Sort  (cost=160245190041.10..160245190962.07 rows=368391 width=182)
   Sort Key: (count(methods.method))
   ->  GroupAggregate  (cost=160245017241.77..160245057764.73 rows=368391 width=182)
       ->  Sort  (cost=160245017241.77..160245026451.53 rows=3683905 width=182)
             Sort Key: methods.hash, methods.string
             ->  Seq Scan on methods  (cost=0.00..160243305942.27 rows=3683905 width=182)
                   Filter: (NOT (SubPlan 1))
                   SubPlan 1
                   ->  Materialize  (cost=0.00..41071.54 rows=970636 width=33)
                     ->  Seq Scan on nostring  (cost=0.00..28634.36 rows=970636 width=33)

The hash column is the md5 hash of string and has an index. So I think my problem is that the whole table is sorted by id and not by hash, so it takes a while to sort it first and then group it?

The table nostring contains only a list of hashes I don't want to have. But I need both tables to have all values. So it's not an option to delete these.

additional info: none of the columns can be null (fixed that in the table definition) and i'm using postgresql 9.2.

share|improve this question
1  
Always provide the version of PostgreSQL you use. What is the percentage of NULL values in column method? Are there duplicates on string? –  Erwin Brandstetter Nov 30 '12 at 0:12
add comment

3 Answers

up vote 6 down vote accepted

The LEFT JOIN in @dezso's answer should be good. An index, however, will hardly be useful (per se), because the query has to read the whole table anyway - the exception being index-only scans under PostgreSQL 9.2 and favorable conditions, see below.

SELECT m.hash, m.string, count(m.method) AS method_ct
FROM   methods m
LEFT   JOIN nostring n USING (hash)
WHERE  n.hash IS NULL
GROUP  BY m.hash, m.string 
ORDER  BY count(m.method) DESC;

Run EXPLAIN ANALYSE on the query. 3x to exclude cashing effects. Take the best result.

Create a matching multi-column index that matches your query:

CREATE INDEX methods_cluster_idx ON methods (hash, string, method);

What? After I said an index wouldn't help? Well, we need it to CLUSTER the table:

CLUSTER methods USING methods_cluster_idx;
ANALYZE methods;

Rerun EXPLAIN ANALYSE. Any faster? It should be.

Note that CLUSTER is a one-time operation to rewrite the whole table in the order of the used index. It is also effectively a VACUUM FULL. If you want to be sure, you'd run a pre-test with VACUUM FULL alone to see what can be attributed to that.

If your table sees a lot of write operations, the effect will degrade over time. Schedule CLUSTER at off-hours to restore the effect. Fine tuning depends of your exact use-case. The manual about CLUSTER.


If the percentage of NULL values in the column method is high (more than ~ 20 percent, depending on actual row sizes), a partial index should help:

CREATE INDEX methods_foo_idx ON methods (hash, string)
WHERE method IS NOT NULL;

If you are running PostgreSQL 9.2 or later (as @deszo commented) the presented indexes may be useful without CLUSTER if the planner can utilize index-only scans. Only applicable under favorable conditions: No write operations that would effect the visibility map since the last VACUUM and all columns in the query have to be covered by the index. Basically read-only tables can use this any time, while heavily written tables cannot at all times. More details in the Postgres wiki.

The above mentioned partial index could be even more useful in that case.

If, on the other hand, there are no NULL values in column method, you should
1.) define it NOT NULL and
2.) use count(*) instead of count(method), that's slightly faster and does the same in the absence of NULL values.

If you have to call this query often and the table is read-only, create a materialized view.


Exotic fine point: Your table is named nostring, yet seems to contain hashes. By excluding hashes instead of strings, there is a chance that you exclude more strings than intended. Extremely unlikely, but possible.

share|improve this answer
1  
At the moment I'm not quite in the position of testing that index, but isn't it possible that (in 9.2 of course) it could be used (as an index-only scan)? –  dezso Nov 30 '12 at 10:19
    
@Erwin: If hash is (as hashes are supposed to be) unique, then the group by could be written as GROUP BY hash, correct? Would that help efficiency? –  ypercube Nov 30 '12 at 16:06
1  
@ypercube: hash would have to be the primary key for that. UNIQUE would suffice, logically, but only the primary key has been implemented for this feature (yet). -> sqlfiddle demo. –  Erwin Brandstetter Nov 30 '12 at 16:35
    
@ypercube I don't see any reason to suppose hash is unique here because the thing being hashed isn't. md5('a')=md5('a') but that doesn't mean md5 is broken ;) –  Jack Douglas Nov 30 '12 at 16:45
1  
@dezso: Good point about index-only scans. I added a paragraph to incorporate your corrective. –  Erwin Brandstetter Nov 30 '12 at 17:14
show 11 more comments

Welcome to DBA.SE!

You can try to rephrase your query like this:

SELECT m.hash, string, count(method) 
FROM 
    methods m
    LEFT JOIN nostring n ON m.hash = n.hash
WHERE n.hash IS NULL
GROUP BY hash, string 
ORDER BY count(method) DESC;

or another possibility:

SELECT m.hash, string, count(method) 
FROM 
    methods m
WHERE NOT EXISTS (SELECT hash FROM nostring WHERE hash = m.hash)
GROUP BY hash, string 
ORDER BY count(method) DESC;

NOT IN is a typical sink for performance since it is hard to use an index with it.

This may be further enhanced with indexes. An index on nostring.hash looks useful. But first: what do you get now? (It would be better to see the output of EXPLAIN ANALYZE since the costs themselves don't tell the time the operations took.)

share|improve this answer
    
a index is created on nostring.hash allready, but i think postgres dont use it because of too many tuples... when i explcit disable sequence scan, it uses the index. if i use the left join i get a cost of 32 million, so its way better... but i'm trying to optimize it more... –  reox Nov 29 '12 at 12:28
3  
The cost is only for the planner to be able to schoose a sufficiently good plan. The actual times usually correlate with it, but not necessarily. So if you want to be sure, use EXPLAIN ANALYZE. –  dezso Nov 29 '12 at 13:23
add comment

Since hash is an md5, you may probably try to convert it in a number: you may store it as a number, or just create a functional index that calculate that number in a immutable function.

Other people already created a pl/pgsql function that convert (part of) an md5 value from text to string. See http://stackoverflow.com/questions/9809381/hashing-a-string-to-a-numeric-value-in-postgressql for an example

I believe that you are really spending a lot of time in string comparison while scanning the index. If you manage to store that value as a number, then it should be really really faster.

share|improve this answer
1  
I doubt that this conversion would speed things up. All the queries here use equality for comparison. Computing numeric representations and then check for equality doesn't promise big gains for me. –  dezso Nov 30 '12 at 15:59
2  
I think I'd store md5 as bytea rather than a number for space efficiency: sqlfiddle.com/#!12/d41d8/252 –  Jack Douglas Nov 30 '12 at 16:07
    
Also, welcome to dba.se! –  Jack Douglas Nov 30 '12 at 16:24
    
@JackDouglas: Interesting comment! 16 byte per md5 instead of 32 is quite a bit for big tables. –  Erwin Brandstetter Nov 30 '12 at 16:40
add comment

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.