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       26567 : BATcrossci(BAT **r1p, BAT **r2p, struct canditer *ci1, struct canditer *ci2)
      24             : {
      25       26567 :         BAT *bn1, *bn2 = NULL;
      26       26567 :         oid *restrict p;
      27       26567 :         BUN i, j;
      28             : 
      29       26567 :         lng timeoffset = 0;
      30       26567 :         QryCtx *qry_ctx = MT_thread_get_qry_ctx();
      31       26567 :         if (qry_ctx != NULL) {
      32       26024 :                 timeoffset = (qry_ctx->starttime && qry_ctx->querytimeout) ? (qry_ctx->starttime + qry_ctx->querytimeout) : 0;
      33             :         }
      34             : 
      35             :         /* first some special cases */
      36       26567 :         if (ci1->ncand == 0 || ci2->ncand == 0) {
      37        9652 :                 if ((bn1 = BATdense(0, 0, 0)) == NULL)
      38             :                         return GDK_FAIL;
      39        9654 :                 if (r2p) {
      40        9145 :                         if ((bn2 = BATdense(0, 0, 0)) == NULL) {
      41           0 :                                 BBPreclaim(bn1);
      42           0 :                                 return GDK_FAIL;
      43             :                         }
      44        9144 :                         *r2p = bn2;
      45             :                 }
      46        9653 :                 *r1p = bn1;
      47        9653 :                 return GDK_SUCCEED;
      48             :         }
      49       16915 :         if (ci2->ncand == 1) {
      50       10498 :                 if ((bn1 = canditer_slice(ci1, 0, ci1->ncand)) == NULL)
      51             :                         return GDK_FAIL;
      52       10497 :                 if (r2p) {
      53       10063 :                         if (ci1->ncand == 1) {
      54        3150 :                                 bn2 = canditer_slice(ci2, 0, ci2->ncand);
      55             :                         } else {
      56        6913 :                                 bn2 = BATconstant(0, TYPE_oid, &ci2->seq, ci1->ncand, TRANSIENT);
      57             :                         }
      58       10064 :                         if (bn2 == NULL) {
      59           0 :                                 BBPreclaim(bn1);
      60           0 :                                 return GDK_FAIL;
      61             :                         }
      62       10064 :                         *r2p = bn2;
      63             :                 }
      64       10498 :                 *r1p = bn1;
      65       10498 :                 return GDK_SUCCEED;
      66             :         }
      67        6417 :         if (ci1->ncand == 1) {
      68        1618 :                 bn1 = BATconstant(0, TYPE_oid, &ci1->seq, ci2->ncand, TRANSIENT);
      69        1618 :                 if (bn1 == NULL)
      70             :                         return GDK_FAIL;
      71        1618 :                 if (r2p) {
      72        1490 :                         bn2 = canditer_slice(ci2, 0, ci2->ncand);
      73        1490 :                         if (bn2 == NULL) {
      74           0 :                                 BBPreclaim(bn1);
      75           0 :                                 return GDK_FAIL;
      76             :                         }
      77        1490 :                         *r2p = bn2;
      78             :                 }
      79        1618 :                 *r1p = bn1;
      80        1618 :                 return GDK_SUCCEED;
      81             :         }
      82             : 
      83        4799 :         bn1 = COLnew(0, TYPE_oid, ci1->ncand * ci2->ncand, TRANSIENT);
      84        4799 :         if (r2p)
      85        4496 :                 bn2 = COLnew(0, TYPE_oid, ci1->ncand * ci2->ncand, TRANSIENT);
      86        4798 :         if (bn1 == NULL || (r2p && bn2 == NULL)) {
      87           0 :                 BBPreclaim(bn1);
      88           0 :                 BBPreclaim(bn2);
      89           0 :                 return GDK_FAIL;
      90             :         }
      91        4798 :         if (ci1->ncand > 0 && ci2->ncand > 0) {
      92        4798 :                 BATsetcount(bn1, ci1->ncand * ci2->ncand);
      93        4797 :                 bn1->tsorted = true;
      94        4797 :                 bn1->trevsorted = ci1->ncand <= 1;
      95        4797 :                 bn1->tkey = ci2->ncand <= 1;
      96        4797 :                 bn1->tnil = false;
      97        4797 :                 bn1->tnonil = true;
      98        4797 :                 p = (oid *) Tloc(bn1, 0);
      99      277015 :                 for (i = 0; i < ci1->ncand; i++) {
     100      272216 :                         GDK_CHECK_TIMEOUT_BODY(timeoffset, GOTO_LABEL_TIMEOUT_HANDLER(bailout));
     101      272212 :                         oid x = canditer_next(ci1);
     102     8769367 :                         for (j = 0; j < ci2->ncand; j++) {
     103     8224937 :                                 *p++ = x;
     104             :                         }
     105             :                 }
     106        4799 :                 BATtseqbase(bn1, ci2->ncand == 1 ? *(oid *) Tloc(bn1, 0) : oid_nil);
     107             : 
     108        4799 :                 if (bn2) {
     109        4496 :                         BATsetcount(bn2, ci1->ncand * ci2->ncand);
     110        4496 :                         bn2->tsorted = ci1->ncand <= 1 || ci2->ncand <= 1;
     111        4496 :                         bn2->trevsorted = ci2->ncand <= 1;
     112        4496 :                         bn2->tkey = ci1->ncand <= 1;
     113        4496 :                         bn2->tnil = false;
     114        4496 :                         bn2->tnonil = true;
     115        4496 :                         p = (oid *) Tloc(bn2, 0);
     116      241297 :                         for (i = 0; i < ci1->ncand; i++) {
     117      236801 :                                 GDK_CHECK_TIMEOUT_BODY(timeoffset, GOTO_LABEL_TIMEOUT_HANDLER(bailout));
     118     2339580 :                                 for (j = 0; j < ci2->ncand; j++) {
     119     2102796 :                                         *p++ = canditer_next(ci2);
     120             :                                 }
     121      236784 :                                 canditer_reset(ci2);
     122             :                         }
     123        4496 :                         BATtseqbase(bn2, ci1->ncand == 1 ? *(oid *) Tloc(bn2, 0) : oid_nil);
     124             :                 }
     125             :         }
     126        4799 :         *r1p = bn1;
     127        4799 :         if (r2p)
     128        4496 :                 *r2p = bn2;
     129        4799 :         if (r2p)
     130        4496 :                 TRC_DEBUG(ALGO, "BATsubcross()=(" ALGOBATFMT "," ALGOBATFMT ")\n", ALGOBATPAR(bn1), ALGOBATPAR(bn2));
     131             :         else
     132         303 :                 TRC_DEBUG(ALGO, "BATsubcross()=(" ALGOBATFMT ")\n", ALGOBATPAR(bn1));
     133             :         return GDK_SUCCEED;
     134             : 
     135           0 :   bailout:
     136           0 :         BBPreclaim(bn1);
     137           0 :         BBPreclaim(bn2);
     138             :         return GDK_FAIL;
     139             : }
     140             : 
     141             : gdk_return
     142       26294 : BATsubcross(BAT **r1p, BAT **r2p, BAT *l, BAT *r, BAT *sl, BAT *sr, bool max_one)
     143             : {
     144       26294 :         struct canditer ci1, ci2;
     145             : 
     146       26294 :         canditer_init(&ci1, l, sl);
     147       26293 :         canditer_init(&ci2, r, sr);
     148       26292 :         if (max_one && ci1.ncand > 0 && ci2.ncand > 1) {
     149          76 :                 GDKerror("more than one match");
     150          76 :                 return GDK_FAIL;
     151             :         }
     152       26216 :         return BATcrossci(r1p, r2p, &ci1, &ci2);
     153             : }
     154             : 
     155             : /* [left] outer cross */
     156             : gdk_return
     157         396 : BAToutercross(BAT **r1p, BAT **r2p, BAT *l, BAT *r, BAT *sl, BAT *sr, bool max_one)
     158             : {
     159         396 :         struct canditer ci1, ci2;
     160             : 
     161         396 :         canditer_init(&ci1, l, sl);
     162         396 :         canditer_init(&ci2, r, sr);
     163         396 :         if (max_one && ci1.ncand > 0 && ci2.ncand > 1) {
     164           0 :                 GDKerror("more than one match");
     165           0 :                 return GDK_FAIL;
     166             :         }
     167             : 
     168         396 :         if (ci1.ncand == 0) {
     169          14 :                 BAT *bn = COLnew(0, TYPE_void, 0, TRANSIENT);
     170          14 :                 if (bn == NULL)
     171             :                         return GDK_FAIL;
     172          14 :                 BATtseqbase(bn, oid_nil);
     173          14 :                 *r1p = bn;
     174          14 :                 if (r2p) {
     175          14 :                         bn = COLnew(0, TYPE_void, 0, TRANSIENT);
     176          14 :                         if (bn == NULL) {
     177           0 :                                 BBPreclaim(*r1p);
     178           0 :                                 return GDK_FAIL;
     179             :                         }
     180          14 :                         BATtseqbase(bn, oid_nil);
     181          14 :                         *r2p = bn;
     182             :                 }
     183          14 :                 return GDK_SUCCEED;
     184             :         }
     185         382 :         if (ci2.ncand == 0) {
     186          31 :                 BAT *bn = canditer_slice(&ci1, 0, ci1.ncand);
     187          31 :                 if (bn == NULL)
     188             :                         return GDK_FAIL;
     189          31 :                 *r1p = bn;
     190          31 :                 if (r2p) {
     191          31 :                         BAT *bn = COLnew(0, TYPE_void, ci1.ncand, TRANSIENT);
     192          31 :                         if (bn == NULL)
     193             :                                 return GDK_FAIL;
     194          31 :                         BATtseqbase(bn, oid_nil);
     195          31 :                         BATsetcount(bn, ci1.ncand);
     196          31 :                         *r2p = bn;
     197             :                 }
     198          31 :                 return GDK_SUCCEED;
     199             :         }
     200         351 :         return BATcrossci(r1p, r2p, &ci1, &ci2);
     201             : }