oxirs_arq/
query_fingerprinting.rs

1//! Advanced Query Fingerprinting for SPARQL Query Analysis
2//!
3//! This module provides sophisticated query fingerprinting for:
4//! - Query deduplication and caching
5//! - Query pattern recognition
6//! - Workload analysis
7//! - Query similarity detection
8//!
9//! # Features
10//!
11//! - **Structural Fingerprinting**: Captures query structure independent of literal values
12//! - **Semantic Fingerprinting**: Incorporates predicate and type information
13//! - **Normalized Fingerprints**: Canonicalized representation for comparison
14//! - **Parameterized Templates**: Extracts query templates with parameter slots
15//! - **Similarity Metrics**: Computes query similarity scores
16//!
17//! # Example
18//!
19//! ```rust
20//! use oxirs_arq::query_fingerprinting::{QueryFingerprinter, FingerprintConfig};
21//!
22//! let config = FingerprintConfig::default();
23//! let fingerprinter = QueryFingerprinter::new(config);
24//!
25//! let query1 = "SELECT ?s WHERE { ?s <http://example.org/name> \"Alice\" }";
26//! let query2 = "SELECT ?s WHERE { ?s <http://example.org/name> \"Bob\" }";
27//!
28//! let fp1 = fingerprinter.fingerprint(query1)?;
29//! let fp2 = fingerprinter.fingerprint(query2)?;
30//!
31//! // Same structure, different literals -> similar fingerprints
32//! let similarity = fingerprinter.similarity(&fp1, &fp2);
33//! println!("Similarity: {:.2}", similarity);
34//! # Ok::<(), anyhow::Error>(())
35//! ```
36
37use anyhow::Result;
38use regex::Regex;
39use serde::{Deserialize, Serialize};
40use sha2::{Digest, Sha256};
41use std::collections::{HashMap, HashSet};
42use std::hash::{Hash, Hasher};
43use std::sync::atomic::{AtomicU64, Ordering};
44use std::sync::{Arc, OnceLock, RwLock};
45
46/// Configuration for query fingerprinting
47#[derive(Debug, Clone, Serialize, Deserialize)]
48pub struct FingerprintConfig {
49    /// Include variable names in fingerprint
50    pub include_variables: bool,
51    /// Normalize literal values (replace with placeholders)
52    pub normalize_literals: bool,
53    /// Normalize numeric values
54    pub normalize_numbers: bool,
55    /// Normalize IRI local names
56    pub normalize_iri_locals: bool,
57    /// Preserve predicate IRIs
58    pub preserve_predicates: bool,
59    /// Preserve type assertions (rdf:type)
60    pub preserve_types: bool,
61    /// Hash algorithm to use
62    pub hash_algorithm: HashAlgorithm,
63    /// Maximum fingerprint cache size
64    pub cache_size: usize,
65}
66
67impl Default for FingerprintConfig {
68    fn default() -> Self {
69        Self {
70            include_variables: false,
71            normalize_literals: true,
72            normalize_numbers: true,
73            normalize_iri_locals: true,
74            preserve_predicates: true,
75            preserve_types: true,
76            hash_algorithm: HashAlgorithm::Sha256,
77            cache_size: 10000,
78        }
79    }
80}
81
82/// Hash algorithm options
83#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
84pub enum HashAlgorithm {
85    /// MD5 (fast, 128-bit)
86    Md5,
87    /// SHA-256 (secure, 256-bit)
88    Sha256,
89    /// FNV-1a (very fast, 64-bit)
90    Fnv1a,
91}
92
93/// Query fingerprint
94#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
95pub struct QueryFingerprint {
96    /// Primary hash of normalized query structure
97    pub hash: String,
98    /// Short hash for quick comparison
99    pub short_hash: String,
100    /// Query template with parameter placeholders
101    pub template: String,
102    /// Extracted parameters
103    pub parameters: Vec<ParameterSlot>,
104    /// Query form (SELECT, ASK, CONSTRUCT, DESCRIBE)
105    pub query_form: QueryForm,
106    /// Structural features
107    pub features: QueryFeatures,
108    /// Original query length
109    pub original_length: usize,
110}
111
112impl QueryFingerprint {
113    /// Get the template ID (short hash)
114    pub fn template_id(&self) -> &str {
115        &self.short_hash
116    }
117
118    /// Check if this fingerprint matches another (same template)
119    pub fn matches_template(&self, other: &Self) -> bool {
120        self.short_hash == other.short_hash
121    }
122
123    /// Get parameter count
124    pub fn parameter_count(&self) -> usize {
125        self.parameters.len()
126    }
127
128    /// Check if query has parameters
129    pub fn is_parameterized(&self) -> bool {
130        !self.parameters.is_empty()
131    }
132}
133
134/// Parameter slot in a query template
135#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
136pub struct ParameterSlot {
137    /// Slot name ($1, $2, etc.)
138    pub name: String,
139    /// Parameter type
140    pub param_type: ParameterType,
141    /// Position in original query
142    pub position: usize,
143    /// Original value (if extracted)
144    pub original_value: Option<String>,
145}
146
147/// Types of parameters
148#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
149pub enum ParameterType {
150    /// String literal
151    StringLiteral,
152    /// Numeric literal
153    NumericLiteral,
154    /// Date/time literal
155    DateTimeLiteral,
156    /// IRI reference
157    Iri,
158    /// Boolean literal
159    Boolean,
160    /// Language-tagged literal
161    LangLiteral,
162    /// Unknown type
163    Unknown,
164}
165
166/// Query form types
167#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
168pub enum QueryForm {
169    /// SELECT query
170    Select,
171    /// ASK query
172    Ask,
173    /// CONSTRUCT query
174    Construct,
175    /// DESCRIBE query
176    Describe,
177    /// INSERT/DELETE (update)
178    Update,
179    /// Unknown
180    Unknown,
181}
182
183impl QueryForm {
184    fn from_str(s: &str) -> Self {
185        match s.to_uppercase().as_str() {
186            "SELECT" => QueryForm::Select,
187            "ASK" => QueryForm::Ask,
188            "CONSTRUCT" => QueryForm::Construct,
189            "DESCRIBE" => QueryForm::Describe,
190            "INSERT" | "DELETE" => QueryForm::Update,
191            _ => QueryForm::Unknown,
192        }
193    }
194}
195
196/// Structural features of a query
197#[derive(Debug, Clone, Default, PartialEq, Eq, Hash, Serialize, Deserialize)]
198pub struct QueryFeatures {
199    /// Number of triple patterns
200    pub triple_pattern_count: usize,
201    /// Number of variables
202    pub variable_count: usize,
203    /// Number of filters
204    pub filter_count: usize,
205    /// Number of OPTIONAL blocks
206    pub optional_count: usize,
207    /// Number of UNION blocks
208    pub union_count: usize,
209    /// Number of subqueries
210    pub subquery_count: usize,
211    /// Has GROUP BY
212    pub has_group_by: bool,
213    /// Has ORDER BY
214    pub has_order_by: bool,
215    /// Has LIMIT
216    pub has_limit: bool,
217    /// Has OFFSET
218    pub has_offset: bool,
219    /// Has DISTINCT
220    pub has_distinct: bool,
221    /// Has SERVICE (federated)
222    pub has_service: bool,
223    /// Has VALUES clause
224    pub has_values: bool,
225    /// Has property paths
226    pub has_property_paths: bool,
227    /// Has aggregates
228    pub has_aggregates: bool,
229    /// Has BIND
230    pub has_bind: bool,
231    /// Has MINUS
232    pub has_minus: bool,
233    /// Estimated complexity score
234    pub complexity_score: u32,
235}
236
237/// Query fingerprinter
238pub struct QueryFingerprinter {
239    /// Configuration
240    config: FingerprintConfig,
241    /// Fingerprint cache
242    cache: Arc<RwLock<HashMap<String, QueryFingerprint>>>,
243    /// Statistics
244    stats: FingerprintStats,
245}
246
247/// Fingerprinting statistics
248#[derive(Debug, Default)]
249struct FingerprintStats {
250    /// Total fingerprints computed
251    computed: AtomicU64,
252    /// Cache hits
253    cache_hits: AtomicU64,
254    /// Cache misses
255    cache_misses: AtomicU64,
256}
257
258impl QueryFingerprinter {
259    /// Create new fingerprinter
260    pub fn new(config: FingerprintConfig) -> Self {
261        Self {
262            config,
263            cache: Arc::new(RwLock::new(HashMap::new())),
264            stats: FingerprintStats::default(),
265        }
266    }
267
268    /// Compute fingerprint for a query
269    pub fn fingerprint(&self, query: &str) -> Result<QueryFingerprint> {
270        // Check cache first
271        let query_hash = self.quick_hash(query);
272        {
273            let cache = self.cache.read().expect("read lock should not be poisoned");
274            if let Some(fp) = cache.get(&query_hash) {
275                self.stats.cache_hits.fetch_add(1, Ordering::Relaxed);
276                return Ok(fp.clone());
277            }
278        }
279
280        self.stats.cache_misses.fetch_add(1, Ordering::Relaxed);
281
282        // Compute fingerprint
283        let fingerprint = self.compute_fingerprint(query)?;
284
285        // Update cache
286        {
287            let mut cache = self
288                .cache
289                .write()
290                .expect("write lock should not be poisoned");
291            if cache.len() >= self.config.cache_size {
292                // Simple eviction: clear half the cache
293                let keys_to_remove: Vec<_> = cache.keys().take(cache.len() / 2).cloned().collect();
294                for key in keys_to_remove {
295                    cache.remove(&key);
296                }
297            }
298            cache.insert(query_hash, fingerprint.clone());
299        }
300
301        self.stats.computed.fetch_add(1, Ordering::Relaxed);
302        Ok(fingerprint)
303    }
304
305    /// Compute fingerprint without caching
306    fn compute_fingerprint(&self, query: &str) -> Result<QueryFingerprint> {
307        // Extract query form
308        let query_form = self.extract_query_form(query);
309
310        // Normalize the query
311        let (normalized, parameters) = self.normalize_query(query)?;
312
313        // Extract structural features
314        let features = self.extract_features(query);
315
316        // Compute hash
317        let hash = self.compute_hash(&normalized);
318        let short_hash = hash[..16].to_string();
319
320        Ok(QueryFingerprint {
321            hash,
322            short_hash,
323            template: normalized,
324            parameters,
325            query_form,
326            features,
327            original_length: query.len(),
328        })
329    }
330
331    /// Extract query form
332    fn extract_query_form(&self, query: &str) -> QueryForm {
333        let trimmed = query.trim_start();
334        let first_word = trimmed.split_whitespace().next().unwrap_or("");
335        QueryForm::from_str(first_word)
336    }
337
338    /// Normalize query and extract parameters
339    fn normalize_query(&self, query: &str) -> Result<(String, Vec<ParameterSlot>)> {
340        let mut normalized = query.to_string();
341        let mut parameters = Vec::new();
342        let mut param_index = 0;
343
344        // Remove comments
345        normalized = remove_comments(&normalized);
346
347        // Normalize whitespace
348        normalized = normalize_whitespace(&normalized);
349
350        // Normalize literals
351        if self.config.normalize_literals {
352            let (new_query, new_params) =
353                self.normalize_string_literals(&normalized, param_index)?;
354            normalized = new_query;
355            param_index += new_params.len();
356            parameters.extend(new_params);
357        }
358
359        // Normalize numbers
360        if self.config.normalize_numbers {
361            let (new_query, new_params) =
362                self.normalize_numeric_literals(&normalized, param_index)?;
363            normalized = new_query;
364            param_index += new_params.len();
365            parameters.extend(new_params);
366        }
367
368        // Normalize IRI locals (unless predicate or type)
369        if self.config.normalize_iri_locals {
370            let (new_query, new_params) = self.normalize_iri_locals(&normalized, param_index)?;
371            normalized = new_query;
372            parameters.extend(new_params);
373        }
374
375        // Normalize variable names if configured
376        if !self.config.include_variables {
377            normalized = self.normalize_variables(&normalized);
378        }
379
380        // Final cleanup
381        normalized = normalize_whitespace(&normalized);
382
383        Ok((normalized, parameters))
384    }
385
386    /// Normalize string literals
387    fn normalize_string_literals(
388        &self,
389        query: &str,
390        start_index: usize,
391    ) -> Result<(String, Vec<ParameterSlot>)> {
392        let string_pattern = string_literal_regex();
393        let mut result = query.to_string();
394        let mut params = Vec::new();
395
396        // Find all string literals
397        let matches: Vec<_> = string_pattern.find_iter(query).collect();
398
399        // Replace from end to preserve positions
400        for (index, m) in (start_index..).zip(matches.into_iter().rev()) {
401            let original = m.as_str().to_string();
402            let param_name = format!("${}", index);
403
404            // Determine type
405            let param_type = if original.contains("@") {
406                ParameterType::LangLiteral
407            } else if original.contains("^^") {
408                if original.contains("dateTime") || original.contains("date") {
409                    ParameterType::DateTimeLiteral
410                } else {
411                    ParameterType::StringLiteral
412                }
413            } else {
414                ParameterType::StringLiteral
415            };
416
417            params.push(ParameterSlot {
418                name: param_name.clone(),
419                param_type,
420                position: m.start(),
421                original_value: Some(original),
422            });
423
424            result = format!(
425                "{}{}{}",
426                &result[..m.start()],
427                param_name,
428                &result[m.end()..]
429            );
430        }
431
432        params.reverse(); // Correct order
433        Ok((result, params))
434    }
435
436    /// Normalize numeric literals
437    fn normalize_numeric_literals(
438        &self,
439        query: &str,
440        start_index: usize,
441    ) -> Result<(String, Vec<ParameterSlot>)> {
442        let number_pattern = numeric_literal_regex();
443        let mut result = query.to_string();
444        let mut params = Vec::new();
445
446        let matches: Vec<_> = number_pattern.find_iter(query).collect();
447
448        for (index, m) in (start_index..).zip(matches.into_iter().rev()) {
449            let original = m.as_str().to_string();
450            let param_name = format!("${}", index);
451
452            params.push(ParameterSlot {
453                name: param_name.clone(),
454                param_type: ParameterType::NumericLiteral,
455                position: m.start(),
456                original_value: Some(original),
457            });
458
459            result = format!(
460                "{}{}{}",
461                &result[..m.start()],
462                param_name,
463                &result[m.end()..]
464            );
465        }
466
467        params.reverse();
468        Ok((result, params))
469    }
470
471    /// Normalize IRI local names
472    fn normalize_iri_locals(
473        &self,
474        query: &str,
475        start_index: usize,
476    ) -> Result<(String, Vec<ParameterSlot>)> {
477        // Skip predicates and type IRIs if configured
478        let iri_pattern = iri_local_regex();
479        let mut result = query.to_string();
480        let mut params = Vec::new();
481        let mut index = start_index;
482
483        let matches: Vec<_> = iri_pattern.find_iter(query).collect();
484
485        for m in matches.into_iter().rev() {
486            let iri = m.as_str();
487
488            // Check if this should be preserved
489            if self.config.preserve_predicates && is_likely_predicate(query, m.start()) {
490                continue;
491            }
492            if self.config.preserve_types && iri.contains("rdf:type") || iri.contains("#type") {
493                continue;
494            }
495
496            let param_name = format!("${}", index);
497
498            params.push(ParameterSlot {
499                name: param_name.clone(),
500                param_type: ParameterType::Iri,
501                position: m.start(),
502                original_value: Some(iri.to_string()),
503            });
504
505            // Replace only the local name part
506            if let Some(local_start) = iri.rfind('#').or_else(|| iri.rfind('/')) {
507                let prefix = &iri[..=local_start];
508                result = format!(
509                    "{}{}{}{}",
510                    &result[..m.start()],
511                    prefix,
512                    param_name,
513                    &result[m.end()..]
514                );
515            }
516            index += 1;
517        }
518
519        params.reverse();
520        Ok((result, params))
521    }
522
523    /// Normalize variable names
524    fn normalize_variables(&self, query: &str) -> String {
525        let var_pattern = variable_regex();
526        let mut result = query.to_string();
527        let mut var_mapping: HashMap<String, String> = HashMap::new();
528        let mut var_index = 0;
529
530        // Find all variables and create mapping
531        for m in var_pattern.find_iter(query) {
532            let var_name = m.as_str().to_string();
533            if !var_mapping.contains_key(&var_name) {
534                var_mapping.insert(var_name.clone(), format!("?v{}", var_index));
535                var_index += 1;
536            }
537        }
538
539        // Replace variables (sorted by length descending to avoid partial replacements)
540        let mut sorted_vars: Vec<_> = var_mapping.iter().collect();
541        sorted_vars.sort_by_key(|b| std::cmp::Reverse(b.0.len()));
542
543        for (original, normalized) in sorted_vars {
544            result = result.replace(original, normalized);
545        }
546
547        result
548    }
549
550    /// Extract structural features
551    fn extract_features(&self, query: &str) -> QueryFeatures {
552        let upper_query = query.to_uppercase();
553
554        let triple_pattern_count = count_triple_patterns(query);
555        let variable_count = count_variables(query);
556        let filter_count = upper_query.matches("FILTER").count();
557        let optional_count = upper_query.matches("OPTIONAL").count();
558        let union_count = upper_query.matches("UNION").count();
559        let subquery_count = upper_query.matches("SELECT").count().saturating_sub(1);
560
561        let has_group_by = upper_query.contains("GROUP BY");
562        let has_order_by = upper_query.contains("ORDER BY");
563        let has_limit = upper_query.contains("LIMIT");
564        let has_offset = upper_query.contains("OFFSET");
565        let has_distinct = upper_query.contains("DISTINCT");
566        let has_service = upper_query.contains("SERVICE");
567        let has_values = upper_query.contains("VALUES");
568        let has_property_paths = query.contains("/")
569            || query.contains("*")
570            || query.contains("+")
571            || query.contains("|");
572        let has_aggregates = upper_query.contains("COUNT")
573            || upper_query.contains("SUM")
574            || upper_query.contains("AVG")
575            || upper_query.contains("MIN")
576            || upper_query.contains("MAX");
577        let has_bind = upper_query.contains("BIND");
578        let has_minus = upper_query.contains("MINUS");
579
580        // Calculate complexity score
581        let complexity_score = (triple_pattern_count * 10
582            + filter_count * 5
583            + optional_count * 8
584            + union_count * 6
585            + subquery_count * 15
586            + if has_group_by { 5 } else { 0 }
587            + if has_order_by { 3 } else { 0 }
588            + if has_service { 20 } else { 0 }
589            + if has_property_paths { 10 } else { 0 }
590            + if has_aggregates { 7 } else { 0 }
591            + if has_minus { 5 } else { 0 }) as u32;
592
593        QueryFeatures {
594            triple_pattern_count,
595            variable_count,
596            filter_count,
597            optional_count,
598            union_count,
599            subquery_count,
600            has_group_by,
601            has_order_by,
602            has_limit,
603            has_offset,
604            has_distinct,
605            has_service,
606            has_values,
607            has_property_paths,
608            has_aggregates,
609            has_bind,
610            has_minus,
611            complexity_score,
612        }
613    }
614
615    /// Compute hash of normalized query
616    fn compute_hash(&self, normalized: &str) -> String {
617        match self.config.hash_algorithm {
618            HashAlgorithm::Md5 => {
619                let digest = md5::compute(normalized.as_bytes());
620                format!("{:x}", digest)
621            }
622            HashAlgorithm::Sha256 => {
623                let mut hasher = Sha256::new();
624                hasher.update(normalized.as_bytes());
625                hex::encode(hasher.finalize())
626            }
627            HashAlgorithm::Fnv1a => {
628                let mut hasher = std::collections::hash_map::DefaultHasher::new();
629                normalized.hash(&mut hasher);
630                format!("{:016x}", hasher.finish())
631            }
632        }
633    }
634
635    /// Quick hash for cache lookup
636    fn quick_hash(&self, query: &str) -> String {
637        let mut hasher = std::collections::hash_map::DefaultHasher::new();
638        query.hash(&mut hasher);
639        format!("{:016x}", hasher.finish())
640    }
641
642    /// Calculate similarity between two fingerprints
643    pub fn similarity(&self, fp1: &QueryFingerprint, fp2: &QueryFingerprint) -> f64 {
644        // If same hash, they're identical
645        if fp1.hash == fp2.hash {
646            return 1.0;
647        }
648
649        // Different query forms = very different
650        if fp1.query_form != fp2.query_form {
651            return 0.0;
652        }
653
654        // Calculate structural similarity
655        let structure_sim = self.structural_similarity(&fp1.features, &fp2.features);
656
657        // Calculate template similarity (string similarity)
658        let template_sim = string_similarity(&fp1.template, &fp2.template);
659
660        // Weighted combination
661        0.6 * structure_sim + 0.4 * template_sim
662    }
663
664    /// Calculate structural similarity between features
665    fn structural_similarity(&self, f1: &QueryFeatures, f2: &QueryFeatures) -> f64 {
666        let mut matches = 0.0;
667        let mut total = 0.0;
668
669        // Compare numeric features
670        let num_features = [
671            (f1.triple_pattern_count, f2.triple_pattern_count, 2.0),
672            (f1.variable_count, f2.variable_count, 1.0),
673            (f1.filter_count, f2.filter_count, 1.5),
674            (f1.optional_count, f2.optional_count, 1.5),
675            (f1.union_count, f2.union_count, 1.5),
676            (f1.subquery_count, f2.subquery_count, 2.0),
677        ];
678
679        for (v1, v2, weight) in num_features {
680            total += weight;
681            if v1 == v2 {
682                matches += weight;
683            } else {
684                let max_val = v1.max(v2) as f64;
685                let min_val = v1.min(v2) as f64;
686                if max_val > 0.0 {
687                    matches += weight * (min_val / max_val);
688                }
689            }
690        }
691
692        // Compare boolean features
693        let bool_features = [
694            (f1.has_group_by, f2.has_group_by),
695            (f1.has_order_by, f2.has_order_by),
696            (f1.has_limit, f2.has_limit),
697            (f1.has_distinct, f2.has_distinct),
698            (f1.has_service, f2.has_service),
699            (f1.has_values, f2.has_values),
700            (f1.has_property_paths, f2.has_property_paths),
701            (f1.has_aggregates, f2.has_aggregates),
702            (f1.has_bind, f2.has_bind),
703            (f1.has_minus, f2.has_minus),
704        ];
705
706        for (b1, b2) in bool_features {
707            total += 1.0;
708            if b1 == b2 {
709                matches += 1.0;
710            }
711        }
712
713        matches / total
714    }
715
716    /// Find similar fingerprints in a collection
717    pub fn find_similar(
718        &self,
719        target: &QueryFingerprint,
720        fingerprints: &[QueryFingerprint],
721        threshold: f64,
722    ) -> Vec<(usize, f64)> {
723        let mut results: Vec<(usize, f64)> = fingerprints
724            .iter()
725            .enumerate()
726            .filter_map(|(idx, fp)| {
727                let sim = self.similarity(target, fp);
728                if sim >= threshold {
729                    Some((idx, sim))
730                } else {
731                    None
732                }
733            })
734            .collect();
735
736        results.sort_by(|a, b| b.1.partial_cmp(&a.1).unwrap_or(std::cmp::Ordering::Equal));
737        results
738    }
739
740    /// Group fingerprints by similarity
741    pub fn cluster_fingerprints(
742        &self,
743        fingerprints: &[QueryFingerprint],
744        threshold: f64,
745    ) -> Vec<Vec<usize>> {
746        let n = fingerprints.len();
747        let mut visited = vec![false; n];
748        let mut clusters = Vec::new();
749
750        for i in 0..n {
751            if visited[i] {
752                continue;
753            }
754
755            let mut cluster = vec![i];
756            visited[i] = true;
757
758            for j in (i + 1)..n {
759                if visited[j] {
760                    continue;
761                }
762
763                let sim = self.similarity(&fingerprints[i], &fingerprints[j]);
764                if sim >= threshold {
765                    cluster.push(j);
766                    visited[j] = true;
767                }
768            }
769
770            clusters.push(cluster);
771        }
772
773        clusters
774    }
775
776    /// Get fingerprinting statistics
777    pub fn statistics(&self) -> FingerprintingStatistics {
778        FingerprintingStatistics {
779            fingerprints_computed: self.stats.computed.load(Ordering::Relaxed),
780            cache_hits: self.stats.cache_hits.load(Ordering::Relaxed),
781            cache_misses: self.stats.cache_misses.load(Ordering::Relaxed),
782            cache_size: self
783                .cache
784                .read()
785                .expect("read lock should not be poisoned")
786                .len(),
787        }
788    }
789
790    /// Clear the fingerprint cache
791    pub fn clear_cache(&self) {
792        self.cache
793            .write()
794            .expect("write lock should not be poisoned")
795            .clear();
796    }
797}
798
799/// Fingerprinting statistics
800#[derive(Debug, Clone, Serialize, Deserialize)]
801pub struct FingerprintingStatistics {
802    /// Total fingerprints computed
803    pub fingerprints_computed: u64,
804    /// Cache hits
805    pub cache_hits: u64,
806    /// Cache misses
807    pub cache_misses: u64,
808    /// Current cache size
809    pub cache_size: usize,
810}
811
812impl FingerprintingStatistics {
813    /// Calculate cache hit rate
814    pub fn cache_hit_rate(&self) -> f64 {
815        let total = self.cache_hits + self.cache_misses;
816        if total == 0 {
817            0.0
818        } else {
819            self.cache_hits as f64 / total as f64
820        }
821    }
822}
823
824// Helper functions
825
826fn remove_comments(query: &str) -> String {
827    let mut result = String::new();
828    let mut in_string = false;
829    let mut escape = false;
830    let mut chars = query.chars().peekable();
831
832    while let Some(c) = chars.next() {
833        if escape {
834            result.push(c);
835            escape = false;
836            continue;
837        }
838
839        if c == '\\' && in_string {
840            result.push(c);
841            escape = true;
842            continue;
843        }
844
845        if c == '"' && !in_string {
846            in_string = true;
847            result.push(c);
848            continue;
849        }
850
851        if c == '"' && in_string {
852            in_string = false;
853            result.push(c);
854            continue;
855        }
856
857        if !in_string && c == '#' {
858            // Skip to end of line
859            while let Some(&nc) = chars.peek() {
860                if nc == '\n' {
861                    break;
862                }
863                chars.next();
864            }
865            result.push(' ');
866            continue;
867        }
868
869        result.push(c);
870    }
871
872    result
873}
874
875fn normalize_whitespace(query: &str) -> String {
876    let whitespace_pattern = whitespace_regex();
877    whitespace_pattern
878        .replace_all(query, " ")
879        .trim()
880        .to_string()
881}
882
883fn count_triple_patterns(query: &str) -> usize {
884    // Count occurrences of patterns like "?var predicate ?var" or ". ?var predicate"
885    let triple_pattern = triple_pattern_regex();
886    triple_pattern.find_iter(query).count()
887}
888
889fn count_variables(query: &str) -> usize {
890    let var_pattern = variable_regex();
891    let vars: HashSet<_> = var_pattern.find_iter(query).map(|m| m.as_str()).collect();
892    vars.len()
893}
894
895fn is_likely_predicate(query: &str, position: usize) -> bool {
896    // Check if this IRI is in predicate position (middle of triple pattern)
897    // This is a heuristic - look for variable before and after
898    let before = &query[..position];
899    let after = &query[position..];
900
901    // Check if there's a variable or IRI before (subject)
902    let has_subject = before
903        .trim_end()
904        .ends_with(|c: char| c == '>' || c.is_alphabetic() || c == '_');
905    // Check if there's a variable or literal after (object)
906    let has_object = after.trim_start().starts_with(['?', '<', '"']);
907
908    has_subject && has_object
909}
910
911fn string_similarity(s1: &str, s2: &str) -> f64 {
912    // Simple Jaccard similarity on tokens
913    let tokens1: HashSet<_> = s1.split_whitespace().collect();
914    let tokens2: HashSet<_> = s2.split_whitespace().collect();
915
916    let intersection = tokens1.intersection(&tokens2).count();
917    let union = tokens1.union(&tokens2).count();
918
919    if union == 0 {
920        1.0
921    } else {
922        intersection as f64 / union as f64
923    }
924}
925
926// Lazy static regex patterns
927
928fn string_literal_regex() -> &'static Regex {
929    static REGEX: OnceLock<Regex> = OnceLock::new();
930    REGEX.get_or_init(|| {
931        Regex::new(r#""(?:[^"\\]|\\.)*"(?:@[a-zA-Z-]+)?(?:\^\^<[^>]+>)?"#).expect("Invalid regex")
932    })
933}
934
935fn numeric_literal_regex() -> &'static Regex {
936    static REGEX: OnceLock<Regex> = OnceLock::new();
937    REGEX.get_or_init(|| {
938        // Simple numeric pattern without look-around (which regex crate doesn't support)
939        // Match numbers that appear as standalone tokens
940        Regex::new(r"\b[-+]?(?:\d+\.?\d*|\.\d+)(?:[eE][-+]?\d+)?\b").expect("Invalid regex")
941    })
942}
943
944fn iri_local_regex() -> &'static Regex {
945    static REGEX: OnceLock<Regex> = OnceLock::new();
946    REGEX.get_or_init(|| Regex::new(r"<[^>]+>").expect("Invalid regex"))
947}
948
949fn variable_regex() -> &'static Regex {
950    static REGEX: OnceLock<Regex> = OnceLock::new();
951    REGEX.get_or_init(|| Regex::new(r"\?[a-zA-Z_][a-zA-Z0-9_]*").expect("Invalid regex"))
952}
953
954fn whitespace_regex() -> &'static Regex {
955    static REGEX: OnceLock<Regex> = OnceLock::new();
956    REGEX.get_or_init(|| Regex::new(r"\s+").expect("Invalid regex"))
957}
958
959fn triple_pattern_regex() -> &'static Regex {
960    static REGEX: OnceLock<Regex> = OnceLock::new();
961    REGEX.get_or_init(|| {
962        Regex::new(r#"(?:\?[a-zA-Z_]\w*|<[^>]+>)\s+(?:\?[a-zA-Z_]\w*|<[^>]+>|[a-zA-Z]+:[a-zA-Z_]\w*)\s+(?:\?[a-zA-Z_]\w*|<[^>]+>|"[^"]*"|[0-9]+)"#).expect("Invalid regex")
963    })
964}
965
966#[cfg(test)]
967mod tests {
968    use super::*;
969
970    #[test]
971    fn test_basic_fingerprint() {
972        let config = FingerprintConfig::default();
973        let fingerprinter = QueryFingerprinter::new(config);
974
975        let query = "SELECT ?s WHERE { ?s <http://example.org/name> \"Alice\" }";
976        let fp = fingerprinter.fingerprint(query).unwrap();
977
978        assert_eq!(fp.query_form, QueryForm::Select);
979        assert!(!fp.hash.is_empty());
980        assert!(!fp.template.is_empty());
981    }
982
983    #[test]
984    fn test_similar_queries_same_template() {
985        let config = FingerprintConfig::default();
986        let fingerprinter = QueryFingerprinter::new(config);
987
988        let query1 = "SELECT ?s WHERE { ?s <http://example.org/name> \"Alice\" }";
989        let query2 = "SELECT ?s WHERE { ?s <http://example.org/name> \"Bob\" }";
990
991        let fp1 = fingerprinter.fingerprint(query1).unwrap();
992        let fp2 = fingerprinter.fingerprint(query2).unwrap();
993
994        // Same structure, different literals
995        let similarity = fingerprinter.similarity(&fp1, &fp2);
996        assert!(
997            similarity > 0.7,
998            "Similarity should be high for same structure"
999        );
1000    }
1001
1002    #[test]
1003    fn test_different_queries_different_template() {
1004        let config = FingerprintConfig::default();
1005        let fingerprinter = QueryFingerprinter::new(config);
1006
1007        let query1 = "SELECT ?s WHERE { ?s <http://example.org/name> \"Alice\" }";
1008        let query2 = "ASK { ?x <http://example.org/age> ?y . ?y <http://example.org/value> ?z }";
1009
1010        let fp1 = fingerprinter.fingerprint(query1).unwrap();
1011        let fp2 = fingerprinter.fingerprint(query2).unwrap();
1012
1013        let similarity = fingerprinter.similarity(&fp1, &fp2);
1014        assert!(
1015            similarity < 0.5,
1016            "Similarity should be low for different structures"
1017        );
1018    }
1019
1020    #[test]
1021    fn test_feature_extraction() {
1022        let config = FingerprintConfig::default();
1023        let fingerprinter = QueryFingerprinter::new(config);
1024
1025        let query = r#"
1026            SELECT ?s ?name (COUNT(?o) AS ?count)
1027            WHERE {
1028                ?s <http://example.org/type> <http://example.org/Person> .
1029                ?s <http://example.org/name> ?name .
1030                OPTIONAL { ?s <http://example.org/friend> ?o }
1031                FILTER(?name != "")
1032            }
1033            GROUP BY ?s ?name
1034            ORDER BY DESC(?count)
1035            LIMIT 10
1036        "#;
1037
1038        let fp = fingerprinter.fingerprint(query).unwrap();
1039
1040        assert!(fp.features.has_group_by);
1041        assert!(fp.features.has_order_by);
1042        assert!(fp.features.has_limit);
1043        assert!(fp.features.has_aggregates);
1044        assert!(fp.features.optional_count > 0);
1045        assert!(fp.features.filter_count > 0);
1046    }
1047
1048    #[test]
1049    fn test_cache_behavior() {
1050        let config = FingerprintConfig::default();
1051        let fingerprinter = QueryFingerprinter::new(config);
1052
1053        let query = "SELECT ?s WHERE { ?s ?p ?o }";
1054
1055        // First call - cache miss
1056        let _fp1 = fingerprinter.fingerprint(query).unwrap();
1057        let stats1 = fingerprinter.statistics();
1058        assert_eq!(stats1.cache_misses, 1);
1059
1060        // Second call - cache hit
1061        let _fp2 = fingerprinter.fingerprint(query).unwrap();
1062        let stats2 = fingerprinter.statistics();
1063        assert_eq!(stats2.cache_hits, 1);
1064    }
1065
1066    #[test]
1067    fn test_query_forms() {
1068        let config = FingerprintConfig::default();
1069        let fingerprinter = QueryFingerprinter::new(config);
1070
1071        let select = "SELECT ?s WHERE { ?s ?p ?o }";
1072        let ask = "ASK { ?s ?p ?o }";
1073        let construct = "CONSTRUCT { ?s ?p ?o } WHERE { ?s ?p ?o }";
1074        let describe = "DESCRIBE <http://example.org/thing>";
1075
1076        assert_eq!(
1077            fingerprinter.fingerprint(select).unwrap().query_form,
1078            QueryForm::Select
1079        );
1080        assert_eq!(
1081            fingerprinter.fingerprint(ask).unwrap().query_form,
1082            QueryForm::Ask
1083        );
1084        assert_eq!(
1085            fingerprinter.fingerprint(construct).unwrap().query_form,
1086            QueryForm::Construct
1087        );
1088        assert_eq!(
1089            fingerprinter.fingerprint(describe).unwrap().query_form,
1090            QueryForm::Describe
1091        );
1092    }
1093
1094    #[test]
1095    fn test_parameter_extraction() {
1096        let config = FingerprintConfig::default();
1097        let fingerprinter = QueryFingerprinter::new(config);
1098
1099        let query = r#"SELECT ?s WHERE { ?s <http://example.org/age> 25 . ?s <http://example.org/name> "Alice" }"#;
1100        let fp = fingerprinter.fingerprint(query).unwrap();
1101
1102        assert!(!fp.parameters.is_empty());
1103    }
1104
1105    #[test]
1106    fn test_find_similar() {
1107        let config = FingerprintConfig::default();
1108        let fingerprinter = QueryFingerprinter::new(config);
1109
1110        let queries = [
1111            "SELECT ?s WHERE { ?s <http://example.org/name> \"Alice\" }",
1112            "SELECT ?s WHERE { ?s <http://example.org/name> \"Bob\" }",
1113            "SELECT ?s WHERE { ?s <http://example.org/name> \"Charlie\" }",
1114            "ASK { ?x <http://example.org/age> ?y }",
1115        ];
1116
1117        let fingerprints: Vec<_> = queries
1118            .iter()
1119            .map(|q| fingerprinter.fingerprint(q).unwrap())
1120            .collect();
1121
1122        let target = &fingerprints[0];
1123        let similar = fingerprinter.find_similar(target, &fingerprints, 0.7);
1124
1125        // Should find at least the first 3 as similar
1126        assert!(similar.len() >= 2);
1127    }
1128
1129    #[test]
1130    fn test_cluster_fingerprints() {
1131        let config = FingerprintConfig::default();
1132        let fingerprinter = QueryFingerprinter::new(config);
1133
1134        let queries = [
1135            "SELECT ?s WHERE { ?s <http://example.org/name> \"Alice\" }",
1136            "SELECT ?s WHERE { ?s <http://example.org/name> \"Bob\" }",
1137            "ASK { ?x <http://example.org/age> ?y }",
1138            "ASK { ?x <http://example.org/age> ?z }",
1139        ];
1140
1141        let fingerprints: Vec<_> = queries
1142            .iter()
1143            .map(|q| fingerprinter.fingerprint(q).unwrap())
1144            .collect();
1145
1146        let clusters = fingerprinter.cluster_fingerprints(&fingerprints, 0.7);
1147
1148        // Should have 2 clusters: one for SELECT queries, one for ASK queries
1149        assert!(clusters.len() >= 2);
1150    }
1151
1152    #[test]
1153    fn test_complexity_score() {
1154        let config = FingerprintConfig::default();
1155        let fingerprinter = QueryFingerprinter::new(config);
1156
1157        let simple = "SELECT ?s WHERE { ?s ?p ?o }";
1158        let complex = r#"
1159            SELECT ?s ?name (COUNT(?friend) AS ?friendCount)
1160            WHERE {
1161                ?s <http://example.org/type> <http://example.org/Person> .
1162                ?s <http://example.org/name> ?name .
1163                OPTIONAL { ?s <http://example.org/friend> ?friend }
1164                FILTER(?name != "")
1165                UNION {
1166                    ?s <http://example.org/nickname> ?name
1167                }
1168            }
1169            GROUP BY ?s ?name
1170            ORDER BY DESC(?friendCount)
1171            LIMIT 100
1172        "#;
1173
1174        let fp_simple = fingerprinter.fingerprint(simple).unwrap();
1175        let fp_complex = fingerprinter.fingerprint(complex).unwrap();
1176
1177        assert!(fp_complex.features.complexity_score > fp_simple.features.complexity_score);
1178    }
1179
1180    #[test]
1181    fn test_hash_algorithms() {
1182        let queries = "SELECT ?s WHERE { ?s ?p ?o }";
1183
1184        // MD5
1185        let config_md5 = FingerprintConfig {
1186            hash_algorithm: HashAlgorithm::Md5,
1187            ..Default::default()
1188        };
1189        let fp_md5 = QueryFingerprinter::new(config_md5)
1190            .fingerprint(queries)
1191            .unwrap();
1192        assert_eq!(fp_md5.hash.len(), 32); // MD5 = 128 bits = 32 hex chars
1193
1194        // SHA-256
1195        let config_sha = FingerprintConfig {
1196            hash_algorithm: HashAlgorithm::Sha256,
1197            ..Default::default()
1198        };
1199        let fp_sha = QueryFingerprinter::new(config_sha)
1200            .fingerprint(queries)
1201            .unwrap();
1202        assert_eq!(fp_sha.hash.len(), 64); // SHA256 = 256 bits = 64 hex chars
1203
1204        // FNV-1a
1205        let config_fnv = FingerprintConfig {
1206            hash_algorithm: HashAlgorithm::Fnv1a,
1207            ..Default::default()
1208        };
1209        let fp_fnv = QueryFingerprinter::new(config_fnv)
1210            .fingerprint(queries)
1211            .unwrap();
1212        assert_eq!(fp_fnv.hash.len(), 16); // FNV-1a 64-bit = 16 hex chars
1213    }
1214
1215    #[test]
1216    fn test_statistics() {
1217        let config = FingerprintConfig::default();
1218        let fingerprinter = QueryFingerprinter::new(config);
1219
1220        let _ = fingerprinter.fingerprint("SELECT ?s WHERE { ?s ?p ?o }");
1221        let _ = fingerprinter.fingerprint("SELECT ?s WHERE { ?s ?p ?o }"); // Cache hit
1222
1223        let stats = fingerprinter.statistics();
1224        assert_eq!(stats.fingerprints_computed, 1);
1225        assert_eq!(stats.cache_hits, 1);
1226        assert_eq!(stats.cache_misses, 1);
1227        assert!(stats.cache_hit_rate() > 0.0);
1228    }
1229
1230    #[test]
1231    fn test_clear_cache() {
1232        let config = FingerprintConfig::default();
1233        let fingerprinter = QueryFingerprinter::new(config);
1234
1235        let _ = fingerprinter.fingerprint("SELECT ?s WHERE { ?s ?p ?o }");
1236        assert_eq!(fingerprinter.statistics().cache_size, 1);
1237
1238        fingerprinter.clear_cache();
1239        assert_eq!(fingerprinter.statistics().cache_size, 0);
1240    }
1241}
oxirs_arq/query_fingerprinting.rs

oxirs_arq/
query_fingerprinting.rs
