How to select efficiently by list of dateranges?

Question

I have two tables:

create table foo(
  id serial primary key,
  ts timestamp
);

create table bar(
  id serial primary key,
  ts_start timestamp,
  ts_end timestamp
);

I need to select all rows from foo in which ts lies between bar.ts_start and bar.ts_end. My initial try:

SELECT * FROM foo JOIN bar ON foo.ts BETWEEN bar.start AND bar.end;

The problem is that table foo has 1-3 millions of rows. And despite the fact that I only need to join them with quite small amount of rows from bar (30-100), it still performs poorly (6-20s) if I need to add a few more conditions on foo (simple equality conditions).

Is there a way or approach to optimize this query?
I expect nested loops in the query plan to be a problem, but I'm out of ideas.

Answer 1

Assuming the ranges in table bar are mutually exclusive, and their bounds inclusive, your query is as good as it gets.

You need a basic B-tree index on foo(ts), as a bare minimum:

CREATE INDEX ON foo (ts);

Depending on undisclosed information, we might be able to optimize index and query (a lot) more.