1

I'm trying to figure out the optimal solution for filtering a result set by every permutation of a given input criteria. We're using Postgresql 11 on AWS RDS

I've created a sql fiddle here that outlines the schema I'm dealing with. Below is a copy of the sample data in that problem.

In this example we use "investors" with "holdings" (positions) in certain "securities". Securities have 3 attributes we care about:

  1. Market Cap
  2. Sector
  3. Country

I'd like to be able to filter investors on one or more of these 3 criteria. So for instance I'd like to ask a question like "show me investors that focus in small-cap, canadian, mining companies" and get only those investors with holdings in securities matching those attributes. Or, "show me investors that focus in small-cap, mid-cap and large-cap companies"

For each of these attributes, I'd like to be able to query by one or many values, and I'd want to see investors that hold all permutations of those types of securities. So "show me investors in small-cap, mid-cap, canadian, american, materials" companies means:

Show me investors with:

  • at least one holding in small-cap, canadian, materials AND
  • at least one holding in mid-cap, canadian, materials AND
  • at least one holding in small-cap, american, materials AND
  • at least one holding in mid-cap, american, materials

The naive solution I've come up with is something along the lines of:

SELECT * from investors i
-- small-cap, canadian, materials holdings
WHERE EXISTS (
  SELECT 1 FROM holdings h
    JOIN securities s on h.security_id = s.id
  WHERE s.market_cap = 'SM'
    AND s.country = 'CA'
    AND s.sector = 'materials'
  AND h.investor_id = i.id
)
-- mid-cap, canadian, materials holdings
AND EXISTS (...)
-- and so-on for each permutation of the criteria

While this works, it's definitely not scalable. I'm pretty sure there's a way to improve upon this situation so it's not exponential in cost, but the formula eludes me at this moment.

Our system has hundreds of millions of holdings for hundreds of thousands of investors so this naive solution simply won't scale.

Can someone point me in the right direction here that would yield an optimal solution and avoid the exponential sub-selects that this naive solution would lead to?


Sample Data

Securities

| id | name         | sector      | market_cap | country |
|----+--------------+-------------+------------+---------|
| 1  | 'Mining ABC' | 'materials' |  'SM'      | 'CA'    |
| 2  | 'SilverFox'  | 'materials' |  'MD'      | 'CA'    |
| 3  | 'Big Coppa'  | 'materials' |  'LG'      | 'CA'    |
| 4  | 'Golds R Us' | 'materials' |  'LG'      | 'US'    |
| 5  | 'Weedly'     | 'pharma'    |  'SM'      | 'CA'    |
| 6  | 'HazeMaker'  | 'pharma'    |  'MD'      | 'US'    |
| 7  | 'StickyIcky' | 'pharma'    |  'LG'      | 'US'    |

Investors

| id | name   |
|----+--------|
| 11 | 'john' |
| 22 | 'bill' |
| 33 | 'susan'|
| 44 | 'jill' |

Holdings

| security_id | investor_id | shares |
|-------------+-------------+--------|
| 5           | 11          | 1      | -- john,  small-cap canadian pharma
| 7           | 11          | 12     | -- john,  large-cap american pharma
| 2           | 11          | 13     | -- john,  mid-cap   canadian materials
| 3           | 11          | 514    | -- john,  large-cap canadian materials
| 7           | 22          | 15     | -- bill,  large-cap american pharma
| 5           | 22          | 16     | -- bill,  small-cap canadian pharma
| 1           | 22          | 117    | -- bill,  small-cap canadian materials
| 2           | 33          | 18     | -- susan, mid-cap   canadian materials
| 3           | 33          | 919    | -- susan, large-cap canadian materials
| 4           | 33          | 20     | -- susan, large-cap american materials
| 1           | 44          | 21     | -- jill,  small-cap canadian materials
| 3           | 44          | 22     | -- jill,  large-cap canadian materials
| 4           | 44          | 123    | -- jill,  large-cap american materials
| 5           | 44          | 456    | -- jill,  small-cap canadian pharma
| 6           | 44          | 20     | -- jill,  mid-cap   american pharma
| 7           | 44          | 3      | -- jill,  large-cap american pharma
0
1

If they have to have one from each, then the total number of distinct holdings they have, when distinction is based only on those 3 properties, must be equal to the number of "permutations" which exist:

select investor_id from holdings h join securities s on (h.security_id = s.id) 
   where market_cap  in ('SM', 'MD') and country in ('CA','US') and sector in ('materials')
   group by investor_id
   having count(distinct (market_cap, country, sector)) = 2*2*1

This is probably not going to scale awesome, but probably better than your initial idea.

5
  • Oh interesting... i hadn't thought about actually matching against the permutation count. Let me try that out.
    – brad
    Oct 31 '19 at 13:14
  • I just realized I wasn't clear enough in my question, which I've now updated. It's not required that all of those attributes are filtered by. I could simply as for investors that care about small, mid and large market_cap. This example fails using the above: db-fiddle.com/f/m88X6j1UjrN4EXPndDBXwf/2 You can see the last 2 queries are the naive solution and your solution to that problem
    – brad
    Oct 31 '19 at 14:40
  • You would have to remove from the count(disintct(...)) any fields which are unconstrained by the where clause in your query. So, you would have to somehow construct the query programmatically.
    – jjanes
    Oct 31 '19 at 20:01
  • haha I JUST came to this conclusion on my way home also. Yup this totally works. Thanks!
    – brad
    Oct 31 '19 at 21:59
  • I'm just going to leave this open for a bit though as I feel there's a more optimal calculation, but will mark this as the right answer if I don't get any other solutions
    – brad
    Oct 31 '19 at 22:00

Your Answer

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

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