Does Postgresql have an efficient storage/search algorithm for date range availability?

There are hundreds of thousands of paddle boards, so storing separate records for each day’s availability for each is untenable (e.g., 350k paddle boards w/ 2 years availability data results in over 250 million rows).

250 million rows can be handled, with some care, and we can likely reduce that by at least an order of magnitude.

Your proposed solution is, effectively, trying to make your own indexing system. Regex searches over a database are typically quite slow. And by cramming all checkouts into one row you cannot store any information about each checkout: who checked it out, what price did they pay, what condition was the board returned, etc.

Instead, use a conventional table and rely on indexes and 50 years of cumulative relational database development.

We can drastically reduce the number of rows by assuming paddleboards will spend most of their time sitting around waiting to be checked out (you can verify this assumption). Instead of storing the state of each paddleboard for each day, only store the dates when they are checked out. Use the daterange type. This lets us use range operations.

(Note: I would recommend against datemultirange. Any solution which tries to cram all checkouts into one row means you cannot store information about each checkout. Who checked it out? What condition was it returned? What price did they pay? Were they late?)

(Note: Consider using a tsrange, timestamp range, instead and defaulting the time to noon. Assuming the pickup/dropoff time will always be noon is a business requirement and can change at any time. Avoid hard coding it into your schema. While you can change the column type later and convert the data, it will be painful with that much data.)

create table paddleboards (
  id serial primary key

  -- and other information about each paddleboard
  -- who owns the paddleboard?
  -- where is it located?
  -- what condition is it in?
);

create table paddleboard_checkouts (
  paddleboard_id integer not null references paddleboards(id),
  in_use daterange not null

  -- and other information about this checkout
  -- who checked it out?
  -- what condition was it returned?
);

Then index in_use and paddleboard_id. These indexes will make these queries fast even as the amount of data gets larger. Instead of scanning the whole table, it can search the index. They are (often literally) the search trees you’re wanting.

paddleboard_id can be a normal b-tree index. However, in_use should use a GIST index because it supports important range operations like intersection (&&).

create index paddleboard_checkouts_fk on paddleboard_checkouts (paddleboard_id);
create index paddleboard_in_use using gist (in_use);

Here are some examples of queries the indexes will cover.

-- When is a particular paddleboard in use?
-- This will use paddleboard_checkouts_fk
select in_use
from paddleboard_checkouts
where paddleboard_id = 12345;

-- What paddleboards are checked out this week?
-- This will use paddleboard_in_use
select paddleboard_id
from paddleboard_checkouts
where in_use && daterange('2023-05-29', '2023-06-02');

-- What paddleboards are available this week?
-- This will use paddleboard_in_use
select paddleboard_id
from paddleboard_checkouts
where not in_use && daterange('2023-05-29', '2023-06-02');

-- Is this paddleboard available this week?
-- This will probably use paddleboard_checkouts_fk to narrow
-- the rows to just one paddleboard then linear search the few
-- remaining rows.
select paddleboard_id
from paddleboard_checkouts
where paddleboard_id = 12345
  and not in_use && daterange('2023-05-29', '2023-06-02');

Since your data will continuously grow, you may wish to consider partitioning the table by year or perhaps month. This won’t necessarily improve performance, but it will make it easier to drop old data and keep the table from continuously growing.

The complete data can be mirrored into a data warehouse. This is a database which is optimized for storing and searching extremely large amounts of data. For example, Google BigQuery.

Finally, if necessary for performance, you can add a cache for the results of common queries. It’s likely most of your queries will cluster around a few months or weeks in the future.

Use the data warehouse for high-latency business intelligence tasks which need to see the whole range of data such as reports, statistics, and so on. Use the PostgreSQL database for low-latency tasks such as serving web requests. Use the cache to decrease latency even further.