Deprecated: Creation of dynamic property wpdb::$categories is deprecated in /home/garrens3/public_html/blog/wp-includes/wp-db.php on line 760

Deprecated: Creation of dynamic property wpdb::$post2cat is deprecated in /home/garrens3/public_html/blog/wp-includes/wp-db.php on line 760

Deprecated: Creation of dynamic property wpdb::$link2cat is deprecated in /home/garrens3/public_html/blog/wp-includes/wp-db.php on line 760

Deprecated: Using ${var} in strings is deprecated, use {$var} instead in /home/garrens3/public_html/blog/wp-includes/comment-template.php on line 1747

Deprecated: Optional parameter $term_id declared before required parameter $meta_value is implicitly treated as a required parameter in /home/garrens3/public_html/blog/wp-content/plugins/advanced-code-editor/advanced-code-editor.php on line 1927

Deprecated: Optional parameter $term_id declared before required parameter $meta_value is implicitly treated as a required parameter in /home/garrens3/public_html/blog/wp-content/plugins/advanced-code-editor/advanced-code-editor.php on line 1941

Deprecated: Optional parameter $term_id declared before required parameter $meta_key is implicitly treated as a required parameter in /home/garrens3/public_html/blog/wp-content/plugins/advanced-code-editor/advanced-code-editor.php on line 1956

Deprecated: Optional parameter $term_id declared before required parameter $key is implicitly treated as a required parameter in /home/garrens3/public_html/blog/wp-content/plugins/advanced-code-editor/advanced-code-editor.php on line 1970

Deprecated: Automatic conversion of false to array is deprecated in /home/garrens3/public_html/blog/wp-content/plugins/loginizer/init.php on line 250

Deprecated: Automatic conversion of false to array is deprecated in /home/garrens3/public_html/blog/wp-content/plugins/loginizer/init.php on line 265

Deprecated: Creation of dynamic property WP_Block_Type::$skip_inner_blocks is deprecated in /home/garrens3/public_html/blog/wp-includes/class-wp-block-type.php on line 391

Deprecated: Creation of dynamic property WP_Block_Type::$skip_inner_blocks is deprecated in /home/garrens3/public_html/blog/wp-includes/class-wp-block-type.php on line 391

Deprecated: Return type of Requests_Cookie_Jar::offsetExists($key) should either be compatible with ArrayAccess::offsetExists(mixed $offset): bool, or the #[\ReturnTypeWillChange] attribute should be used to temporarily suppress the notice in /home/garrens3/public_html/blog/wp-includes/Requests/Cookie/Jar.php on line 63

Deprecated: Return type of Requests_Cookie_Jar::offsetGet($key) should either be compatible with ArrayAccess::offsetGet(mixed $offset): mixed, or the #[\ReturnTypeWillChange] attribute should be used to temporarily suppress the notice in /home/garrens3/public_html/blog/wp-includes/Requests/Cookie/Jar.php on line 73

Deprecated: Return type of Requests_Cookie_Jar::offsetSet($key, $value) should either be compatible with ArrayAccess::offsetSet(mixed $offset, mixed $value): void, or the #[\ReturnTypeWillChange] attribute should be used to temporarily suppress the notice in /home/garrens3/public_html/blog/wp-includes/Requests/Cookie/Jar.php on line 89

Deprecated: Return type of Requests_Cookie_Jar::offsetUnset($key) should either be compatible with ArrayAccess::offsetUnset(mixed $offset): void, or the #[\ReturnTypeWillChange] attribute should be used to temporarily suppress the notice in /home/garrens3/public_html/blog/wp-includes/Requests/Cookie/Jar.php on line 102

Deprecated: Return type of Requests_Cookie_Jar::getIterator() should either be compatible with IteratorAggregate::getIterator(): Traversable, or the #[\ReturnTypeWillChange] attribute should be used to temporarily suppress the notice in /home/garrens3/public_html/blog/wp-includes/Requests/Cookie/Jar.php on line 111

Deprecated: Return type of Requests_Utility_CaseInsensitiveDictionary::offsetExists($key) should either be compatible with ArrayAccess::offsetExists(mixed $offset): bool, or the #[\ReturnTypeWillChange] attribute should be used to temporarily suppress the notice in /home/garrens3/public_html/blog/wp-includes/Requests/Utility/CaseInsensitiveDictionary.php on line 40

Deprecated: Return type of Requests_Utility_CaseInsensitiveDictionary::offsetGet($key) should either be compatible with ArrayAccess::offsetGet(mixed $offset): mixed, or the #[\ReturnTypeWillChange] attribute should be used to temporarily suppress the notice in /home/garrens3/public_html/blog/wp-includes/Requests/Utility/CaseInsensitiveDictionary.php on line 51

Deprecated: Return type of Requests_Utility_CaseInsensitiveDictionary::offsetSet($key, $value) should either be compatible with ArrayAccess::offsetSet(mixed $offset, mixed $value): void, or the #[\ReturnTypeWillChange] attribute should be used to temporarily suppress the notice in /home/garrens3/public_html/blog/wp-includes/Requests/Utility/CaseInsensitiveDictionary.php on line 68

Deprecated: Return type of Requests_Utility_CaseInsensitiveDictionary::offsetUnset($key) should either be compatible with ArrayAccess::offsetUnset(mixed $offset): void, or the #[\ReturnTypeWillChange] attribute should be used to temporarily suppress the notice in /home/garrens3/public_html/blog/wp-includes/Requests/Utility/CaseInsensitiveDictionary.php on line 82

Deprecated: Return type of Requests_Utility_CaseInsensitiveDictionary::getIterator() should either be compatible with IteratorAggregate::getIterator(): Traversable, or the #[\ReturnTypeWillChange] attribute should be used to temporarily suppress the notice in /home/garrens3/public_html/blog/wp-includes/Requests/Utility/CaseInsensitiveDictionary.php on line 91

Warning: Cannot modify header information - headers already sent by (output started at /home/garrens3/public_html/blog/wp-includes/Requests/Cookie/Jar.php:15) in /home/garrens3/public_html/blog/wp-includes/rest-api/class-wp-rest-server.php on line 1723

Warning: Cannot modify header information - headers already sent by (output started at /home/garrens3/public_html/blog/wp-includes/Requests/Cookie/Jar.php:15) in /home/garrens3/public_html/blog/wp-includes/rest-api/class-wp-rest-server.php on line 1723

Warning: Cannot modify header information - headers already sent by (output started at /home/garrens3/public_html/blog/wp-includes/Requests/Cookie/Jar.php:15) in /home/garrens3/public_html/blog/wp-includes/rest-api/class-wp-rest-server.php on line 1723

Warning: Cannot modify header information - headers already sent by (output started at /home/garrens3/public_html/blog/wp-includes/Requests/Cookie/Jar.php:15) in /home/garrens3/public_html/blog/wp-includes/rest-api/class-wp-rest-server.php on line 1723

Warning: Cannot modify header information - headers already sent by (output started at /home/garrens3/public_html/blog/wp-includes/Requests/Cookie/Jar.php:15) in /home/garrens3/public_html/blog/wp-includes/rest-api/class-wp-rest-server.php on line 1723

Warning: Cannot modify header information - headers already sent by (output started at /home/garrens3/public_html/blog/wp-includes/Requests/Cookie/Jar.php:15) in /home/garrens3/public_html/blog/wp-includes/rest-api/class-wp-rest-server.php on line 1723

Warning: Cannot modify header information - headers already sent by (output started at /home/garrens3/public_html/blog/wp-includes/Requests/Cookie/Jar.php:15) in /home/garrens3/public_html/blog/wp-includes/rest-api/class-wp-rest-server.php on line 1723

Warning: Cannot modify header information - headers already sent by (output started at /home/garrens3/public_html/blog/wp-includes/Requests/Cookie/Jar.php:15) in /home/garrens3/public_html/blog/wp-includes/rest-api/class-wp-rest-server.php on line 1723
{"id":10,"date":"2014-07-29T02:27:57","date_gmt":"2014-07-29T02:27:57","guid":{"rendered":"http:\/\/garrens.com\/blog\/?p=10"},"modified":"2014-07-29T02:30:27","modified_gmt":"2014-07-29T02:30:27","slug":"integer-ranges-in-sql","status":"publish","type":"post","link":"https:\/\/garrens.com\/blog\/2014\/07\/29\/integer-ranges-in-sql\/","title":{"rendered":"Integer Ranges in SQL"},"content":{"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).<\/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>\n

Say 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>\n

Now 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>\n

Now 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>\n

But 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>\n

Find 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>\n

Let 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>\n

Here'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>\n

Many ranges could be less than 7, but not contain 7, so we don't really care about those.<\/p>\n

LIMIT 1<\/pre>\n

Only 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>\n

Then 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>\n

Going 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>\n

In 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→<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/garrens.com\/blog\/wp-json\/wp\/v2\/posts\/10"}],"collection":[{"href":"https:\/\/garrens.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/garrens.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/garrens.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/garrens.com\/blog\/wp-json\/wp\/v2\/comments?post=10"}],"version-history":[{"count":16,"href":"https:\/\/garrens.com\/blog\/wp-json\/wp\/v2\/posts\/10\/revisions"}],"predecessor-version":[{"id":26,"href":"https:\/\/garrens.com\/blog\/wp-json\/wp\/v2\/posts\/10\/revisions\/26"}],"wp:attachment":[{"href":"https:\/\/garrens.com\/blog\/wp-json\/wp\/v2\/media?parent=10"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/garrens.com\/blog\/wp-json\/wp\/v2\/categories?post=10"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/garrens.com\/blog\/wp-json\/wp\/v2\/tags?post=10"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}