{"action":"reopened","issue":{"url":"https://api.github.com/repos/tarantool/tarantool/issues/1557","repository_url":"https://api.github.com/repos/tarantool/tarantool","labels_url":"https://api.github.com/repos/tarantool/tarantool/issues/1557/labels{/name}","comments_url":"https://api.github.com/repos/tarantool/tarantool/issues/1557/comments","events_url":"https://api.github.com/repos/tarantool/tarantool/issues/1557/events","html_url":"https://github.com/tarantool/tarantool/issues/1557","id":161695616,"number":1557,"title":"NULL support in indexes","user":{"login":"rtsisyk","id":1799054,"avatar_url":"https://avatars2.githubusercontent.com/u/1799054?v=3","gravatar_id":"","url":"https://api.github.com/users/rtsisyk","html_url":"https://github.com/rtsisyk","followers_url":"https://api.github.com/users/rtsisyk/followers","following_url":"https://api.github.com/users/rtsisyk/following{/other_user}","gists_url":"https://api.github.com/users/rtsisyk/gists{/gist_id}","starred_url":"https://api.github.com/users/rtsisyk/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/rtsisyk/subscriptions","organizations_url":"https://api.github.com/users/rtsisyk/orgs","repos_url":"https://api.github.com/users/rtsisyk/repos","events_url":"https://api.github.com/users/rtsisyk/events{/privacy}","received_events_url":"https://api.github.com/users/rtsisyk/received_events","type":"User","site_admin":false},"labels":[{"id":55628742,"url":"https://api.github.com/repos/tarantool/tarantool/labels/feature","name":"feature","color":"bfe5bf","default":false},{"id":336193145,"url":"https://api.github.com/repos/tarantool/tarantool/labels/sql","name":"sql","color":"bfe5bf","default":false}],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":{"url":"https://api.github.com/repos/tarantool/tarantool/milestones/17","html_url":"https://github.com/tarantool/tarantool/milestone/17","labels_url":"https://api.github.com/repos/tarantool/tarantool/milestones/17/labels","id":1692869,"number":17,"title":"1.8.0","description":"","creator":{"login":"rtsisyk","id":1799054,"avatar_url":"https://avatars2.githubusercontent.com/u/1799054?v=3","gravatar_id":"","url":"https://api.github.com/users/rtsisyk","html_url":"https://github.com/rtsisyk","followers_url":"https://api.github.com/users/rtsisyk/followers","following_url":"https://api.github.com/users/rtsisyk/following{/other_user}","gists_url":"https://api.github.com/users/rtsisyk/gists{/gist_id}","starred_url":"https://api.github.com/users/rtsisyk/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/rtsisyk/subscriptions","organizations_url":"https://api.github.com/users/rtsisyk/orgs","repos_url":"https://api.github.com/users/rtsisyk/repos","events_url":"https://api.github.com/users/rtsisyk/events{/privacy}","received_events_url":"https://api.github.com/users/rtsisyk/received_events","type":"User","site_admin":false},"open_issues":27,"closed_issues":14,"state":"open","created_at":"2016-04-08T11:13:16Z","updated_at":"2017-04-17T15:13:12Z","due_on":null,"closed_at":null},"comments":3,"created_at":"2016-06-22T14:18:10Z","updated_at":"2017-04-17T15:13:12Z","closed_at":null,"body":"Implement support for NULL values in indexes.\n\nNULL has special semantics in databases. \nPlease read [this article](https://en.wikipedia.org/wiki/Null_%28SQL%29) carefully, especially part about [ternary logic](https://en.wikipedia.org/wiki/Null_%28SQL%29#Comparisons_with_NULL_and_the_three-valued_logic_.283VL.29).\n### 1. NULL value in UNIQUE index\n\n**Unique index can contain more than one NULL values**\n\n```\nCREATE TABLE nulltest (id INT PRIMARY KEY, val INT, UNIQUE(val)) -- unique constraint\nINSERT INTO nulltest VALUES(1, null);\nINSERT INTO nulltest VALUES(6, 6);\nINSERT INTO nulltest VALUES(5, 5);\nINSERT INTO nulltest VALUES(4, null);\nINSERT INTO nulltest VALUES(3, null);\nINSERT INTO nulltest VALUES(2, 2);\nSELECT * FROM nulltest ORDER BY val;\n id | val \n----+-----\n  2 |   2\n  5 |   5\n  6 |   6\n  3 |    \n  4 |     -- multiple rows with NULL values in UNIQUE index\n  1 |    \n(6 rows)  \n```\n\n`(x <OPERATOR> NULL)` is NULL, not TRUE or FALSE. Even `(NULL == NULL)` is `NULL`.\n\nANSI SQL 2011, part 2, section 4.18.3.2 \"Unique constraints\":\n\n> Unique constraint is satisfied if and only if there do not exist two rows R1 and R2 of T (table) such that R1 and R2 have the same **non-null** values in the unique columns.\n\nPlease read [Peter's article](http://ocelot.ca/blog/blog/2013/09/11/null-and-unique/) on NULL and UNIQUE constraints in SQL for detailed explanation.\n\n`space:create_index(name, { unique = true })` in Tarantool is semantically equivalent to `CREATE UNIQUE INDEX name ON space (key)` in SQL. Therefore, `unique = true` must also allow multiple nulls values.\n### 2. Sort order for NULL values\n\n**Sort order for NULL values is implementation defined**, like for non-unique indexes. \n\nTechnically, you can't apply ternary logic directly to B-trees. A tree comparator function must be transitive to define strict order over the set of keys in tree. In other words, if cmp(a, NULL) is \"less\" then cmp(NULL, a) should be \"great or equal\", otherwise tree properties will not be met. \n\nSome SQL implementations consider NULLs values less than any other value (\"nulls low\"), whereas other implementations consider NULLs great than other values (\"nulls high\").\n\nExample - PostgreSQL - \"nulls high\":\n\n```\npostgres> SELECT id, val, ctid FROM nulltest ORDER BY val;\n id | val | ctid   -- \n----+-----+-------\n  2 |   2 | (0,6)\n  5 |   5 | (0,3)\n  6 |   6 | (0,2)\n  3 |     | (0,5)  --  nulls high\n  4 |     | (0,4)  --  order for records 3, 4, 1 is random, based on physical location on the disk\n  1 |     | (0,1)  --\n```\n\nExample - sqlite3 - \"nulls low\":\n\n```\nsqlite> SELECT id, val, rowid FROM nulltest ORDER BY val ASC;\n1||1    -- nulls low\n4||4    -- order for records 1, 4, 3 is random, based on physical location  on the disk\n3||5\n2|2|6\n5|5|3  \n6|6|2\n```\n\nTarantool/SQL is based on sqlite3. Therefore, let's choose \"nulls low\" order for compatibility with sqlite3.\n\n`space:select({}, {iterator='GE'})` should have the same order as\n`SELECT * FROM space ORDER BY val ASC NULLS FIRST`\nand space:select({}, {iterator='LE'}) should have the same order as\n`SELECT * FROM space ORDER BY val DESC NULLS LAST`\n## 3. NOT NULL constraint\n\nSQL has `NOT NULL` constraint:\n\n```\nCREATE TABLE table (..., val INT NOT NULL, ... )\n```\n\nBy default any column without \"NOT NULL\" constraint can store NULLs. NOT NULL columns can't store NULL (an error is raised).\n\nThere are two options for us:\n- Add `not_null = false` option per field in _space.format.\n  Pros: like SQL\n  Cons: `not_null = false` is inverted logic; option is not 1.6->1.7 forward-compatible.\n- Add `null = true` option per field in _space.format\n\nLet's discuss these two options. \n## 4.  PRIMARY KEY must not allow NULLs\n\nSince there is no way to unique identify rows in an index by NULL key, primary key must not allow NULLs. `PRIMARY KEY` in SQL effectively means \"UNIQUE\" and \"NOT NULL\". \n\nIt is possible to enable NOT NULL constraint explicitly, based on knowledge that index is \"first\" (primary).\n## 5. Lua and nils\n\n`nil` has special meaning in Lua - `table[x] = nil` means `delete x from table`.\n`{'a', 'b', nil}` is semantically equivalent to table = {}; table[1] = 'a', table[2] = 'b', table[3] = nil, therefore `nil` is not usable in tables. See #1123 for nice examples of buggy design of Lua.\n\nLua's `nil` also doesn't support ternary logic:\n\n```\ntarantool> 1 < nil\n\n---\n- error: '[string \"return 1 < nil\"]:1: attempt to compare number with nil'\n...\n\ntarantool> 1 + nil\n\n---\n- error: '[string \"return 1 + nil\"]:1: attempt to perform arithmetic on a nil value'\n...\n```\n\nThere are also msgpack.NULL/yaml.NULL/json.NULL which can be safetly inserted to Lua table.\n\nProbably we should add box.NULL special value which will fully support ternary NULL logic in Lua.\nIt is easy to implement using Lua table with __eq and __serialize meta-methods. \n\nLet's discuss this part. See #1300 for details.\n## 6. SELECT \\* FROM tab WHERE x = NULL\n\n**`box.space.test:select({NULL}, {iterator = 'EQ'})`  is empty set:**\n\n```\nSELECT * FROM nulltest WHERE val = NULL;\n id | val \n----+-----\n(0 rows)\n```\n\nSQL has a special syntax for that:\n\n```\nSELECT * FROM nulltest WHERE val is NULL;\n id | val \n----+-----\n  1 |    \n  4 |    \n  3 |    \n  7 |\n```\n\nIt is possible to add a special iterator type, like \"EQ_IS\" in the future to implement \"IS NULL\" feature. This feature is not part of this ticket.\n\nEQ/GE/GT/LE/LT iterators must work properly at least on `null = true` indexes. Support for NULL queries over not-null indexes is senseless and will introduce performance regression at least for `NUM` and `STR` indexes.\n\nOne more problem is how to handle space:select(nil) and space:select(msgpack.NULL).\n\nCurrently space:select(scalar) == space:select({scalar}).\nspace:select({scalar}) is like \"SELECT \\* FROM space WHERE key=scalar ORDER BY key ASC\", so\nspace:select(scalar) is also like \"SELECT \\* FROM space WHERE key=scalar ORDER BY key ASC\".\n\nAt the same time, somefunc(nil) == somefun() in Lua, so space:select(nil) == space:select() == space:select({}).\n\nHow to handle space:select(msgpack.NULL) and space:select(nil)?\na) space:select(msgpack.NULL) == space:select({msgpack.NULL})\nb) space:select(msgpack.NULL) == space:select(nil) == space:select({})\nc) ban space:select(msgpack.NULL)\nd) ban space:select(msgpack.NULL) and space:select(nil, {...})\n\nLet's discuss these options.\n## 7. Partial indexes\n\nIt was an idea to omit NULL records from indexes to save some memory. SQLITE calls this feature \"[partial index](https://www.sqlite.org/partialindex.html)\", some other database use \"fileterd index\" terminology.\n\nWe don't implement this feature as part of this ticket. I think this behaviour can be controlled by some create_index() option, e.g. \"partial = true/false/filter_function/where clause from sql\".\n## 8. Default values\n\nDefault values are not part of this feature.\n\n---\n\nI added this ticket to 1.7.0, but actually this feature is rolling and can be postponed to 1.7.1+ or even to 1.8.x.\n"}}
{"actor":{"display_login":"rtsisyk"}}