Friday, February 22, 2019

Simple example on why LIMIT is not always the best thing for SQL Database

Since our production database grew to the size where querying data without indices became a suicide mission, we have learned that LIMIT does not always translate into faster query time and less work on the machine. Today at work, we ran into a beautifully simple example to illustrate this point, which was perceived as counter-intuitive by more junior teammates.

Here we have a query over a 8M-row table, the condition fits squarely into an index.

EXPLAIN SELECT "record".*
FROM "record" WHERE ("record"."status" = 'not_found' AND "record"."updated_date" < '2018-12-23 15:48:23.008320+00:00');
                                                             QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on record  (cost=256890.59..3475874.26 rows=8448978 width=1740)
   Recheck Cond: (((status)::text = 'not_found'::text) AND (updated_date < '2018-12-23 15:48:23.00832+00'::timestamp with time zone))
   ->  Bitmap Index Scan on not_found_records_idx  (cost=0.00..254778.35 rows=8448978 width=0)
         Index Cond: (((status)::text = 'not_found'::text) AND (updated_date < '2018-12-23 15:48:23.00832+00'::timestamp with time zone))
(4 rows)


That was still lot of records, so we were hoping a LIMIT clause would shorten the execution time.

EXPLAIN SELECT "record".*
FROM "record" WHERE ("record"."status" = 'not_found' AND "record"."updated_date" < '2018-12-23 15:48:23.008320+00:00') LIMIT 1;
                                                              QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.00..0.46 rows=1 width=1740)
   ->  Seq Scan on record  (cost=0.00..3923250.74 rows=8448978 width=1740)
         Filter: ((updated_date < '2018-12-23 15:48:23.00832+00'::timestamp with time zone) AND ((status)::text = 'not_found'::text))
(3 rows)


Only that it didn't. Adding the LIMIT clause changed the query plan from Bitmap Index Scan to a Sequence Scan, which is about the worst thing we want to do on a 8M-row table. It is a typical "optimization" of the planner, who thought that the query with LIMIT clause was too small.

Operation wise, an index scan is more expensive than a sequence scan. An index scan would require to read the index pages first and then read the data pages for relevant rows. The sequence scan only deal with data pages. And so when the LIMIT is small, combined with the table statistics, the planner is tempted to believe there are enough (random) rows that match the filter condition, which makes a sequence scan cheaper.

In fact, somehow this table statistics suggests that every LIMIT is too small till it is half of the table!

EXPLAIN SELECT "record".*
FROM "record" WHERE ("record"."status" = 'not_found' AND "record"."updated_date" < '2018-12-23 15:48:23.008320+00:00') LIMIT 3000000;
                                                              QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.00..1393038.57 rows=3000000 width=1740)
   ->  Seq Scan on record  (cost=0.00..3923250.74 rows=8448978 width=1740)
         Filter: ((updated_date < '2018-12-23 15:48:23.00832+00'::timestamp with time zone) AND ((status)::text = 'not_found'::text))
(3 rows)

EXPLAIN SELECT "record".*
FROM "record" WHERE ("record"."status" = 'not_found' AND "record"."updated_date" < '2018-12-23 15:48:23.008320+00:00') LIMIT 4000000;
                                                                   QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=257234.59..1781198.16 rows=4000000 width=1740)
   ->  Bitmap Heap Scan on record  (cost=257234.59..3476218.26 rows=8448978 width=1740)
         Recheck Cond: (((status)::text = 'not_found'::text) AND (updated_date < '2018-12-23 15:48:23.00832+00'::timestamp with time zone))
         ->  Bitmap Index Scan on not_found_records_idx  (cost=0.00..255122.35 rows=8448978 width=0)
               Index Cond: (((status)::text = 'not_found'::text) AND (updated_date < '2018-12-23 15:48:23.00832+00'::timestamp with time zone))
(5 rows)


Adding an ORDER BY clause into the query brings structure to the search and guide the planner to use the index

EXPLAIN SELECT "record".*
FROM "record" WHERE ("record"."status" = 'not_found' AND "record"."updated_date" < '2018-12-23 15:48:23.008320+00:00') ORDER BY "record"."imported_date" LIMIT 1;
                                                                      QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=3518127.15..3518127.15 rows=1 width=1740)
   ->  Sort  (cost=3518127.15..3539249.59 rows=8448978 width=1740)
         Sort Key: imported_date
         ->  Bitmap Heap Scan on record  (cost=256898.59..3475882.26 rows=8448978 width=1740)
               Recheck Cond: (((status)::text = 'not_found'::text) AND (updated_date < '2018-12-23 15:48:23.00832+00'::timestamp with time zone))
               ->  Bitmap Index Scan on not_found_records_idx  (cost=0.00..254786.35 rows=8448978 width=0)
                     Index Cond: (((status)::text = 'not_found'::text) AND (updated_date < '2018-12-23 15:48:23.00832+00'::timestamp with time zone))
(7 rows)

Actually, any random ORDER BY would do

EXPLAIN SELECT "record".*
FROM "record" WHERE ("record"."status" = 'not_found' AND "record"."updated_date" < '2018-12-23 15:48:23.008320+00:00') ORDER BY random() LIMIT 1;
                                                                      QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=3539253.59..3539253.60 rows=1 width=1748)
   ->  Sort  (cost=3539253.59..3560376.04 rows=8448978 width=1748)
         Sort Key: (random())
         ->  Bitmap Heap Scan on record  (cost=256902.59..3497008.70 rows=8448978 width=1748)
               Recheck Cond: (((status)::text = 'not_found'::text) AND (updated_date < '2018-12-23 15:48:23.00832+00'::timestamp with time zone))
               ->  Bitmap Index Scan on not_found_records_idx  (cost=0.00..254790.35 rows=8448978 width=0)
                     Index Cond: (((status)::text = 'not_found'::text) AND (updated_date < '2018-12-23 15:48:23.00832+00'::timestamp with time zone))
(7 rows)


However, that is still far from optimal. In order to return the first row, the database first needs to fetch all rows matching the index condition, and only after that, sorts. This creates strains on the machine memory and maybe even disk swap.

Index is actually ordered structure (BTree). The most optimal query is the one using one of the indexed columns for sorting.

EXPLAIN SELECT "record".*
FROM "record" WHERE ("record"."status" = 'not_found' AND "record"."updated_date" < '2018-12-23 15:48:23.008320+00:00') ORDER BY "record"."updated_date" LIMIT 1;
                                                                QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.56..1.90 rows=1 width=1740)
   ->  Index Scan using not_found_records_idx on record  (cost=0.56..11280384.47 rows=8448978 width=1740)
         Index Cond: (((status)::text = 'not_found'::text) AND (updated_date < '2018-12-23 15:48:23.00832+00'::timestamp with time zone))
(3 rows)

This, in fact, is even more effective that the original no-order query, with or without LIMIT.

Friday, February 1, 2019

2018 - Shit am I getting old?

Roughly 4 years ago I put together The Transforming 2014. In retrospective, it was a great year. It felt exactly what youth should feel like, feel like I can afford to fail and bounce back, that opportunities are there to take, and that I am the master of my life. 2018 feels very different. The year followed a trajectory I have carved out over the last few years. It is not particularly eventful, the changes are there, but not exactly tangible. For the lack of eloquence, I would put it similar to when one cries, all the sorrows and memories and grudges build up inside, but till the instant everything bursts out in the form of tear drops, the entire thing is internal and invisible. If a tree falls in a forest and no one is around to hear it, does it make a sound?


Size and Duration matter

Before I got accused for having lewd thought, this is a note about Parcel Perform. That's what I do. I am a software engineer here. For the fourth year. I have never worked on a single project that long, and I definitely have been staying in Vietnam longer than my intention.

We build a product around the belief that logistics optimization is the next frontier of e-commerce war. And in that business, size matters. Specifically, dataset size, which grows by dozens of GB every week. At that speed, what worked a month ago, wouldn't work for the next. The job description is as pure as it can get, find a way to process incoming data most efficiently before the size squashes you like an insignificant insect in tropical storm, all while adding increasingly advanced features to deliver values. Or to build a train from the first material you find, all while keeping it running on a century-old rails, hoping you would make it to the next station, if you prefer to speak metaphors.

I can no longer just add a column with a default value to my database, because that would update hundreds of millions of rows and grind everything to a halt in the process. Everything I thought I knew about software is put into tests. At times, I feel like an imposter, a fraud. I feel alive every time anything breaks. Which is about every day.

This is also my third time being employee #0 and building a tech team from the ground up. I have a knack doing this. I know which minimal unit of work provides most impact. And I know what developers need to level up their career. But I hope I won't have to repeat the same thing in my next job. The first year of every startup is to build glorified excel sheets. The first engineer's day is always a constant juggle between development, test, and expectation management. It gets old.

I have hung around with Parcel Perform long enough to pass that stage. We get to work on interesting challenges unique to our business. Our tech stack moulded around us. We have a support network so that the weight of the entire system does not have to rest on a single shoulder. It takes time for things to come together, and so, duration matters.

Creativity Winter

As much as I enjoy seeing my technical skills grow in the last couple of years, the same can't be said about my creativity outside of work.
  • Between 2016 and 2018, I wrote 13 posts. I wrote 19 posts in 2015 alone. 
  • At some points, my photo app only shows content on white board I took post-meeting.
  • The last Barcamp in Saigon was in 2016.
None of these was an act of consciousness. Like, I never decided I didn't need this in my life any more. I noticed that my most creative period was when my life happens between airports and on MRT rides. Somehow the constant scenery change kept my mind alert and fresh. Though I successfully prevented my career from repeating itself, the life outside of work got stuck in an explore and exploit paradox. On the one hand, there must still be stuff out there to give me an adrenaline rush. On the other hand, comfort feels good. I long for a kick start to get out of this stage of limbo.

Not all hope is lost. I am writing this, albeit sluggish. A kid at work got into photography recently, perhaps I can get a partner in crime. And Barcamp is back in 2019. (Surprised? Me too!)

Pretty sure we are the only company throwing morning kayak sessions in the city

I was in a HackerX event in 2018. Basically speed dating for developer employment. And that was literally how I started my part of flirting duty. Getting a tandem kayak was pretty much an impulsive purchase. But it was a great one. I wondered why I didn't think of that earlier. In Vietnam, I get to pretty much drag the boat and pop it in any body of water I feel like. That my office is a few hundreds meters away from a pier also helps. The same can't be said for any other countries I have lived, due to either regularity or location. Be it a morning exercise before work, or a more adventurous weekend, it's good fun and brings friends together. One at a time. There are only two seats on a tandem kayak, damn it.


I wish 2018 was a grandiose. Instead, I just got lot of doubts. I had thing figured out, or my life just got boring? The progress I made in my career was solid, or I was making excuse and succumbing to familiar comfort? I've got the right balance, or work was slowly gulping my life? I still identify myself more as a 20 year-old kid scared shitless in his first job, rather than a 30 year-old I would be when this year ends. Well, I guess that's it right? Till this year ends, I have another year to live in my 20s and do stupid stuff. 30s uncertainty can wait, its time will come later :)