Find actual data area inside the main-range...
and trim all ranges to match this actual data area. Don't do
this optimization for COUNTIFS where there is no main-range.
This optimization is also turned off if any of the parameter
ranges are not double-refs.
Benefits in cases like -
=SUMIFS(A:A, B:B, ">=20", C:C, "<=10") and the is data only
in say A1:A10000 and rest are empty. Range trimming in this
case saves lot of execution time and memory (for vConditions
and vRefArrayConditions).
Change-Id: I6b4ad91e23f89dc48603b98000bcef4dbdb03112
Reviewed-on: https://gerrit.libreoffice.org/64657
Tested-by: Jenkins
Reviewed-by: Eike Rathke <erack@redhat.com>
(cherry picked from commit cb52b112c0d44d7a6849f773fd1ee4e863ab91da)
Reviewed-on: https://gerrit.libreoffice.org/64833
Reviewed-by: Dennis Francis <dennis.francis@collabora.com>
diff --git a/sc/inc/column.hxx b/sc/inc/column.hxx
index 0a328f0..b1e890a6 100644
--- a/sc/inc/column.hxx
+++ b/sc/inc/column.hxx
@@ -222,6 +222,7 @@ public:
bool bConsiderCellDrawObjects=false ) const;
bool GetPrevDataPos(SCROW& rRow) const;
bool GetNextDataPos(SCROW& rRow) const;
bool TrimEmptyBlocks(SCROW& rRowStart, SCROW& rRowEnd) const;
void FindDataAreaPos(SCROW& rRow, bool bDown) const; // (without Broadcaster)
void FindUsed( SCROW nStartRow, SCROW nEndRow, mdds::flat_segment_tree<SCROW, bool>& rUsed ) const;
diff --git a/sc/inc/document.hxx b/sc/inc/document.hxx
index 04ff9a0..31278f8 100644
--- a/sc/inc/document.hxx
+++ b/sc/inc/document.hxx
@@ -1385,6 +1385,15 @@ public:
SCCOL& rEndCol, SCROW& rEndRow,
bool bIncludeOld, bool bOnlyDown ) const;
/**
* Returns true if there is a non-empty subrange in the range given as input.
* In that case it also modifies rRange to largest subrange that does not
* have empty col/row inrange-segments in the beginning/end.
* It returns false if rRange is completely empty and in this case rRange is
* left unmodified.
*/
bool GetDataAreaSubrange(ScRange& rRange) const;
SC_DLLPUBLIC bool GetCellArea( SCTAB nTab, SCCOL& rEndCol, SCROW& rEndRow ) const;
SC_DLLPUBLIC bool GetTableArea( SCTAB nTab, SCCOL& rEndCol, SCROW& rEndRow ) const;
SC_DLLPUBLIC bool GetPrintArea( SCTAB nTab, SCCOL& rEndCol, SCROW& rEndRow,
diff --git a/sc/inc/table.hxx b/sc/inc/table.hxx
index aae436e..e804a1c 100644
--- a/sc/inc/table.hxx
+++ b/sc/inc/table.hxx
@@ -576,6 +576,8 @@ public:
void GetDataArea( SCCOL& rStartCol, SCROW& rStartRow, SCCOL& rEndCol, SCROW& rEndRow,
bool bIncludeOld, bool bOnlyDown ) const;
bool GetDataAreaSubrange( ScRange& rRange ) const;
bool ShrinkToUsedDataArea( bool& o_bShrunk, SCCOL& rStartCol, SCROW& rStartRow,
SCCOL& rEndCol, SCROW& rEndRow, bool bColumnsOnly,
bool bStickyTopRow, bool bStickyLeftCol, bool bConsiderCellNotes,
diff --git a/sc/source/core/data/column2.cxx b/sc/source/core/data/column2.cxx
index d2e81de..c46f1a70 100644
--- a/sc/source/core/data/column2.cxx
+++ b/sc/source/core/data/column2.cxx
@@ -1405,6 +1405,52 @@ bool ScColumn::GetNextDataPos(SCROW& rRow) const // greater than rRow
return true;
}
bool ScColumn::TrimEmptyBlocks(SCROW& rRowStart, SCROW& rRowEnd) const
{
assert(rRowStart <= rRowEnd);
SCROW nRowStartNew = rRowStart, nRowEndNew = rRowEnd;
// Trim down rRowStart first
std::pair<sc::CellStoreType::const_iterator,size_t> aPos = maCells.position(rRowStart);
sc::CellStoreType::const_iterator it = aPos.first;
if (it == maCells.end())
return false;
if (it->type == sc::element_type_empty)
{
// This block is empty. Skip ahead to the next block (if exists).
nRowStartNew += it->size - aPos.second;
if (nRowStartNew > rRowEnd)
return false;
++it;
if (it == maCells.end())
// No more next block.
return false;
}
// Trim up rRowEnd next
aPos = maCells.position(rRowEnd);
it = aPos.first;
if (it == maCells.end())
{
rRowStart = nRowStartNew;
return true; // Because trimming of rRowStart is ok
}
if (it->type == sc::element_type_empty)
{
// rRowEnd cannot be in the first block which is empty !
assert(it != maCells.begin());
// This block is empty. Skip to the previous block (it exists).
nRowEndNew -= aPos.second + 1; // Last row position of the previous block.
assert(nRowStartNew <= nRowEndNew);
}
rRowStart = nRowStartNew;
rRowEnd = nRowEndNew;
return true;
}
SCROW ScColumn::FindNextVisibleRow(SCROW nRow, bool bForward) const
{
if(bForward)
diff --git a/sc/source/core/data/document.cxx b/sc/source/core/data/document.cxx
index 9693edf..dbba8a2 100644
--- a/sc/source/core/data/document.cxx
+++ b/sc/source/core/data/document.cxx
@@ -1098,6 +1098,18 @@ void ScDocument::GetDataArea( SCTAB nTab, SCCOL& rStartCol, SCROW& rStartRow,
maTabs[nTab]->GetDataArea( rStartCol, rStartRow, rEndCol, rEndRow, bIncludeOld, bOnlyDown );
}
bool ScDocument::GetDataAreaSubrange(ScRange& rRange) const
{
SCTAB nTab = rRange.aStart.Tab();
if (nTab != rRange.aEnd.Tab())
return true;
if (ValidTab(nTab) && nTab < static_cast<SCTAB> (maTabs.size()) && maTabs[nTab])
return maTabs[nTab]->GetDataAreaSubrange(rRange);
return true;
}
void ScDocument::LimitChartArea( SCTAB nTab, SCCOL& rStartCol, SCROW& rStartRow,
SCCOL& rEndCol, SCROW& rEndRow )
{
diff --git a/sc/source/core/data/table1.cxx b/sc/source/core/data/table1.cxx
index ede4096..cef0563 100644
--- a/sc/source/core/data/table1.cxx
+++ b/sc/source/core/data/table1.cxx
@@ -904,6 +904,47 @@ void ScTable::GetDataArea( SCCOL& rStartCol, SCROW& rStartRow, SCCOL& rEndCol, S
}
}
bool ScTable::GetDataAreaSubrange( ScRange& rRange ) const
{
SCCOL nCol1 = rRange.aStart.Col(), nCol2 = rRange.aEnd.Col();
if ( nCol1 >= aCol.size() )
return false;
nCol2 = std::min<SCCOL>( nCol2, aCol.size()-1 );
SCROW nRow1 = rRange.aStart.Row(), nRow2 = rRange.aEnd.Row();
SCCOL nFirstNonEmptyCol = -1, nLastNonEmptyCol = -1;
SCROW nRowStart = nRow2, nRowEnd = nRow1;
for ( SCCOL nCol = nCol1; nCol <= nCol2; ++nCol )
{
SCROW nRowStartThis = nRow1, nRowEndThis = nRow2;
bool bTrimmed = aCol[nCol].TrimEmptyBlocks(nRowStartThis, nRowEndThis);
if ( bTrimmed )
{
if ( nFirstNonEmptyCol == -1 )
nFirstNonEmptyCol = nCol;
nLastNonEmptyCol = nCol;
nRowStart = std::min<SCROW>(nRowStart, nRowStartThis);
nRowEnd = std::max<SCROW>(nRowEnd, nRowEndThis);
}
}
if ( nFirstNonEmptyCol == -1 )
return false;
assert(nFirstNonEmptyCol <= nLastNonEmptyCol);
assert(nRowStart <= nRowEnd);
rRange.aStart.Set(nFirstNonEmptyCol, nRowStart, rRange.aStart.Tab());
rRange.aEnd.Set(nLastNonEmptyCol, nRowEnd, rRange.aEnd.Tab());
return true;
}
bool ScTable::ShrinkToUsedDataArea( bool& o_bShrunk, SCCOL& rStartCol, SCROW& rStartRow,
SCCOL& rEndCol, SCROW& rEndRow, bool bColumnsOnly, bool bStickyTopRow, bool bStickyLeftCol,
bool bConsiderCellNotes, bool bConsiderCellDrawObjects ) const
diff --git a/sc/source/core/tool/interpr1.cxx b/sc/source/core/tool/interpr1.cxx
index 9476c64..d7279c1 100644
--- a/sc/source/core/tool/interpr1.cxx
+++ b/sc/source/core/tool/interpr1.cxx
@@ -5842,6 +5842,55 @@ void ScInterpreter::IterateParametersIfs( double(*ResultFunc)( const sc::ParamIf
// with a single InterpretTail() call it results in evaluation of all the cells in the
// matrix formula.
vConditions.clear();
SCCOL nStartColDiff = 0;
SCCOL nEndColDiff = 0;
SCROW nStartRowDiff = 0;
SCROW nEndRowDiff = 0;
bool bRangeReduce = false;
// Range-reduce optimization
if (nParamCount % 2) // Not COUNTIFS
{
bool bHasDoubleRefCriteriaRanges = true;
// Do not attempt main-range reduce if any of the criteria-ranges are not double-refs.
for (sal_uInt16 nParamIdx = 2; nParamIdx < nParamCount; nParamIdx += 2 )
{
const formula::FormulaToken* pCriteriaRangeToken = pStack[ sp-nParamIdx ];
if (pCriteriaRangeToken->GetType() != svDoubleRef )
{
bHasDoubleRefCriteriaRanges = false;
break;
}
}
// Probe the main range token, and try if we can shrink the range without altering results.
const formula::FormulaToken* pMainRangeToken = pStack[ sp-nParamCount ];
if (pMainRangeToken->GetType() == svDoubleRef && bHasDoubleRefCriteriaRanges)
{
const ScComplexRefData* pRefData = pMainRangeToken->GetDoubleRef();
if (!pRefData->IsDeleted())
{
ScRange aMainRange, aSubRange;
DoubleRefToRange( *pRefData, aMainRange);
if (aMainRange.aStart.Tab() == aMainRange.aEnd.Tab())
{
// Shrink the range to actual data content.
aSubRange = aMainRange;
pDok->GetDataAreaSubrange(aSubRange);
nStartColDiff = aSubRange.aStart.Col() - aMainRange.aStart.Col();
nStartRowDiff = aSubRange.aStart.Row() - aMainRange.aStart.Row();
nEndColDiff = aSubRange.aEnd.Col() - aMainRange.aEnd.Col();
nEndRowDiff = aSubRange.aEnd.Row() - aMainRange.aEnd.Row();
bRangeReduce = nStartColDiff || nStartRowDiff || nEndColDiff || nEndRowDiff;
}
}
}
}
double fVal = 0.0;
SCCOL nDimensionCols = 0;
SCROW nDimensionRows = 0;
@@ -6024,6 +6073,15 @@ void ScInterpreter::IterateParametersIfs( double(*ResultFunc)( const sc::ParamIf
return;
}
if (bRangeReduce)
{
nCol1 += nStartColDiff;
nRow1 += nStartRowDiff;
nCol2 += nEndColDiff;
nRow2 += nEndRowDiff;
}
// All reference ranges must be of same dimension and size.
if (!nDimensionCols)
nDimensionCols = nCol2 - nCol1 + 1;
@@ -6262,6 +6320,15 @@ void ScInterpreter::IterateParametersIfs( double(*ResultFunc)( const sc::ParamIf
return;
}
if (bRangeReduce)
{
nMainCol1 += nStartColDiff;
nMainRow1 += nStartRowDiff;
nMainCol2 += nEndColDiff;
nMainRow2 += nEndRowDiff;
}
// All reference ranges must be of same dimension and size.
if ((nDimensionCols != (nMainCol2 - nMainCol1 + 1)) || (nDimensionRows != (nMainRow2 - nMainRow1 + 1)))
{
