Postgres returns records in wrong order

Question

I have pretty big table messages. It contains about 100mil records.

When I run simple query:

select uid from messages order by uid asc limit 1000

The result is very strange. Records from the beginning are ok, but then they are not always ordered by column uid.

   uid    
----------
 94621458 
 94637590 
 94653611 
 96545014 
 96553145 
 96581957 
 96590621 
102907437 
.....
446131576 
459475933 
424507749 
424507166 
459474125 
431059132 
440517049 
446131301 
475651666 
413687676 
.....

Here is analyze

 Limit  (cost=0.00..3740.51 rows=1000 width=4) (actual time=0.009..4.630 rows=1000 loops=1)
   Output: uid
   ->  Index Scan using messages_pkey on public.messages  (cost=0.00..376250123.91 rows=100587944 width=4) (actual time=0.009..4.150 rows=1000 loops=1)
         Output: uid
 Total runtime: 4.796 ms

PostgreSQL 9.1.12

The table is always under high load(inserts, updates, deletes) and almost constantly autovacuuming. May that cause the problem?

UPD. Added table definition. Sorry cannot add full table definition, but all impotant fields and their types are here.

# \d+ messages
                                                   Table "public.messages"
    Column    |            Type             |                       Modifiers                        | Storage  | Description
--------------+-----------------------------+--------------------------------------------------------+----------+-------------
 uid          | integer                     | not null default nextval('messages_uid_seq'::regclass) | plain    |
 code         | character(22)               | not null                                               | extended |
 created      | timestamp without time zone | not null                                               | plain    |
 accountid    | integer                     | not null                                               | plain    |
 status       | character varying(20)       | not null                                               | extended |
 hash         | character(3)                | not null                                               | extended |
 xxxxxxxx     | timestamp without time zone | not null                                               | plain    |
 xxxxxxxx     | integer                     |                                                        | plain    |
 xxxxxxxx     | character varying(255)      |                                                        | extended |
 xxxxxxxx     | text                        | not null                                               | extended |
 xxxxxxxx     | character varying(250)      | not null                                               | extended |
 xxxxxxxx     | text                        |                                                        | extended |
 xxxxxxxx     | text                        | not null                                               | extended |
Indexes:
    "messages_pkey" PRIMARY KEY, btree (uid)
    "messages_unique_code" UNIQUE CONSTRAINT, btree (code)
    "messages_accountid_created_idx" btree (accountid, created)
    "messages_accountid_hash_idx" btree (accountid, hash)
    "messages_accountid_status_idx" btree (accountid, status)
Has OIDs: no

Answer 1

Save yourself the long wait trying to run the query without index. The problem is most probably due to a corrupted index. Repair it right away and see if that fixes the problem.

Since your table is always under high load, consider building a new index concurrently. Takes a bit longer, but does not block concurrent writes. Per documentation on REINDEX:

To build the index without interfering with production you should drop the index and reissue the CREATE INDEX CONCURRENTLY command.

And under CREATE INDEX:

CONCURRENTLY

When this option is used, PostgreSQL will build the index without taking any locks that prevent concurrent inserts, updates, or deletes on the table; whereas a standard index build locks out writes (but not reads) on the table until it's done. There are several caveats to be aware of when using this option — see Building Indexes Concurrently.

So I suggest:

ALTER TABLE news DROP CONSTRAINT messages_pkey;
CREATE UNIQUE INDEX CONCURRENTLY messages_pkey ON news (uid);
ALTER TABLE news ADD PRIMARY KEY USING INDEX messages_pkey;

The last step is just a tiny update to the system catalogs.

Answer 2

Here's a very general answer:

Try :

SET enable_indexscan TO off;

Rerun the query in the same session.

If the order of the results is different than with enable_indexscan to on, then the index is corrupted.

In this case, fix it with:

REINDEX INDEX index_name;