| 1 | // SPDX-License-Identifier: GPL-3.0-or-later |
| 2 | |
| 3 | #include "query-internal.h" |
| 4 | |
| 5 | static int compare_contributions(const void *a, const void *b) { |
| 6 | const struct { size_t dim_idx; NETDATA_DOUBLE contribution; } *da = a; |
| 7 | const struct { size_t dim_idx; NETDATA_DOUBLE contribution; } *db = b; |
| 8 | |
| 9 | if (da->contribution > db->contribution) return -1; |
| 10 | if (da->contribution < db->contribution) return 1; |
| 11 | return 0; |
| 12 | } |
| 13 | |
| 14 | RRDR *rrd2rrdr_cardinality_limit(RRDR *r) { |
| 15 | QUERY_TARGET *qt = r->internal.qt; |
| 16 | |
| 17 | if(!qt || qt->request.cardinality_limit == 0 || r->d <= qt->request.cardinality_limit) |
| 18 | return r; |
| 19 | |
| 20 | ONEWAYALLOC *owa = r->internal.owa; |
| 21 | |
| 22 | // Calculate contribution of each dimension using dview statistics (sum of values) |
| 23 | NETDATA_DOUBLE *contributions = onewayalloc_mallocz(owa, r->d * sizeof(NETDATA_DOUBLE)); |
| 24 | |
| 25 | // Count queried dimensions and get their contributions from dview |
| 26 | size_t queried_count = 0; |
| 27 | for (size_t d = 0; d < r->d; d++) { |
| 28 | contributions[d] = 0.0; |
| 29 | |
| 30 | if (!(r->od[d] & RRDR_DIMENSION_QUERIED)) |
| 31 | continue; |
| 32 | |
| 33 | queried_count++; |
| 34 | |
| 35 | // Use the sum from dview if available, otherwise fall back to manual calculation |
| 36 | if(r->dview && !isnan(r->dview[d].sum)) { |
| 37 | contributions[d] = fabsndd(r->dview[d].sum); |
| 38 | } else { |
| 39 | // Fallback: calculate manually from values |
| 40 | for(size_t i = 0; i < r->rows; i++) { |
| 41 | size_t idx = i * r->d + d; |
| 42 | |
| 43 | if(r->o[idx] & RRDR_VALUE_EMPTY) |
| 44 | continue; |
| 45 | |
| 46 | NETDATA_DOUBLE value = r->v[idx]; |
| 47 | if(!isnan(value)) |
| 48 | contributions[d] += fabsndd(value); |
| 49 | } |
| 50 | } |
| 51 | } |
| 52 | |
| 53 | // If we don't need to reduce, return original |
| 54 | if(queried_count <= qt->request.cardinality_limit) { |
| 55 | onewayalloc_freez(owa, contributions); |
| 56 | return r; |
| 57 | } |
| 58 | |
| 59 | // Create array of dimension indices sorted by contribution (descending) |
| 60 | struct { |
| 61 | size_t dim_idx; |
| 62 | NETDATA_DOUBLE contribution; |
| 63 | } *sorted_dims = onewayalloc_mallocz(owa, queried_count * sizeof(*sorted_dims)); |
| 64 | |
| 65 | size_t sorted_idx = 0; |
| 66 | for (size_t d = 0; d < r->d; d++) { |
| 67 | if (r->od[d] & RRDR_DIMENSION_QUERIED) { |
| 68 | sorted_dims[sorted_idx].dim_idx = d; |
| 69 | sorted_dims[sorted_idx].contribution = contributions[d]; |
| 70 | sorted_idx++; |
| 71 | } |
| 72 | } |
| 73 | |
| 74 | // Sort by contribution (descending) |
| 75 | qsort(sorted_dims, queried_count, sizeof(*sorted_dims), compare_contributions); |
| 76 | |
| 77 | // Create new RRDR with limited dimensions |
| 78 | size_t new_d = qt->request.cardinality_limit; |
| 79 | size_t remaining_count = queried_count - (qt->request.cardinality_limit - 1); |
| 80 | if(remaining_count > 0) |
| 81 | new_d = qt->request.cardinality_limit; // Keep one slot for "remaining N dimensions" |
| 82 | else |
| 83 | new_d = queried_count; // No remaining dimensions needed |
| 84 | |
| 85 | RRDR *new_r = rrdr_create(owa, qt, new_d, r->n); |
| 86 | if (!new_r) { |
| 87 | internal_error(true, "QUERY: cannot create cardinality limited RRDR"); |
| 88 | onewayalloc_freez(owa, contributions); |
| 89 | onewayalloc_freez(owa, sorted_dims); |
| 90 | return r; |
| 91 | } |
| 92 | |
| 93 | // Copy basic metadata from original RRDR |
| 94 | new_r->view = r->view; |
| 95 | new_r->time_grouping = r->time_grouping; |
| 96 | new_r->partial_data_trimming = r->partial_data_trimming; |
| 97 | new_r->rows = r->rows; |
| 98 | |
| 99 | // Copy timestamps |
| 100 | memcpy(new_r->t, r->t, r->n * sizeof(time_t)); |
| 101 | |
| 102 | // Setup arrays for new RRDR |
| 103 | if(new_r->d) { |
| 104 | new_r->dp = onewayalloc_callocz(owa, new_r->d, sizeof(*new_r->dp)); |
| 105 | new_r->dview = onewayalloc_callocz(owa, new_r->d, sizeof(*new_r->dview)); |
| 106 | |
| 107 | if(new_r->n) { |
| 108 | // Initialize all values as empty |
| 109 | for (size_t i = 0; i < new_r->n; i++) { |
| 110 | for (size_t d = 0; d < new_r->d; d++) { |
| 111 | size_t idx = i * new_r->d + d; |
| 112 | new_r->v[idx] = NAN; |
| 113 | new_r->ar[idx] = 0.0; |
| 114 | new_r->o[idx] = RRDR_VALUE_EMPTY; |
| 115 | } |
| 116 | } |
| 117 | } |
| 118 | } |
| 119 | |
| 120 | // Copy top dimensions |
| 121 | size_t kept_dimensions = (remaining_count > 0) ? qt->request.cardinality_limit - 1 : queried_count; |
| 122 | |
| 123 | for (size_t i = 0; i < kept_dimensions; i++) { |
| 124 | size_t src_d = sorted_dims[i].dim_idx; |
| 125 | |
| 126 | // Copy metadata |
| 127 | new_r->di[i] = string_dup(r->di[src_d]); |
| 128 | new_r->dn[i] = string_dup(r->dn[src_d]); |
| 129 | new_r->od[i] = r->od[src_d]; |
| 130 | new_r->du[i] = string_dup(r->du[src_d]); |
| 131 | new_r->dp[i] = r->dp[src_d]; |
| 132 | |
| 133 | // Copy data |
| 134 | for (size_t row = 0; row < r->rows; row++) { |
| 135 | size_t src_idx = row * r->d + src_d; |
| 136 | size_t dst_idx = row * new_r->d + i; |
| 137 | |
| 138 | new_r->v[dst_idx] = r->v[src_idx]; |
| 139 | new_r->ar[dst_idx] = r->ar[src_idx]; |
| 140 | new_r->o[dst_idx] = r->o[src_idx]; |
| 141 | } |
| 142 | |
| 143 | // Copy dview stats |
| 144 | if(r->dview) |
| 145 | new_r->dview[i] = r->dview[src_d]; |
| 146 | } |
| 147 | |
| 148 | // Create "remaining N dimensions" if needed |
| 149 | if (remaining_count > 0) { |
| 150 | size_t remaining_idx = kept_dimensions; |
| 151 | |
| 152 | char remaining_name[256]; |
| 153 | snprintfz(remaining_name, sizeof(remaining_name), "remaining %zu dimension%s", |
| 154 | remaining_count, remaining_count == 1 ? "" : "s"); |
| 155 | |
| 156 | new_r->di[remaining_idx] = string_strdupz(remaining_name); |
| 157 | new_r->dn[remaining_idx] = string_strdupz(remaining_name); |
| 158 | new_r->od[remaining_idx] = RRDR_DIMENSION_QUERIED | RRDR_DIMENSION_NONZERO; |
| 159 | |
| 160 | // Use the units from the first remaining dimension |
| 161 | if(kept_dimensions < queried_count) { |
| 162 | size_t first_remaining_d = sorted_dims[kept_dimensions].dim_idx; |
| 163 | new_r->du[remaining_idx] = string_dup(r->du[first_remaining_d]); |
| 164 | new_r->dp[remaining_idx] = r->dp[first_remaining_d]; |
| 165 | } |
| 166 | |
| 167 | // Aggregate remaining dimensions |
| 168 | NETDATA_DOUBLE sum = 0.0, min = NAN, max = NAN, ars = 0.0; |
| 169 | size_t count = 0; |
| 170 | |
| 171 | for (size_t row = 0; row < r->rows; row++) { |
| 172 | size_t dst_idx = row * new_r->d + remaining_idx; |
| 173 | NETDATA_DOUBLE aggregated_value = 0.0; |
| 174 | NETDATA_DOUBLE aggregated_ar = 0.0; |
| 175 | RRDR_VALUE_FLAGS aggregated_flags = RRDR_VALUE_NOTHING; |
| 176 | bool has_values = false; |
| 177 | |
| 178 | for (size_t i = kept_dimensions; i < queried_count; i++) { |
| 179 | size_t src_d = sorted_dims[i].dim_idx; |
| 180 | size_t src_idx = row * r->d + src_d; |
| 181 | |
| 182 | if(!(r->o[src_idx] & RRDR_VALUE_EMPTY)) { |
| 183 | NETDATA_DOUBLE value = r->v[src_idx]; |
| 184 | if(!isnan(value)) { |
| 185 | aggregated_value += value; |
| 186 | aggregated_ar += r->ar[src_idx]; |
| 187 | aggregated_flags |= (r->o[src_idx] & (RRDR_VALUE_RESET | RRDR_VALUE_PARTIAL)); |
| 188 | has_values = true; |
| 189 | } |
| 190 | } |
| 191 | } |
| 192 | |
| 193 | if(has_values) { |
| 194 | new_r->v[dst_idx] = aggregated_value; |
| 195 | new_r->ar[dst_idx] = aggregated_ar; |
| 196 | new_r->o[dst_idx] = aggregated_flags & ~RRDR_VALUE_EMPTY; |
| 197 | |
| 198 | // Update statistics for dview |
| 199 | sum += aggregated_value; |
| 200 | ars += aggregated_ar; |
| 201 | if(count == 0) { |
| 202 | min = max = aggregated_value; |
| 203 | } else { |
| 204 | if(aggregated_value < min) min = aggregated_value; |
| 205 | if(aggregated_value > max) max = aggregated_value; |
| 206 | } |
| 207 | count++; |
| 208 | } else { |
| 209 | new_r->v[dst_idx] = NAN; |
| 210 | new_r->ar[dst_idx] = 0.0; |
| 211 | new_r->o[dst_idx] = RRDR_VALUE_EMPTY; |
| 212 | } |
| 213 | } |
| 214 | |
| 215 | // Set dview for remaining dimension |
| 216 | if(new_r->dview) { |
| 217 | new_r->dview[remaining_idx] = (STORAGE_POINT) { |
| 218 | .sum = sum, |
| 219 | .count = count, |
| 220 | .min = min, |
| 221 | .max = max, |
| 222 | .anomaly_count = (size_t)(ars * RRDR_DVIEW_ANOMALY_COUNT_MULTIPLIER / 100.0), |
| 223 | }; |
| 224 | } |
| 225 | } |
| 226 | |
| 227 | // Cleanup |
| 228 | onewayalloc_freez(owa, contributions); |
| 229 | onewayalloc_freez(owa, sorted_dims); |
| 230 | |
| 231 | // Free the original RRDR |
| 232 | rrdr_free(owa, r); |
| 233 | |
| 234 | return new_r; |
| 235 | } |