SQLite

**
** The LogEst can be negative to indicate fractional values.
** Examples:
**
**    0.5 -> -10           0.1 -> -33        0.0625 -> -40
*/
typedef INT16_TYPE LogEst;
#define LOGEST_MIN (-32768)
#define LOGEST_MAX (32767)

/*
** Set the SQLITE_PTRSIZE macro to the number of bytes in a pointer
*/
#ifndef SQLITE_PTRSIZE
# if defined(__SIZEOF_POINTER__)
#   define SQLITE_PTRSIZE __SIZEOF_POINTER__

**
**     18    for star queries
**     12    otherwise
**
** For the purposes of this heuristic, a star-query is defined as a query
** with a large central table that is joined using an INNER JOIN,
** not CROSS or OUTER JOINs, against four or more smaller tables.
** The central table is called the "fact" table.  The smaller tables
** that get joined are "dimension tables".  Also, any table that is
** self-joined cannot be a dimension table; we assume that dimension
** tables may only be joined against fact tables.
**
** SIDE EFFECT:  (and really the whole point of this subroutine)
**
** If pWInfo describes a star-query, then the cost for SCANs of dimension
** WhereLoops is increased to be slightly larger than the cost of a SCAN
** in the fact table.  Only SCAN costs are increased.  SEARCH costs are
** unchanged. This heuristic helps keep fact tables in outer loops. Without
** this heuristic, paths with fact tables in outer loops tend to get pruned
** by the mxChoice limit on the number of paths, resulting in poor query
** plans.  See the starschema1.test test module for examples of queries
** that need this heuristic to find good query plans.

**
** This heuristic can be completely disabled, so that no query is
** considered a star-query, using SQLITE_TESTCTRL_OPTIMIZATION to
** disable the SQLITE_StarQuery optimization.  In the CLI, the command
** to do that is:  ".testctrl opt -starquery".
**
** HISTORICAL NOTES:
**
** This optimization was first added on 2024-05-09 by check-in 38db9b5c83d.
** The original optimization reduced the cost and output size estimate for
** fact tables to help them move to outer loops.  But months later (as people
** started upgrading) performance regression reports started caming in,
** including:
**
**    forum post b18ef983e68d06d1 (2024-12-21)
**    forum post 0025389d0860af82 (2025-01-14)
**    forum post d87570a145599033 (2025-01-17)
**
** To address these, the criteria for a star-query was tightened to exclude
** cases where the fact and dimensions are separated by an outer join, and
** the affect of star-schema detection was changed to increase the rRun cost
** on just full table scans of dimension tables, rather than reducing costs
** in the all access methods of the fact table.
*/
static int computeMxChoice(WhereInfo *pWInfo){
  int nLoop = pWInfo->nLevel;    /* Number of terms in the join */
  WhereLoop *pWLoop;             /* For looping over WhereLoops */

#ifdef SQLITE_DEBUG
  /* The star-query detection code below makes use of the following
  ** properties of the WhereLoop list, so verify them before
  ** continuing:
  **    (1)  .maskSelf is the bitmask corresponding to .iTab
  **    (2)  The WhereLoop list is in ascending .iTab order
  */
  for(pWLoop=pWInfo->pLoops; pWLoop; pWLoop=pWLoop->pNextLoop){
    assert( pWLoop->maskSelf==MASKBIT(pWLoop->iTab) );
    assert( pWLoop->pNextLoop==0 || pWLoop->iTab<=pWLoop->pNextLoop->iTab );

    int iFromIdx;          /* Term of FROM clause is the candidate fact-table */
    Bitmask m;             /* Bitmask for candidate fact-table */
    Bitmask mSelfJoin = 0; /* Tables that cannot be dimension tables */       
    WhereLoop *pStart;     /* Where to start searching for dimension-tables */

    pWInfo->bStarDone = 1; /* Only do this computation once */

    /* Check to see if we are dealing with a star schema and if so, adjust
    ** SCAN cost of dimensino tables so that they are as large as the SCAN
    ** cost of the fact table.  This is a heuristic that helps keep the
    ** fact tables in outer loops.
    */
    assert( !pWInfo->bStarUsed );
    aFromTabs = pWInfo->pTabList->a;
    pStart = pWInfo->pLoops;
    for(iFromIdx=0, m=1; iFromIdx<nLoop; iFromIdx++, m<<=1){
      int nDep = 0;             /* Number of dimension tables */
      LogEst mxRun;             /* Maximum SCAN cost of a fact table */

          }else{
            nDep++;
            mSeen |= pWLoop->maskSelf;
          }
        }
      }
      if( nDep<=3 ) continue;
      /* If we reach this point, it means that pFactTab is a fact table */






     
#ifdef WHERETRACE_ENABLED
      /* Make sure rStarDelta values are initialized */
      if( !pWInfo->bStarUsed ){
        for(pWLoop=pWInfo->pLoops; pWLoop; pWLoop=pWLoop->pNextLoop){
          pWLoop->rStarDelta = 0;
        }
      }
#endif
      pWInfo->bStarUsed = 1;

      /* Compute one more than the maximum cost of any WhereLoop for the
      ** fact table */
      mxRun = LOGEST_MIN;
      for(pWLoop=pStart; pWLoop; pWLoop=pWLoop->pNextLoop){
        if( pWLoop->iTab<iFromIdx ) continue;
        if( pWLoop->iTab>iFromIdx ) break;
        if( pWLoop->rRun>mxRun ) mxRun = pWLoop->rRun;
      }
      if( ALWAYS(mxRun<LOGEST_MAX) ) mxRun++;

      /* Increase the cost of table scans for dimension tables to be slightly
      ** more than the maximum cost of fact table */
      for(pWLoop=pStart; pWLoop; pWLoop=pWLoop->pNextLoop){
        if( (pWLoop->maskSelf & mSeen)==0 ) continue;
        if( pWLoop->nLTerm ) continue;
        if( pWLoop->rRun<mxRun ){
#ifdef WHERETRACE_ENABLED /* 0x80000 */
          if( sqlite3WhereTrace & 0x80000 ){
            SrcItem *pDim = aFromTabs + pWLoop->iTab;
            sqlite3DebugPrintf(
              "Increase SCAN cost of dimension %s(%d) of fact %s(%d) to %d\n",
              pDim->zAlias ? pDim->zAlias: pDim->pSTab->zName, pWLoop->iTab,
              pFactTab->zAlias ? pFactTab->zAlias : pFactTab->pSTab->zName,
              iFromIdx, mxRun
            );
          }
          pWLoop->rStarDelta = mxRun - pWLoop->rRun;
#endif /* WHERETRACE_ENABLED */

          pWLoop->rRun = mxRun;
        }
      }
    }
#ifdef WHERETRACE_ENABLED /* 0x80000 */
    if( (sqlite3WhereTrace & 0x80000)!=0 && pWInfo->bStarUsed ){
      sqlite3DebugPrintf("WhereLoops changed by star-query heuristic:\n");
      for(pWLoop=pWInfo->pLoops; pWLoop; pWLoop=pWLoop->pNextLoop){

  } u;
  u32 wsFlags;          /* WHERE_* flags describing the plan */
  u16 nLTerm;           /* Number of entries in aLTerm[] */
  u16 nSkip;            /* Number of NULL aLTerm[] entries */
  /**** whereLoopXfer() copies fields above ***********************/
# define WHERE_LOOP_XFER_SZ offsetof(WhereLoop,nLSlot)
  u16 nLSlot;           /* Number of slots allocated for aLTerm[] */
#ifdef WHERETRACE_ENABLED
  LogEst rStarDelta;    /* Cost delta due to star-schema heuristic.  Not
                        ** initialized unless pWInfo->bStarUsed */
#endif
  WhereTerm **aLTerm;   /* WhereTerms used */
  WhereLoop *pNextLoop; /* Next WhereLoop object in the WhereClause */
  WhereTerm *aLTermSpace[3];  /* Initial aLTerm[] space */
};

/* This object holds the prerequisites and the cost of running a
** subquery on one operand of an OR operator in the WHERE clause.

  u8 nLevel;                /* Number of nested loop */
  i8 nOBSat;                /* Number of ORDER BY terms satisfied by indices */
  u8 eOnePass;              /* ONEPASS_OFF, or _SINGLE, or _MULTI */
  u8 eDistinct;             /* One of the WHERE_DISTINCT_* values */
  unsigned bDeferredSeek :1;   /* Uses OP_DeferredSeek */
  unsigned untestedTerms :1;   /* Not all WHERE terms resolved by outer loop */
  unsigned bOrderedInnerLoop:1;/* True if only the inner-most loop is ordered */
  unsigned sorted        :1;   /* True if really sorted (not just grouped) */
  unsigned bStarDone     :1;   /* True if check for star-query is complete */
  unsigned bStarUsed     :1;   /* True if star-query heuristic is used */
  LogEst nRowOut;           /* Estimated number of output rows */
#ifdef WHERETRACE_ENABLED
  LogEst rTotalCost;        /* Total cost of the solution */
#endif
  int iTop;                 /* The very beginning of the WHERE loop */
  int iEndWhere;            /* End of the WHERE clause itself */
  WhereLoop *pLoops;        /* List of all WhereLoop objects */

# 2024-05-28
#
# The author disclaims copyright to this source code.  In place of
# a legal notice, here is a blessing:
#
#    May you do good and not evil.
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# 
# Test cases for the ability of the query planner to cope with
# star-schema queries.
#

set testdir [file dirname $argv0]
source $testdir/tester.tcl
set ::testprefix starschema1

do_execsql_test 1.1 {