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 27038 : BATcrossci(BAT **r1p, BAT **r2p, struct canditer *ci1, struct canditer *ci2)
24 : {
25 27038 : BAT *bn1, *bn2 = NULL;
26 27038 : oid *restrict p;
27 27038 : BUN i, j;
28 :
29 27038 : QryCtx *qry_ctx = MT_thread_get_qry_ctx();
30 :
31 : /* first some special cases */
32 27039 : if (ci1->ncand == 0 || ci2->ncand == 0) {
33 9751 : if ((bn1 = BATdense(0, 0, 0)) == NULL)
34 : return GDK_FAIL;
35 9746 : if (r2p) {
36 9233 : if ((bn2 = BATdense(0, 0, 0)) == NULL) {
37 0 : BBPreclaim(bn1);
38 0 : return GDK_FAIL;
39 : }
40 9236 : *r2p = bn2;
41 : }
42 9749 : *r1p = bn1;
43 9749 : return GDK_SUCCEED;
44 : }
45 17288 : if (ci2->ncand == 1) {
46 10919 : if ((bn1 = canditer_slice(ci1, 0, ci1->ncand)) == NULL)
47 : return GDK_FAIL;
48 10919 : if (r2p) {
49 10463 : if (ci1->ncand == 1) {
50 3490 : bn2 = canditer_slice(ci2, 0, ci2->ncand);
51 : } else {
52 6973 : bn2 = BATconstant(0, TYPE_oid, &ci2->seq, ci1->ncand, TRANSIENT);
53 : }
54 10464 : if (bn2 == NULL) {
55 0 : BBPreclaim(bn1);
56 0 : return GDK_FAIL;
57 : }
58 10464 : *r2p = bn2;
59 : }
60 10920 : *r1p = bn1;
61 10920 : return GDK_SUCCEED;
62 : }
63 6369 : if (ci1->ncand == 1) {
64 1627 : bn1 = BATconstant(0, TYPE_oid, &ci1->seq, ci2->ncand, TRANSIENT);
65 1627 : if (bn1 == NULL)
66 : return GDK_FAIL;
67 1627 : if (r2p) {
68 1499 : bn2 = canditer_slice(ci2, 0, ci2->ncand);
69 1499 : if (bn2 == NULL) {
70 0 : BBPreclaim(bn1);
71 0 : return GDK_FAIL;
72 : }
73 1499 : *r2p = bn2;
74 : }
75 1627 : *r1p = bn1;
76 1627 : return GDK_SUCCEED;
77 : }
78 :
79 4742 : bn1 = COLnew(0, TYPE_oid, ci1->ncand * ci2->ncand, TRANSIENT);
80 4740 : if (r2p)
81 4455 : bn2 = COLnew(0, TYPE_oid, ci1->ncand * ci2->ncand, TRANSIENT);
82 4742 : if (bn1 == NULL || (r2p && bn2 == NULL)) {
83 0 : BBPreclaim(bn1);
84 0 : BBPreclaim(bn2);
85 0 : return GDK_FAIL;
86 : }
87 4742 : if (ci1->ncand > 0 && ci2->ncand > 0) {
88 4742 : BATsetcount(bn1, ci1->ncand * ci2->ncand);
89 4742 : bn1->tsorted = true;
90 4742 : bn1->trevsorted = ci1->ncand <= 1;
91 4742 : bn1->tkey = ci2->ncand <= 1;
92 4742 : bn1->tnil = false;
93 4742 : bn1->tnonil = true;
94 4742 : p = (oid *) Tloc(bn1, 0);
95 278640 : for (i = 0; i < ci1->ncand; i++) {
96 273898 : GDK_CHECK_TIMEOUT_BODY(qry_ctx, GOTO_LABEL_TIMEOUT_HANDLER(bailout, qry_ctx));
97 273929 : oid x = canditer_next(ci1);
98 8734044 : for (j = 0; j < ci2->ncand; j++) {
99 8186217 : *p++ = x;
100 : }
101 : }
102 4742 : BATtseqbase(bn1, ci2->ncand == 1 ? *(oid *) Tloc(bn1, 0) : oid_nil);
103 :
104 4742 : if (bn2) {
105 4457 : BATsetcount(bn2, ci1->ncand * ci2->ncand);
106 4457 : bn2->tsorted = ci1->ncand <= 1 || ci2->ncand <= 1;
107 4457 : bn2->trevsorted = ci2->ncand <= 1;
108 4457 : bn2->tkey = ci1->ncand <= 1;
109 4457 : bn2->tnil = false;
110 4457 : bn2->tnonil = true;
111 4457 : p = (oid *) Tloc(bn2, 0);
112 244089 : for (i = 0; i < ci1->ncand; i++) {
113 239632 : GDK_CHECK_TIMEOUT_BODY(qry_ctx, GOTO_LABEL_TIMEOUT_HANDLER(bailout, qry_ctx));
114 2297336 : for (j = 0; j < ci2->ncand; j++) {
115 2057859 : *p++ = canditer_next(ci2);
116 : }
117 239477 : canditer_reset(ci2);
118 : }
119 4457 : BATtseqbase(bn2, ci1->ncand == 1 ? *(oid *) Tloc(bn2, 0) : oid_nil);
120 : }
121 : }
122 4742 : *r1p = bn1;
123 4742 : if (r2p)
124 4457 : *r2p = bn2;
125 4742 : if (r2p)
126 4457 : TRC_DEBUG(ALGO, "BATsubcross()=(" ALGOBATFMT "," ALGOBATFMT ")\n", ALGOBATPAR(bn1), ALGOBATPAR(bn2));
127 : else
128 285 : TRC_DEBUG(ALGO, "BATsubcross()=(" ALGOBATFMT ")\n", ALGOBATPAR(bn1));
129 : return GDK_SUCCEED;
130 :
131 0 : bailout:
132 0 : BBPreclaim(bn1);
133 0 : BBPreclaim(bn2);
134 : return GDK_FAIL;
135 : }
136 :
137 : gdk_return
138 26753 : BATsubcross(BAT **r1p, BAT **r2p, BAT *l, BAT *r, BAT *sl, BAT *sr, bool max_one)
139 : {
140 26753 : struct canditer ci1, ci2;
141 :
142 26753 : canditer_init(&ci1, l, sl);
143 26751 : canditer_init(&ci2, r, sr);
144 26750 : if (max_one && ci1.ncand > 0 && ci2.ncand > 1) {
145 78 : GDKerror("more than one match");
146 78 : return GDK_FAIL;
147 : }
148 26672 : 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 : }
|
