Can PostgreSQL use nulls in its indexes?

Question

I've been reading this book which says that

The database assumes that Indexed_Col IS NOT NULL covers too large a range to be useful, so the database will not drive to an index from this condition.

I recognize that the book is more than 10 years old, but it has already proven quite useful--Using instructions gleaned from its pages, I've sped a query up by a factor of ten.

Further, in running EXPLAIN ANALYZE on a SELECT query, I've found that none of my indexes are being used, even when by all rights, they ought to be.

Thus, my question is:

Supposing there is a table which has a column, whose column definition includes "NOT NULL", and that an index exists which covers this column, would this index be used in a query of that table where the columns is part of the query?

Like:

CREATE TABLE my_table(
a varchar NOT NULL
);

CREATE INDEX ix_my_table ON my_table(a);

SELECT a from my_table;

Answer 1

PostgreSQL certainly can use an index for IS NOT NULL. I don't see any query planner assumptions about that condition, either.

If the null fraction for the column (pg_statistic.stanullfrac) is low enough to suggest that the index is usefully selective for the query, PostgreSQL will use an index.

I can't figure out what you're trying to say with:

If this is correct, is my understanding that an index on a column defined as "NOT NULL" not be used in a query which uses that column?

Certainly an index won't get used for an IS NOT NULL condition on a NOT NULL column. It'd always match 100% of rows, so a seqscan will almost always be much faster.

PostgreSQL won't use an index if the index doesn't filter out a large proportion of rows for a query. The only likely exception is when you're asking for a set of columns covered by a single index, in an order matching that of the index. PostgreSQL might do an index-only scan then. E.g. if there's an index on t(a, b, c) and you:

select a, b FROM t ORDER BY a, b, c;

PostgreSQL might use your index, even though no rows are filtered out, because it only has to read the index and can skip reading the heap, avoid doing a sort, etc.

Answer 2

In addition to Craig's thorough answer, I wanted to add that the cover of the book you reference says:

Covers Oracle, DB2 & SQL Server

So I wouldn't trust it to be a great source of advice on PostgreSQL in particular. Every RDBMS can be surprisingly different!

I'm a little confused about your original question, but here's an example showing that section of the book is not 100% correct. To avoid further confusion, here's the whole relevant paragraph, you can see it in Google Book Search.

The database assumes that Indexed_Col IS NOT NULL covers too large a range to be useful, so the database will not drive to an index from this condition. In rare cases, having any nonnull value is so rare that an index range scan over all possible nonnull values is beneficial. In such cases, if you can figure out a safe lower or upper limit to the range of all possible values, you can enable a range scan with a condition such as Positive_ID_Column > -1 or Date_Column > TO_DATE('0001/01/01', 'YYYY/MM/DD').

Postgres can actually (in the following contrived case) use an index to satisfy IS NOT NULL queries without adding range scan kludges like the suggested Positive_ID_Column > -1. See the comments on Craig's questions for why Postgres is choosing this index in this particular case, and the note about using partial indexes.

CREATE TABLE bar (a int);
INSERT INTO bar (a) SELECT NULL FROM generate_series(1,1000000);
INSERT INTO bar (a) VALUES (1);
CREATE INDEX bar_idx ON bar (a);

EXPLAIN ANALYZE SELECT * FROM bar WHERE a IS NOT NULL;
                                                QUERY PLAN                                                    
------------------------------------------------------------------------------------------------------------------
 Index Only Scan using bar_idx on bar  (cost=0.42..8.44 rows=1 width=4) (actual time=0.094..0.095 rows=1 loops=1)
   Index Cond: (a IS NOT NULL)
   Heap Fetches: 1
 Total runtime: 0.126 ms
(4 rows)

This is Postgres 9.3 by the way, but I believe the results would be roughly similar on 9.1, although it wouldn't use an "Index Only Scan".

Edit: I see you've clarified your original question, and you are apparently wondering why Postgres isn't using an index in a simple example like:

CREATE TABLE my_table(
a varchar NOT NULL
);

CREATE INDEX ix_my_table ON my_table(a);

SELECT a from my_table;

Probably because you don't have any rows in the table. So add some test data and ANALYZE my_table;.

Answer 3

You haven't posted your query or example data. But the most common reason indexes are not used has to do with volume.

Indexes are like a phonebook that translates a column to a row location. If you're only looking for a few rows, it makes sense to look up each row in the phonebook, and then look up the row in the main table.

But for more than a few rows, it's cheaper to skip the phonebook, and iterate over all rows in the main table. In my experience the tipping point is around 100 rows.