<commit_before>/*
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package org.apache.kylin.cube.cuboid;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.concurrent.ConcurrentHashMap;

import org.apache.kylin.common.util.Bytes;
import org.apache.kylin.cube.model.CubeDesc;
import org.apache.kylin.cube.model.RowKeyColDesc;
import org.apache.kylin.cube.model.RowKeyDesc;
import org.apache.kylin.cube.model.RowKeyDesc.AggrGroupMask;
import org.apache.kylin.cube.model.RowKeyDesc.HierarchyMask;
import org.apache.kylin.metadata.model.TblColRef;

/**
 * @author <NAME> (ysong1)
 */
public class Cuboid implements Comparable<Cuboid> {

    private final static Map<String, Map<Long, Cuboid>> CUBOID_CACHE = new ConcurrentHashMap<String, Map<Long, Cuboid>>();

    public static Cuboid findById(CubeDesc cube, byte[] cuboidID) {
        return findById(cube, Bytes.toLong(cuboidID));
    }

    public static Cuboid findById(CubeDesc cube, long cuboidID) {
        Map<Long, Cuboid> cubeCache = CUBOID_CACHE.get(cube.getName());
        if (cubeCache == null) {
            cubeCache = new ConcurrentHashMap<Long, Cuboid>();
            CUBOID_CACHE.put(cube.getName(), cubeCache);
        }
        Cuboid cuboid = cubeCache.get(cuboidID);
        if (cuboid == null) {
            long validCuboidID = translateToValidCuboid(cube, cuboidID);
            cuboid = new Cuboid(cube, cuboidID, validCuboidID);
            cubeCache.put(cuboidID, cuboid);
        }
        return cuboid;

    }

    public static boolean isValid(CubeDesc cube, long cuboidID) {
        RowKeyDesc rowkey = cube.getRowkey();

        if (cuboidID < 0) {
            throw new IllegalArgumentException("Cuboid " + cuboidID + " should be greater than 0");
        }

        if (checkBaseCuboid(rowkey, cuboidID)) {
            return true;
        }

        if (checkMandatoryColumns(rowkey, cuboidID) == false) {
            return false;
        }

        if (checkAggregationGroup(rowkey, cuboidID) == false) {
            return false;
        }

        if (checkHierarchy(rowkey, cuboidID) == false) {
            return false;
        }

        return true;
    }

    public static long getBaseCuboidId(CubeDesc cube) {
        return cube.getRowkey().getFullMask();
    }

    // Breadth-First-Search
    private static long translateToValidCuboid(CubeDesc cube, long cuboidID) {
        if (Cuboid.isValid(cube, cuboidID)) {
            return cuboidID;
        }

        HashSet<Long> dedupped = new HashSet<Long>();
        Queue<Long> queue = new LinkedList<Long>();
        List<Long> parents = Cuboid.getAllPossibleParents(cube, cuboidID);

        // check each parent
        addToQueue(queue, parents, dedupped);
        while (queue.size() > 0) {
            long parent = pollFromQueue(queue, dedupped);
            if (Cuboid.isValid(cube, parent)) {
                return parent;
            } else {
                addToQueue(queue, Cuboid.getAllPossibleParents(cube, parent), dedupped);
            }
        }
        return -1;
    }

    private static List<Long> getAllPossibleParents(CubeDesc cube, long cuboidID) {
        List<Long> allPossibleParents = new ArrayList<Long>();

        for (int i = 0; i < cube.getRowkey().getRowKeyColumns().length; i++) {
            long mask = 1L << i;<commit_msg>KYLIN-1048 fix CPU and memory killer in Cuboid.findById()<commit_after>/*
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package org.apache.kylin.cube.cuboid;

import org.apache.kylin.common.util.Bytes;
import org.apache.kylin.cube.model.*;
import org.apache.kylin.cube.model.RowKeyDesc.AggrGroupMask;
import org.apache.kylin.cube.model.RowKeyDesc.HierarchyMask;
import org.apache.kylin.metadata.model.TblColRef;

import java.util.*;
import java.util.concurrent.ConcurrentHashMap;

/**
 * @author <NAME> (ysong1)
 */
public class Cuboid implements Comparable<Cuboid> {

    private final static Map<String, Map<Long, Cuboid>> CUBOID_CACHE = new ConcurrentHashMap<String, Map<Long, Cuboid>>();

    public static Cuboid findById(CubeDesc cube, byte[] cuboidID) {
        return findById(cube, Bytes.toLong(cuboidID));
    }

    public static Cuboid findById(CubeDesc cube, long cuboidID) {
        Map<Long, Cuboid> cubeCache = CUBOID_CACHE.get(cube.getName());
        if (cubeCache == null) {
            cubeCache = new ConcurrentHashMap<Long, Cuboid>();
            CUBOID_CACHE.put(cube.getName(), cubeCache);
        }
        Cuboid cuboid = cubeCache.get(cuboidID);
        if (cuboid == null) {
            long validCuboidID = translateToValidCuboid(cube, cuboidID);
            if (Cuboid.isValid(cube, validCuboidID) == false) {
                throw new RuntimeException("Didn't find a valid cuboid: " + validCuboidID);
            }

            cuboid = new Cuboid(cube, cuboidID, validCuboidID);
            cubeCache.put(cuboidID, cuboid);
        }
        return cuboid;

    }

    public static boolean isValid(CubeDesc cube, long cuboidID) {
        RowKeyDesc rowkey = cube.getRowkey();

        if (cuboidID < 0) {
            throw new IllegalArgumentException("Cuboid " + cuboidID + " should be greater than 0");
        }

        if (checkBaseCuboid(rowkey, cuboidID)) {
            return true;
        }

        if (checkMandatoryColumns(rowkey, cuboidID) == false) {
            return false;
        }

        if (checkAggregationGroup(rowkey, cuboidID) == false) {
            return false;
        }

        if (checkHierarchy(rowkey, cuboidID) == false) {
            return false;
        }

        return true;
    }

    public static long getBaseCuboidId(CubeDesc cube) {
        return cube.getRowkey().getFullMask();
    }

    private static long translateToValidCuboid(CubeDesc cubeDesc, long cuboidID) {
        // add mandantory
        RowKeyDesc rowkey = cubeDesc.getRowkey();
        long mandatoryColumnMask = rowkey.getMandatoryColumnMask();
        if (cuboidID < mandatoryColumnMask) {
            cuboidID = cuboidID | mandatoryColumnMask;
        }

        // add hierarchy
        for (DimensionDesc dimension : cubeDesc.getDimensions()) {
            HierarchyDesc[] hierarchies = dimension.getHierarchy();
            boolean found = false;
            long result = 0;
            if (hierarchies != null && hierarchies.length > 0) {
                for (int i = hierarchies.length - 1; i >= 0; i--) {
                    TblColRef hColumn = hierarchies[i].getColumnRef();
                    Integer index = rowkey.getColumnBitIndex(hColumn);
                    long bit = 1L << index;

                    if ((rowkey.getTailMask() & bit) > 0)
                        continue; // ignore levels in tail, they don't participate

                    if ((bit & cuboidID) > 0) {
                        found = true;
                    }

                    if (found == true) {
                        result = result | bit;
                    }
                }
                cuboidID = cuboidID | result;
            }
        }

        // find the left-most aggregation group
        long cuboidWithoutMandatory = cuboidID & ~rowkey.getMandatoryColumnMask();
        long leftover;
        for (AggrGroupMask mask : rowkey.getAggrGroupMasks()) {
            if ((cuboidWithoutMandatory & mask.uniqueMask) == mask.uniqueMask) {
                leftover = cuboidWithoutMandatory & ~mask.groupMask;

                if (leftover == 0) {
                    return cuboidID;
                }

                if (leftover != 0) {
                    cuboidID = cuboidID | mask.leftoverMask;
                    return cuboidID;
                }
            }
        }

        // doesn't have column in aggregation groups
        leftover = cuboidWithoutMandatory & rowkey.getTailMask();
        if (leftover == 0) {
            // doesn't have column in tail group
            if (cuboidWithoutMandatory != 0) {
                return cuboidID;
            } else {
                // no column (except mandatory), add one column
                long toAddCol = (1 << (BitSet.valueOf(new long[] { rowkey.getTailMask() }).cardinality()));
                // check if the toAddCol belongs to any hierarchy
                List<HierarchyMask> hierarchyMaskList = rowkey.getHierarchyMasks();
                if (hierarchyMaskList != null && hierarchyMaskList.size() > 0) {
                    for (HierarchyMask hierarchyMasks : hierarchyMaskList) {
                        long result = toAddCol & hierarchyMasks.fullMask;
                        if (result > 0) {
                            // replace it with the root col in hierarchy
                            toAddCol = hierarchyMasks.allMasks[0];
                            break;
                        }
                    }
                }
                cuboidID = cuboidID | toAddCol;
                return cuboidID;
            }
        }

        // has column in tail group
        cuboidID = cuboidID | rowkey.getTailMask();
        return cuboidID;

    }

    // Breadth-First-Search

    /**
     * @deprecated due to poor performance
     * @param cube
     * @param cuboidID
     * @return
     */
    private static long translateToValidCuboidDeprecated(CubeDesc cube, long cuboidID) {
        if (Cuboid.isValid(cube, cuboidID)) {
            return cuboidID;
        }

        HashSet<Long> dedupped = new HashSet<Long>();
        Queue<Long> queue = new LinkedList<Long>();
        List<Long> parents = Cuboid.getAllPossibleParents(cube, cuboidID);

        // check each parent
        addToQueue(queue, parents, dedupped);
        while (queue.size() > 0) {
            long parent = pollFromQueue(queue, dedupped);
            if (Cuboid.isValid(cube, parent)) {
                return parent;
            } else {
                addToQueue(queue, Cuboid.getAllPossibleParents(cube, parent), dedupped);
            }
        }
        return -1;
    }

    private static List<Long> getAllPossibleParents(CubeDesc cube, long cuboidID) {
        List<Long> allPossibleParents = new ArrayList<Long>();

        for (int i = 0; i < cube.getRowkey().getRowKeyColumns().length; i++) {
            long mask = 1L << i;
{'fraction_non_alphanumeric': 0.0962268928842745, 'fraction_numerical': 0.003460791761627416, 'mean_word_length': 2.1662212720470335, 'pattern_counts': {'":': 0, '<': 49, '<?xml version=': 0, '>': 44, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6437751', 'n_tokens_mistral': 3525, 'n_tokens_neox': 3373, 'n_words': 902}