0

In my application I have requests and items, each of which are associated with property tuples (key value pairs, where keys can be repeated) stored in a Postgres database.

The goal is to find a single matching item for each request, after which they are paired and removed from future searches (basically this a queuing problem). Example:

CREATE TABLE request (
    request_id uuid PRIMARY KEY,
    create_time TIMESTAMP NOT NULL,
);

CREATE TABLE request_property (
    request_id uuid REFERENCES request (request_id),
    key VARCHAR(80),
    value VARCHAR(80),
    PRIMARY KEY(request_id, key, value)
);

CREATE TABLE item (
    item_id uuid PRIMARY KEY
);

CREATE TABLE item_property (
    item_id uuid REFERENCES item (item_id),
    key VARCHAR(80),
    value VARCHAR(80),
    PRIMARY KEY(item_id, key, value)
);

To find a match, the request properties must be a superset of the item properties. For example, the following requests would all match the same item:

request_properties0 = [('color', 'red'), ('type', 'fruit'), ('type', 'apple')]
request_properties1 = [('color', 'red'), ('type', 'fruit')]
request_properties2 = [('color', 'red'), ('type', 'apple')]
request_properties3 = [('type', 'fruit'), ('type', 'apple')]
request_properties4 = [('color', 'red')]
request_properties5 = [('type', 'fruit')]
request_properties6 = [('type', 'apple')]
request_properties7 = []

item_properties = [('color', 'red'), ('type', 'fruit'), ('type', 'apple')]

I'm struggling to find a decent way to perform this matching efficiently. Essentially, to match an item against the active requests, you need to consider the powerset of its properties (all possible subsets of the item properties).

One strategy we've taken so far, is to calculate a hash of the sorted properties in each request, and store that along with the request. Then we take the hash of each possible subset of item properties and store this as well. We can then join based on the hashes.

This works somewhat well, but the cost grows exponentially as we add more properties. 5 properties produce 32 possible subsets, while 10 properties produce 1024. This is beginning to become a bottleneck and is limiting us from adding more properties.

Other details that could be useful to consider:

  • In peak periods there are 100,000 waiting requests, and items can be assigned as soon as they become available.
  • In slow periods, there are 5,000 available items, and requests can be assigned as soon as they become available.
  • The types of requests and items are somewhat predictable. The types of items that will become available can be known ahead of time, however, the types of requests may vary (although they are usually reoccurring).
  • We reject requests upfront if we can determine they will never become available (i.e. never match an item), as some combinations of properties are invalid.
    • e.g. it wouldn't make sense to list an item with both ('size', 'big') and ('size', 'small')

If anyone has worked on a similar type of problem I'd love to hear your strategies or advice.

I'm open to completely reworking this system in any way.

1 Answer 1

1

compound index

You only disclosed a single index on item_property:

    PRIMARY KEY(item_id, key, value)

(In one of your alternate setups the table includes a hash column, plus indexing for that.)

You need a (key, value, item_id) index to support queries. Additionally, the request_property table would benefit from a (key, value, request_id) compound index. Now you can efficiently JOIN on exact key + value match.


The separate key and value columns are very nice, but a unified key_value column suffices for this particular query.


Goal: We wish to match requests against items with low latency.

Think about how the backend query optimizer looks for an access path. Given the conjuncts WHERE x AND y AND z it will determine which of the three is most selective, and exploit that index.

In your situation, the various key strings are regrettably opaque. But you say their populations tend to be fairly stable over time. Let's introduce key popularity rankings. It could be via another column. For simplicity I will introduce it as modified key_value spellings.

Specifying type is more common than color, so we will give them prefixes of 01 and 09 respectively.

Specifying a color of red is more common than blue, leading to prefixes of 02 and 05. (Only order matters.) Similarly for type choices.

This gives us an item that looks like

item_properties = ['09_color_02_red', '01_type_02_fruit', '01_type_05_apple']

What have we accomplished here?

Some requests will be for rare items and typically will need to wait, while other requests can be for popular items, rapidly satisfied. We have lexically ordered type before color.

Based on pending requests we can frequently issue item queries (JOINs) that mention WHERE key_value LIKE '01_type_%', or even ... LIKE '01_%', if several popular things share that same ranking. This limits the number of rows we must examine, and quickly moves popular items through the system, so we needn't keep re-examining such items. Numeric column comparisons would be more flexible than LIKE patterns.

Less frequently, perhaps once per minute, we can issue an unselective query that sweeps out all the rare items which happen to have matching requests.

One way to think of this is we plan to sweep out ~ 10% of the rows with each query, both for low- and highly-selective queries. And we delay issuing the query until enough backlogged rows have accumulated that we're confident we'll find a bunch of matches, even though 90% of the retrieved rows won't help us make immediate progress. This motivates high frequency queries for popular items, and low frequency queries for rare items.


Here is one potential query schedule, with brief sleep()'s in between:

  • common
  • common
  • common
  • rare (which also encompasses "common" item matches)

And then we repeat.

Obviously the latency for a rare item match will be bigger than for a common item match.

Here is a competing schedule, taken from an example trace:

  • common
  • rare (exclusively, won't match common, therefore few rows, very fast)
  • common
  • rare (exclusively)

Notice that this schedule does less work, in the sense of four invocations retrieving fewer total rows. And retrieving fewer rows can spell better cache hit ratios for rare item rows.

Also notice that, based on incoming item arrivals and request arrivals, we can rapidly schedule a rare item query. Which might lead to this dynamic schedule:

  • common
  • rare
  • rare
  • common

That is, upon receiving a rare request, we might choose to immediately issue a query for it, even though we recently issued such a query. Rapid back-to-back queries for rare items can make more sense than for common items, as we know that something just changed, and our query will rapidly complete. Going through all the "common" rows is more of a slog, better suited to the cadence of a regular wallclock schedule.

So latency for rare vs common items might be separate KPI metrics to track.

We know that rare items will take longer to match, it's inherent, even if all DB operations took zero milliseconds. So a single unified "extra latency" metric might be what the code wishes to optimize.


Maintain four counters:

  • {rare, common} items
  • {rare, common} requests

Each incoming {item, request} event will bump one of the counters. If the counter exceeds a threshold, clear relevant counters to zero and issue a DB query. This lets you wait for "enough" things to accumulate in the DB that there's a good chance we'll be able to match and clear some out.

The rare threshold can be set lower than the common threshold.

An occasional (hourly?) query that measures what fraction of unmatched rows are for "rare" items might be responsible for setting that threshold.

3
  • This approach is interesting. I like how it reduces the search space. I'd still like to avoid slow downs on the rarer items (minimizing latency is pretty important for this system). I suppose I could have two workers running, one for the fast-lane items and one for the slow-lane items? In such a system when do you go about computing the popularity/rankings? Would it be something that updates live as requests are submitted, or some batch job run separately?
    – flakes
    Feb 10 at 22:30
  • 1
    I was serious about that 90 / 10 rule. (Or 80 / 20, whatever.) Each query drags in a bunch of "useless" (unmatched) rows, thereby slowing down other concurrent competing queries. So we should have a principled approach of "I believe that issuing this query now will remove N pending requests from the system." Impatient queries that remove zero requests are bad queries. // Good news on "rare": they are cheap queries, retrieving few rows. // I envision popularity rankings as being pretty static, set just once upon enqueueing. It's merely a heuristic. Even rare requests eventually get matched.
    – J_H
    Feb 10 at 22:36
  • Very insightful. I'll have to think this through a bit more. We run a few separate instances of this software where problem is the same but the properties are different. Still known ahead of time, but will have different frequencies. Will be a matter of allowing this to be configuration driven, and provide a good plan for redetermining the weights when we go to add new property pairs.
    – flakes
    Feb 10 at 22:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.