Sometimes we need to store integers, but we have too many to store for a traditional relational database like MySQL, and Hadoop wouldn’t bat an eye at the amount. However we want to use SQL, because it poses a new challenge (and may be necessary for other reasons we won’t go into).<\/p>\n
A typical table to store orders with their corresponding cities may have this structure:<\/p>\n
CREATE TABLE order_cities\r\n(\r\n order_num int unsigned,\r\n city varchar(255),\r\n KEY (order_num)\r\n)\r\n<\/pre>\n\r\nINSERT INTO order_cities VALUES (7,'Seattle'),(8,'Seattle'),(9,'San Francisco'),(10,'San Francisco'),(11,'New York')\r\n<\/pre>\nSay we want to store 2^32 (~4.3B) orders. While some storage engines (i.e. TokuDB) can handle exceptionally large tables, their performance will be mostly undesirable. So let’s use an integer range to represent this data instead!<\/p>\n
order_range_cities\r\n(\r\n order_start int unsigned,\r\n order_end int unsigned,\r\n city varchar(255),\r\n PRIMARY KEY (order_start),\r\n UNIQUE KEY (order_end)\r\n)\r\n<\/pre>\n\r\nINSERT INTO order_range_cities VALUES (7,8,'Seattle'),(9,10,'San Francisco'),(11,'New York')\r\n<\/pre>\nNow normally when using integers, we could simply ask for all rows with num between 7 and 11.<\/p>\n
\r\nSELECT *\r\nFROM order_cities\r\nWHERE order_num BETWEEN 7 AND 11\r\n<\/pre>\nNow to get all orders between 7 and 11, the solution seems straightforward:<\/p>\n
\r\nSELECT *\r\nFROM order_cities\r\nWHERE order_start BETWEEN 7 AND 11\r\n<\/pre>\nBut that would be wrong for when the range boundaries do not align. <\/p>\n
Say that instead of Seattle starting at 7 and ending at 8, it started at 5 and ended at 8. The above query would miss it entirely. So what can we do to find the range boundaries?<\/p>\n
The easy (and slow way):<\/p>\n
\r\nSELECT *\r\nFROM order_cities\r\nWHERE 7 BETWEEN order_start AND order_end\r\n<\/pre>\nFind the first range boundary at the low end:<\/p>\n
\r\nSELECT IF(order_end >= 7, order_start, NULL)\r\nFROM order_cities\r\nWHERE order_start <= 7\r\nORDER BY order_start DESC\r\nLIMIT 1\r\n<\/pre>\nLet me explain...<\/p>\n
Let's find any ranges that are less than or equal to 7 (in our case, it will find \"5\")<\/p>\n
WHERE order_start <= 7<\/pre>\nHere's a little trick with integer ranges. We want to see the highest value order_start that is closest to 7 first. We'll assume ranges are contiguous and do not overlap at all, therefore the highest value would also be most likely to be the range containing 7.<\/p>\n
ORDER BY order_start DESC<\/pre>\nMany ranges could be less than 7, but not contain 7, so we don't really care about those.<\/p>\n
LIMIT 1<\/pre>\nOnly return the order_start if the order_end also includes 7 (this will protect us from grabbing ranges that are lower the 7, but do not contain 7).<\/p>\n
SELECT IF(order_end >= 7, order_start, NULL)<\/pre>\nThen since we already know the max value (11), we can use 11 as the highest inclusive order_start.<\/p>\n
To recap, we wanted all rows whose range contained 7 through 11, and we found the low end range boundary to be 5, left the high end range boundary at 11 and ended up with this query:<\/p>\n
\r\nSELECT *\r\nFROM order_cities\r\nWHERE order_start BETWEEN 5 AND 11\r\n<\/pre>\nGoing through and manually finding the low end range boundary may not be possible\/desired every time, so we can create a stored function that retrieves this value for us:<\/p>\n
CREATE FUNCTION get_order_start(v_order_num int unsigned) returns int unsigned\r\nBEGIN\r\n...\r\nRETURN ifnull( -- Return 0 if the result is null\r\n\t(\r\n\t\tSELECT if(order_end >= v_order_num,order_start,NULL)\r\n\t\tFROM order_range_cities \r\n\t\tWHERE order_start <= v_order_num\r\n\t\tORDER BY order_start DESC \r\n\t\tLIMIT 1\r\n\t)\r\n,0);\r\n...\r\nEND<\/pre>\nIn MySQL, when we want to use this automatically generated value, we cannot use it directly in a SQL clause (ie a WHERE clause). We have to wrap it in a derived table like this:<\/p>\n
SELECT *\r\nFROM\r\n(\r\n SELECT get_order_start(7) AS first_order_start\r\n) lower_bounary\r\nJOIN order_range_cities orc ON (orc.order_start BETWEEN lower_boundary.first_order_start AND 11) -- first_order_start will be = 5<\/pre>\n","protected":false},"excerpt":{"rendered":"Sometimes we need to store integers, but we have too many to store for a traditional relational database like MySQL, and Hadoop wouldn’t bat an eye at the amount. However we want to use SQL, because it poses a new challenge (and may be necessary for other reasons we won’t go into). A typical table… Continue reading