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 47241 : BATcrossci(BAT **r1p, BAT **r2p, struct canditer *ci1, struct canditer *ci2)
24 : {
25 47241 : BAT *bn1, *bn2 = NULL;
26 47241 : oid *restrict p;
27 47241 : BUN i, j;
28 :
29 47241 : QryCtx *qry_ctx = MT_thread_get_qry_ctx();
30 :
31 : /* first some special cases */
32 47246 : if (ci1->ncand == 0 || ci2->ncand == 0) {
33 24544 : if ((bn1 = BATdense(0, 0, 0)) == NULL)
34 : return GDK_FAIL;
35 24285 : if (r2p) {
36 23636 : if ((bn2 = BATdense(0, 0, 0)) == NULL) {
37 0 : BBPreclaim(bn1);
38 0 : return GDK_FAIL;
39 : }
40 23740 : *r2p = bn2;
41 : }
42 24389 : *r1p = bn1;
43 24389 : return GDK_SUCCEED;
44 : }
45 22702 : if (ci2->ncand == 1) {
46 15248 : if ((bn1 = canditer_slice(ci1, 0, ci1->ncand)) == NULL)
47 : return GDK_FAIL;
48 14950 : if (r2p) {
49 14323 : if (ci1->ncand == 1) {
50 4862 : bn2 = canditer_slice(ci2, 0, ci2->ncand);
51 : } else {
52 9461 : bn2 = BATconstant(0, TYPE_oid, &ci2->seq, ci1->ncand, TRANSIENT);
53 : }
54 14392 : if (bn2 == NULL) {
55 0 : BBPreclaim(bn1);
56 0 : return GDK_FAIL;
57 : }
58 14392 : *r2p = bn2;
59 : }
60 15019 : *r1p = bn1;
61 15019 : return GDK_SUCCEED;
62 : }
63 7454 : if (ci1->ncand == 1) {
64 2169 : bn1 = BATconstant(0, TYPE_oid, &ci1->seq, ci2->ncand, TRANSIENT);
65 2153 : if (bn1 == NULL)
66 : return GDK_FAIL;
67 2153 : if (r2p) {
68 1942 : bn2 = canditer_slice(ci2, 0, ci2->ncand);
69 1943 : if (bn2 == NULL) {
70 0 : BBPreclaim(bn1);
71 0 : return GDK_FAIL;
72 : }
73 1943 : *r2p = bn2;
74 : }
75 2154 : *r1p = bn1;
76 2154 : return GDK_SUCCEED;
77 : }
78 :
79 5285 : bn1 = COLnew(0, TYPE_oid, ci1->ncand * ci2->ncand, TRANSIENT);
80 5274 : if (r2p)
81 4997 : bn2 = COLnew(0, TYPE_oid, ci1->ncand * ci2->ncand, TRANSIENT);
82 5268 : if (bn1 == NULL || (r2p && bn2 == NULL)) {
83 0 : BBPreclaim(bn1);
84 0 : BBPreclaim(bn2);
85 0 : return GDK_FAIL;
86 : }
87 5268 : if (ci1->ncand > 0 && ci2->ncand > 0) {
88 5266 : BATsetcount(bn1, ci1->ncand * ci2->ncand);
89 5279 : bn1->tsorted = true;
90 5279 : bn1->trevsorted = ci1->ncand <= 1;
91 5279 : bn1->tkey = ci2->ncand <= 1;
92 5279 : bn1->tnil = false;
93 5279 : bn1->tnonil = true;
94 5279 : p = (oid *) Tloc(bn1, 0);
95 263012 : for (i = 0; i < ci1->ncand; i++) {
96 257742 : GDK_CHECK_TIMEOUT_BODY(qry_ctx, GOTO_LABEL_TIMEOUT_HANDLER(bailout, qry_ctx));
97 257966 : oid x = canditer_next(ci1);
98 7911813 : for (j = 0; j < ci2->ncand; j++) {
99 7396114 : *p++ = x;
100 : }
101 : }
102 5270 : BATtseqbase(bn1, ci2->ncand == 1 ? *(oid *) Tloc(bn1, 0) : oid_nil);
103 :
104 5252 : if (bn2) {
105 4982 : BATsetcount(bn2, ci1->ncand * ci2->ncand);
106 4986 : bn2->tsorted = ci1->ncand <= 1 || ci2->ncand <= 1;
107 4986 : bn2->trevsorted = ci2->ncand <= 1;
108 4986 : bn2->tkey = ci1->ncand <= 1;
109 4986 : bn2->tnil = false;
110 4986 : bn2->tnonil = true;
111 4986 : p = (oid *) Tloc(bn2, 0);
112 224853 : for (i = 0; i < ci1->ncand; i++) {
113 219864 : GDK_CHECK_TIMEOUT_BODY(qry_ctx, GOTO_LABEL_TIMEOUT_HANDLER(bailout, qry_ctx));
114 2199996 : for (j = 0; j < ci2->ncand; j++) {
115 1979990 : *p++ = canditer_next(ci2);
116 : }
117 220006 : canditer_reset(ci2);
118 : }
119 4989 : BATtseqbase(bn2, ci1->ncand == 1 ? *(oid *) Tloc(bn2, 0) : oid_nil);
120 : }
121 : }
122 5255 : *r1p = bn1;
123 5255 : if (r2p)
124 4985 : *r2p = bn2;
125 5255 : if (r2p)
126 4985 : TRC_DEBUG(ALGO, "BATsubcross()=(" ALGOBATFMT "," ALGOBATFMT ")\n", ALGOBATPAR(bn1), ALGOBATPAR(bn2));
127 : else
128 270 : 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 46954 : BATsubcross(BAT **r1p, BAT **r2p, BAT *l, BAT *r, BAT *sl, BAT *sr, bool max_one)
139 : {
140 46954 : struct canditer ci1, ci2;
141 :
142 46954 : canditer_init(&ci1, l, sl);
143 46948 : canditer_init(&ci2, r, sr);
144 46975 : if (max_one && ci1.ncand > 0 && ci2.ncand > 1) {
145 78 : GDKerror("more than one match");
146 78 : return GDK_FAIL;
147 : }
148 46897 : 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 : }
|
