Module | Sequel::Plugins::RcteTree |
In: |
lib/sequel/plugins/rcte_tree.rb
|
The rcte_tree plugin deals with tree structured data stored in the database using the adjacency list model (where child rows have a foreign key pointing to the parent rows), using recursive common table expressions to load all ancestors in a single query, all descendants in a single query, and all descendants to a given level (where level 1 is children, level 2 is children and grandchildren etc.) in a single query.
There are two types of common models for storing tree structured data in an SQL database, the adjacency list model and the nested set model. Before recursive common table expressions (or similar capabilities such as CONNECT BY for Oracle), the nested set model was the only easy way to retrieve all ancestors and descendants in a single query. However, it has significant performance corner cases.
On PostgreSQL 8.4, with a significant number of rows, the nested set model is almost 500 times slower than using a recursive common table expression with the adjacency list model to get all descendants, and almost 24,000 times slower to get all descendants to a given level.
Considering that the nested set model requires more difficult management than the adjacency list model, it‘s almost always better to use the adjacency list model if your database supports common table expressions. See explainextended.com/2009/09/24/adjacency-list-vs-nested-sets-postgresql/ for detailed analysis.
The rcte_tree plugin is unlike most plugins in that it doesn‘t add any class, instance, or dataset modules. It only has a single apply method, which adds four associations to the model: parent, children, ancestors, and descendants. Both the parent and children are fairly standard many_to_one and one_to_many associations, respectively. However, the ancestors and descendants associations are special. Both the ancestors and descendants associations will automatically set the parent and children associations, respectively, for current object and all of the ancestor or descendant objects, whenever they are loaded (either eagerly or lazily). Additionally, the descendants association can take a level argument when called eagerly, which limits the returned objects to only that many levels in the tree (see the Overview).
Model.plugin :rcte_tree # Lazy loading model = Model.first model.parent model.children model.ancestors # Populates :parent association for all ancestors model.descendants # Populates :children association for all descendants # Eager loading - also populates the :parent and children associations # for all ancestors and descendants Model.filter(:id=>[1, 2]).eager(:ancestors, :descendants).all # Eager loading children and grand children Model.filter(:id=>[1, 2]).eager(:descendants=>2).all # Eager loading children, grand children, and great grand children Model.filter(:id=>[1, 2]).eager(:descendants=>3).all
You can override the options for any specific association by making sure the plugin options contain one of the following keys:
Note that you can change the name of the above associations by specifying a :name key in the appropriate hash of options above. For example:
Model.plugin :rcte_tree, :parent=>{:name=>:mother}, :children=>{:name=>:daughters}, :descendants=>{:name=>:offspring}
Any other keys in the main options hash are treated as options shared by all of the associations. Here‘s a few options that affect the plugin:
Create the appropriate parent, children, ancestors, and descendants associations for the model.
# File lib/sequel/plugins/rcte_tree.rb, line 97 97: def self.apply(model, opts={}) 98: opts = opts.dup 99: opts[:class] = model 100: 101: key = opts[:key] ||= :parent_id 102: prkey = opts[:primary_key] ||= model.primary_key 103: 104: par = opts.merge(opts.fetch(:parent, {})) 105: parent = par.fetch(:name, :parent) 106: model.many_to_one parent, par 107: 108: chi = opts.merge(opts.fetch(:children, {})) 109: childrena = chi.fetch(:name, :children) 110: model.one_to_many childrena, chi 111: 112: ka = opts[:key_alias] ||= :x_root_x 113: t = opts[:cte_name] ||= :t 114: opts[:reciprocal] = nil 115: c_all = SQL::ColumnAll.new(model.table_name) 116: 117: a = opts.merge(opts.fetch(:ancestors, {})) 118: ancestors = a.fetch(:name, :ancestors) 119: a[:read_only] = true unless a.has_key?(:read_only) 120: a[:eager_loader_key] = key 121: a[:dataset] ||= proc do 122: model.from(t). 123: with_recursive(t, model.filter(prkey=>send(key)), 124: model.join(t, key=>prkey). 125: select(c_all)) 126: end 127: aal = Array(a[:after_load]) 128: aal << proc do |m, ancs| 129: unless m.associations.has_key?(parent) 130: parent_map = {m[prkey]=>m} 131: child_map = {} 132: child_map[m[key]] = m if m[key] 133: m.associations[parent] = nil 134: ancs.each do |obj| 135: obj.associations[parent] = nil 136: parent_map[obj[prkey]] = obj 137: if ok = obj[key] 138: child_map[ok] = obj 139: end 140: end 141: parent_map.each do |parent_id, obj| 142: if child = child_map[parent_id] 143: child.associations[parent] = obj 144: end 145: end 146: end 147: end 148: a[:after_load] ||= aal 149: a[:eager_loader] ||= proc do |eo| 150: id_map = eo[:key_hash][key] 151: parent_map = {} 152: children_map = {} 153: eo[:rows].each do |obj| 154: parent_map[obj[prkey]] = obj 155: (children_map[obj[key]] ||= []) << obj 156: obj.associations[ancestors] = [] 157: obj.associations[parent] = nil 158: end 159: r = model.association_reflection(ancestors) 160: model.eager_loading_dataset(r, 161: model.from(t). 162: with_recursive(t, model.filter(prkey=>id_map.keys). 163: select(SQL::AliasedExpression.new(prkey, ka), c_all), 164: model.join(t, key=>prkey). 165: select(SQL::QualifiedIdentifier.new(t, ka), c_all)), 166: r.select, 167: eo[:associations], eo).all do |obj| 168: opk = obj[prkey] 169: if in_pm = parent_map.has_key?(opk) 170: if idm_obj = parent_map[opk] 171: idm_obj.values[ka] = obj.values[ka] 172: obj = idm_obj 173: end 174: else 175: obj.associations[parent] = nil 176: parent_map[opk] = obj 177: (children_map[obj[key]] ||= []) << obj 178: end 179: 180: if roots = id_map[obj.values.delete(ka)] 181: roots.each do |root| 182: root.associations[ancestors] << obj 183: end 184: end 185: end 186: parent_map.each do |parent_id, obj| 187: if children = children_map[parent_id] 188: children.each do |child| 189: child.associations[parent] = obj 190: end 191: end 192: end 193: end 194: model.one_to_many ancestors, a 195: 196: d = opts.merge(opts.fetch(:descendants, {})) 197: descendants = d.fetch(:name, :descendants) 198: d[:read_only] = true unless d.has_key?(:read_only) 199: la = d[:level_alias] ||= :x_level_x 200: d[:dataset] ||= proc do 201: model.from(t). 202: with_recursive(t, model.filter(key=>send(prkey)), 203: model.join(t, prkey=>key). 204: select(SQL::ColumnAll.new(model.table_name))) 205: end 206: dal = Array(d[:after_load]) 207: dal << proc do |m, descs| 208: unless m.associations.has_key?(childrena) 209: parent_map = {m[prkey]=>m} 210: children_map = {} 211: m.associations[childrena] = [] 212: descs.each do |obj| 213: obj.associations[childrena] = [] 214: if opk = obj[prkey] 215: parent_map[opk] = obj 216: end 217: if ok = obj[key] 218: (children_map[ok] ||= []) << obj 219: end 220: end 221: children_map.each do |parent_id, objs| 222: parent_map[parent_id].associations[childrena] = objs 223: end 224: end 225: end 226: d[:after_load] = dal 227: d[:eager_loader] ||= proc do |eo| 228: id_map = eo[:key_hash][prkey] 229: associations = eo[:associations] 230: parent_map = {} 231: children_map = {} 232: eo[:rows].each do |obj| 233: parent_map[obj[prkey]] = obj 234: obj.associations[descendants] = [] 235: obj.associations[childrena] = [] 236: end 237: r = model.association_reflection(descendants) 238: base_case = model.filter(key=>id_map.keys). 239: select(SQL::AliasedExpression.new(key, ka), c_all) 240: recursive_case = model.join(t, prkey=>key). 241: select(SQL::QualifiedIdentifier.new(t, ka), c_all) 242: if associations.is_a?(Integer) 243: level = associations 244: no_cache_level = level - 1 245: associations = {} 246: base_case = base_case.select_more(SQL::AliasedExpression.new(0, la)) 247: recursive_case = recursive_case.select_more(SQL::AliasedExpression.new(SQL::QualifiedIdentifier.new(t, la) + 1, la)).filter(SQL::QualifiedIdentifier.new(t, la) < level - 1) 248: end 249: model.eager_loading_dataset(r, 250: model.from(t).with_recursive(t, base_case, recursive_case), 251: r.select, 252: associations, eo).all do |obj| 253: if level 254: no_cache = no_cache_level == obj.values.delete(la) 255: end 256: 257: opk = obj[prkey] 258: if in_pm = parent_map.has_key?(opk) 259: if idm_obj = parent_map[opk] 260: idm_obj.values[ka] = obj.values[ka] 261: obj = idm_obj 262: end 263: else 264: obj.associations[childrena] = [] unless no_cache 265: parent_map[opk] = obj 266: end 267: 268: if root = id_map[obj.values.delete(ka)].first 269: root.associations[descendants] << obj 270: end 271: 272: (children_map[obj[key]] ||= []) << obj 273: end 274: children_map.each do |parent_id, objs| 275: parent_map[parent_id].associations[childrena] = objs.uniq 276: end 277: end 278: model.one_to_many descendants, d 279: end