1

I have following use case where there are bunch of IDs (GUID) which are mapped to each other. I need to lookup all the IDs given any single ID. For example, let's say my data has following columns:

uid, id1, id2, id3, id4, id5

How to support the following queries:

1. SELECT uid FROM table WHERE id1=x;
2. SELECT id1, id2, id3, id4 FROM table WHERE uid=xyz;

The number of IDs can change (I have to add new columns).

I can create indexes on all columns but that would not be very effective. Should I model this data differently? Is there any NoSQL database which can help model this use-case?

To give more business context for clarity, we have data coming from multiple data sources which have their own custom_id. But they all identify the same person (UID). Thats why we need to map all the data source ids to our own internal UID. Hence the question.

  • The number of columns have max bound of 20-25.
  • They are nullable.
  • The number of id's can be different per row (thats why nullable).
  • Datatypes are STRING for all.
  • UID will be primary key.
  • 2
    You can create a single array column that contains all IDs. Then you can run something like where 'foobar' = any (ids) or even search for multiple ID values: where ids @> array['foo', 'bar']. The array can be indexed. If that is really a "map" of IDs then using a hstore (key/value map) might also be an option – a_horse_with_no_name Apr 21 '17 at 9:03
  • @a_horse_with_no_name I have thought of that approach. Having a single column for all ID's increases the number of rows (maybe even data size). Having a hstore will require database and hstore to be in sync always. – cmbendre Apr 25 '17 at 6:07
  • I am talking about an array of ID values. It's still a single column, but contains multiple values create table x(uid uuid, ids integer[]); A hstore column is also a single column that is part of the table definition. It is by definition "in sync" with the database as it is in in the database. – a_horse_with_no_name Apr 25 '17 at 6:31
3

You can model your table as a dictionary with two columns:

  1. UID
  2. ID_VALUE

Both would be indexed with dedicated index.

You can then add as many ID_VALUE rows for any UID and search for an UID given ID_VALUE.

Queries would then look like

SELECT UID FROM table WHERE ID_VALUE=x;
SELECT ID_VALUE FROM table WHERE UID=xyz;

Second query would return more than one row.


EDIT

I need to lookup all the id's given any single id

As long as you have all IDs bound by a common column, in this case UID, this should be possible. Consider following query:

SELECT t2.id_value
  FROM table t1
      ,table t2
 WHERE t1.uid = t2.uid
   AND t1.id_value = x

This will return all id's given a single id X.

It really doesn't matter what are the values of ID_VALUE. They may be other UIDs pointing to this one or any other arbitrary number. If you want to search of any ID_VALUE including the UID value, you can include this UID value into the set too so you will have one row where UID = ID_VALUE.

EXAMPLE

Let's say you have following data in your model:

UID   ID1   ID2  ID3
--------------------
  1     2     3    4
  2     1     4
  3     4
  4     2     3

You can model this data in a dictionary table like so:

UID   ID_VALUE
--------------
  1          2
  1          3
  1          4
  2          1
  2          4
  3          4
  4          2
  4          3

If you want to include the UID in the list so the last query in my example would return ALL of IDs including the UID, you would then have:

UID   ID_VALUE
--------------
  1          2
  1          3
  1          4
  1          1 <---
  2          1
  2          4
  2          2 <---
  3          4
  3          3 <---
  4          2
  4          3
  4          4 <---

I've marked the rows added to satisfy this requirement. Executing the query:

SELECT t2.uid
      ,t2.id_value
  FROM table t1
      ,table t2
 WHERE t1.uid = t2.uid
   AND t1.id_value = 1

Will result in:

UID   ID_VALUE
--------------
  1          2
  1          3
  1          4
  1          1 
  2          1
  2          4
  2          2

This will return all IDs given any single id as per requirement. Note that ID_VALUE of 1 can be found in both sets with UID = 1 and UID = 2, both are returned.

This would be equivalent to executing this query on your flat design:

SELECT * FROM table WHERE UID=1 OR ID1=1 OR ID2=1 OR ID3=1
  • @MarkoVodopija This approach is good. But the only trade-off is that number of rows increases 20x if we assume there are 20 ids mapped to each UID. Is there any drawback to having such a large number of rows in a single table ? – cmbendre Apr 25 '17 at 6:10
  • @cmbendre Can you predict how many rows would you have? I don't see any problems for any modern RDBMS to handle millions of rows efficiently given proper indexes. – Marko Vodopija Apr 25 '17 at 9:26
  • We will have around 100 million UID over the long term. So according to your approach, each having 20 rows will make it 2 billion rows with indexes. How do you think Postgres will perform for such large number of rows ? – cmbendre Apr 26 '17 at 11:35
  • @cmbendre Seems a_horse_with_no_name has better grasp over Postgres than me and in his answer he is saying you should not have problems with it. Depending on how Postgres is handling array indexes in comparison to standard b-tree column index, you might have similar performance with either option. Number of rows is not relevant here. The amount of data you will have would be (more or less) the same regardless of the choice of the design. Indexes would be very similar too.. Why don't you test both approaches? Generate huge amount of data (rows or array items) and see how it performs... – Marko Vodopija Apr 26 '17 at 12:12
2

In this case an array seems approriate:

create table t1
(
  uid varchar(50) not null primary key,
  alternate_ids varchar(50)[] 
);

insert into t1 (uid, alternate_ids)
values 
('one', array['eno', 'noe']),
('two', array['owt', 'tow', 'wto']),
('three', null);

Querying the table:

SELECT uid 
FROM t1
WHERE 'eno' = any(alternate_ids);

SELECT alternate_ids
FROM t1 
WHERE uid = 'one';

Find rows that contain two specific alternate IDs:

SELECT uid 
FROM t1
WHERE alternate_ids @> array['owt', 'wto']::varchar[];
uid
---
two

(Note: the cast ::varchar[] would not be needed if the column was declared as text[])

Find rows that contain any of the alternate IDs:

SELECT uid 
FROM t1
WHERE alternate_ids && array['owt', 'noe'];
uid
---
one
two

The array can be indexed which makes looking for alternate IDs quite efficient using the @> and && operators:

I filled the above table with a million rows. Each one with a random array of 1 to 20 values.

The following query returns about 10000 rows (out of 1 million) from that table

select *
from t1 
where alternate_ids @> array['42'];

The execution plan is:

Bitmap Heap Scan on t1  (cost=47.13..9624.00 rows=10567 width=115) (actual time=5.872..14.894 rows=10635 loops=1)                   
  Recheck Cond: (alternate_ids @> '{42}'::text[])                                                                                   
  Heap Blocks: exact=8169                                                                                                           
  ->  Bitmap Index Scan on t1_alternate_ids_idx  (cost=0.00..44.48 rows=10567 width=0) (actual time=3.665..3.665 rows=10635 loops=1)
        Index Cond: (alternate_ids @> '{42}'::text[])                                                                               
Planning time: 0.274 ms                                                                                                             
Execution time: 15.411 ms                                                                                                           

If you are unfamiliar with Postgres execution plans: those 10635 rows are retrieved from that table in about 15ms (milliseconds)


However, a properly normalized model would also work just as fine. And it might give you more flexibility. Tables with millions of rows are not a problem. Even hundreds of million depending on how you access them.

0

I can't se any reason to use arrays or other complex data types.

For each person you have zero or more customer IDs. The usual approach to implement a 1:n relationship is the following (* identifies the primary key)

person(uid*,...)
personsource(sourceid*, customerid*,uid,...)
personsource.uid references person.uid

Maybe you should not trust the uniqueness of (sourceid, customerid) because it is from an external source and you should make (sourceid, customerid, uid) your primary key.

This is similar to the approach of Marko Vodopia except when you use Marko's approach you will lose some information: The source of your id, which is represented by the column here the id is stored in your table, so the id in column id1 means source 1, the id in column id2 is from source 2,... Your queries can be implemented in the following way:

1. SELECT uid FROM source WHERE source=1 and customerid=x;
2. SELECT sourceid, customerid FROM source WHERE uid=xyz and source in (1,2,3,4);

Note that the second query returns up to four rows instead of one row as your query does.

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.