module Sequel::Plugins::RcteTree

  1. lib/sequel/plugins/rcte_tree.rb

Overview ↑

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.

Usage ↑

The rcte_tree plugin 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.where(id: [1, 2]).eager(:ancestors, :descendants).all

# Eager loading children and grandchildren
Model.where(id: [1, 2]).eager(descendants: 2).all
# Eager loading children, grandchildren, and great grandchildren
Model.where(id: [1, 2]).eager(descendants: 3).all

Options ↑

You can override the options for any specific association by making sure the plugin options contain one of the following keys:

:parent

hash of options for the parent association

:children

hash of options for the children association

:ancestors

hash of options for the ancestors association

:descendants

hash of options for the descendants association

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:

:key

The foreign key in the table that points to the primary key of the parent (default: :parent_id)

:primary_key

The primary key to use (default: the model’s primary key)

:key_alias

The symbol identifier to use for aliasing when eager loading (default: :x_root_x)

:cte_name

The symbol identifier to use for the common table expression (default: :t)

:level_alias

The symbol identifier to use when eagerly loading descendants up to a given level (default: :x_level_x)

:union_all

Whether to use UNION ALL or UNION with the recursive common table expression (default: true)

Methods

Public Class

  1. apply

Public Class methods

apply(model, opts=OPTS)

Create the appropriate parent, children, ancestors, and descendants associations for the model.

[show source] 
    # File lib/sequel/plugins/rcte_tree.rb
 79 def self.apply(model, opts=OPTS)
 80   model.plugin :tree, opts
 81 
 82   opts = opts.dup
 83   opts[:class] = model
 84   opts[:methods_module] = Sequel.set_temp_name(Module.new){"#{model.name}::_rcte_tree[:methods_module]"}
 85   opts[:union_all] = opts[:union_all].nil? ? true : opts[:union_all]
 86   model.send(:include, opts[:methods_module])
 87   
 88   key = opts[:key] ||= :parent_id
 89   prkey = opts[:primary_key] ||= model.primary_key
 90   ka = opts[:key_alias] ||= :x_root_x
 91   t = opts[:cte_name] ||= :t
 92   c_all = if model.dataset.recursive_cte_requires_column_aliases?
 93     # Work around Oracle/ruby-oci8 bug that returns integers as BigDecimals in recursive queries.
 94     conv_bd = model.db.database_type == :oracle
 95     col_aliases = model.dataset.columns
 96     model_table = model.table_name
 97     col_aliases.map{|c| SQL::QualifiedIdentifier.new(model_table, c)}
 98   else
 99     [SQL::ColumnAll.new(model.table_name)]
100   end
101   
102   bd_conv = lambda{|v| conv_bd && v.is_a?(BigDecimal) ? v.to_i : v}
103 
104   key_array = Array(key)
105   prkey_array = Array(prkey)
106   if key.is_a?(Array)
107     key_conv = lambda{|m| key_array.map{|k| m[k]}}
108     key_present = lambda{|m| key_conv[m].all?}
109     prkey_conv = lambda{|m| prkey_array.map{|k| m[k]}}
110     key_aliases = (0...key_array.length).map{|i| :"#{ka}_#{i}"}
111     ancestor_base_case_columns = prkey_array.zip(key_aliases).map{|k, ka_| SQL::AliasedExpression.new(k, ka_)} + c_all
112     descendant_base_case_columns = key_array.zip(key_aliases).map{|k, ka_| SQL::AliasedExpression.new(k, ka_)} + c_all
113     recursive_case_columns = prkey_array.zip(key_aliases).map{|k, ka_| SQL::QualifiedIdentifier.new(t, ka_)} + c_all
114     extract_key_alias = lambda{|m| key_aliases.map{|ka_| bd_conv[m.values.delete(ka_)]}}
115   else
116     key_present = key_conv = lambda{|m| m[key]}
117     prkey_conv = lambda{|m| m[prkey]}
118     key_aliases = [ka]
119     ancestor_base_case_columns = [SQL::AliasedExpression.new(prkey, ka)] + c_all
120     descendant_base_case_columns = [SQL::AliasedExpression.new(key, ka)] + c_all
121     recursive_case_columns = [SQL::QualifiedIdentifier.new(t, ka)] + c_all
122     extract_key_alias = lambda{|m| bd_conv[m.values.delete(ka)]}
123   end
124   
125   parent = opts.merge(opts.fetch(:parent, OPTS)).fetch(:name, :parent)
126   childrena = opts.merge(opts.fetch(:children, OPTS)).fetch(:name, :children)
127   
128   opts[:reciprocal] = nil
129   a = opts.merge(opts.fetch(:ancestors, OPTS))
130   ancestors = a.fetch(:name, :ancestors)
131   a[:read_only] = true unless a.has_key?(:read_only)
132   a[:eager_grapher] = proc do |_|
133     raise Sequel::Error, "the #{ancestors} association for #{self} does not support eager graphing"
134   end
135   a[:eager_loader_key] = key
136   a[:dataset] ||= proc do
137     base_ds = model.where(prkey_array.zip(key_array.map{|k| get_column_value(k)}))
138     recursive_ds = model.join(t, key_array.zip(prkey_array))
139     if c = a[:conditions]
140       (base_ds, recursive_ds) = [base_ds, recursive_ds].map do |ds|
141         (c.is_a?(Array) && !Sequel.condition_specifier?(c)) ? ds.where(*c) : ds.where(c)
142       end
143     end
144     table_alias = model.dataset.schema_and_table(model.table_name)[1].to_sym
145     model.from(SQL::AliasedExpression.new(t, table_alias)).
146      with_recursive(t, col_aliases ? base_ds.select(*col_aliases) : base_ds.select_all,
147       recursive_ds.select(*c_all),
148       :args=>col_aliases, union_all: opts[:union_all])
149   end
150   aal = Array(a[:after_load])
151   aal << proc do |m, ancs|
152     unless m.associations.has_key?(parent)
153       parent_map = {prkey_conv[m]=>m}
154       child_map = {}
155       child_map[key_conv[m]] = m if key_present[m]
156       m.associations[parent] = nil
157       ancs.each do |obj|
158         obj.associations[parent] = nil
159         parent_map[prkey_conv[obj]] = obj
160         if ok = key_conv[obj]
161           child_map[ok] = obj
162         end
163       end
164       parent_map.each do |parent_id, obj|
165         if child = child_map[parent_id]
166           child.associations[parent] = obj
167         end
168       end
169     end
170   end
171   a[:after_load] ||= aal
172   a[:eager_loader] ||= proc do |eo|
173     id_map = eo[:id_map]
174     parent_map = {}
175     children_map = {}
176     Sequel.synchronize_with(eo[:mutex]) do
177       eo[:rows].each do |obj|
178         parent_map[prkey_conv[obj]] = obj
179         (children_map[key_conv[obj]] ||= []) << obj
180         obj.associations[ancestors] = []
181         obj.associations[parent] = nil
182       end
183     end
184     r = model.association_reflection(ancestors)
185     base_case = model.where(prkey=>id_map.keys).
186      select(*ancestor_base_case_columns)
187     recursive_case = model.join(t, key_array.zip(prkey_array)).
188      select(*recursive_case_columns)
189     if c = r[:conditions]
190       (base_case, recursive_case) = [base_case, recursive_case].map do |ds|
191         (c.is_a?(Array) && !Sequel.condition_specifier?(c)) ? ds.where(*c) : ds.where(c)
192       end
193     end
194     table_alias = model.dataset.schema_and_table(model.table_name)[1].to_sym
195     ds = model.from(SQL::AliasedExpression.new(t, table_alias)).
196       with_recursive(t, base_case, recursive_case,
197        :args=>((key_aliases + col_aliases) if col_aliases), union_all: opts[:union_all])
198     ds = r.apply_eager_dataset_changes(ds)
199     ds = ds.select_append(ka) unless ds.opts[:select] == nil
200     model.eager_load_results(r, eo.merge(:loader=>false, :initialize_rows=>false, :dataset=>ds, :id_map=>nil)) do |obj|
201       opk = prkey_conv[obj]
202       if idm_obj = parent_map[opk]
203         key_aliases.each{|ka_| idm_obj.values[ka_] = obj.values[ka_]}
204         obj = idm_obj
205       else
206         obj.associations[parent] = nil
207         parent_map[opk] = obj
208         (children_map[key_conv[obj]] ||= []) << obj
209       end
210       
211       id_map[extract_key_alias[obj]].each do |root|
212         root.associations[ancestors] << obj
213       end
214     end
215     Sequel.synchronize_with(eo[:mutex]) do
216       parent_map.each do |parent_id, obj|
217         if children = children_map[parent_id]
218           children.each do |child|
219             child.associations[parent] = obj
220           end
221         end
222       end
223     end
224   end
225   model.one_to_many ancestors, a
226   
227   d = opts.merge(opts.fetch(:descendants, OPTS))
228   descendants = d.fetch(:name, :descendants)
229   d[:read_only] = true unless d.has_key?(:read_only)
230   d[:eager_grapher] = proc do |_|
231     raise Sequel::Error, "the #{descendants} association for #{self} does not support eager graphing"
232   end
233   la = d[:level_alias] ||= :x_level_x
234   d[:dataset] ||= proc do
235     base_ds = model.where(key_array.zip(prkey_array.map{|k| get_column_value(k)}))
236     recursive_ds = model.join(t, prkey_array.zip(key_array))
237     if c = d[:conditions]
238       (base_ds, recursive_ds) = [base_ds, recursive_ds].map do |ds|
239         (c.is_a?(Array) && !Sequel.condition_specifier?(c)) ? ds.where(*c) : ds.where(c)
240       end
241     end
242     table_alias = model.dataset.schema_and_table(model.table_name)[1].to_sym
243     model.from(SQL::AliasedExpression.new(t, table_alias)).
244      with_recursive(t, col_aliases ? base_ds.select(*col_aliases) : base_ds.select_all,
245       recursive_ds.select(*c_all),
246       :args=>col_aliases, union_all: opts[:union_all])
247     end
248   dal = Array(d[:after_load])
249   dal << proc do |m, descs|
250     unless m.associations.has_key?(childrena)
251       parent_map = {prkey_conv[m]=>m}
252       children_map = {}
253       m.associations[childrena] = []
254       descs.each do |obj|
255         obj.associations[childrena] = []
256         if opk = prkey_conv[obj]
257           parent_map[opk] = obj
258         end
259         if ok = key_conv[obj]
260           (children_map[ok] ||= []) << obj
261         end
262       end
263       children_map.each do |parent_id, objs|
264         parent_obj = parent_map[parent_id]
265         parent_obj.associations[childrena] = objs
266         objs.each do |obj|
267           obj.associations[parent] = parent_obj
268         end
269       end
270     end
271   end
272   d[:after_load] = dal
273   d[:eager_loader] ||= proc do |eo|
274     id_map = eo[:id_map]
275     associations = eo[:associations]
276     parent_map = {}
277     children_map = {}
278     Sequel.synchronize_with(eo[:mutex]) do
279       eo[:rows].each do |obj|
280         parent_map[prkey_conv[obj]] = obj
281         obj.associations[descendants] = []
282         obj.associations[childrena] = []
283       end
284     end
285     r = model.association_reflection(descendants)
286     base_case = model.where(key=>id_map.keys).
287      select(*descendant_base_case_columns)
288     recursive_case = model.join(t, prkey_array.zip(key_array)).
289      select(*recursive_case_columns)
290     if c = r[:conditions]
291       (base_case, recursive_case) = [base_case, recursive_case].map do |ds|
292         (c.is_a?(Array) && !Sequel.condition_specifier?(c)) ? ds.where(*c) : ds.where(c)
293       end
294     end
295     if associations.is_a?(Integer)
296       level = associations
297       no_cache_level = level - 1
298       associations = {}
299       base_case = base_case.select_append(SQL::AliasedExpression.new(Sequel.cast(0, Integer), la))
300       recursive_case = recursive_case.select_append(SQL::AliasedExpression.new(SQL::QualifiedIdentifier.new(t, la) + 1, la)).where(SQL::QualifiedIdentifier.new(t, la) < level - 1)
301     end
302     table_alias = model.dataset.schema_and_table(model.table_name)[1].to_sym
303     ds = model.from(SQL::AliasedExpression.new(t, table_alias)).
304       with_recursive(t, base_case, recursive_case,
305         :args=>((key_aliases + col_aliases + (level ? [la] : [])) if col_aliases), union_all: opts[:union_all])
306     ds = r.apply_eager_dataset_changes(ds)
307     ds = ds.select_append(ka) unless ds.opts[:select] == nil
308     model.eager_load_results(r, eo.merge(:loader=>false, :initialize_rows=>false, :dataset=>ds, :id_map=>nil, :associations=>OPTS)) do |obj|
309       if level
310         no_cache = no_cache_level == obj.values.delete(la)
311       end
312       
313       opk = prkey_conv[obj]
314       if idm_obj = parent_map[opk]
315         key_aliases.each{|ka_| idm_obj.values[ka_] = obj.values[ka_]}
316         obj = idm_obj
317       else
318         obj.associations[childrena] = [] unless no_cache
319         parent_map[opk] = obj
320       end
321       
322       if root = id_map[extract_key_alias[obj]].first
323         root.associations[descendants] << obj
324       end
325       
326       (children_map[key_conv[obj]] ||= []) << obj
327     end
328     Sequel.synchronize_with(eo[:mutex]) do
329       children_map.each do |parent_id, objs|
330         objs = objs.uniq
331         parent_obj = parent_map[parent_id]
332         parent_obj.associations[childrena] = objs
333         objs.each do |obj|
334           obj.associations[parent] = parent_obj
335         end
336       end
337     end
338   end
339   model.one_to_many descendants, d
340 end