Source code

001package gudusoft.gsqlparser.sqlenv;
002
003import java.text.Collator;
004import java.util.*;
005
006/**
007 * 分桶索引（SQL Server COLLATION_BASED 专用）
008 *
009 * <p>用于优化 SQL Server 的 schema 对象查找，将 O(N) 全表扫描优化为 O(1) + O(bucket_size)。
010 *
011 * <p><strong>核心思想：</strong>
012 * <ul>
013 * <li>桶键 = ASCII lowercase + 长度（例如："MyTable" → "mytable_7"）
014 * <li>相同桶键的对象放在同一桶内（通常 < 20 个对象）
015 * <li>查找时先定位桶（O(1)），再用 Collator 比较桶内对象（O(bucket_size)）
016 * </ul>
017 *
018 * <p><strong>性能特性：</strong>
019 * <ul>
020 * <li>10,000 对象场景：从 ~20μs（全表扫描）优化到 ~800ns（分桶）
021 * <li>性能提升：~25x
022 * <li>内存开销：每个对象额外 ~8 bytes（HashMap overhead）
023 * </ul>
024 *
025 * <p>使用示例：
026 * <pre>
027 * CollatorProvider provider = new CollatorProvider();
028 * BucketedIndex index = new BucketedIndex(provider, "SQL_Latin1_General_CP1_CI_AS");
029 *
030 * // 添加对象
031 * index.put("MyTable", tableObject);
032 * index.put("MYTABLE", tableObject2);  // 同一桶（mytable_7）
033 *
034 * // 查找对象（使用 Collator 比较）
035 * TSQLSchemaObject found = index.get("myTable");  // CI: 能找到
036 * </pre>
037 *
038 * @since 3.1.0.9
039 */
040public class BucketedIndex {
041
042    // 桶索引：bucketKey → 候选对象列表
043    private final Map<String, List<TSQLSchemaObject>> buckets = new HashMap<>();
044
045    private final CollatorProvider collatorProvider;
046    private final String collationName;
047    private final ESQLDataObjectType objectType;
048
049    /**
050     * 构造分桶索引
051     *
052     * @param collatorProvider Collator 提供者（ThreadLocal 缓存）
053     * @param collationName SQL Server collation 名称
054     * @param objectType 对象类型（用于日志）
055     */
056    public BucketedIndex(CollatorProvider collatorProvider, String collationName, ESQLDataObjectType objectType) {
057        this.collatorProvider = collatorProvider;
058        this.collationName = collationName;
059        this.objectType = objectType;
060    }
061
062    /**
063     * 添加对象到桶
064     *
065     * <p>语义：与 {@link java.util.HashMap#put} 一致——若桶内已存在与 {@code name} 在
066     * collation 下相等的条目，则替换之；否则追加。这样 BucketedIndex 与 schemaObjectMap
067     * （legacy）/ tables（hierarchical）三处索引在重复写入时一致采用 overwrite 语义，
068     * 避免 {@link #get} 在 case-different 重复 put 后返回较早条目而 legacy/hierarchical
069     * 返回较晚条目的不对称（slice S3 修复）。
070     *
071     * <p><strong>已知遗留问题（slice S3 范围外，待 S4 处理）：</strong>
072     * {@link #computeBucketKey} 与 collator 比较都基于 raw {@code name}，不剥离 vendor
073     * delimiter（{@code []} / {@code ""} / {@code ``}）。因此 SQL Server 下以加引号
074     * 与不加引号写入的等价标识符（如 {@code "[FOO]"} 与 {@code "foo"}）会落入不同的桶，
075     * 而 legacy {@code SQLUtil.getIdentifierNormalName} 会把两者归一化为同一 key
076     * （{@code "FOO"}）。此差异在 SQL Server + bucketed flag 启用 + 直接构造重复 table
077     * 的窄场景下出现；正常使用 {@code createTable} 不会触发，因为它在构造前会先
078     * dedupe。后续修复方向：在 {@code computeBucketKey} 与 collator 比较时先剥离
079     * vendor delimiter（需要在 {@link BucketedIndex} 引入 vendor / delimiter
080     * stripper 上下文）。
081     *
082     * @param name 对象名称
083     * @param object schema 对象
084     */
085    public void put(String name, TSQLSchemaObject object) {
086        if (name == null || object == null) {
087            return;
088        }
089
090        String bucketKey = computeBucketKey(name);
091
092        // buckets 与桶内 ArrayList 均非线程安全；共享 TSQLEnv 下注册与查找并发进行
093        synchronized (buckets) {
094            List<TSQLSchemaObject> bucket = buckets.computeIfAbsent(bucketKey,
095                k -> new ArrayList<>());
096
097            Collator collator = collatorProvider.getCollator(collationName);
098            for (int i = 0; i < bucket.size(); i++) {
099                if (collator.compare(name, bucket.get(i).name) == 0) {
100                    bucket.set(i, object);
101                    return;
102                }
103            }
104            bucket.add(object);
105        }
106    }
107
108    /**
109     * 查找对象（先定位桶，再 Collator 比较）
110     *
111     * @param name 对象名称
112     * @return 找到的对象，未找到时返回 null
113     */
114    public TSQLSchemaObject get(String name) {
115        if (name == null) {
116            return null;
117        }
118
119        String bucketKey = computeBucketKey(name);
120
121        synchronized (buckets) {
122            List<TSQLSchemaObject> candidates = buckets.get(bucketKey);
123            if (candidates == null || candidates.isEmpty()) {
124                return null;  // 桶不存在
125            }
126
127            // 在候选列表中使用 Collator 比较（通常 < 20 个对象）
128            Collator collator = collatorProvider.getCollator(collationName);
129            for (TSQLSchemaObject candidate : candidates) {
130                if (collator.compare(name, candidate.name) == 0) {
131                    return candidate;  // 找到匹配
132                }
133            }
134
135            return null;  // 未找到
136        }
137    }
138
139    /**
140     * 移除对象
141     *
142     * @param name 对象名称
143     * @param object 要移除的对象
144     * @return true 如果成功移除
145     */
146    public boolean remove(String name, TSQLSchemaObject object) {
147        if (name == null || object == null) {
148            return false;
149        }
150
151        String bucketKey = computeBucketKey(name);
152
153        synchronized (buckets) {
154            List<TSQLSchemaObject> bucket = buckets.get(bucketKey);
155            if (bucket != null) {
156                boolean removed = bucket.remove(object);
157                if (bucket.isEmpty()) {
158                    buckets.remove(bucketKey);  // 清理空桶
159                }
160                return removed;
161            }
162
163            return false;
164        }
165    }
166
167    /**
168     * 获取所有对象（用于遍历）
169     *
170     * @return 所有对象的列表
171     */
172    public List<TSQLSchemaObject> getAllObjects() {
173        List<TSQLSchemaObject> result = new ArrayList<>();
174        synchronized (buckets) {
175            for (List<TSQLSchemaObject> bucket : buckets.values()) {
176                result.addAll(bucket);
177            }
178        }
179        return result;
180    }
181
182    /**
183     * 获取桶数量（用于调试）
184     *
185     * @return 桶的数量
186     */
187    public int getBucketCount() {
188        synchronized (buckets) {
189            return buckets.size();
190        }
191    }
192
193    /**
194     * 获取对象数量
195     *
196     * @return 对象总数
197     */
198    public int getObjectCount() {
199        int count = 0;
200        synchronized (buckets) {
201            for (List<TSQLSchemaObject> bucket : buckets.values()) {
202                count += bucket.size();
203            }
204        }
205        return count;
206    }
207
208    /**
209     * 计算桶键：ASCII lowercase + 长度
210     *
211     * <p>桶键计算规则：
212     * <ol>
213     * <li>将 ASCII 字母转换为小写（A-Z → a-z）
214     * <li>保留非 ASCII 字符（如中文）
215     * <li>附加长度信息（避免不同长度的字符串冲突）
216     * </ol>
217     *
218     * <p>例如：
219     * <ul>
220     * <li>"MyTable" → "mytable_7"
221     * <li>"MYTABLE" → "mytable_7"（同一桶）
222     * <li>"myTable" → "mytable_7"（同一桶）
223     * <li>"MyTab" → "mytab_5"（不同桶，长度不同）
224     * <li>"员工Table" → "员工table_8"（保留中文，T→t）
225     * </ul>
226     *
227     * @param name 对象名称
228     * @return 桶键
229     */
230    private String computeBucketKey(String name) {
231        if (name == null || name.isEmpty()) {
232            return "_0";
233        }
234
235        StringBuilder sb = new StringBuilder(name.length() + 5);
236
237        for (int i = 0; i < name.length(); i++) {
238            char c = name.charAt(i);
239
240            // 仅将 ASCII 大写字母转换为小写（A-Z → a-z）
241            if (c >= 'A' && c <= 'Z') {
242                sb.append((char) (c + 32));  // A(65) + 32 = a(97)
243            } else {
244                sb.append(c);  // 保留其他字符（小写字母、数字、Unicode）
245            }
246        }
247
248        // 附加长度信息（避免 "ab" 和 "abc" 的桶键冲突）
249        sb.append('_').append(name.length());
250
251        return sb.toString();
252    }
253
254    /**
255     * 获取桶统计信息（用于性能分析）
256     *
257     * @return 桶统计信息字符串
258     */
259    public String getBucketStats() {
260        synchronized (buckets) {
261            if (buckets.isEmpty()) {
262                return "Empty index";
263            }
264
265            int totalObjects = 0;
266            int maxBucketSize = 0;
267            int minBucketSize = Integer.MAX_VALUE;
268
269            for (List<TSQLSchemaObject> bucket : buckets.values()) {
270                int size = bucket.size();
271                totalObjects += size;
272                maxBucketSize = Math.max(maxBucketSize, size);
273                minBucketSize = Math.min(minBucketSize, size);
274            }
275
276            double avgBucketSize = (double) totalObjects / buckets.size();
277
278            return String.format(
279                "Buckets: %d, Objects: %d, Avg/Min/Max per bucket: %.2f/%d/%d",
280                buckets.size(), totalObjects, avgBucketSize, minBucketSize, maxBucketSize
281            );
282        }
283    }
284}