Line data Source code
1 : /*
2 : * SPDX-License-Identifier: MPL-2.0
3 : *
4 : * This Source Code Form is subject to the terms of the Mozilla Public
5 : * License, v. 2.0. If a copy of the MPL was not distributed with this
6 : * file, You can obtain one at http://mozilla.org/MPL/2.0/.
7 : *
8 : * Copyright 2024 MonetDB Foundation;
9 : * Copyright August 2008 - 2023 MonetDB B.V.;
10 : * Copyright 1997 - July 2008 CWI.
11 : */
12 :
13 : #include "monetdb_config.h"
14 : #include "gdk.h"
15 : #include "gdk_private.h"
16 :
17 : /* Calculate a cross product between bats l and r with optional
18 : * candidate lists sl for l and sr for r.
19 : * The result is two bats r1 and r2 which contain the OID (head
20 : * values) of the input bats l and r.
21 : * If max_one is set, r can have at most one row. */
22 : static gdk_return
23 46486 : BATcrossci(BAT **r1p, BAT **r2p, struct canditer *ci1, struct canditer *ci2)
24 : {
25 46486 : BAT *bn1, *bn2 = NULL;
26 46486 : oid *restrict p;
27 46486 : BUN i, j;
28 :
29 46486 : QryCtx *qry_ctx = MT_thread_get_qry_ctx();
30 :
31 : /* first some special cases */
32 46500 : if (ci1->ncand == 0 || ci2->ncand == 0) {
33 24482 : if ((bn1 = BATdense(0, 0, 0)) == NULL)
34 : return GDK_FAIL;
35 24264 : if (r2p) {
36 23617 : if ((bn2 = BATdense(0, 0, 0)) == NULL) {
37 0 : BBPreclaim(bn1);
38 0 : return GDK_FAIL;
39 : }
40 23733 : *r2p = bn2;
41 : }
42 24380 : *r1p = bn1;
43 24380 : return GDK_SUCCEED;
44 : }
45 22018 : if (ci2->ncand == 1) {
46 15000 : if ((bn1 = canditer_slice(ci1, 0, ci1->ncand)) == NULL)
47 : return GDK_FAIL;
48 14944 : if (r2p) {
49 14352 : if (ci1->ncand == 1) {
50 4786 : bn2 = canditer_slice(ci2, 0, ci2->ncand);
51 : } else {
52 9566 : bn2 = BATconstant(0, TYPE_oid, &ci2->seq, ci1->ncand, TRANSIENT);
53 : }
54 14233 : if (bn2 == NULL) {
55 0 : BBPreclaim(bn1);
56 0 : return GDK_FAIL;
57 : }
58 14233 : *r2p = bn2;
59 : }
60 14825 : *r1p = bn1;
61 14825 : return GDK_SUCCEED;
62 : }
63 7018 : if (ci1->ncand == 1) {
64 2147 : bn1 = BATconstant(0, TYPE_oid, &ci1->seq, ci2->ncand, TRANSIENT);
65 2130 : if (bn1 == NULL)
66 : return GDK_FAIL;
67 2130 : if (r2p) {
68 1932 : bn2 = canditer_slice(ci2, 0, ci2->ncand);
69 1941 : if (bn2 == NULL) {
70 0 : BBPreclaim(bn1);
71 0 : return GDK_FAIL;
72 : }
73 1941 : *r2p = bn2;
74 : }
75 2139 : *r1p = bn1;
76 2139 : return GDK_SUCCEED;
77 : }
78 :
79 4871 : bn1 = COLnew(0, TYPE_oid, ci1->ncand * ci2->ncand, TRANSIENT);
80 4860 : if (r2p)
81 4586 : bn2 = COLnew(0, TYPE_oid, ci1->ncand * ci2->ncand, TRANSIENT);
82 4855 : if (bn1 == NULL || (r2p && bn2 == NULL)) {
83 0 : BBPreclaim(bn1);
84 0 : BBPreclaim(bn2);
85 0 : return GDK_FAIL;
86 : }
87 4855 : if (ci1->ncand > 0 && ci2->ncand > 0) {
88 4853 : BATsetcount(bn1, ci1->ncand * ci2->ncand);
89 4867 : bn1->tsorted = true;
90 4867 : bn1->trevsorted = ci1->ncand <= 1;
91 4867 : bn1->tkey = ci2->ncand <= 1;
92 4867 : bn1->tnil = false;
93 4867 : bn1->tnonil = true;
94 4867 : p = (oid *) Tloc(bn1, 0);
95 261189 : for (i = 0; i < ci1->ncand; i++) {
96 256334 : GDK_CHECK_TIMEOUT_BODY(qry_ctx, GOTO_LABEL_TIMEOUT_HANDLER(bailout, qry_ctx));
97 256584 : oid x = canditer_next(ci1);
98 8829698 : for (j = 0; j < ci2->ncand; j++) {
99 8316792 : *p++ = x;
100 : }
101 : }
102 4855 : BATtseqbase(bn1, ci2->ncand == 1 ? *(oid *) Tloc(bn1, 0) : oid_nil);
103 :
104 4830 : if (bn2) {
105 4565 : BATsetcount(bn2, ci1->ncand * ci2->ncand);
106 4571 : bn2->tsorted = ci1->ncand <= 1 || ci2->ncand <= 1;
107 4571 : bn2->trevsorted = ci2->ncand <= 1;
108 4571 : bn2->tkey = ci1->ncand <= 1;
109 4571 : bn2->tnil = false;
110 4571 : bn2->tnonil = true;
111 4571 : p = (oid *) Tloc(bn2, 0);
112 222982 : for (i = 0; i < ci1->ncand; i++) {
113 218403 : GDK_CHECK_TIMEOUT_BODY(qry_ctx, GOTO_LABEL_TIMEOUT_HANDLER(bailout, qry_ctx));
114 2186962 : for (j = 0; j < ci2->ncand; j++) {
115 1968323 : *p++ = canditer_next(ci2);
116 : }
117 218639 : canditer_reset(ci2);
118 : }
119 4579 : BATtseqbase(bn2, ci1->ncand == 1 ? *(oid *) Tloc(bn2, 0) : oid_nil);
120 : }
121 : }
122 4843 : *r1p = bn1;
123 4843 : if (r2p)
124 4579 : *r2p = bn2;
125 4843 : if (r2p)
126 4579 : TRC_DEBUG(ALGO, "BATsubcross()=(" ALGOBATFMT "," ALGOBATFMT ")\n", ALGOBATPAR(bn1), ALGOBATPAR(bn2));
127 : else
128 264 : TRC_DEBUG(ALGO, "BATsubcross()=(" ALGOBATFMT ")\n", ALGOBATPAR(bn1));
129 : return GDK_SUCCEED;
130 :
131 8 : bailout:
132 8 : BBPreclaim(bn1);
133 8 : BBPreclaim(bn2);
134 : return GDK_FAIL;
135 : }
136 :
137 : gdk_return
138 46193 : BATsubcross(BAT **r1p, BAT **r2p, BAT *l, BAT *r, BAT *sl, BAT *sr, bool max_one)
139 : {
140 46193 : struct canditer ci1, ci2;
141 :
142 46193 : canditer_init(&ci1, l, sl);
143 46218 : canditer_init(&ci2, r, sr);
144 46220 : if (max_one && ci1.ncand > 0 && ci2.ncand > 1) {
145 78 : GDKerror("more than one match");
146 78 : return GDK_FAIL;
147 : }
148 46142 : return BATcrossci(r1p, r2p, &ci1, &ci2);
149 : }
150 :
151 : /* [left] outer cross */
152 : gdk_return
153 425 : BAToutercross(BAT **r1p, BAT **r2p, BAT *l, BAT *r, BAT *sl, BAT *sr, bool max_one)
154 : {
155 425 : struct canditer ci1, ci2;
156 :
157 425 : canditer_init(&ci1, l, sl);
158 425 : canditer_init(&ci2, r, sr);
159 425 : if (max_one && ci1.ncand > 0 && ci2.ncand > 1) {
160 0 : GDKerror("more than one match");
161 0 : return GDK_FAIL;
162 : }
163 :
164 425 : if (ci1.ncand == 0) {
165 30 : BAT *bn = COLnew(0, TYPE_void, 0, TRANSIENT);
166 30 : if (bn == NULL)
167 : return GDK_FAIL;
168 30 : BATtseqbase(bn, oid_nil);
169 30 : *r1p = bn;
170 30 : if (r2p) {
171 30 : bn = COLnew(0, TYPE_void, 0, TRANSIENT);
172 30 : if (bn == NULL) {
173 0 : BBPreclaim(*r1p);
174 0 : return GDK_FAIL;
175 : }
176 30 : BATtseqbase(bn, oid_nil);
177 30 : *r2p = bn;
178 : }
179 30 : return GDK_SUCCEED;
180 : }
181 395 : if (ci2.ncand == 0) {
182 28 : BAT *bn = canditer_slice(&ci1, 0, ci1.ncand);
183 28 : if (bn == NULL)
184 : return GDK_FAIL;
185 28 : *r1p = bn;
186 28 : if (r2p) {
187 28 : BAT *bn = COLnew(0, TYPE_void, ci1.ncand, TRANSIENT);
188 28 : if (bn == NULL)
189 : return GDK_FAIL;
190 28 : BATtseqbase(bn, oid_nil);
191 28 : BATsetcount(bn, ci1.ncand);
192 28 : *r2p = bn;
193 : }
194 28 : return GDK_SUCCEED;
195 : }
196 367 : return BATcrossci(r1p, r2p, &ci1, &ci2);
197 : }
|
