I'm finishing off work on a complex rule-engine for Hotel Rates with real-time queries. There is a lot of conditions addressing intersections of periods for options, restrictions and policies. All of these are per date, meaning the time of day is irrelevant.

It varies wildly, from customer to customer, whether period spans a few days or several years, so it is not a feasible solution to denormalize to each day in the period for each thing in the system.

Currently, I'm using skip lists with 2 entries per 'thing' that has a period. Then I can intersect 'things' starting before end of relevant period, and ending after the beginning of the relevant period. This works ok, it's the best compromise so far, but I still end up mostly allocating nodes I don't need, and spending CPU filtering away 'from' nodes that don't have a corresponding 'to' node in the output set.

It is implemented in C# (state is in-mem, loaded by event-streams)), mostly immutable objects, classes for things that gets passed around a lot, structs for private collections within classes.

  • I don't have time to write a full answer, but here's a pointer that may let you answer this yourself. There's a structure generally called a QuadTree that stores rectangles in a 2d space and let's you query it efficiently for a list of rectangles that intersect a rectangle you're interested in. There's also a 3d generalisation of the same structure called an Octree. What you're looking for is the 1-dimensional equivalent, which ought to be easy to work out looking at how the higher dimensional variants work. – Jules Mar 18 '17 at 14:03
  • Are you sure denormalizing per day is infeasible (have you measured)? A few thousand entries ought to be trivial for a modern database, especially for something that changes relatively infrequently. – Karl Bielefeldt Mar 18 '17 at 15:04
  • 1
    Just as a pointer: google.github.io/guava/releases/16.0/api/docs/com/google/common/… (for Java and not C# but I imagine you can find an equivalent / implement your own). – walpen Mar 18 '17 at 16:14
  • 1
    Interval tree (Wikipedia.org) There are some other choices, all trying to optimize on similar situations. – rwong Mar 20 '17 at 2:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.