How to model data which requires index on all columns?

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

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.

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.