diff options
author | GitLab Bot <gitlab-bot@gitlab.com> | 2021-08-19 12:08:42 +0300 |
---|---|---|
committer | GitLab Bot <gitlab-bot@gitlab.com> | 2021-08-19 12:08:42 +0300 |
commit | b76ae638462ab0f673e5915986070518dd3f9ad3 (patch) | |
tree | bdab0533383b52873be0ec0eb4d3c66598ff8b91 /lib/gitlab/pagination | |
parent | 434373eabe7b4be9593d18a585fb763f1e5f1a6f (diff) |
Add latest changes from gitlab-org/gitlab@14-2-stable-eev14.2.0-rc42
Diffstat (limited to 'lib/gitlab/pagination')
-rw-r--r-- | lib/gitlab/pagination/keyset/column_condition_builder.rb | 206 | ||||
-rw-r--r-- | lib/gitlab/pagination/keyset/order.rb | 48 | ||||
-rw-r--r-- | lib/gitlab/pagination/keyset/simple_order_builder.rb | 1 |
3 files changed, 211 insertions, 44 deletions
diff --git a/lib/gitlab/pagination/keyset/column_condition_builder.rb b/lib/gitlab/pagination/keyset/column_condition_builder.rb new file mode 100644 index 00000000000..ca436000abe --- /dev/null +++ b/lib/gitlab/pagination/keyset/column_condition_builder.rb @@ -0,0 +1,206 @@ +# frozen_string_literal: true + +module Gitlab + module Pagination + module Keyset + class ColumnConditionBuilder + # This class builds the WHERE conditions for the keyset pagination library. + # It produces WHERE conditions for one column at a time. + # + # Requisite 1: Only the last column (columns.last) is non-nullable and distinct. + # Requisite 2: Only one column is distinct and non-nullable. + # + # Scenario: We want to order by columns named X, Y and Z and build the conditions + # used in the WHERE clause of a pagination query using a set of cursor values. + # X is the column definition for a nullable column + # Y is the column definition for a non-nullable but not distinct column + # Z is the column definition for a distinct, non-nullable column used as a tie breaker. + # + # Then the method is initially invoked with these arguments: + # columns = [ColumnDefinition for X, ColumnDefinition for Y, ColumnDefinition for Z] + # values = { X: x, Y: y, Z: z } => these represent cursor values for pagination + # (x could be nil since X is nullable) + # current_conditions is initialized to [] to store the result during the iteration calls + # invoked within the Order#build_where_values method. + # + # The elements of current_conditions are instances of Arel::Nodes and - + # will be concatenated using OR or UNION to be used in the WHERE clause. + # + # Example: Let's say we want to build WHERE clause conditions for + # ORDER BY X DESC NULLS LAST, Y ASC, Z DESC + # + # Iteration 1: + # columns = [X, Y, Z] + # At the end, current_conditions should be: + # [(Z < z)] + # + # Iteration 2: + # columns = [X, Y] + # At the end, current_conditions should be: + # [(Y > y) OR (Y = y AND Z < z)] + # + # Iteration 3: + # columns = [X] + # At the end, current_conditions should be: + # [((X IS NOT NULL AND Y > y) OR (X IS NOT NULL AND Y = y AND Z < z)) + # OR + # ((x IS NULL) OR (X IS NULL))] + # + # Parameters: + # + # - columns: instance of ColumnOrderDefinition + # - value: cursor value for the column + def initialize(column, value) + @column = column + @value = value + end + + def where_conditions(current_conditions) + return not_nullable_conditions(current_conditions) if column.not_nullable? + return nulls_first_conditions(current_conditions) if column.nulls_first? + + # Here we are dealing with the case of column_definition.nulls_last? + # Suppose ORDER BY X DESC NULLS FIRST, Y ASC, Z DESC is the ordering clause + # and we already have built the conditions for columns Y and Z. + # + # We first need a set of conditions to use when x (the value for X) is NULL: + # null_conds = [ + # (x IS NULL AND X IS NULL AND Y<y), + # (x IS NULL AND X IS NULL AND Y=y AND Z<z), + null_conds = current_conditions.map do |conditional| + Arel::Nodes::And.new([value_is_null, column_is_null, conditional]) + end + + # We then need a set of conditions to use when m has an actual value: + # non_null_conds = [ + # (x IS NOT NULL AND X IS NULL), + # (x IS NOT NULL AND X < x) + # (x IS NOT NULL AND X = x AND Y > y), + # (x IS NOT NULL AND X = x AND Y = y AND Z < z), + tie_breaking_conds = current_conditions.map do |conditional| + Arel::Nodes::And.new([column_equals_to_value, conditional]) + end + + non_null_conds = [column_is_null, compare_column_with_value, *tie_breaking_conds].map do |conditional| + Arel::Nodes::And.new([value_is_not_null, conditional]) + end + + [*null_conds, *non_null_conds] + end + + private + + # WHEN THE COLUMN IS NON-NULLABLE AND DISTINCT + # Per Assumption 1, only the last column can be non-nullable and distinct + # (column Z is non-nullable/distinct and comes last in the example). + # So the Order#build_where_conditions is being called for the first time with current_conditions = []. + # + # At the end of the call, we should expect: + # current_conditions should be [(Z < z)] + # + # WHEN THE COLUMN IS NON-NULLABLE BUT NOT DISTINCT + # Let's say Z has been processed and we are about to process the column Y next. + # (per requisite 1, if a non-nullable but not distinct column is being processed, + # at the least, the conditional for the non-nullable/distinct column exists) + # + # At the start of the method call: + # current_conditions = [(Z < z)] + # comparison_node = (Y < y) + # eqaulity_node = (Y = y) + # + # We should add a comparison node for the next column Y, (Y < y) + # then break a tie using the previous conditionals, (Y = y AND Z < z) + # + # At the end of the call, we should expect: + # current_conditions = [(Y < y), (Y = y AND Z < z)] + def not_nullable_conditions(current_conditions) + tie_break_conds = current_conditions.map do |conditional| + Arel::Nodes::And.new([column_equals_to_value, conditional]) + end + + [compare_column_with_value, *tie_break_conds] + end + + def nulls_first_conditions(current_conditions) + # Using the same scenario described earlier, + # suppose the ordering clause is ORDER BY X DESC NULLS FIRST, Y ASC, Z DESC + # and we have built the conditions for columns Y and Z in previous iterations: + # + # current_conditions = [(Y > y), (Y = y AND Z < z)] + # + # In this branch of the iteration, + # we first need a set of conditions to use when m (the value for M) is NULL: + # null_conds = [ + # (x IS NULL AND X IS NULL AND Y > y), + # (x IS NULL AND X IS NULL AND Y = y AND Z < z), + # (x IS NULL AND X IS NOT NULL)] + # + # Note that when x has an actual value, say x = 3, null_conds evalutes to FALSE. + tie_breaking_conds = current_conditions.map do |conditional| + Arel::Nodes::And.new([column_is_null, conditional]) + end + + null_conds = [*tie_breaking_conds, column_is_not_null].map do |conditional| + Arel::Nodes::And.new([value_is_null, conditional]) + end + + # We then need a set of conditions to use when m has an actual value: + # non_null_conds = [ + # (x IS NOT NULL AND X < x), + # (x IS NOT NULL AND X = x AND Y > y), + # (x IS NOT NULL AND X = x AND Y = y AND Z < z)] + # + # Note again that when x IS NULL, non_null_conds evaluates to FALSE. + tie_breaking_conds = current_conditions.map do |conditional| + Arel::Nodes::And.new([column_equals_to_value, conditional]) + end + + # The combined OR condition (null_where_cond OR non_null_where_cond) will return a correct result - + # without having to account for whether x is nil or an actual value at the application level. + non_null_conds = [compare_column_with_value, *tie_breaking_conds].map do |conditional| + Arel::Nodes::And.new([value_is_not_null, conditional]) + end + + [*null_conds, *non_null_conds] + end + + def column_equals_to_value + @equality_node ||= column.column_expression.eq(value) + end + + def column_is_null + @column_is_null ||= column.column_expression.eq(nil) + end + + def column_is_not_null + @column_is_not_null ||= column.column_expression.not_eq(nil) + end + + def value_is_null + @value_is_null ||= build_quoted_value.eq(nil) + end + + def value_is_not_null + @value_is_not_null ||= build_quoted_value.not_eq(nil) + end + + def compare_column_with_value + if column.descending_order? + column.column_expression.lt(value) + else + column.column_expression.gt(value) + end + end + + # Turns the given value to an SQL literal by casting it to the proper format. + def build_quoted_value + return value if value.instance_of?(Arel::Nodes::SqlLiteral) + + Arel::Nodes.build_quoted(value, column.column_expression) + end + + attr_reader :column, :value + end + end + end +end diff --git a/lib/gitlab/pagination/keyset/order.rb b/lib/gitlab/pagination/keyset/order.rb index 19d44ee69dd..ccfa9334a12 100644 --- a/lib/gitlab/pagination/keyset/order.rb +++ b/lib/gitlab/pagination/keyset/order.rb @@ -141,24 +141,10 @@ module Gitlab return use_composite_row_comparison(values) if composite_row_comparison_possible? - where_values = [] - - reversed_column_definitions = column_definitions.reverse - reversed_column_definitions.each_with_index do |column_definition, i| - value = values[column_definition.attribute_name] - - conditions_for_column(column_definition, value).each do |condition| - column_definitions_after_index = reversed_column_definitions.last(column_definitions.reverse.size - i - 1) - - equal_conditon_for_rest = column_definitions_after_index.map do |definition| - definition.column_expression.eq(values[definition.attribute_name]) - end - - where_values << Arel::Nodes::Grouping.new(Arel::Nodes::And.new([condition, *equal_conditon_for_rest].compact)) - end - end - - where_values + column_definitions + .map { ColumnConditionBuilder.new(_1, values[_1.attribute_name]) } + .reverse + .reduce([]) { |where_conditions, column| column.where_conditions(where_conditions) } end def where_values_with_or_query(values) @@ -222,32 +208,6 @@ module Gitlab scope end - def conditions_for_column(column_definition, value) - conditions = [] - # Depending on the order, build a query condition fragment for taking the next rows - if column_definition.distinct? || (!column_definition.distinct? && value.present?) - conditions << compare_column_with_value(column_definition, value) - end - - # When the column is nullable, additional conditions for NULL a NOT NULL values are necessary. - # This depends on the position of the nulls (top or bottom of the resultset). - if column_definition.nulls_first? && value.blank? - conditions << column_definition.column_expression.not_eq(nil) - elsif column_definition.nulls_last? && value.present? - conditions << column_definition.column_expression.eq(nil) - end - - conditions - end - - def compare_column_with_value(column_definition, value) - if column_definition.descending_order? - column_definition.column_expression.lt(value) - else - column_definition.column_expression.gt(value) - end - end - def build_or_query(expressions) return [] if expressions.blank? diff --git a/lib/gitlab/pagination/keyset/simple_order_builder.rb b/lib/gitlab/pagination/keyset/simple_order_builder.rb index 76d6bbadaa4..5e79910a3e9 100644 --- a/lib/gitlab/pagination/keyset/simple_order_builder.rb +++ b/lib/gitlab/pagination/keyset/simple_order_builder.rb @@ -122,6 +122,7 @@ module Gitlab return unless attribute return unless tie_breaker_attribute + return unless attribute.respond_to?(:name) model_class.column_names.include?(attribute.name.to_s) && arel_table[primary_key].to_s == tie_breaker_attribute.to_s |