Objective: Users submit their Contact Books and then application looks for connections between users according to their Phone Number. Something like "6 Handshakes" idea (https://en.wikipedia.org/wiki/Six_degrees_of_separation).

Problem: Make this query performance close to real time, when User submits his phone number and gets full list of other phones he may know. Plain list - without connections (graph vertexes etc), but full, not paginated (this requirement is here because original goal is more complex)

Question: is this possible to achieve close-to-realtime performance with pure relational database, without Graph databases (Neo4j, etc), graph extensions (bitnine agensgraph) or workflow redesign? Any denormalization is possible, but as far as I understand, it won't help.


test=# select * from connections;
 user_phone | friend_phone
          1 |            2
          1 |            3
          1 |            4
          2 |            6
          2 |            7
          2 |            8
          8 |           10
          8 |           11
          8 |           12
         20 |           30
         40 |           50
         60 |           70

I expect to receive following connections for User with Phone === 1:

(9 rows)

It is really difficult to estimate real-world connections numbers. But I was testing at least with:

  • 10,000 Users (Phone Numbers)
  • Each user was randomly assigned with 50-1000 Connections with pseudo-random other Users
  • This resulted in about 1,000,000 Connections

If it is impossible to achieve this in general (using some tricky ORDER BYs or subqueries etc) - what metrics should be considered for example to understand that:

with 1,000,000 connections you need 128GB RAM instance to get 2 seconds response time


for 100,000,000 connections you need 1TB RAM instance to get 5 seconds response time


P.S. I tried subqueries, CTEs, JOINs, but eventually I've found that WITH RECURCISVE is the most explicit way and it has the same resulting time as other approaches.

This is the table:

CREATE TABLE connections (
  user_phone bigint NOT NULL,
  friend_phone bigint NOT NULL

This is how I seed data:

INSERT INTO connections(user_phone, friend_phone) (
  SELECT generate_series AS user_phone, generate_series(1, (random()*5000)::int) AS friend_phone from generate_series(1, 500) ORDER BY user_phone

I've created some indexes:

test=# \d connections
               Table "public.connections"
    Column    |  Type  | Collation | Nullable | Default
 user_phone   | bigint |           | not null |
 friend_phone | bigint |           | not null |
    "connections_user_phone_friend_phone_idx" UNIQUE, btree (user_phone, friend_phone)
    "connections_friend_phone_idx" btree (friend_phone)
    "connections_friend_phone_user_phone_idx" btree (friend_phone, user_phone)
    "connections_user_phone_idx" btree (user_phone)

I expect friend_phones.count >>> user_phones.count, so index connections(friend_phones, user_phones) seems to be the most appropriate, but I've created all 4 indexes during testing.

2270852 connections records were generated. Then I run this query:

    SELECT friend_phone FROM connections WHERE connections.user_phone = 1

    SELECT friends.friend_phone FROM connections AS friends JOIN p ON friends.user_phone = p.friend_phone
SELECT COUNT(friend_phone) FROM p;

It returns 5002 records and executes for about 3 seconds. EXPLAIN ANALYZE looks like the following:

                                                                                      QUERY PLAN
 Aggregate  (cost=3111105.00..3111105.01 rows=1 width=8) (actual time=3151.781..3151.781 rows=1 loops=1)
   CTE p
     ->  Recursive Union  (cost=0.43..2146207.20 rows=42884347 width=8) (actual time=0.060..3148.294 rows=5002 loops=1)
           ->  Index Scan using connections_user_phone_idx on connections  (cost=0.43..3003.69 rows=4617 width=8) (actual time=0.055..2.024 rows=4137 loops=1)
                 Index Cond: (user_phone = 1)
           ->  Merge Join  (cost=4500.77..128551.66 rows=4287973 width=8) (actual time=768.577..1359.598 rows=635428 loops=2)
                 Merge Cond: (friends.user_phone = p_1.friend_phone)
                 ->  Index Scan using connections_user_phone_idx on connections friends  (cost=0.43..54054.59 rows=2270852 width=16) (actual time=0.013..793.467 rows=1722262 loops=2)
                 ->  Sort  (cost=4500.34..4615.77 rows=46170 width=8) (actual time=0.765..74.850 rows=637677 loops=2)
                       Sort Key: p_1.friend_phone
                       Sort Method: quicksort  Memory: 65kB
                       ->  WorkTable Scan on p p_1  (cost=0.00..923.40 rows=46170 width=8) (actual time=0.001..0.314 rows=2501 loops=2)
   ->  CTE Scan on p  (cost=0.00..857686.94 rows=42884347 width=8) (actual time=0.062..3150.755 rows=5002 loops=1)
 Planning Time: 0.409 ms
 Execution Time: 3152.412 ms
(15 rows)

I feel like I'm missing something, because, even if many loops are required, it is a finit number of connections for each user which is greatly less than total amount of connections (in the example above - 5000 user connections against 2,2M connections overall ~ 0,25%). Maybe some specific index type? Maybe some other tricks I don't know about?

Thanks in advance for reading such a big question :)

P.P.S, used Postgres 12 with next postgresql.conf:

# DB Version: 12
# OS Type: mac
# DB Type: web
# Total Memory (RAM): 16 GB
# CPUs num: 8
# Data Storage: ssd

max_connections = 200
shared_buffers = 4GB
effective_cache_size = 12GB
maintenance_work_mem = 1GB
checkpoint_completion_target = 0.7
wal_buffers = 16MB
default_statistics_target = 100
random_page_cost = 1.1
work_mem = 5242kB
min_wal_size = 1GB
max_wal_size = 4GB
max_worker_processes = 8
max_parallel_workers_per_gather = 4
max_parallel_workers = 8
max_parallel_maintenance_workers = 4
  • The two single-column indexes are probably just a waste of space since they are covered by the other two. To avoid cycles in the graph, you may want to add a constraint or index for that. Example: create unique index ak2 on connections (least(friend_phone, user_phone), greatest(friend_phone, user_phone)); A before trigger can be handy for satisfying such constraint. If your sample data contains rows like (1,2), (2,3),..(n,1) that may cause problem for the recursive CTE – Lennart Jul 15 at 21:31
  • If you run the query a second time, does it take equally long as the first time? – Lennart Jul 15 at 21:33
  • In addition, you may want a constraint like check (user_phone<>friend_phone) – Lennart Jul 15 at 21:36
  • I have added some observations in https://dbfiddle.uk/?rdbms=postgres_12&fiddle=6f54d05b434d3482dfbe1e9268de1a37 With the constraints I mentioned earlier and a modified population, the first level contains ~1000 neighbours and second layer ~1000000, i.e. almost all of the table. – Lennart Jul 15 at 21:53
  • Some additional observations on how many duplicates that has to be removed by the union operator in the CTE: dbfiddle.uk/… – Lennart Jul 15 at 22:03

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.