[XS] Change in asterixdb[master]: [ASTERIXDB-8192][STO] Fixed global theta for cardinal estimation

[AsterixDB Code Review <do...@asterix-gerrit.ics.uci.edu>]

From Ritik Raj <ri...@couchbase.com>:

Ritik Raj has uploaded this change for review. ( https://asterix-gerrit.ics.uci.edu/c/asterixdb/+/21793?usp=email )


Change subject: [ASTERIXDB-8192][STO] Fixed global theta for cardinal estimation
......................................................................

[ASTERIXDB-8192][STO] Fixed global theta for cardinal estimation

Details: The calculated global theta for the cardinality estimation for
a partition involves global theta (θ) where the samples having value
less then θ is only considered for the estimation, there was a gap in
the θ  calculation as it was not involving the delete samples, hence if
calculated θ using the insert samples is less than the actual θ_prime
calculated considering the delete samples, there won't any entry in
delete samples between 0 <= sample_theta <= θ_prime, then the entries in
the insert sample betweeen the range will be considered alive which
might have been dead.

The simple fix is to consider both the insert and delete samples for θ
calculation, this gives the correct population view of insert and delete
sampels for the cardinality estimation.

Change-Id: I3cb67354948bd3a9eca879953a4c58e45bb1647b
---
M hyracks-fullstack/hyracks/hyracks-storage-am-lsm-common/src/main/java/org/apache/hyracks/storage/am/lsm/common/theta/ThetaEstimator.java
1 file changed, 6 insertions(+), 2 deletions(-)



  git pull ssh://asterix-gerrit.ics.uci.edu:29418/asterixdb refs/changes/93/21793/1

diff --git a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-common/src/main/java/org/apache/hyracks/storage/am/lsm/common/theta/ThetaEstimator.java b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-common/src/main/java/org/apache/hyracks/storage/am/lsm/common/theta/ThetaEstimator.java
index e4172fb..72acb1a 100644
--- a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-common/src/main/java/org/apache/hyracks/storage/am/lsm/common/theta/ThetaEstimator.java
+++ b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-common/src/main/java/org/apache/hyracks/storage/am/lsm/common/theta/ThetaEstimator.java
@@ -41,10 +41,14 @@
         }
 
         public double getTheta() {
-            if (insertSamples.length < K) {
+            return Math.min(thetaOf(insertSamples), thetaOf(deleteSamples));
+        }
+
+        private double thetaOf(long[] samples) {
+            if (samples.length < K) {
                 return 1.0;
             }
-            return (double) insertSamples[insertSamples.length - 1] / (double) Long.MAX_VALUE;
+            return (double) samples[samples.length - 1] / (double) Long.MAX_VALUE;
         }
 
         public long estimateLiveCardinality() {

-- 
To view, visit https://asterix-gerrit.ics.uci.edu/c/asterixdb/+/21793?usp=email
To unsubscribe, or for help writing mail filters, visit https://asterix-gerrit.ics.uci.edu/settings?usp=email

Gerrit-MessageType: newchange
Gerrit-Project: asterixdb
Gerrit-Branch: master
Gerrit-Change-Id: I3cb67354948bd3a9eca879953a4c58e45bb1647b
Gerrit-Change-Number: 21793
Gerrit-PatchSet: 1
Gerrit-Owner: Ritik Raj <ri...@couchbase.com>