What is the sort of Index that should be used for date range queries?

Question

I am using postgresql. My table has the columns name, date. Assume that both the columns are non-unique. What is the type of optimization (in terms of indexes) that I can do to be able to retrieve rows based on between two dates?

I know a unique index makes retrieval faster by creating a tree kind of structure to make access easier (log n ?). But what kind of an index should be created for making range queries faster? Is it even possible?

Answer 1

B-tree index is able to speed up range query. It is the default type when you create index with simple CREATE INDEX.

https://www.postgresql.org/docs/14/indexes-types.html

B-trees can handle equality and range queries on data that can be sorted into some ordering.

You can check it with following example:

create table dba_test (my_name varchar, my_date timestamp);

create index dba_test_idx on dba_test(my_date);

insert into dba_test select random()::text, to_timestamp((random()*1000)::int) from generate_series(0,10000) r(s);
analyse dba_test;

explain analyse select * from dba_test
where my_date between '1970-01-01 00:00:30' and '1970-01-01 00:00:50';
--drop table dba_test;

Here is EXPLAIN output for select ... statement:

    QUERY PLAN                                                                         
-----------------------------------------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on dba_test  (cost=6.46..83.64 rows=212 width=27) (actual time=0.151..0.578 rows=203 loops=1)
   Recheck Cond: ((my_date >= '1970-01-01 00:00:30'::timestamp without time zone) AND (my_date <= '1970-01-01 00:00:50'::timestamp without time zone))
   Heap Blocks: exact=69
   ->  Bitmap Index Scan on dba_test_idx  (cost=0.00..6.41 rows=212 width=0) (actual time=0.098..0.099 rows=203 loops=1)
         Index Cond: ((my_date >= '1970-01-01 00:00:30'::timestamp without time zone) AND (my_date <= '1970-01-01 00:00:50'::timestamp without time zone))
 Planning Time: 0.786 ms
 Execution Time: 0.705 ms
(7 rows)

As you can see, your range condition is in Index Cond. But you should be aware that Postgresql planner will not choose [Bitmap] Index Scan if the range is too wide (as it is more costly than read all data sequentially).