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 45344 : BATcrossci(BAT **r1p, BAT **r2p, struct canditer *ci1, struct canditer *ci2)
24 : {
25 45344 : BAT *bn1, *bn2 = NULL;
26 45344 : oid *restrict p;
27 45344 : BUN i, j;
28 :
29 45344 : QryCtx *qry_ctx = MT_thread_get_qry_ctx();
30 :
31 : /* first some special cases */
32 45346 : if (ci1->ncand == 0 || ci2->ncand == 0) {
33 24211 : if ((bn1 = BATdense(0, 0, 0)) == NULL)
34 : return GDK_FAIL;
35 23995 : if (r2p) {
36 23381 : if ((bn2 = BATdense(0, 0, 0)) == NULL) {
37 0 : BBPreclaim(bn1);
38 0 : return GDK_FAIL;
39 : }
40 23410 : *r2p = bn2;
41 : }
42 24024 : *r1p = bn1;
43 24024 : return GDK_SUCCEED;
44 : }
45 21135 : if (ci2->ncand == 1) {
46 14273 : if ((bn1 = canditer_slice(ci1, 0, ci1->ncand)) == NULL)
47 : return GDK_FAIL;
48 13985 : if (r2p) {
49 13533 : if (ci1->ncand == 1) {
50 4422 : bn2 = canditer_slice(ci2, 0, ci2->ncand);
51 : } else {
52 9111 : bn2 = BATconstant(0, TYPE_oid, &ci2->seq, ci1->ncand, TRANSIENT);
53 : }
54 13508 : if (bn2 == NULL) {
55 0 : BBPreclaim(bn1);
56 0 : return GDK_FAIL;
57 : }
58 13508 : *r2p = bn2;
59 : }
60 13960 : *r1p = bn1;
61 13960 : return GDK_SUCCEED;
62 : }
63 6862 : if (ci1->ncand == 1) {
64 2099 : bn1 = BATconstant(0, TYPE_oid, &ci1->seq, ci2->ncand, TRANSIENT);
65 2085 : if (bn1 == NULL)
66 : return GDK_FAIL;
67 2085 : if (r2p) {
68 1894 : bn2 = canditer_slice(ci2, 0, ci2->ncand);
69 1886 : if (bn2 == NULL) {
70 0 : BBPreclaim(bn1);
71 0 : return GDK_FAIL;
72 : }
73 1886 : *r2p = bn2;
74 : }
75 2077 : *r1p = bn1;
76 2077 : return GDK_SUCCEED;
77 : }
78 :
79 4763 : bn1 = COLnew(0, TYPE_oid, ci1->ncand * ci2->ncand, TRANSIENT);
80 4756 : if (r2p)
81 4513 : bn2 = COLnew(0, TYPE_oid, ci1->ncand * ci2->ncand, TRANSIENT);
82 4754 : if (bn1 == NULL || (r2p && bn2 == NULL)) {
83 0 : BBPreclaim(bn1);
84 0 : BBPreclaim(bn2);
85 0 : return GDK_FAIL;
86 : }
87 4754 : if (ci1->ncand > 0 && ci2->ncand > 0) {
88 4754 : BATsetcount(bn1, ci1->ncand * ci2->ncand);
89 4761 : bn1->tsorted = true;
90 4761 : bn1->trevsorted = ci1->ncand <= 1;
91 4761 : bn1->tkey = ci2->ncand <= 1;
92 4761 : bn1->tnil = false;
93 4761 : bn1->tnonil = true;
94 4761 : p = (oid *) Tloc(bn1, 0);
95 258539 : for (i = 0; i < ci1->ncand; i++) {
96 253797 : GDK_CHECK_TIMEOUT_BODY(qry_ctx, GOTO_LABEL_TIMEOUT_HANDLER(bailout, qry_ctx));
97 254031 : oid x = canditer_next(ci1);
98 8712440 : for (j = 0; j < ci2->ncand; j++) {
99 8204631 : *p++ = x;
100 : }
101 : }
102 4742 : BATtseqbase(bn1, ci2->ncand == 1 ? *(oid *) Tloc(bn1, 0) : oid_nil);
103 :
104 4723 : if (bn2) {
105 4495 : BATsetcount(bn2, ci1->ncand * ci2->ncand);
106 4498 : bn2->tsorted = ci1->ncand <= 1 || ci2->ncand <= 1;
107 4498 : bn2->trevsorted = ci2->ncand <= 1;
108 4498 : bn2->tkey = ci1->ncand <= 1;
109 4498 : bn2->tnil = false;
110 4498 : bn2->tnonil = true;
111 4498 : p = (oid *) Tloc(bn2, 0);
112 222492 : for (i = 0; i < ci1->ncand; i++) {
113 217986 : GDK_CHECK_TIMEOUT_BODY(qry_ctx, GOTO_LABEL_TIMEOUT_HANDLER(bailout, qry_ctx));
114 2186126 : for (j = 0; j < ci2->ncand; j++) {
115 1968011 : *p++ = canditer_next(ci2);
116 : }
117 218115 : canditer_reset(ci2);
118 : }
119 4506 : BATtseqbase(bn2, ci1->ncand == 1 ? *(oid *) Tloc(bn2, 0) : oid_nil);
120 : }
121 : }
122 4731 : *r1p = bn1;
123 4731 : if (r2p)
124 4503 : *r2p = bn2;
125 4731 : if (r2p)
126 4503 : TRC_DEBUG(ALGO, "BATsubcross()=(" ALGOBATFMT "," ALGOBATFMT ")\n", ALGOBATPAR(bn1), ALGOBATPAR(bn2));
127 : else
128 228 : 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 45082 : BATsubcross(BAT **r1p, BAT **r2p, BAT *l, BAT *r, BAT *sl, BAT *sr, bool max_one)
139 : {
140 45082 : struct canditer ci1, ci2;
141 :
142 45082 : canditer_init(&ci1, l, sl);
143 45061 : canditer_init(&ci2, r, sr);
144 45094 : if (max_one && ci1.ncand > 0 && ci2.ncand > 1) {
145 54 : GDKerror("more than one match");
146 54 : return GDK_FAIL;
147 : }
148 45040 : return BATcrossci(r1p, r2p, &ci1, &ci2);
149 : }
150 :
151 : /* [left] outer cross */
152 : gdk_return
153 366 : BAToutercross(BAT **r1p, BAT **r2p, BAT *l, BAT *r, BAT *sl, BAT *sr, bool max_one)
154 : {
155 366 : struct canditer ci1, ci2;
156 :
157 366 : canditer_init(&ci1, l, sl);
158 366 : canditer_init(&ci2, r, sr);
159 366 : if (max_one && ci1.ncand > 0 && ci2.ncand > 1) {
160 0 : GDKerror("more than one match");
161 0 : return GDK_FAIL;
162 : }
163 :
164 366 : 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 336 : if (ci2.ncand == 0) {
182 18 : BAT *bn = canditer_slice(&ci1, 0, ci1.ncand);
183 18 : if (bn == NULL)
184 : return GDK_FAIL;
185 18 : *r1p = bn;
186 18 : if (r2p) {
187 18 : BAT *bn = COLnew(0, TYPE_void, ci1.ncand, TRANSIENT);
188 18 : if (bn == NULL)
189 : return GDK_FAIL;
190 18 : BATtseqbase(bn, oid_nil);
191 18 : BATsetcount(bn, ci1.ncand);
192 18 : *r2p = bn;
193 : }
194 18 : return GDK_SUCCEED;
195 : }
196 318 : return BATcrossci(r1p, r2p, &ci1, &ci2);
197 : }
|
