I happened across an interesting thread on Twitter today which posed the question about when you should intervene with alternative solutions as a table gets larger over time:

image

It is always good practice to be proactive on thinking about potential future problems before they occur because obviously it is better to solve them before they become a crisis for your customers. Conversely I can already hear you reaching for your keyboards and getting ready to flame me with Knuth quotes Smile

"The real problem is that programmers have spent far too much time worrying about efficiency in the wrong places and at the wrong times; premature optimization is the root of all evil (or at least most of it) in programming."

Anyway, after some others had inquired a little more about typical usage:

image

I replied with a claim about relational databases and how they would handle such a table

image

But as anyone that knows me from AskTom I always recommend that no-one should ever believe anything they read on the internet Smile unless it comes with some evidence to back it up.

So here's a demo I've put together on the machine at home, and I'm going to scale up things a tad to really test out just what the limits of using a relational database might be. Based on what I've read from the Twitter thread, I'm assuming we have a table that logs every time a user "likes" a post and we'll store when that like was logged. That gives me this simple structure:

  SQL> create table user_likes (   2    user_id int not null,   3    post_id int not null,   4    dt      date default sysdate not null   5  ) ;  Table created.

I can't be sure how close this is to the true requirement/implementation, but lets go with it and see how it handles some load.

I'm going to populate this table under the following assumptions

  • We have a user population of 200,000 distinct users (approximately 2x how many followers @techgirl1908 has).
  • We have 10,000 posts that might be liked (I don't know how many posts have really been done)
  • To give our table some good volume, we'll assume every post has been liked by every user Smile.

Based on this assumption, we can populate the table in random sequence with the following INSERT

 SQL> insert /*+ APPEND */ into user_likes   2  with   3  u as (   4    select /*+ materialize */ rownum user_id from dual   5    connect by level <= 200000   6    order by dbms_random.value ),   7  p as (   8    select /*+ materialize */ rownum post_id from dual   9    connect by level <= 10000  10    order by dbms_random.value )  11  select user_id, post_id, sysdate  12  from u,p;  2000000000 rows created.

which yields 2billion rows. Yes, 2 billion. I don't want to see if 9 million is an issue - I want to know if 200 times that amount is an issue.Smile

Now I'll index that table based on the following (assumed) requirements

  • For a known user and post, do a single row lookup to see if a "like" is present.
  • For a known user, show me all of the posts they have liked.
  • For a known post, show me all of the users that have liked it

This is why I let every user and every post be present in the table, so that when we benchmark the three above scenarios we wont get any artificially good results due to the non-existence of data. In fact, I've done exactly the opposite. Not only will every query we perform in any of the above tests always find some data, they are deliberately more expensive than what we'd expect to find in an real life scenario. Querying posts for a user will always find 10,000 posts! Querying users for a post will always find 200,000 users! I'm going for a worst case scenario for the data we're using.

I'll add the two indexes we'll need.

 SQL> alter table user_likes   2   add constraint user_likes_pk primary key   3     ( user_id, post_id );  Table altered.  SQL> create index user_likes_ix on user_likes ( post_id, user_id , dt);  Index created.

And now here's a PL/SQL routine that will run through the test. It will do 50,000 iterations picking a random user and random post, and exercise the above queries.

Then we'll output the average query elapsed time, and the min/max extrema to get an idea of the response time duration

 SQL> set serverout on SQL> declare   2    type numlist is table of number index by pls_integer;   3    iter int := 50000;   4    u numlist;   5    p numlist;   6    res numlist; resrow user_likes%rowtype;   7    s1 timestamp;   8    s2 timestamp;   9    s3 timestamp;  10    delt number;  11    lo number := 999999999;  12    hi number := 0;  13    cnt int;  14  begin  15    select trunc(dbms_random.value(1,200000) )  16    bulk collect into u  17    from dual  18    connect by level <= iter;  19  20    select trunc(dbms_random.value(1,10000) )  21    bulk collect into p  22    from dual  23    connect by level <= iter;  24  25    s1 := localtimestamp;  26    for i in 1 .. iter  27    loop  28      s2 := systimestamp;  29      select user_id  30      bulk collect into res  31      from   user_likes  32      where  user_id = u(i);  33      delt := extract(second from localtimestamp - s2);  34      if delt < lo then lo := delt; end if;  35      if delt > hi then hi := delt; cnt := res.count; end if;  36    end loop;  37    delt := extract(second from localtimestamp - s1) + 60*extract(minute from localtimestamp - s1);  38  39    dbms_output.put_line(iter||' executions: All posts for nominated user');  40    dbms_output.put_line('=====================================');  41    dbms_output.put_line('Total: '||delt);  42    dbms_output.put_line('Avg: '||(delt/iter));  43    dbms_output.put_line('Low: '||lo);  44    dbms_output.put_line('Hi: '||hi);  45  46    lo  := 999999999;  47    hi  := 0;  48    s1 := localtimestamp;  49    for i in 1 .. iter  50    loop  51      s2 := systimestamp;  52      select user_id  53      bulk collect into res  54      from   user_likes  55      where  post_id = p(i);  56      delt := extract(second from localtimestamp - s2);  57      if delt < lo then lo := delt; end if;  58      if delt > hi then hi := delt; cnt := res.count; end if;  59    end loop;  60    delt := extract(second from localtimestamp - s1) + 60*extract(minute from localtimestamp - s1);  61  62    dbms_output.put_line(iter||' executions: All users for nominated post');  63    dbms_output.put_line('=====================================');  64    dbms_output.put_line('Total: '||delt);  65    dbms_output.put_line('Avg: '||(delt/iter));  66    dbms_output.put_line('Low: '||lo);  67    dbms_output.put_line('Hi: '||hi);  68  69    lo  := 999999999;  70    hi  := 0;  71    s1 := localtimestamp;  72    for i in 1 .. iter  73    loop  74      s2 := systimestamp;  75      select user_id  76      into resrow  77      from   user_likes  78      where  post_id = p(i)  79      and    user_id = u(i);  80      delt := extract(second from localtimestamp - s2);  81      if delt < lo then lo := delt; end if;  82      if delt > hi then hi := delt; end if;  83    end loop;  84    delt := extract(second from localtimestamp - s1) + 60*extract(minute from localtimestamp - s1);  85  86    dbms_output.put_line(iter||' executions: Lookup single post for a nominated user');  87    dbms_output.put_line('=======================================');  88    dbms_output.put_line('Total: '||delt);  89    dbms_output.put_line('Avg: '||(delt/iter));  90    dbms_output.put_line('Low: '||lo);  91    dbms_output.put_line('Hi: '||hi);  92  93  end;  94  / 50000 executions: All posts for nominated user ===================================== Total: 214.157 Avg: .00428314 Low: 0 Hi: .246 50000 executions: All users for nominated post ===================================== Total: 2602.467 Avg: .05204934 Low: .019 Hi: .371 50000 executions: Lookup single post for a nominated user ======================================= Total: 9.169 Avg: .00018338 Low: 0 Hi: .003

Lets take a moment to digest some of that information.

  • You can do ~5400 single row lookups (known user/post combo) per second! (ie, less than a millisecond per query)
  • Grabbing 10,000 posts for a known user will take about 4ms, and at worst 246ms
  • Grabbing 200,000 users for a known post will take about 5ms, and at worst 371ms

So there we go. You can see that even as we scale to billions of rows, the compact branch structure of B-tree indexes means very efficient data access to data. When the volume of rows needed by an index is small (and in this case, I'm even treating 200,000 rows as small!), then in most circumstances, the overall size of the table is not an issue.