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        List<TSQLSchemaObject> bucket = buckets.computeIfAbsent(bucketKey,
093            k -> new ArrayList<>());
094
095        Collator collator = collatorProvider.getCollator(collationName);
096        for (int i = 0; i < bucket.size(); i++) {
097            if (collator.compare(name, bucket.get(i).name) == 0) {
098                bucket.set(i, object);
099                return;
100            }
101        }
102        bucket.add(object);
103    }
104
105    /**
106     * 查找对象（先定位桶，再 Collator 比较）
107     *
108     * @param name 对象名称
109     * @return 找到的对象，未找到时返回 null
110     */
111    public TSQLSchemaObject get(String name) {
112        if (name == null) {
113            return null;
114        }
115
116        String bucketKey = computeBucketKey(name);
117
118        List<TSQLSchemaObject> candidates = buckets.get(bucketKey);
119        if (candidates == null || candidates.isEmpty()) {
120            return null;  // 桶不存在
121        }
122
123        // 在候选列表中使用 Collator 比较（通常 < 20 个对象）
124        Collator collator = collatorProvider.getCollator(collationName);
125        for (TSQLSchemaObject candidate : candidates) {
126            if (collator.compare(name, candidate.name) == 0) {
127                return candidate;  // 找到匹配
128            }
129        }
130
131        return null;  // 未找到
132    }
133
134    /**
135     * 移除对象
136     *
137     * @param name 对象名称
138     * @param object 要移除的对象
139     * @return true 如果成功移除
140     */
141    public boolean remove(String name, TSQLSchemaObject object) {
142        if (name == null || object == null) {
143            return false;
144        }
145
146        String bucketKey = computeBucketKey(name);
147
148        List<TSQLSchemaObject> bucket = buckets.get(bucketKey);
149        if (bucket != null) {
150            boolean removed = bucket.remove(object);
151            if (bucket.isEmpty()) {
152                buckets.remove(bucketKey);  // 清理空桶
153            }
154            return removed;
155        }
156
157        return false;
158    }
159
160    /**
161     * 获取所有对象（用于遍历）
162     *
163     * @return 所有对象的列表
164     */
165    public List<TSQLSchemaObject> getAllObjects() {
166        List<TSQLSchemaObject> result = new ArrayList<>();
167        for (List<TSQLSchemaObject> bucket : buckets.values()) {
168            result.addAll(bucket);
169        }
170        return result;
171    }
172
173    /**
174     * 获取桶数量（用于调试）
175     *
176     * @return 桶的数量
177     */
178    public int getBucketCount() {
179        return buckets.size();
180    }
181
182    /**
183     * 获取对象数量
184     *
185     * @return 对象总数
186     */
187    public int getObjectCount() {
188        int count = 0;
189        for (List<TSQLSchemaObject> bucket : buckets.values()) {
190            count += bucket.size();
191        }
192        return count;
193    }
194
195    /**
196     * 计算桶键：ASCII lowercase + 长度
197     *
198     * <p>桶键计算规则：
199     * <ol>
200     * <li>将 ASCII 字母转换为小写（A-Z → a-z）
201     * <li>保留非 ASCII 字符（如中文）
202     * <li>附加长度信息（避免不同长度的字符串冲突）
203     * </ol>
204     *
205     * <p>例如：
206     * <ul>
207     * <li>"MyTable" → "mytable_7"
208     * <li>"MYTABLE" → "mytable_7"（同一桶）
209     * <li>"myTable" → "mytable_7"（同一桶）
210     * <li>"MyTab" → "mytab_5"（不同桶，长度不同）
211     * <li>"员工Table" → "员工table_8"（保留中文，T→t）
212     * </ul>
213     *
214     * @param name 对象名称
215     * @return 桶键
216     */
217    private String computeBucketKey(String name) {
218        if (name == null || name.isEmpty()) {
219            return "_0";
220        }
221
222        StringBuilder sb = new StringBuilder(name.length() + 5);
223
224        for (int i = 0; i < name.length(); i++) {
225            char c = name.charAt(i);
226
227            // 仅将 ASCII 大写字母转换为小写（A-Z → a-z）
228            if (c >= 'A' && c <= 'Z') {
229                sb.append((char) (c + 32));  // A(65) + 32 = a(97)
230            } else {
231                sb.append(c);  // 保留其他字符（小写字母、数字、Unicode）
232            }
233        }
234
235        // 附加长度信息（避免 "ab" 和 "abc" 的桶键冲突）
236        sb.append('_').append(name.length());
237
238        return sb.toString();
239    }
240
241    /**
242     * 获取桶统计信息（用于性能分析）
243     *
244     * @return 桶统计信息字符串
245     */
246    public String getBucketStats() {
247        if (buckets.isEmpty()) {
248            return "Empty index";
249        }
250
251        int totalObjects = 0;
252        int maxBucketSize = 0;
253        int minBucketSize = Integer.MAX_VALUE;
254
255        for (List<TSQLSchemaObject> bucket : buckets.values()) {
256            int size = bucket.size();
257            totalObjects += size;
258            maxBucketSize = Math.max(maxBucketSize, size);
259            minBucketSize = Math.min(minBucketSize, size);
260        }
261
262        double avgBucketSize = (double) totalObjects / buckets.size();
263
264        return String.format(
265            "Buckets: %d, Objects: %d, Avg/Min/Max per bucket: %.2f/%d/%d",
266            buckets.size(), totalObjects, avgBucketSize, minBucketSize, maxBucketSize
267        );
268    }
269}