{"id":5311,"date":"2013-01-08T13:19:56","date_gmt":"2013-01-08T11:19:56","guid":{"rendered":"http:\/\/code.openark.org\/blog\/?p=5311"},"modified":"2013-01-08T13:19:56","modified_gmt":"2013-01-08T11:19:56","slug":"hierarchical-data-in-information_schema-and-derivatives","status":"publish","type":"post","link":"https:\/\/code.openark.org\/blog\/mysql\/hierarchical-data-in-information_schema-and-derivatives","title":{"rendered":"Hierarchical data in INFORMATION_SCHEMA and derivatives"},"content":{"rendered":"

Just how often do you encounter hierarchical data? Consider a table with some parent-child relation, like the this classic employee<\/strong> table:<\/p>\n

\n
CREATE TABLE employee (\r\n\u00a0 employee_id INT UNSIGNED PRIMARY KEY,\r\n\u00a0 employee_name VARCHAR(100),\r\n\u00a0 manager_id INT UNSIGNED,\r\n\u00a0 CONSTRAINT `employee_manager_fk` FOREIGN KEY (manager_id) REFERENCES employee (employee_id)\r\n) engine=innodb\r\n;\r\n+-------------+---------------+------------+\r\n| employee_id | employee_name | manager_id |\r\n+-------------+---------------+------------+\r\n|\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 1 | Rachel\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 |\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 NULL |\r\n|\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 2 | John\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 |\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 1 |\r\n|\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 3 | Stan\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 |\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 1 |\r\n|\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 4 | Naomi\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 |\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 2 |\r\n+-------------+---------------+------------+<\/pre>\n<\/blockquote>\n
Questions like “What is the (nested) list of employees managed by Rachel?”<\/em> or “Get Naomi’s managers chain of command”<\/em> are classical questions. There are sometimes dependencies: if John leaves, does that mean Naomi loses her job, or does she get promoted, or something else? If John and Stan are on sick leave, does Rachel have any reason to come to work?<\/p>\n
Hierarchical data is not limited to a single-table structure. Sometimes it takes a combination of a few tables (it’s just a JOIN<\/strong>) to make out the parent-child relation.<\/p>\n
Hierarchical data is difficult to manage with SQL. This is especially true for MySQL, which does not support the WITH<\/strong> recursive query syntax.<\/p>\n
Where can you find hierarchical data?<\/h4>\n
Even if you do not provide it by yourself, MySQL’s INFORMATION_SCHEMA<\/strong> has some for you. Partly obvious, partly implicit, here are some examples:<\/p>\n
Foreign Keys<\/h4>\n
This is probably the most obvious hierarchical dataset in INFORMATION_SCHEMA<\/strong>. The KEY_COLUMN_USAGE<\/strong> table lists the table dependencies based on foreign key constraints. It’s a bit confusing, as it also lists UNIQUE<\/strong> constraints, and the complete list of FKs are in REFERENTIAL_CONSTRAINTS<\/strong> — but the latter table does not list the dependencies. You typically want to join both tables to get the complete information.<\/p>\n
So, taking sakila<\/strong>‘s DVD rental shop sample,\u00a0 film_actor<\/strong> table depends on film<\/strong> as well as on actor<\/strong> via foreign keys. film<\/strong> can depend on the category<\/strong> table, etc. The hierarchies can turn to be very complex, with multiple roots an very deep branches.<\/p>\n
Dependency questions are very clear when speaking of foreign keys: what happens when we delete some film<\/strong> record? Does it hold that we also delete all references to that film on film_actor<\/strong>? Or do we deny deletion of said film in such case?<\/p>\n
Redundant Keys<\/h4>\n
The KEY (col1, col2)<\/strong> makes the KEY (col1)<\/strong> redundant. The latter is not strictly required (though you may wish to keep it for covering index performance reason). The list of dominant-redundant<\/em> keys makes for hierarchical data. It is typically very shallow (keys can only be redundant within the scope of a single table — how deep can you get with such small dataset?)<\/p>\n
There is no immediate reference in INFORMATION_SCHEMA<\/strong> as for redundant keys, but it can be inferred by self joining the\u00a0STATISTICS<\/strong> table onto itself. It is not immediate, since you need to do some aggregation and check for particular cases. For example, UNIQUE KEY (col1, col2)<\/strong> is actually made redundant by UNIQUE KEY (col1)<\/strong>, which is just the opposite from our previous example.<\/p>\n
common_schema<\/a> provides with this implicit information now turned explicit, in the for of the redundant_keys<\/a> view: the redundant_index_name<\/strong> and dominant_index_name<\/strong> columns make for parent-child relationship.<\/p>\n
Dependency questions are a bit redundant here: the general objective is to not have<\/em> dependencies. So get rid of redundant keys – and do so wisely. There’s a good discussion of index redundancies on redundant_keys<\/strong>‘s documentation<\/a>.<\/p>\n
Locked transactions<\/h4>\n
A transaction is locked. It is locked because another transaction holds some locks needed by locked transaction. But this transaction in itself can obtain locks needed by yet other transactions. And so we can get a hierarchy of locked transaction. The “parent” is the one blocking the “child”.<\/p>\n
Combining InnoDB’s INNODB_TRX<\/strong> – INNODB_LOCK_WAITS<\/strong> – INNODB_TRX<\/strong> tables, we get this information. common_schema<\/em> provides with this inferred data in the form of innodb_locked_transactions<\/a>.<\/p>\n
Hierarchies in locked-transactions could be deep, and they can most commonly be wide<\/em>. A single transaction can lock dozens of others.<\/p>\n
Dependency questions are “would killing this transaction release all other waiting transactions?”<\/em>; “What is <\/em>the one transaction I need to kill in order to release the bottleneck?”<\/em>; “Why are these transactions related in the first place? Can I remove this dependency?”<\/em>. etc.<\/p>\n
Locks<\/h4>\n
You can look at the same dataset as above from a different angle. Instead of looking at transaction-lock-transaction, you can look at lock-transaction-lock. Which locks are causing other locks to be held? This is counter-intuitive to our understanding of how things work, but is valid nonetheless.<\/p>\n
Views<\/h4>\n
A VIEW<\/strong> can query a table or another view. It can join multiple views. This hierarchy of view-reading-from-view can turn out to be complex; if not for the human mind then for the optimizer.<\/p>\n
Surprisingly, there is no data in INFORMATION_SCHEMA<\/strong>, other than the CREATE VIEW<\/strong> clause, to help us out in resolving these dependencies. Even more surprising is MySQL’s own inability to get clear conclusions itself. The view definition clause is parsed, re-parsed and re-evaluated whenever information on “parent” views is required. For example, try to DESCRIBE<\/strong> a view. How does MySQL deduce the data types of columns? It dives in head first into the hierarchy, crawls and parses view definitions, till it resolves the answer. The mycheckpoint<\/a> projects uses view hierarchies intensively. It draws powers from the hierarchy and produces some surprising data (charts<\/a> from raw data, for example). But it also suffers from MySQL indirect inference of views. Checking up a deep-nested mycehckpoint<\/em> view in INFORMATION_SCHEMA<\/strong> makes for a heavyweight dive for MySQL into locks and table handles.<\/p>\n
Dependency questions are “what is the type of this column?”<\/em>, “are there any TEMPTABLE<\/strong> views along the chain of execution? Or are all MERGE<\/strong> views?”<\/em> and more.<\/p>\n","protected":false},"excerpt":{"rendered":"
Just how often do you encounter hierarchical data? Consider a table with some parent-child relation, like the this classic employee table: CREATE TABLE employee ( \u00a0 employee_id INT UNSIGNED PRIMARY KEY, \u00a0 employee_name VARCHAR(100), \u00a0 manager_id INT UNSIGNED, \u00a0 CONSTRAINT `employee_manager_fk` FOREIGN KEY (manager_id) REFERENCES employee (employee_id) ) engine=innodb ; +————-+—————+————+ | employee_id | employee_name […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"enabled":false},"version":2}},"categories":[5],"tags":[24,21],"class_list":["post-5311","post","type-post","status-publish","format-standard","hentry","category-mysql","tag-information_schema","tag-sql"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p2bZZp-1nF","_links":{"self":[{"href":"https:\/\/code.openark.org\/blog\/wp-json\/wp\/v2\/posts\/5311","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/code.openark.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/code.openark.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/code.openark.org\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/code.openark.org\/blog\/wp-json\/wp\/v2\/comments?post=5311"}],"version-history":[{"count":19,"href":"https:\/\/code.openark.org\/blog\/wp-json\/wp\/v2\/posts\/5311\/revisions"}],"predecessor-version":[{"id":5981,"href":"https:\/\/code.openark.org\/blog\/wp-json\/wp\/v2\/posts\/5311\/revisions\/5981"}],"wp:attachment":[{"href":"https:\/\/code.openark.org\/blog\/wp-json\/wp\/v2\/media?parent=5311"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/code.openark.org\/blog\/wp-json\/wp\/v2\/categories?post=5311"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/code.openark.org\/blog\/wp-json\/wp\/v2\/tags?post=5311"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}