DBBinarySearch

An Active Support concern extending Active Record with the ability to binary search a table for use with non-indexed, sorted tables.

The gem allows you to avoid slow database scans if you have an auto-incrementing primary key running in parallel with a column which you want to search.

For example if you have a log table with a lot of records and it has the typical rails setup with id and created_at columns. You want to locate a specific date but the created_at column is not indexed, you can use db_binary_search to locate a row based on created_at faster than letting the database scan the entire column/table for the record.

Unlike a regular binary search algorithm which generally looks for an exact value, this method will return the closest matching primary key.

Prerequisites

This approach will only work if you have an automatically incrementing (or similar) primary key column and a chronologically sorted column to search, e.g. a rails created_at column which doesn't change.

Installation

Add this line to your Gemfile:

gem 'db_binary_search'

And then execute:

    $ bundle

Or install it yourself as:

    $ gem install db_binary_search

Usage

First include the DBBinarySearch concern into your ActiveRecord model, then call the binary_search class method to search for the id.

binary_search(column, value, lower_id=nil, upper_id=nil)

column a symbol, is the table column to search for.
value a comparable value of same type as column, the value you are searching for.
lower_id optional primary key value to start searching lower bound at. Defaults to model.first.id.
upper_id optional primary key value to start searching upper bound at. Defaults to model.last.id.

Full example:

class Log < ActiveRecord::Base
  include DBBinarySearch
end

id = Log.binary_search(:created_at, DateTime.parse("2017-01-07 00:00:00"))
# use id...

Development

After checking out the repo, run bin/setup to install dependencies. Then, run bundle exec rake spec to run the tests. You can also run bin/console for an interactive prompt that will allow you to experiment.

To install this gem onto your local machine, run bundle exec rake install. To release a new version, update the version number in version.rb, and then run bundle exec rake release, which will create a git tag for the version, push git commits and tags, and push the .gem file to rubygems.org.

Contributing

Bug reports and pull requests are welcome on GitHub at https://github.com/acrookston/db_binary_search.

If you're making a big change, please open an Issue first, so we can discuss. Otherwise:

Fork it
Run setup bin/setup
Make your changes
Run tests (bundle exec rake spec)
Send me a pull request

This project is intended to be a safe, welcoming space for collaboration, and contributors are expected to adhere to the Contributor Covenant code of conduct.

License

The gem is available as open source under the terms of the MIT License.